Data structure of the lemmings in MD\Genesis port

[Gronkling]

Working on my TAS I've decently reverse-engineered how the data of a lemming is stored, and what data is stored about it. Since the MD/genesis port is very similar to other ports, this may also be true for systems like Amiga and DOS. However there are still some MYSTERIES (fun!), what are byte 10, 13 and 14, and what is skill 19.

Each lemming has 16 bytes stored about it. These chunks of 16 bytes are stored in an array, starting with the data about the first lemming to enter, then the second, and so on. In the version I have, this array starts at address E6B4 in the RAM.

Things found by geoo are in blue text, more details in 3rd reply

Now for a byte-by-byte breakdown of what exactly is stored about each lemming.
BYTE 1: The "half" of the level it is in, if it's in the left half the value is 0, if it's in the right half the value is 1. Basically it's just an extra bit for the X-position of the lemming. Hacking this value to be >1 doesn't seem to result in the lemming being erased, instead it gets "stuck in a wall" rapidly alternating left and right, but not visible in the level.

BYTE 2: The standard X-position of the lemming, all values are used

BYTE 3: The Y-position of the lemming. 0 is the top of the level and 174 is the bottom. There is a "ceiling" at value 8 though and it is impossible to go any higher with current knowledge. The actual bottom of the visible level is 160, but the lemming dies at Y-value 174. Hacking any higher values causes the lemming to instantly die, though hacking it to be it's maximum value causes the lemming to wrap around to the top of the screen, and fall all the way down again with no collision, before dying as usual.

BYTE 4: This one seems to control the X-offset of the sprite used by the lemming, with different skills requiring different offsets to render in the correct position. I have found a single non-hacking glitch where this seems to go wrong, using a climber glitch in terrain, and going through a blocker field may make the sprite render a bit further to the right than it's actual position would suggest for a few frames.

BYTE 5: Same as above, but for the Y-offset.

BYTE 6: Each bit in this byte is a different property

Spoiler

bit 0: direction
bit 1: climber flag
bit 2: floater flag
bit 3: removed from level
bit 4: player
bit 5: blocker related
bit 6: blocker related

BYTE 7: This cycles through the frames of the lemming's sprite animation.

BYTE 8: The skill of the lemming!

Spoiler

0    Walker
1    Oh-noer
2    Drowner
3    Instant Explosion
4    Faller
5    Jumper (used when going up steps greater than 2 pixels)
6    Exiter
7    Climber
8    Hoister (when finished climbing)
9    Shrugger (when finished building)
10   Floater Start
11   Floater
12   Splatter
13   Digger
14   Blocker
15   Miner
16   Die in fire trap
17   Builder
18   Basher
19   Occurs when a floater is assigned as a lemming is falling
above that causes game to crash

BYTE 9: Bomber countdown. Is set to 79 when a bomber is applied and decreases by 1 every physics update cycle. Turns into an oh-noer when this reaches 0.

BYTE 10: Counts up by two every physics update cycle when a lemming is floating down, seems linked to the floater sprite animation.

BYTE 11: Combined fall distance and builder countdown. It counts up when a lemming is falling to keep track of fall distance, to check if it should splat. When a builder is assigned it counts down from 12, reducing by one each time it lays a step (every 15 physics update cycles). This counter is only reset when the lemming becomes a builder or a faller or a blocker.

BYTE 12: This changes based on what sort of object trigger area or terrain it is in. For example it is 0 when in air, 1 in an exit trigger area, 8 when in a steel area. Haven't really looked into what each number means. This does not seem to actually affect the lemming's actions though, hacking it to be 1 does not cause the lemming to exit for example, and it is reset back to a normal value the next physics update cycle.

BYTE 13 and BYTE 14: UNKNOWN never seen these change, however is referenced in blocker-related code

BYTE 15 and BYTE 16: Work together to give address in memory where to find the sprite's animation: "if you look in the ROM, the value of these bytes plus 0x40644 give you the address where to find the sprites for the state (BYTE 8) this lemming is in. The exact offset also depends on the animation frame of the lemming (BYTE 7), and is computed in the skill-specific rendering code from off_9156 and off_9FC4. For example, for the walker or jumper, you'd find the ROM address of the current sprite of the lemming by taking 0x40664 + 0x168 (the value of BYTE 15-16 for walkers) + 0x28 * (BYTE 7). The sprites are encoded with 4 bits per pixel, and I believe for the walker the dimensions are 8x10 (not sure where the game gets the width and height of each frame from)"

[EricLang]

Hello, what is TAS?
Which files are you analyzing? Maybe I can help.
I have all genesis levels and graphics on my PC (forgot where they exactly came from but ccexplore was involved).

[Gronkling]

Hello, what is TAS?
Which files are you analyzing? Maybe I can help.
I have all genesis levels and graphics on my PC (forgot where they exactly came from but ccexplore was involved).

