Golems — a DOS Lemmings game engine

[Mindless]

I can finally announce the project I've been working on for the past year and a half.  Golems!

Golems is a DOS Lemmings game engine.  It represents an original reverse engineering effort that is not based on Lemmix.

Golems v1.0 (for Windows)

Golems does not come with any data files.  To play levels, run the Golems executable, install the .NET 8 Runtime if it isn't already installed, click Game ▸ Load Game..., and select a "MAIN.DAT" file from a DOS Lemmings game.  The remaining data files will be loaded from the same directory that contains "MAIN.DAT".  The mode of the game engine (release X offset, splat height, etc.) will be determined automatically from this file.  The game engine assumes that your files are from the floppy disk version of the game, not the CD versions with the splat height that breaks WAFD.

You can also pick "CSTM.DAT" to play a Customized Lemmings level pack.

Or pick a file named "GOLEMS.DAT" (renamed from "CSTM.DAT") to play in the "Golems" game mode.  This game mode is similar to Customized Lemmings (which is the same as the Holiday game mode except for the red-blue palette swap) except that the one-way mining bug is fixed and the splat height is reduced by 3 for lemmings that start falling when walking or bashing.  I think this mode represents a good compromise between not breaking WAFD and not breaking most custom level packs.

There are a few bugs that are not and will not be implemented:

• Pause for time – because the behavior depends on picking High Performance PC mode or not.
• Nuke saved % – because the bug is arguably in the saved percentage calculation, and Golems doesn't use percentages. (Okay, it's mostly due to how much I dislike this bug and the percentages.)
• Right-click-and-hold – because a faithful implementation is fundamentally incompatible with rewinding.
• [Visual Only] Walking shrugger – because the visual part of this bug can cause out-of-bounds memory access.  The gameplay part is implemented.

I did also make some visual-only improvements to the control panel (status text, pause button, nuke button, and minimap) and to the level view (highlight selected lemming).  I limited these changes to what could have been done in the original game engines.

Aside from the above bugs, visual-only changes, and any bugs that result from out-of-bounds memory access, I hope to have implemented the game engine so that it behaves exactly as the original game engines.  Please let me know if you find any unexpected differences!  (Please note the game mode shown in Help ▸ About.)

Also let me know if you encounter any other bugs.

Some keyboard controls:

• Space – Pause
• ~ – X-ray View
• W – Fast/Step Backward
• Left Shift + W – Faster Backward
• E – Fast/Step Forward
• Left Shift + E – Faster Forward

And one more thing:

Golems in your browser

[namida]

One gotcha that Lemmix didn't reproduce (and this is only relevant to custom data files) - if a terrain piece has a pixel that uses one of the fixed 8 colors, that pixel will be visible but nonsolid.

EDIT: The browser player for the levels DB is really nice! One thing that would be nice - it's possible to set a page so that a tap and hold on mobile doesn't get treated as a right click (ish). I remember encountering that with some dumb Flash-style games I made at one point. I forget what the fix was though...

[WillLem]

Great effort! The smoothness of the rewind feature is particularly impressive, might I ask how you achieve this in Golems?

Also, is this open-source? Not looking to do anything with it (I already have more than enough to be getting on with Lemmings-wise!), but would be interested to see how you've approached the reverse-engineering. As this is a relatively back-to-basics engine compared to the likes of Lemmix & co, Lix and even Lemmini & co, it would be great to see what's happening under the hood.

[Mindless]

if a terrain piece has a pixel that uses one of the fixed 8 colors, that pixel will be visible but nonsolid.

I haven't tested it, but Golems should have this implemented at least half correctly.  It uses the most-significant bitplane for terrain existence, so gameplay should be correct.  It probably does not currently display the phantom terrain, however.

One thing that would be nice - it's possible to set a page so that a tap and hold on mobile doesn't get treated as a right click (ish).

This should be the case already?  The game screen area has touch-action: none;, which should suppress that.  Maybe I need to apply it to the black area outside the game screen as well in case the touch is just outside the game screen?

The smoothness of the rewind feature is particularly impressive, might I ask how you achieve this in Golems?

The game takes a snapshot of the game state every 17 frames (1 second of game-time).  Stepping back one frame is accomplished by going back to the previous game state snapshot and stepping forward however many frames necessary to end up one frame back.

All those snapshots would eat up memory pretty quickly, so I added a super fast/simple algorithm for compressing the terrain bitmap.  Any snapshot older than the latest snapshot gets compressed.  The game holds on to a copy of the original terrain bitmap to reference.  The compression algorithm produces a data stream that can be interpreted according to the following algorithm:

Code Select Expand


Set `refCursor` to the first pixel in the reference bitmap.
Set `dstCursor` to the first pixel in the destination bitmap.
While `dstCursor` is not at the end of the destination bitmap:
    Read a 16-bit unsigned integer from the stream and store it in `sameCount`.
    Read `sameCount` pixels from `refCursor` and write them to `dstCursor`; `refCursor` and `dstCursor` advance by `sameCount` pixels.
    Read a 16-bit unsigned integer from the stream and store it in `diffCount`.
    Read `diffCount` pixels from the stream and write them to `dstCursor`; `dstCursor` advanced by `diffCount` pixels.
    Advance `refCursor` by `diffCount` pixels.

The same compression scheme is applied to the effect map as well.  This way each snapshot basically only needs to store the accumulated changes to the terrain and effect maps along with the (uncompressed) creature states, gadget states, and various other small bits of game state.

It could probably be smarter and occasionally choose to create a new reference bitmap if the terrain changes a lot.

Also, is this open-source?

Not yet, but probably eventually.  But it is .NET and not obfuscated, so you could use ILSpy to easily peek at the code.

[mobius]

