timetraveler.lua - A rewind module for LÖVE

[otapliger]

Hello all, I am new here, I usually use Defold... but as I wrote a Lua module that might be useful to other people using different Lua game engines, here I am. This module essentially implements the rewind mechanic you can find in games like Braid. Have a look, it is under MIT license so do whatever you want with it

In the examples folder you will find a LOVE project to try. Left and Right arrows to move, Z to jump and LShift to rewind the time.

https://github.com/otapliger/timetraveler

[zorg]

I looked at the code, and i see that you only use dt in the record function to decide whether or not the beginning of the stored data should be trimmed to limit the interval one can rewind back. You could remove the argument from the other function since it's not used.

This is a good way of handling time, since the stored state is not using time-stamps, they're going by ticks... but maybe you should stress that this will only work correctly if the games it is used in use a fixed time-step. (Otherwise it might rewind with varying speeds, it should still be correct in a sense unless you also have things unaffected by such mechanics, like in braid, then it becomes an issue.)

The code for making it work with variable time-steps would be harder, since you'd need to store time-stamps so that the rewind speed would stay consistent, along with some mechanism to only allow returning to actually stored, valid timestamps, and not any in-between state that would be only for smooth rendering.

[otapliger]

I looked at the code, and i see that you only use dt in the record function to decide whether or not the beginning of the stored data should be trimmed to limit the interval one can rewind back. You could remove the argument from the other function since it's not used.

This is a good way of handling time, since the stored state is not using time-stamps, they're going by ticks... but maybe you should stress that this will only work correctly if the games it is used in use a fixed time-step. (Otherwise it might rewind with varying speeds, it should still be correct in a sense unless you also have things unaffected by such mechanics, like in braid, then it becomes an issue.)

The code for making it work with variable time-steps would be harder, since you'd need to store time-stamps so that the rewind speed would stay consistent, along with some mechanism to only allow returning to actually stored, valid timestamps, and not any in-between state that would be only for smooth rendering.

Thank you for the feedback, I really appreciated it. Yes, I will remove useless arguments and also update the readme as I forgot to mention you need to pass the delta time to the record function As you said, going by ticks is the easiest way and as Defold and LOVE per default use fixed time-steps I thought it was the right and quickest way. I will stress out in the readme that you should use it with fixed time-steps or at least expects some unconsistent behaviours, and maybe in the future add the option to choose between fixed (dt based) or variable (time stamps) time-steps.

[zorg]

Löve doesnt use fixed timesteps though.

The fact that vsync is on by default only functions as a coincidence regarding forcing the combined game loop (love.run) to execute once every <selected screen's vertical refresh rate> times a second. And even then, if you have multiple screens, moving the game window from one to another, that has a different refresh rate, will make the game run at a different speed; this is kinda why people are urged to use the dt argument, even with vsync on, in löve, and not do logic that assumes one tick took a pre-defined constant value.

This is the reason i suggested you warn people, since some might like or need to turn off vsync, and then things will stop being deterministic.

[otapliger]

I see... I updated the module and added an initial support for variable time-steps. By default fixedStep is false so, until people set it to true, the module will use timestamps. But I am still not satisfied. I mean, I tested it with LOVE with vsync off and it works, the rewind speed is constant... but the rewind speed is slightly faster than the play speed. I like the effect but I would like it to be a choice any idea on how to improve further?

[0x25a0]

First of all, that's a cool idea for a module

I get the same result; the rewind speed differs from the play speed when vsync is turned off. I compared the FPS while playing vs rewinding, and the framerate is higher during rewinding (about 270fps while rewinding vs 230fps while recording). That makes sense: especially with high framerates the library stores quite a lot of timeFrames, and this code segment iterates over all of them every single frame:

Code: Select all

      -- timetraveler.lua:41
      for i, v in ipairs(timeFrames) do
        if os.difftime(os.time(), v[2][2]) >= M.rewindLimit then
          table.remove(timeFrames, i)
        end
      end

