# Implementing "Rewind Time", like in the Prince of Persia - Sands of time series

This topic is 2189 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi,

I am not sure if you guys are familiar with the PoP Sands of time series, I was trying to look for a video on youtube demonstrating this feature, surprisingly I haven't found one, I'll try to describe it however. In these games, you have the ability, to hold down a button, and rewind the last 5-10 seconds of time that has just passed, affecting you, the objects and enemies, and all this is going smoothly in real time. It would be similar as if you are watching a video, then you rewind 5 seconds of it, then go again. Only in the game if you made a mistake, fell off a platform now you have the chance to get another shot at it.

I found this feature improving the game experience a lot, such that after any small mistake you don't die, face a loading screen, have the whole thing interrupted, then start from a checkpoint, but at the same time the usage of this ability was limited, so it didn't make the game too easy either.

I am now thinking of implementing this in my 2d scrolling space shooter engine, but it makes me wonder how am I supposed to do this..
The only way I can imagine it, is that the past 5 seconds from current time, so the past 300frames at 60FPS is "recorded", such that for the player and every object, at every iteration of the game loop "saves" all their important variables, for example x,y position, velocity, current action etc into a corresponding past_x[300], past_y[300], past_velocity[300] etc.. array, and when rewind is flagged, at each game loop iteration, the current x,y, velocity, etc is updated from the past_x, past_y etc.

Now, considering enemies, bullets, particles, that is a lot of information to store, and would take up quite some memory.

Do you guys think this is the way I should try to implement this as I described above, or there is some better/more efficient way that I am overlooking?

##### Share on other sites
Basically, yes, that is what you need to do. Another fun game to do it was Braid.

Rather than recording the position of every particle, store the events behind everything.

Recording events at timestamps requires less space. You know an event at a time "bullet 7 fired from (x,y) @30:14.03", another event "bullet 7 hit target at (x,y0) @30:29.54". Then if your clock is at 30:16.43, you can figure out where the bullet was at that time.

Also, consider organizing your events into a spatial tree with one dimension as time so your list of items doesn't overwhelm you when rolling back and forth over time.

##### Share on other sites
[indent=1]What happens to your physics or particle pathing if you use negative time as your timestep?[/indent]

[indent=1]if for instance particles animated exactly backwards for path and effects using a negative timestep, you wouldn't have to record anything but their "fizz out" locations to spawn backwards animating particles as it rewinds the scene.[/indent]

##### Share on other sites
I've experimented a bit with this some time ago for a very stupid platformer. I could more or less make it work for most "well known" objects but in general, allowing a generic object to go back in time imposed quite some limitations I could not really live with.
Simply mandating timestep to be always positive nonzero (time monotonically increasing) simplifies things a lot. When I abandoned that assumption I had to rewrite some gameplay code with some propagations in logic as well.
I later experimented with "stateless" systems, where objects would collect events in queues. Instead of going back and forth in time, each object would be fetched a time gap from t[sub]0[/sub] (start of the event queue). This initially worked as expected but at this point I ran out of time for further experiments.

##### Share on other sites
Recording events is the idea, but events are not only when things are created (ie a bullet fired), but also when their velocity changes. If you record their changing velocity for a certain amount of time, you can reverse the velocities and work backwards. So, you store all these events in a queue, but clear out old events that happen longer than 5 seconds ago (or whatever your max rewind time is).

For example, an enemy spawns at position 10, 10 and begins chasing the player to the right (record timestamp, new location (10, 10), and velocity (10, 0)). 1.5 seconds later, he jumps up, following the player onto a platform (record timestamp, location and new velocity (10, -10)). When he lands on the platform 0.5 seconds later, his y velocity goes to 0 (record timestamp, location, and new velocity (10, 0)). 2 seconds later, the player kills the enemy (record timestamp and location of enemy dying).

