Author Topic: How does NeoLemmix handle fast-rewind?  (Read 6984 times)

0 Members and 1 Guest are viewing this topic.

Offline LJLPM

  • Posts: 402
    • View Profile
How does NeoLemmix handle fast-rewind?
« on: February 17, 2018, 08:49:34 AM »
Hi,
I found a bug in my Android game's fast-rewind option, and levels may not be well saved/restored :(
How does NeoLemmix handle fast-rewind/saved "snapshots" in RAM? How does NeoLemmix keep tracks of level modifications, during the game?
Maybe I could use the same method in the Android game?
Thank you for your help!
 

Offline Nepster

  • Posts: 1829
    • View Profile
Re: How does NeoLemmix handle fast-rewind?
« Reply #1 on: February 17, 2018, 10:43:50 AM »
namida has coded this part, so he knows better why this was coded the way it is. If you want to look at the actual code, you should search for TLemmingGameSavedState in LemGame.pas. The RAM-intensive parts of it are the TerrainLayer and the PhysicsMap, which both are TBitmap32s (a tightly packed byte array of the bitmap info). Apart from that we still save a TByteMap for zombies, though this should be obsolete by now.
Regarding how often this is saved, I have found some comment in the code:
Code: [Select]
  // What we want to save:
  // -- Last minute: One save every 10 seconds
  // -- Last 3 minutes: One save every 30 seconds
  // -- Beyond that: One save every minute
  // -- Additionally, a save immediately after the level is initially rendered
  // This will result in 11 saved states, plus one more for every minute taken
  // that isn't in the most recent 3 minutes. This should be manageable.
and every now and then the list of save states is cleaned and the no longer needed save states are deleted.
On huge maps that go on for 10 minutes or more, this might take about 100MB storage or even more. But as NeoLemmix targets actual computers and not smartphones, this is acceptable for NeoLemmix.

Offline LJLPM

  • Posts: 402
    • View Profile
Re: How does NeoLemmix handle fast-rewind?
« Reply #2 on: February 18, 2018, 11:13:52 AM »
Thank you for your reply!
I also save level's bitmaps (actual level's image + level's mask), and I hoped for a less RAM-expensive method, in NL...
In the Android game, I've done tests using up to 3 recyclable saves -as I can't use 100MB in RAM-. Since it's a very convenient feature, it's too bad I can't allow many saves in RAM, for the game (unless I find a lighter, and more reliable, way to save level's bitmaps... As a matter of fact, level modifications only deal with few pixels...)

Offline namida

  • Administrator
  • Posts: 12398
    • View Profile
    • NeoLemmix Website
Re: How does NeoLemmix handle fast-rewind?
« Reply #3 on: March 18, 2018, 05:04:28 AM »
The amount of saves NeoLemmix makes is probably excessive. Even saving perhaps (where N = now) N - 20 seconds, N - 40 seconds, N - 60 seconds plus a save every 2 minute mark, is probably enough. It's worth noting that NeoLemmix's processing / rendering was far from optimal at the point where this feature was first implemented, so it benefitted much more from having more-frequent saves. I suspect that the amount of saves kept could be greatly reduced on the current version with no noticable degradation in performance except maybe on particularly large levels with a lot of action going on at once.
My Lemmings projects
2D Lemmings: NeoLemmix (engine) | Lemmings Plus Series (level packs) | Doomsday Lemmings (level pack)
3D Lemmings: Loap (engine) | L3DEdit (level / graphics editor) | L3DUtils (replay / etc utility) | Lemmings Plus 3D (level pack)

Offline EricLang

  • Posts: 464
    • View Profile
Re: How does NeoLemmix handle fast-rewind?
« Reply #4 on: October 25, 2018, 12:50:09 PM »
Actually rewind could be implemented just replaying the game without updating the screen. This is quite fast and does not need any buffering / saving.

Offline Simon

  • Administrator
  • Posts: 3860
    • View Profile
    • Lix
Re: How does NeoLemmix handle fast-rewind?
« Reply #5 on: October 25, 2018, 01:52:12 PM »
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
« Last Edit: October 25, 2018, 02:08:11 PM by Simon »

Offline Nepster

  • Posts: 1829
    • View Profile
Re: How does NeoLemmix handle fast-rewind?
« Reply #6 on: October 25, 2018, 08:15:15 PM »
When mass replay checking (F7 on the main menu), we do exactly that in NeoLemmix: No drawing to the screen and no buffering. As we print out the in-game time regularly, you can watch yourself how fast this would be. And the answer is: Not nearly fast enough. Especially with long levels streatching over 10 minutes or so, you would have to wait several real-time seconds until the replay is finished.

I haven't profiled this, but my guess for the most time-consuming tasks would be on applying the terrain removal masks: The solid pixels are still stored in a huge bitmap and when removing or adding terrain, the corresponding mask is just drawn onto this bitmap (or rather the corresponding data manipulations are made). Yes, there are certainly faster ways to get the correct physics map (especially when not having to render the level at all), but that would mean quite a big change in how the code is set up.

However it really depends on the way the game physics are implemented - LJLPM might be luckier there than Lix and NeoLemmix are.

Offline namida

  • Administrator
  • Posts: 12398
    • View Profile
    • NeoLemmix Website
Re: How does NeoLemmix handle fast-rewind?
« Reply #7 on: October 26, 2018, 10:39:02 PM »
Actually rewind could be implemented just replaying the game without updating the screen. This is quite fast and does not need any buffering / saving.

Prior to NeoLemmix implementing the internal saved-states, the lag when backwards frameskipping was a very common complaint. It's fast enough on Lemmix, which has much simpler physics, but it is nowhere near fast enough on NeoLemmix, even on fairly powerful PCs.
My Lemmings projects
2D Lemmings: NeoLemmix (engine) | Lemmings Plus Series (level packs) | Doomsday Lemmings (level pack)
3D Lemmings: Loap (engine) | L3DEdit (level / graphics editor) | L3DUtils (replay / etc utility) | Lemmings Plus 3D (level pack)