Since you store those time frames chronologically (newer time frames are at the end of the array, right?), couldn't you do the following instead?

Code: Select all

      local time = os.time()
      for i, v in ipairs(timeFrames) do
        if os.difftime(time, v[2][2]) >= M.rewindLimit then
          table.remove(timeFrames, i)
        else
          break -- skip the other timeframes once we encounter a timeframe that is within the rewindLimit,
                -- since all following time frames will also be within the rewindLimit.
        end
      end

From some quick tests it seems like that does fix the speed differences for the most part.

---

However, I'm not sure if the library is actually supporting variable timesteps, even with the recent changes. That might be a matter of interpretation, and @zorg might correct me on that, but if the library supported variable timesteps then I would expect some sort of linear interpolation between the recorded positions when replaying. Here is what I mean: Let's say that you are on a motor bike. At time 0 you are at position 0, and you start driving. After 15 minutes you traveled 30 kilometres (so on average 2km/min). After another 20 minutes you travelled only 20 more kilometres (so on average 1km/min).

Let's say that these times and positions are your timeFrames: {{0km, 0min}, {30km, 15min}, {50km, 35min}}.
Now, if you were to rewind time by 20 minutes, then you would know exactly where you had been at that time, because one of the timeframes was recorded at that time. But if you wanted to rewind time by 25 minutes instead (so back to the 10th minute of your road trip), then there is no exact time frame for that moment. Instead, you would use the average speed between the first and second timeFrame to estimate where you might have been at that time. That is: (30km - 0km) * (10min/(15min - 0min)) = 20km.

I hope you see what I'm getting at. The point is that with variable timesteps, timeFrames might be recorded at varying speeds, and rewinding might happen at varying speed, too. You would need to walk through your history and interpolate between the two closest timeframes (or at least rewind to the timeFrame that is closest to the queried time) to account for variable timesteps.

[otapliger]

oh yes, I know exactly what you mean. I had the same logic thought. That's why I wrote initial support and asked for ideas .. and yes thanks for the feedback, I will add the break line to the code!

About the interpolation, I will work on it..

[otapliger]

Ok, I improved the module. Now you have a fps option. if you set fixedStep to false (that now by default is true because I mainly use Defold as engine ), through this option you can set how many frames per second record (by default 60). It should solve the variable time-steps problem... or not? @zorg, @0x25a0?

[0x25a0]

Looks good to me That should work fine as long as the actual framerate is higher than the framerate that is specified in the module.

But if the actual framerate drops (temporarily) below the framerate at which you want to record timeframes, then things get wonky again. If you want to cover those cases, too, there are two things you'll need to change:
1. Right now you reset the tick to 0 each time you record a timeFrame. This leads to a small discrepancy in each frame, which accumulates over time. Instead, you would need to do something like

Code: Select all

tick = tick - 1 / M.fps

2. When the actual framerate is lower than the framerate at which you record, you will need to insert more than one timeFrame every now and again to "catch up". Let's say that you want to record a timeFrame every 4 seconds, but the actual framerate only renders a frame every 5 seconds. After 20 seconds, you would have recorded only 4 instead of 5 timeFrames. By inserting two timeFrames at the 20th second, you can sort of get away with recording at a lower framerate.

That could look something like this:

Code: Select all

    tick = tick + dt
    while tick >= 1 / M.fps do
      now = {}
      for i, v in ipairs(properties) do
        table.insert(now, {v[1](), os.time()})
      end
      table.insert(timeFrames, now)
      tick = tick - 1 / M.fps
    end

in lines 33 through 40, and you would need to make pretty much the same changes in lines 74 through 83.

So, say that you want to record at 60fps, but the game only runs at 55fps. Without those changes, you would actually only record timeFrames at 55fps. With those changes, an extra timeFrame would be inserted at every 11th frame, so that after one second you would have 60 timeFrames, even though you only rendered 55 frames.

That's a bit of a hack, but it should make sure that the recording speed equals the rewind speed even with a fluctuating framerate.

[otapliger]

Done thanks for the feedback and help!