1 second later, the player falls off the screen, but hits the "rewind button." Record the time he hit the rewind button, and work through the queue in reverse by subtracting the timestamp when rewind was hit by the time elapsed since then. 1 second later, you'll hit the enemy dies event, and location, but you'll actually spawn the enemy, and set his velocity to reverse what it was when he died (-10, 0).

And so on. If you are doing a platformer, I'd suggest working gravity into the events, since, when a player or enemy is jumping/falling, the velocity will be changing every frame, and you don't want to store all those changes.

Anyway, just a thought.

##### Share on other sites
I would use this on a scrolling shooter, with no physics involved. I would plan on making 3 seconds of max rewind time at 60FPS -> 180frames

[u][b]My concerns so far:[/b][/u]
[b]Randomly generated stuff:[/b]
most enemies are randomly generated, and let's say they have a chance of dropping something when they die too.
My solution to this would be, that everything that is randomly generated has to be determined/generated BEFORE the rewind time range, so before 180frames. So a randomly appearing enemy at the current frame must have been generated 180 frames ago, that way the rewind won't screw with anything that was supposed to happen in the future (counted from the -3 sec rewind time [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img])
I am still wondering if this would be a good method, or it won't work well.

[u][b]Other than that I could divide everything else into 2 categories:[/b][/u]
[b]1.[/b] Stuff that has a constant speed or constant acceleration, not AI driven.
These are primitive bullets that just go straight, stars, scrolling background and background objects and particles.
To record the state of every frame for each of these would consume too much resources, and would be unnecessary, and the above suggested timestamp method would be enough to calculate these objects position at any time having known the velocity (or acceleration if applicable).

[b]2.[/b] Anything more complex than above
More intelligent projectiles and AI driven enemies, that would be really hard (or not quite possible) to calculate their behavior at any given timestamp.
For these I really would just "record" their related variables/states for the last 180 frames in a stack, and during rewind I'd keep popping the topmost one into the corresponding current variables.

Do you guys think this is a good plan, or would you make some adjustments, or do it in an entirely different way?

##### Share on other sites
[quote name='BeerNutts' timestamp='1326982696' post='4904268']
Recording events is the idea, but events are not only when things are created (ie a bullet fired), but also when their velocity changes.[/quote]Yes, let me elaborate. Main problem is that each object must have some sort of log to post its interesting state changes and variable changes. In general this can be done with some way for each object to add events to a queue.
I experimented with both a "central event repository" (try to centralize management) and a distributed queue system (try to simplify). I am inclined to the second, although the amount of redundant code was a source of concern.

[quote name='chondee' timestamp='1327039173' post='4904480']
[b]Randomly generated stuff:[/b]
most enemies are randomly generated, and let's say they have a chance of dropping something when they die too.
My solution to this would be, that everything that is randomly generated has to be determined/generated BEFORE the rewind time range...
[/quote]I'd generate the loot when the enemy is spawned. I'd eventually give it its own random seed and generator.

[quote name='chondee' timestamp='1327039173' post='4904480']Do you guys think this is a good plan, or would you make some adjustments, or do it in an entirely different way?
[/quote]I think it's a good start.

##### Share on other sites
Personally, I would attempt to create an object that hold everything on the screen on each frame. So you could have a screen object. The screen object has a list of objects and there current state that is currently on the screen. You then create an array of these, for the first 300 frames, you save the state of each screen.

After your at 300 frames, you pop off the first frame, and add the next so frame 301 becomes becomes 300 and all other screens move back in the array(probably faster just to copy it into a new array). In this way, after the first 300 your taking just a single "screen shot" of the screen and getting rid of the first one.

Your also not worried about projectile calculations or anything like that since it should just be a matter of running backwards through the frames to restore the state of all objects on the screen 300 frames ago.

##### Share on other sites
I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.