some things here are very intuitive and I like; for example; having "plus X" for save requirement, easily lets even new users know what's going on better than a recolor.

Also want to add that I really like having the FF buttons be hold-down instead of toggle, how I thought they always should've worked

[Simon]

FF buttons be hold-down instead of toggle, how I thought they always should've worked

Interesting observation. In Lix, I hold the 10-second framestepping, too, and it becomes fast-forward for me. Hard to say if it's worthwhile to turn toggle-on fast-forward into hold-to-fast-forward. I imagine that toggle-on is better for recording solution videos, but that's niche. Even in livestreaming, I prefer hold-to-framestep instead of the toggled fast-forward.

I haven't played Golems enough yet to decide if I want a super-fast hold-to-fast-forward in Golems.

snapshot basically only needs to store the accumulated changes to the terrain and effect maps along with the (uncompressed) creature states, gadget states, and various other small bits of game state.

There is wisdom here: Separation of all level state into an immutable and a mutable section. It's enough to store the immutable section once, at the beginning. We store the mutable section in regular intervals, possibly compressed.

We can push this further in all of our engines.

E.g, hatches and water don't need to be part of the mutable state at all. Their animation is only dependent on the number of physics updates since the beginning. We can keep them in the immutable section, and only prepare them just-in-time during the drawing step. It's common to have 10 to 50 water tiles in a level; Lix can omit many allocating deep copies here.

Traps must remain in the mutable section because they eat lemmings at unpredictable times, and both physics and graphics depend on such recent eating. Theoretically, traps can split into an immutable location and the mutable number of the physics update of recent eating, at cost of even more complication.

Thanks!

-- Simon

[EricLang]

Interesting project. Is there sourcecode somewhere?
So you save compressed bitmap states each 17 frames? I was thinking: do you skip that if nothing changed in the terrain and only save the lemming/trap states in that case?

I am still amazed that they managed to do all this with so limited memory. Nowadays we use 30 or 100 MB to run Lemmings

[Mindless]

Is there sourcecode somewhere?

I'm working on refactoring and tidying up the code.  It'll probably be some time next year that I publish it.

[EricLang]

The rewinding mechanism is interesting. The question is: is it worth it?
Looping through all frames, adjusting the terrain can be very fast.
With 128 lemmings running around + building + jobs (without graphics) I get around 24 hours of gameplay in one second.
With 1 lemming that I measured around 75 days of gameplay in one second.
Is rewinding to any moment not instant? Did you measure it? Curious

[namida]

Rewind is considered a must-have feature for Lemmings clone engines these days. Even WillLem's fork SuperLemmix, which has a focus on traditional style gameplay, retains (albeit discourages use of) these features. NeoLemmix and Lix have long since embraced it and consider it a legitimate strategy to make use of; many levels are designed with the assumption players will use such features while solving them.

[EricLang]

With "is it worth it" I was refering to the technical implementation of saving states in between, while "just replaying from the beginning" could be more than fast enough. That is what I am curious about. Saving states in between is a time-consuming thing.

[namida]

NL originally recalculated from the start. Saving states was a huge performance improvement. With that being said, every frame is probably excessive; NL saves every 10 seconds (and eventually discards most states, although it indefinitely keeps states saved on 1-minute marks) and IIRC Loap does every 5. Even Lix I believe is every second, not every frame.

[Mindless]

Did you measure it?

A fair question.  I didn't measure it until now.  I replayed every solution on the LLDB and measured the time:

• debug: 107.8 real-clock-min/sec (92.4 game-clock-min/sec)
• release: 142.4 real-clock-min/sec (122.0 game-clock-min/sec)

Looks like I'm leaving a bit of performance on the table.  Doing some CPU profiling, I see that half of the time is spent copying memory to emulate the effects of terrain changes happening after the terrain is already drawn.  (See attached screenshot of DOSBox where lemmings appear to be falling into the ground 1 frame after an explosion.)  I can probably improve the performance of that part with a bit of additional complexity so that I only copy the parts that matter.

The rewinding mechanism is interesting. The question is: is it worth it?

I think so, but I'm also biased by sunk cost .  Using snapshots changes stepping back one frame from O(n) to O(1).  It's not that much additional complexity or memory or processing.

Edit:
After getting rid of that lazy memory copying:

• debug: 360.6 real-clock-min/sec (308.9 game-clock-min/sec)
• release: 720.6 real-clock-min/sec (617.2 game-clock-min/sec)

A nice improvement!

[EricLang]

release: 720.6 real-clock-min/sec (617.2 game-clock-min/sec)

So that is 12 hours of replay-gameplay without graphics?
Not bad!
I am curious if you pre-allocate a large memoryspace before starting the game to fit in the history for each second.
By the way: are you aware of these new fixed-buffers in C# and this parameter-attribute [ConstExpected] (or [ContantExpected])?
Anway: curious to see the code:)

Question: how do i activate FF and going back etc.? Is there some doc with keybindings?

[Mindless]

I am curious if you pre-allocate a large memoryspace before starting the game to fit in the history for each second.

The game snapshots are allocated on-demand.  I don't think there would be much benefit in pre-allocating memory for the snapshots, and it's easier to work with when it's just a List<GameState>.

By the way: are you aware of these new fixed-buffers in C# and this parameter-attribute [ConstExpected] (or [ContantExpected])?

I didn't use InlineArray or ConstantExpected at all in Golems.  I could probably use InlineArray in a few places, but it's not easy to use.  ConstantExpected has almost no value for application developers.

Question: how do i activate FF and going back etc.? Is there some doc with keybindings?

The keyboard controls are in the first post (or when playing on the LLDB you can get them by clicking the "?" button).  I'm thinking of changing the keys around a bit for the next version -- I keep accidentally pressing Ctrl+W instead of Shift+W while playing on the LLDB, which closes the tab.