TAS - Tool Assisted Speedrun, using an emulator with the genesis game to get the fastest possible completion time. You can find it in the challenges board
I am just observing how the memory registers in the RAM change based on things that occur in the game. It's not to do with the graphics or levels and I don't need help, I just thought this was interesting.
Anyway I checked in 2P mode as I thought maybe one of the unknown use bytes could be in there, but this just uses an extension of byte 6.

[geoo]

I just had a look at the game's code to see if I can figure anything regarding the mystery values. (Attached is an old disassembly I made long time ago when trying to add mouse support to Genesis lemmings -- it's very poorly documented though.)

So each skill (BYTE 8) has its own unique pieces of code that only get executed for that skill. There are three offset tables with pointers to skill-specific code: off_7514 is for the logic executed during each frame, and off_9156 and off_9FC4 seem to be related to the rendering of the sprite.
So now for the 19th skill, it seems like a lemming is assigned this state when a faller (BYTE 8 = 4) is floater and has fallen at least 16 pixels (BYTE 11). Now this doesn't ordinarily happen though because, when a walker that is a floater walks off a ledge, it turns into the pre-floater state (BYTE 8 = 10), and from there into the regular floater state (BYTE 8 = 11). So I think you can only achieve this last state (BYTE 8 = 19) when assigning a floater during the fall? The skill specific code for floater (BYTE 8 = 11) and the last state (BYTE 8 = 19) also seems to have a lot in common, which would support this.

Now BYTE 10 seems to only be used by the blocker (about that later) and the floater. For the floater (BYTE 8 = 11 or 19), it seems like this value increases by 2 each frame and points into a table determining the current sprite of the floater.

So for the blocker, it seems like bytes 10-14 have a special meaning that is somehow related to its trigger area. Not sure what they mean exactly, but bytes 13 and 14 are only referenced by the blocker code, and in that context also bytes 10-14 are accessed, which makes me suspect that in particular byte 11 and 12 have a different meaning for blockers than for other skills.

Another piece of data that is only accessed by the blocker are bits 5 and 6 of BYTE 6. Bit 4 seems to determine which player the lemming belongs to in 2P mode, so let me summarize BYTE 6 with your previous observations:

Code Select Expand

bit 0: direction
bit 1: climber flag
bit 2: floater flag
bit 3: removed from level
bit 4: player
bit 5: blocker related
bit 6: blocker related
One thing to note is that there is a special check so that if bit 5 is set, then the game uses the same rendering code for that lemming as for the blocker (ignoring the skill specific code from off_9156 and off_9FC4). I don't know if it can occur that a lemming is not a blocker and has bit 5 set though.

Finally, BYTES 15-16 form a two-byte value that is an offset into unk_40644 (or unk_467D4 in case the lemming belongs to player 2) which contains the sprites for each possible lemming animation. So basically if you look in the ROM, the value of these bytes plus 0x40644 give you the address where to find the sprites for the state (BYTE 8) this lemming is in. The exact offset also depends on the animation frame of the lemming (BYTE 7), and is computed in the skill-specific rendering code from off_9156 and off_9FC4. For example, for the walker or jumper, you'd find the ROM address of the current sprite of the lemming by taking 0x40664 + 0x168 (the value of BYTE 15-16 for walkers) + 0x28 * (BYTE 7). The sprites are encoded with 4 bits per pixel, and I believe for the walker the dimensions are 8x10 (not sure where the game gets the width and height of each frame from). The first walker frame looks like this:

Code Select Expand

00000000
00022220
00003220
00033300
00001300
00001300
00001300
00001100
00001130
00003300


[Gronkling]

Really cool finds and additions, I'll edit the first post to add what you said. The floater thing with byte 10 does happen when testing in gameplay.
However the blocker doesn't seem to cause an effect in bytes 13 and 14. It resets the counters of byte 10 and 11, and affects byte 6 as you expected.
It seems that skill #19 is given when a lemming is assigned a float whilst falling as you predicted

[Gronkling]

Looking at glitch skills above #19:
Nearly all will completely crash the game as soon as they appear, freezing the screen and stopping all activity. Here's a list of ones that do something different:
#69 - Converts to a shrugger after 1 cycle (and is called "mberdig" for this short time)
#73 - Converts to a shrugger after 1 cycle (and is called "gger bu" for this short time)
#109 - Teleports the lemming to various places. Without screen scrolling it went to the far left side of the level, after scrolling it went to some place far out of bounds.
#113 - Teleports the lemming to the top of the level and flips its direction.
#122 - Makes the lemming disappear instantly and count as dead, shows bomber text for 1 cycle
#146 - Makes the lemming disappear visually, but still exist and be frozen, with name "her flo". Can't be assigned new skills.
#149 - Converts to drowner for one frame but called "zv"vzv, converts to a faller moving the lemming down a few pixels, before walking on as normal
#153 - Converts to a splatter, causes graphical glitches, then crashes
#171 - Glitches all the lemmings graphics, making them squashed and float in the middle of the screen