If you're curious enough to spend $3.95, you can get [url="https://store.cmpgame.com/product/5900/The-Implementation-of-Rewind-in-Braid"]Jonathan Blow's GDC 2010 talk on the Implementation of Rewind in Braid[/url]. There's an interesting [url="http://gamedev.stackexchange.com/questions/15251/how-to-implement-time-traveling-into-a-game"]thread about it here[/url], as well. If I remember what Jonathan Blow said about it, he took a full world snapshot every some-odd frames (or seconds). That was to make sure a user couldn't abuse the physics engine through floating point errors. Then, for the in between frames, I believe he recorded the deltas for each object, but I believe he limited the deltas to just a few bits in order to save storage space (with the limitation that there was an upper limit of how fast an object could move, otherwise the object's delta couldn't be saved in just a few bits). Braid needed to do this though because you can rewind the entire game, practically. If you're only rewinding a few seconds, you don't have to worry as much about compressing the deltas. Unfortunately, I can't remember any other details. (for the curious, this is similar to how a lot of video codecs work, like H.264). #### Share this post ##### Link to post ##### Share on other sites [quote name='AlysiumX' timestamp='1327078691' post='4904615'] I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles. [/quote] You would still need to store states for every frame. 1. The user is typically allowed to cancel rewind at any point in the recording. 2. During recording, you can't throw away state, since a recorded frame T[n] must be saved until T[n+historyLength] #### Share this post ##### Link to post ##### Share on other sites [quote name='Nypyren' timestamp='1327082462' post='4904635'] [quote name='AlysiumX' timestamp='1327078691' post='4904615'] I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles. [/quote] You would still need to store states for every frame. 1. The user is typically allowed to cancel rewind at any point in the recording. 2. During recording, you can't throw away state, since a recorded frame T[n] must be saved until T[n+historyLength] [/quote] To add to the list: 3. That will significantly slow the application because writing a screenshot of each frame to disk is slow 4. You'll need to compress each image (png maybe?) or else you'll end up with gigabytes of screenshots (and compressing/decompressing each frame would be another bottleneck) 5. If you don't write to disk, but instead keep the screenshots in memory, you'll use about a gigabyte of memory for 5 seconds of screenshots at 30 fps and 1080p resolution (uncompressed, but even compressed will be quite large), which will probably kill cache performance in some areas of the program #### Share this post ##### Link to post ##### Share on other sites [quote name='AlysiumX' timestamp='1327078691' post='4904615'] I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles. [/quote] [quote name='Nypyren' timestamp='1327082462' post='4904635'] [quote name='AlysiumX' timestamp='1327078691' post='4904615'] I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles. [/quote] You would still need to store states for every frame. 1. The user is typically allowed to cancel rewind at any point in the recording. 2. During recording, you can't throw away state, since a recorded frame T[n] must be saved until T[n+historyLength] [/quote] What he said. For example, if you just picked up a power-up, then died, when you rewind 3 seconds, you will go back to before you had the power-up, so saving screens/frames isn't enough. You could store the event of "Acquired Power-up" at x time, then, when reversing, at that time, you remove that power-up, etc. #### Share this post ##### Link to post ##### Share on other sites [quote name='BeerNutts' timestamp='1327083278' post='4904638'] [quote name='AlysiumX' timestamp='1327078691' post='4904615'] I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles. [/quote] [quote name='Nypyren' timestamp='1327082462' post='4904635'] [quote name='AlysiumX' timestamp='1327078691' post='4904615'] I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles. [/quote] You would still need to store states for every frame. 1. The user is typically allowed to cancel rewind at any point in the recording. 2. During recording, you can't throw away state, since a recorded frame T[n] must be saved until T[n+historyLength] [/quote] What he said. For example, if you just picked up a power-up, then died, when you rewind 3 seconds, you will go back to before you had the power-up, so saving screens/frames isn't enough. You could store the event of "Acquired Power-up" at x time, then, when reversing, at that time, you remove that power-up, etc. [/quote] Well it seems like a terrific shortcut lol. Ya so basically what I originally said. #### Share this post ##### Link to post ##### Share on other sites [quote name='Cornstalks' timestamp='1327079140' post='4904620'] If you're curious enough to spend$3.95, you can get Jonathan Blow's GDC 2010 talk on the Implementation of Rewind in Braid. There's an interesting thread about it here, as well.
[/quote]

