Time reverse mechanism in games

Question

I am wondering about how time manipulation mechanisms in games are typically designed. I am particularly interested in time reversing (sort of like in the latest SSX or Prince of Persia).

The game is a 2D top down shooter.

The mechanism I am trying to design/implement has the following requirements:

1) Actions of entities apart from the player character are completely deterministic.

• The action an entity takes is based on the frames progressed since level start and/or the position of the player on the screen
• Entities are spawned at set time during the level.

2) Time reverse works by reversing back in realtime.

• Player actions are also reversed, it replays in reverse what the player performed. Player has no control during reverse time.
• There is no limit on the time spent reversing, we can reverse all the way to the beginning of the level if wanted.

As an example:

Frames 0-50: Player moves foward 20 units over this time Enemy 1 spawns at frame 20 Enemy 1 moves left 10 units during frame 30-40 Player shoots bullet at frame 45 Bullet travels 5 foward (45-50) and kills Enemy 1 at frame 50

Reversing this would play back in realtime: Player moves backwards 20 units during this time Enemy 1 revives at frame 50 Bullet reappears at frame 50 Bullet moves backwards 5 and disappears (50-45) Enemy moves left 10 (40-30) Enemy removed at frame 20.

Just looking at movement I had some ideas about how to achieve this, I thought of having a interface that changed behavior for when time was advancing or reversing. Instead of doing something like this:

void update()
{
    movement += new Vector(0,5);
}

I would do something like this:

public interface movement()
{
    public void move(Vector v, Entity e);
}

public class advance() implements movement
{
    public void move(Vector v, Entity e)
    {
            e.location += v;
    }
}


public class reverse() implements movement
{
    public void move(Vector v, Entity e)
    { 
        e.location -= v;
    }
}

public void update()
{
    moveLogic.move(new vector(5,0));
}

However I realised this would not be optimal performance wise and would quickly become complicated for more advance actions (such as smooth movement along curved paths e.t.c.).

Answer 1

You might want to take a look at the Command pattern.

Basically every reversible action your entities take are implemented as a command object. All of those objects implement at least 2 methods: Execute() and Undo(), plus whatever else you need, like a time stamp property for correct timing.

Whenever your entity performs a reversible action, you create an appropriate command object first. You save it on an Undo stack, then feed into your game engine and execute it. When you want to reverse time, you pop actions from the top of the stack and call their Undo() method, which does the opposite of the Execute() method. For example, in case of a jump from point A to point B, you perform a jump from B to A.

After you popped an action, save it on a Redo stack if you want to go forwards and backwards at will, just like the undo/redo function in a text editor or paint program. Of course, your animations must also support a "rewind" mode for playing them backwards.

For more game design shenanigans, let every entity store its actions on its own stack, so you can undo/redo them independently of each other.

A command pattern has other advantages: For example, it's pretty much trivial to build a replay recorder, since you merely need to save all the objects on the stacks to a file, and at replay time, just feed it into the game engine one by one.

Answer 2

You could take a look at the Memento Pattern; its primary intention is to implement undo/redo operations by rolling back object state, but for certain kinds of games it should suffice.

For a game in a real-time loop you could consider each frame of your operations as a state change and store it. This is a simple approach to implement. The alternative is to trap when an object's state is changed. For example, detecting when the forces acting upon a rigid body are changed. If you are using properties to get and set variables, this can also be a relatively straight forward implementation, the difficult part is identifying when to roll back the state, as this won't be the same time for every object (you could store the rollback time as a frame count from the start of the system).

Answer 3

In your particular case handling the rollback by rewinding the motion should work fine. If you are using any form of pathfinding with the AI units, just be sure to recalculate it after the rollback to avoid overlapping units.

The problem is the way you are handling the movement itself: A decent physics engine (a 2D top down shooter will be fine with a very simple one) that keeps track of past-steps info (including position, net force, etc) will provide a solid base. Then, deciding a maximum rollback and a granularity for the rollback-steps you should get the result you want.

Answer 4

While this is an interesting idea. I would advise against it.

Replaying the game forwards works fine, because an operation will always have the same effect on the game state. This doesn't imply that the reverse operation gives you the original state. For example, evaluate the following expression in any programming language (turn optimization off)

(1.1 + 3 - 3) == 1.1

In C and C++ at least, it returns false. While the difference may be small, imagine how much errors can accumulate at 60fps over 10s of seconds of minutes. There will be cases where a player only just misses something, but hits it while the game is replayed backwards.

I would recommend storing keyframes every half second. This won't take up too much memory. You can then either interpolate between keyframes, or even better, simulate the time between two keyframes, and then replay it backwards.

If your game isn't too complicated, just store keyframes of the game state 30 times a second and play that backwards. If you had 15 objects each with a 2D position, it would take a good 1.5 minutes to get up to a MB, without compression. Computers have gigabytes of memory.

So don't overcomplicate it, it won't be easy to replay a game backwards, and it will cause a lot of errors.