Actually rewind could be implemented just replaying the game without updating the screen. This is quite fast and does not need any buffering / saving.
In replay verification, certainly don't buffer; algorithm would run at less than half the speed.
In interactive play, buffering seems better from my experience, unless you can compute 5 minutes of in-game time, including all behind-the-scenes land drawing, in 1/60 of a second. Maybe possible on contemporary machines, but would surprise me?
For best user experience, allow people to hold the framestep-back key and see every single phyu (physics update) frame that is rolled back. For user experience, this is good; to reach the desired phyu, people can quickly decide between rewinding further or stepping ahead.
Assume NL's values for short-term rewinds (buffer every 20 seconds) and you rewind from second 100 to second 90. This is a rewind by 170 physics updates. For every single rewound update, algorithm loads the buffer at second 80, computes forward (340 phyus behind second 100), then draws the result to the screen:
Update physics 339 times, then draw
Update physics 338 times, then draw
Update physics 337 times, then draw
...
Update physics 170 times, then draw= 170 * 180.5 =
30,685 updates to compute +
0 saves. This is because you will not save a single time during this recomputation; we haven't hit any new 20-second boundary at 80, 100, 120, ..., seconds of in-game time.
If, instead of from second 80, you recompute from the beginning (second 0) every time, each of these 170 steps backwards incurs an extra penalty of (80 seconds * 17 phyu/sec) = 1,360 updates. Together with the 30,685 updates that you have to compute after second 80 anyway, you compute a total of 30,685 + 170 * 1,360 =
261,885 updates +
0 saves.
I remember I experimented in Lix with different short-term buffering intervals. For the short term, I buffer even more frequently than NL, every 10 phyus = every 2/3 of a second at normal speed. For the long term, I buffer less frequently. Caveat is that Lix graphics are hardware-accelerated and behave completely differently than software graphics; not necessarily faster because of pixel-drawing on textures all the time.
The downside is that the physics caching is bug-prone. Probably good idea to build the app without caching first, and then decide.
-- Simon