I think Braid is a really brilliant game and the time rewind thing was a main point game mechanic of it. If I remember correctly it had a some stuff going backward in time, some is going forward (at the same real world time), or depending on which direction the player is moving (while the player is moving forward in time) other objects may move either backward or forward in time.

For my game I think Braid's implementation would be overkill.
I would like to implement something simple, only covering my needs for rewinding time in case the player screwed up to have a second shot at it. The core game itself would not rely in time manipulation puzzles.

[quote name='AlysiumX' timestamp='1327078691' post='4904615']
I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.
[/quote]

Let's say taking 60 raw screenshots/second doesn't take an insane amount of memory and processing power.
I try to fight off 3 enemies, I kill two in the process, they explode, but I took too much damage, my health decreased to a minimum, I want to reverse the whole encounter.
Rewind everything.
How will the 2 enemies I killed come back to life, how will my health grow back, how will my position revert back?
That doesn't seem like the way to go.

I guess we can all agree that the current state at a given frame need to be captured of all objects.
For some objects that move constantly in a predictable way, like particles or scrolling stars, the current state can be calculated, this way saving memory and possibly processing power (in contrast to saving all variables for 500 particles and stars / frame)

For more complex AI driven objects I could only imagine that (almost) every variable they which is not constant must be saved for every frame. There are not that high numbers of these objects at any given moment, so that shouldn't be too expensive.

For me the obvious way would be that each objects before its state updated pushes its current variable on top of the corresponding variable's memory stack. On rewind the values are popped from the memory stack to the current.

EDIT:
[b]Another important thing that I just thought of:[/b]
In my current implementation of the game, in every frame all objects are polled to see if their alive flag is turned off, because if it is, they have to be erased from their vector container. (All particles, stars, enemies are stored inside vectors, a new one spawned is push_back() -d on it, dead ones are erased.)
This needs to be adjusted so after the object is not alive, it should not be drawn anymore, and it should not perform any logic anymore (other than keep updating the memory stack of its variables), but it should not be erased until enough time has passed that even after a full (3 seconds -> 180 frames) of rewind, it would not come back to life. So it can only be erased 180 game loop iterations after it died.
/EDIT

[b]My concern/question now:[/b]
Some of you are saying that there should be a separate class that dynamically handles/creates all the memory variables of each object, in contrast to having each object care about its own stuff.

To me having a separate object that has access to all variables of all other objects, and dynamically creates them for each by polling them every frame (lets say a new enemy spawns, after that this time manager object scans through all enemies, recognizes that there is a new one, in response to that it will dynamically allocate memory for all variables of that enemy, gets all values then stores it there) seems unnecessary complicated.

Is there any benefit of having a time state manager object doing all this, instead of having each object doing it for itself? Wouldn't it only over-complicate things?

##### Share on other sites
[quote]Well it seems like a terrific shortcut lol. Ya so basically what I originally said.[/quote]
It's not a shortcut, it's impractical. Constantly recording the X last seconds would consume a lot of CPU time, would saturate the PCI-E bus, would consume an immense amount of memory, and it would be fundamentally very limiting (you wouldn't be able to add visual features, etc...), and it wouldn't be scalable (resolution-dependent, among others).

The correct way to do it (or at least a better way) is to store the state of every relevant object in the game. Also you probably don't need to store state information for every single frame. If you are rewinding say 5 seconds over a duration of 2 seconds, you only need to store states for 2 frames out of 5, instead of all 5. Also you can probably get away with storing states for once every 10 frames and interpolating, it shouldn't be noticeable.

And yes, some items' states don't need to be stored, such as simple physics objects for which the position can be calculated by simply knowing the current time (like particles).

I would probably get a time state manager object to do it, it's just simpler (and once everything is working you can always change it - it's easier to change something that works than to implement the hard way from scratch).