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.
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.
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.
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:
Another important thing that I just thought of:
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
My concern/question now:
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?