# Time reverse mechanism in games

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.).

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.

• Note that the reversibility of actions in a game can be a very touchy thing, because of floating-point precision issues, variable timesteps, etc; it's much safer to save that state than to rebuild it in most situations. – Steven Stadnicki May 18 '12 at 16:39
• @StevenStadnicki Maybe, but it's definitely possible. Off the top of my head, C&C Generals does it this way. It has hours-long replays of up to 8 players, weighing in at a few hundred kB at worst, and it's how I guess most if not all RTS games do their multiplayer: You just can't transmit the full game state with potentially hundreds of units every frame, you have to let the engine do the updating. So yeah, it's definitely viable. – Hackworth May 18 '12 at 16:42
• Replay is a very different thing from rewind, because operations that are consistently reproducible forwards (for instance, finding the position at frame n, x_n, by starting with x_0=0 and adding the deltas v_n for each step) aren't necessarily reproducible backwards; (x+v_n)-v_n does not consistently equal x in floating-point maths. And it's easy to say 'work around it' but you're talking about potentially a complete overhaul, including not being able to use many external libraries. – Steven Stadnicki May 18 '12 at 17:32
• For some games your approach might be feasible, but AFAIK most games that use time-reversal as a mechanic are using something closer to OriginalDaemon's Memento approach where the relevant state is saved for every frame. – Steven Stadnicki May 18 '12 at 17:33
• What about rewinding by recalculating the steps, but saving a key frame every couple of seconds? Floating point errors aren't likely to make a significant difference in just a few seconds (depending on the complexity, of course). It's also shown to work in video compression :P – Tharwen May 18 '12 at 21:21

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).

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.

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.