Rewinding time, what would be the best way to do it?

[Cucurbitacée]

Hi everyone,

I'm still experimenting a lot with LÖVE at the moment, and still having a lot of fun so far. While thinking about gameplay ideas, I thought about games that allow you to rewind time, and how cool it feels when it's correctly used.

Sooooo, I'm wondering what would be the best way to do the same in LÖVE, or most probably only in Lua, I'm not sure a specific part of LÖVE would be used for this.
My first thought would be to store every variable at each frame, but I fear this may generate a lot of data to store... Then I thought about "reverse function" that would do the opposite of what happened; but I guess it would require to record player input anyway...

If you have a genius idea to do so, I'd love to hear it.

[Plu]

You need to make a sort of replay feature. Your program must be able to run entirely independant from input, by taking all its input from a list of input commands with times on them. Then, when the player does something, you add his input command to the input list at the current time-moment.

When the game runs, it simply reads inputs from that list and executes them. If the player overrides the old feed (by rewinding and then playing again) you can simply scrap everything beyond the current playing point in the input list, and then start inserting new actions.

In order to make the game actually run in reverse (not just jump back a few seconds and replay it) you will need to build all your actions in such a way that you can calculate them both forward and backward. I'm not entirely sure how to do this part, as it can get really complex really quickly.

I'm guessing in addition to your input-list (which you need to remember what the player was doing) you will also need to keep an event-list, and then you need code to run any event in forward and reverse. For example; if you shoot a bullet, you need to log a "bullet created" event, then a "bullet hit" event and finally a "bullet dead" event. Each has a timestamp. Then, when running the code, you would run across the "bullet dead" event, and it needs code to run this event in reverse, so that the bullet is created with the final frame of its death animation, and the runs the animation in reverse. And the movement code also needs to be able to run in reverse, so that the bullet flies backwards.


Oh, and a pitfall to avoid: if you ever use random numbers, treat them like input! Do not just grab a random number internally, but grab it from the input list and store the value you got. Otherwise replaying the same game multiple times might not give you the same output, and the reason will be really annoying to track down.

[Plu]

Hm. Perhaps, a bit more simplified... you will need to store your whole game as a long list of events, and attached to each event you need code to run the event forward and backwards. Then you need a general runner-tool that can call each event at the exact right time both in a forward and backward manner. User input needs to be on the event queue, and every other creation/deletion/update of an entity needs to be there as well.

But it'll be interesting stuff. Have you ever looked at the game Braid? It does time-stuff really well. Might give you some ideas.

[micha]

Plu already said that, but I want to state this clearly: If you want to rewind time in a game, then you need to record the game state (coordinates of all objects etc) in all timesteps. It is not possible to run your physics backwards (maybe it is possible partly, but not entirely).

Here is one example for illustration: Image a mario-type game with a goomba-type enemy (just walking and falling down). Let's say this enemy walks on a higher platform, falls down between two walls and starts walking back and forth between these two walls. If you now want to play it backwards, how would you find the moment, when the enemy starts revers-falling up to the platform? Or in other words: Even if the physical simulation is deterministic and without user input, still very different initial conditions might lead to the same end condition. Then a unique inversion of time is not possible.

Bottom line is: You need to store the state of the game in each frame. I have not tried it, but I think the trick is to determine, which quantities you need to store and which ones you can derive from the stored ones. For example, maybe it is enough to store the objects' coordinates, and the animation state can be derived from the coordinates.

[Plu]

You don't need to store every frame (that would be madness and flood your RAM in no time), you only need to store a point in which the behaviour of an entity changes. For example; a goomba in free fall doesn't need its data stored every frame. Neither does a moving goomba. We only need to store the point where the behaviour changes from "falling" to "moving" (ie; the impact point with the ground, or the point where it walked off the platform)

From there, we can calculate its trajectory in both forward and backward mode. In forward mode its simply a matter of adding the effect of gravity to it to make it fall, and then switching to horizontal movement mode when it touches the ground. In reverse mode it's slightly more complex; we need to jump to the previous saved point (where the goomba changed from horizontal movement to falling, on the top platform) and then use that information to calculate the effects of gravity in reverse, so that we can start applying reverse gravity to the goomba to make it fall upwards, back to the edge of the platform.

