Hi,
here's how Lix implements performant rewinding and recomputation. This is the backbone of singleplayer rewinding. And during multiplayer, when an incoming packet had some lag, we can integrate it into the replay and recompute.
Automatic savestates:
- Right now, it's 10:00 UTC, 22nd of August, 2026.
- We remember 00:00 UTC, 22nd of August, 2026.
- We remember 00:00 UTC, 21st of August, 2026.
- We remember 00:00 UTC, 1st of August, 2026.
- We remember 00:00 UTC, 1st of July, 2026.
- We remember 00:00 UTC, 1st of January, 2026.
- We remember 00:00 UTC, 1st of January, 2025.
- We remember the creation of the universe.
How it stores:
- When the game loads, backup #1 into #8. That #8 will never be overwritten.
- Every midnight, we save #1 (the current world) to either #2 or #3.
- Even-odd rule: Even-numbered days will always be saved into #2, overwriting the previously saved even-numbered day. Odd-numbered days will always be saved into #3, overwriting the previous odd-numbered day.
- Every new month, we save #1 into #4 or #5, again with an even-odd rule.
- Every new year, we save #1 into #6 or #7.
I call the pair of #2 and #3 a "leapfrogging pair of savestates". Reason: The even-odd rule above means they'll leapfrog each other. Sometimes #2 is the newest and #3 is one day behind, sometimes #3 is the newest and #2 is one day behind. So far, it alternates nicely. When the user rewinds and replays, it's possible that we'll write to #2 several times in succession before we ever write to #3 again, because of how it's used for rewinding:
How it rewinds:
- To rewind, load the latest savestate that's not later than the rewinding target time, and recompute from there to the time.
- E.g., to rewind by a few hours, you might need load the savestate that's between 1 and 2 days old. Load it, and recompute. During this recomputation, we'll run over a midnight. We should save this! Because of the even-odd rule, this will overwrite the other savestate among #2/#3 from which we didn't load at the beginning of this rewinding.
- Even longer rewinds will load the savestate from last month. During recomputation, we'll cross several midnights, and we should re-save the world every time into #2 or #3.
- Very long rewinds recompute from a few years ago. Along the way, we'll re-save to #2/#3 and to #4/#5, possibly also to one of #6/#7.
What are good intervals for savestating? Days/months/years are only good for the example. The unit of time in Lix is the physics update, not days/months. Normal gameplay speed is 15 physics updates per second. This leads to the following leapfrogging resolution:
- The current world, age n.
- Every 10 physics updates, if n % 20 == 0.
- Every 10 physics updates, if n % 20 == 10.
- Every 60 physics updates, if n % 120 == 0.
- Every 60 physics updates, if n % 120 == 60.
- Every 360 physics updates, if n % 720 == 0.
- Every 360 physics updates, if n % 720 == 360.
- Every 2160 on non-huge levels, if n % 4320 == 0.
- Every 2160 on non-huge levels, if n % 4320 == 2160.
- Every 8640 on smaller levels, if n % 17280 == 0.
- Every 8640 on smaller levels, if n % 17280 == 8640.
- The beginning of the level.
n is the age of the world in physics updates.
% is modulo (computes remainder of division).
Reasoning for the value of 10 for the fastest pair:
- 10 physics updates take 0.666 seconds at normal speed. The fastest leapfrogging pair will offer two savestates between 0 and 1.333 seconds of real-time. That's slow enough for most networking lag, e.g., for bad lag around 0.5 seconds.
- For singleplayer, it's fast enough for the common single-frame rewinds. Most rewindings will recompute only a few physics updates. You can conduct 60 rewindings per second and display all outcomes to the user at 60 fps.
See My implementation on github (https://github.com/SimonN/LixD/blob/master/src/physics/world/cache.d). I've abstracted each pair into its own
struct LeapfrogPair. The physics cache has 5 leapfrogging pairs, and each pair maintains two savestates ("frogs").
To save VRAM on huge maps, I keep only 3 or 4 pairs, not 5 pairs. But this decision is largely out of fear. I don't know how much this helps with crashing for being out of VRAM. It's unrelated to the discussion of the algorithm. Nonetheless, it's in the code like this. Don't copy this decision; use many savestates.
Optimizations:
- Try different widths for leapfrogging pairs. Each of my pairs is 6 times as wide as the next-faster pair; try 5 or 8. My fastest pair is 10, try 5 or 20. So far, I've been happy with my choices of 6 and 10.
- When you rewind for months or years to today, 10:00 UTC at August 22th, you don't have to save into #2 or #3 the stuff from August 2nd, August 3rd, August 4th, August 5th, ... because they'll have been discarded again by the end of the rewinding-and-recomputation operation. What matters is that you remember the newest two: 00:00 August 21st and 00:00 August 22nd.
- During turbo-fast-forward which goes at 540 physics updates per second (36 times faster than regular speed of 15 physics updates per second), I don't save to the fastest leapfrogging pair #2/#3. I accept that the first rewind will take minimally longer because it must load from #4/#5 instead of from #2/#3, and during this rewind I'll refill #2/#3. I don't know if this is still useful in 2026; it looked useful in 2015.
- During non-graphic replay verification, don't save anything at all. You don't need this system of savestating because no interactive user is going to rewind.
-- Simon