This is how the time travel mechanics of Braid were implemented. Record the events, apply those events in a deterministic manner, and then reverse the events to go backwards in time.
Not true, mostly. I recorded world state, not events. The one exception is world 5 where I record events so that your shadow-universe guy can do things.
Event recording has a fair bit of history in games, especially as a debugging technique, but I did not want to use it for rewind, considering it too fragile and annoying, and probably too expensive and complicated (you would have had to store world state anyway, to have something nearby to delta from so that you don't start from the beginning of time every frame, so now you have TWO systems: world state recording and event recording. Better to stick with one.)
If you modify the past, events are recorded and replayed, however (just rewinding focuses on a different world state). This is all baked in directly to the programming model. Another thing we are able to do is capture deltas rather than do entire world checkpoints, which works out well since many states do not change on all time steps (except for that moving bullet, of course). So each cell has multiple entries of temporally scoped values (for values that change on every frame, they just have one for each frame).
Can you elaborate on the distinction between world state and events? As in, you don't capture user inputs but rather track all object positions and states at all times? seems very inefficient that way.
Also, big fan! Great work on the new language/compiler livecasts and can't wait for The Witness.
Exactly: I record the positions of all objects every frame (and other state variables), not the inputs that generated them.
It is more expensive in terms of the amount of memory required, but it is much less expensive in terms of the amount of CPU required, and CPU was ultimately the biggest problem, so it seems I made the right decisions. Even on a limited-memory console like the Xbox 360 you can rewind most levels for 30-45 minutes before running out of buffer. That is more than anyone ever wants to do as a practical gameplay interaction.
Working on The Witness... it will be done ... someday not too long from now.
Did you use deltas a la trie-based immutable data structures, or did you save the entire state every moment? Did you save frame by frame, or did you save ON the event, and then interpolate animations between the two states when reversing?
In most worlds, the oldest state just gets thrown out; you keep playing as usual, it's just that if you were then to try and rewind all the way to the beginning, there would be a limit on how far you can go.
In world 4, though, where you can walk to the beginning of time just by walking to the leftmost part of the level, I actually kick the player out of the level when there's no more memory. I have never heard of anyone noticing this.
That would be a cool game mechanic: you can freeze time and fine tune your behavior over a small window of the immediate past(e.g. the last two seconds), with the ability to see how the game changes over that window "strobe style." Sort of like Sherlock Holmes (in the movie where he thinks everything through "what if" style).
It's efficient enough, given its a 2D plattform jump&run game. The developer wrote an extensive article how it works, it's really interesting, search for it.
You could do that, but then you aren't storing events any more, you're storing world state again. (That is what it means to make events reversible .. or at least that is the straightforward way I would think to do it.)
So as a bluntly simple example, assume the entire world's state is just the number 100. Instead of storing 105 as the new state, you store {:increment, 5}, and somewhere, the reversible counterpart to increment is defined {:decrement, 5}. You're correct that a full global state would have to be stored at SOME point, but could you simply hold the initial state, and the current state, and work from either of those?
Or just do what the mp4 video algorithm does and store so-called "keyframes" every N frames which store the entire state, but all intermediary frames are just diff frames.
Many web apps end up needing a global event feed/stream that various processes hook into via publish/subscribe. In theory, these events are reversible. Of course, in practice, individual types of events may find difficulty, especially if they have side effects that are outside the control of the app developer
More generally this is pretty much the event sourcing pattern: http://martinfowler.com/eaaDev/EventSourcing.html