Usually the forward code is just the regular stuff, but the reverse running code will often need to scan through the list of save points to calculate what a certain variable would have been at its current location. Don't be surprised if the framerate is a bit worse in reverse mode because of the extra calculations. Although generally speaking, if you have a full copy of the entity state in each save point, it should be a rare case where you have to scan back more than one node.

[retrotails]

Have you ever used the rewind feature in retroarch? It makes a savestate every frame, and just 30 MB is good for several minutes in a typical 8/16 bit system. If RAM was an issue, you could do what I did with a tetris clone (not posted on the forums) and use one string for all the variables you want to be able to rewind, and add each frame to a table you can push/pop from.
edit: Also dont forget its best to limit the framerate.

[Plu]

It's probably worth noting that a typical 8/16 bit system is optimised to run on a machine with only a few kb of RAM, and such games have really small footprints. You'd have to do some serious optimising work to get such a small set of data in your löve game I would think. Although I've never actually tried to benchmark löve's actual memory usage.

Of course I also have no idea how complex this game is going to be. If it's relatively simple you don't need a very complex system, and making many copies of the gamestate can work. But considering many games run at 30fps or more, just 1mb of data in use would quickly ramp up to 30mb/s, which could seriously fill up RAM. And probably the last thing you want is squeeze every last byte of memory out of your game, because that'll make the code a lot less readable than a smarter way to handle it.

But I can imagine something along the lines of tetris being compressible into a string short enough that you can store a copy every frame. Guess it really comes down to: what do you want to make with this idea?

(Oh and I just remembered the most insane example of time travelling games. Achron. A full RTS that not only allows you to rewind time, but also allows you to build troops, send them back in time, and then re-fight a battle you originally lost because you now have troops that hadn't been built yet. And the kicker: you can do this in multiplayer against other people. Amazing.)

[micha]

This refers to the post two above:

We only need to store the point where the behaviour changes from "falling" to "moving" (ie; the impact point with the ground, or the point where it walked off the platform)

Ok, I understand. So in the forward simulation there are time-episodes that are reversible and there are moments, when information about the past is lost (behaviour change from falling to moving). So we need to keep track of these moments. Then it is generally possible to reconstruct any previous state of the system (given the current state and the pile of "lost information").
I have to admit that here I am discussing something that I haven't tried myself, but I still doubt that this approach is very practical. Have you tried implementing such a system?

I made a small calculation to see how fast the memory is filled, if you record a game: A double has 64bit = 8 byte. If we have 50 Objects on screen and each objects contains 10 numbers to characterize it's state and if we record 60 frames per second for 10 seconds, then we end up with
8*50*10*60*10 = 2,400,000 byte = 2.4 Mb. That isn't as bad as I expected. But still, yes you can get into a range that will not fit into your memory. So if I wanted to record a game in order to player it backwards, I would have to be careful to select the essential data and only store these. Otherwise it could grow too fast. So maybe an event-based approach is better, than a state-based approach. And this is already what you suggested.

Thanks for discussion. It made me thinking and I learned something.

[retrotails]

Small demo. 2nd number is collectgarbage(math.floor("count")) and for some reason that 210 number seems wrong since the string obviously gets bigger fast.
edit:
this NEEDS vsync, otherwise RAM use could get out of hand. The 2 most important things you need are a constant framerate (as in, never use dt, always use 1/30 and lock the FPS to 30) and limit the time. For example, you might only need 64 MB RAM if you have to solve something in under 1 minute.

[Cucurbitacée]

Thanks for all the answers, it's a very constructive discussion.
In my case I would like to replace the usual smart bomb used in shooting game with this rewind option. I'm trying to imagine what it could be, and I think that 5 seconds would be the huge maximum required for this kind of game.

So, first I'm going to force fps and vsync and add a tracking system for all the necessary variables.

Thanks again.