Author Topic: Lemmings 2 Physics Research  (Read 11494 times)

0 Members and 1 Guest are viewing this topic.

Offline exit

  • Posts: 197
    • View Profile
Lemmings 2 Physics Research
« on: December 17, 2021, 05:46:07 PM »
Ravenix, I did some work almost two years ago reverse engineering Lemmings 2 DOS with the DosBox debugger. The only notes I have saved are an early analysis of some of the explosion physics, but seeing this topic made me want to take another look at the game code and see if I could do anything to help.

If you are interested in looking at the code for any skill in the game, the game handles all of the skills through a call at 2107:0275. Each skill (or lemming state) is associated with a value. Walker is 0, faller is 40, etc. This value is used to find the address in a map which starts in memory at 2107:029A. The game essentially just calls to the address pointed to in the map, then proceeds from there.
I have a code dump of the entire segment 2107, which should contain the code for each skill, but it seems like the disassembly is not entirely correct. At least the walker code was disassembled incorrectly, maybe more. I might try to find a different way to dump the code, but I've found that stepping through the code with the debugger makes it a lot easier to see what's going on.

If you're interested, I can give you all the memory addresses/notes I've made so far. It isn't much, but it should be enough to reverse engineer a good portion of the skills.



« Last Edit: January 07, 2022, 09:33:44 AM by ravenix83 »

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #1 on: December 17, 2021, 09:01:00 PM »
Anything that helps. Thanks. I've made some progress already on the physics using frame analysis. So far I get identical frame-for-frame trajectories on trampolines, launchers, cannons etc. But any insight to how it was actually done would help for sure.

Currently the lemmings have two movement modes. Animation driven and physics sim depending on the skill/state. The physics sim uses fixed-point math for deterministic results. Each delta is sub-stepped at the pixel level to prevent some of the glitches found in the original. e.g. The Nuke fling pushing lemmings inside terrain at certain angles/velocities or some of the amusing Super Lemming glitches.

Offline exit

  • Posts: 197
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #2 on: December 18, 2021, 01:40:12 AM »
I've reverse engineered the air physics into neat c++ code. This physics certainly applies to explosions, jumpers, and cannons, and most likely applies to rollers, skiers, and lemmings flying off chains. The only cause of the different trajectories seems to be the initial velocities and accelerations the game assigns to a lemming. So far, I've only recorded these for the cannon, but it should be easy enough to find it for jumpers and shimmiers, or anything else with a set trajectory. I have some old notes for the code that calculates these initial values for each lemming after an explosion, but haven't yet put them into a nice, readable format.

I've attached the code, as well as the other main notes I've taken so far.

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #3 on: December 18, 2021, 01:21:41 PM »
Thanks. Interesting read so far. I created a fork to test your physics code. The attachment shows a comparison of the Lizard launchers. The objects stored in the style set the initial launcher velocity to x: -10, y: -5. I'm not sure if the initial acceleration values are the same across the board or if there is an acceleration table per skill, but I get somewhere close with initial acceleration of x: 3, y: 7. The screenshot shows the landing zone off by 2 pixels.

My hunch is that there are multiple acceleration tables as the arc at it's peak feels too sharp for launchers vs DOSBox. From testing I found that when hitting a wall, the remainder of the amount to add to the x position is reflected which causes the lemmings to splat at the same point after the third Lizard.

The main modification I made to your code was add collision detection and have it sub-step the x/y differences rather than just add it to the position for collision accuracy.

Looks like you might be onto a winner :)

Offline exit

  • Posts: 197
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #4 on: December 19, 2021, 02:42:59 AM »
The initialization of every trajectory appears to be handled by the same function. I've done the same as before, and rewritten it as c++ code. I was also able to do it for the function which handles explosion trajectories. I've attached both.
I still haven't looked at collisions, but I would suspect that it does only reflect the lemming's velocity and position.

I also took a look at a few of the constant trajectories to find their initial values, which I have attached. Steam and trampolines might not be correct, I'll have to test those more, but the others should be right.

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #5 on: December 19, 2021, 08:32:47 AM »
Thank you for confirming and your help. I will take another look :)


Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #6 on: December 19, 2021, 10:13:47 AM »
The Lizard launchers now match perfectly :)

Thanks again.

Out of curiosity, is this code from part of a bigger project you're working on? Or is it purely curiosity into the inner workings of Lemmings 2 physics?

Don't by any chance have any insight into the .gal file format found in the script sub directories do you? (On the off chance)

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #7 on: December 19, 2021, 10:49:40 AM »
Apologies. My mistake. I misread your initial values. If I initialise Lizard Launcher with ddx: 2 and ddy: 7 it works. If I initialise the other way around as written, the lemming falls way short. For initialisation is the lookup done on ddy or ddx?

Thanks.

Offline exit

  • Posts: 197
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #8 on: December 19, 2021, 01:23:54 PM »
Hmmm... that's strange. The lookup is done for ddY, but it's entirely possible I've overlooked something. Do the values for the cannon and jumper match?
Does the trajectory match the DOS trajectory perfectly with the values you found?

I'll take another look and see if I missed anything, but I won't be able to do this for about a week.

This is all coming purely out of curiosity about the game physics. I had a lot of notes on the last two functions, which made converting them much faster.

I don't know anything about the .gal files.

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #9 on: December 20, 2021, 01:15:48 AM »
I thought it matched at first, but then it only worked for the first of the three launchers. I've been trying varying permutations, but I either over or undershoot the target. Not sure I can see the wood for the trees anymore lol.

I attached the code I am using. I could be wrong or missing something.

The only real change I made was this line;
(Otherwise it causes lemming to oscillate on Y after its negated for array lookup when < 0)

lemming->y_pos = y_position + dY;

to...

lemming->y_pos = y_position + lemming->dY;

I already ruled out my sub-step logic as the results are the same when I simply add the differences directly to the position.

No worries if you don't get change to take a look. If I don't hear from you, hope you enjoy the holidays.

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #10 on: December 23, 2021, 12:51:31 PM »
I had a go at playing with the DOSBox Debugger MEMDUMP and Reko Decompiler. Thanks to your notes I was able to find the functions to compare with. The only difference was I needed to add 0x510 to all of the addresses. So I guess we are using different versions of Lemmings 2. From the looks of it, the negated variable used for the acceleration lookup is a temp var as I thought. So that fixes the oscillation issue. And the only other things are the order of operations for when it samples the y velocity before modifying it and it checks if > 7 rather than 8 for y velocity. I think it's all working now, but I will do some testing with the other objects that trigger the Flinger state.

This is the sanitised version of the disassembly for reference;

Code: [Select]

short accelArray[] = { 0, 0, 0, 1, 1, 2, 2, 3, 3, 8 };

typedef struct Lemming {
int16 posX; // 0x00 pos x
int16 posY; // 0x02 pos y
int16 fallDist; // 0x1E fallDist
int16 velX; // 0x22 vel x
int16 velY; // 0x24 vel y
int8 accX; // 0x26 acc x
int8 accY; // 0x27 acc y
} Lemming;

void fn0C00_C1B3(struct Lemming* lemming)
{
int16 xPos = lemming->posX;
int16 yPos = lemming->posY;
int16 xVel = lemming->velX;

if (xVel != 0)
{
if (xVel >= 0)
{
xPos += xVel;

if (xVel != 1)
{
lemming->accX--;

if (lemming->accX < 0)
{
--lemming->velX;
lemming->accX = 7;
}
}
}
else
{
xPos += xVel;

if (xVel != -1)
{
lemming->accX--;

if (lemming->accX < 0)
{
++lemming->velX;
lemming->accX = 7;
}
}
}
}

int16 yVel = lemming->velY;

if (yVel >= 0)
{
lemming->fallDist += yVel;
}
else
{
lemming->fallDist = 0;
}

lemming->accY--;

int16 newYPos = yPos + yVel;

if (lemming->accY < 0)
{
int16 yVel = yVel + 1;

if (yVel > 7)
{
yVel = 8;
}

lemming->velY = yVel;

int16 yVel2 = yVel;

if (yVel < 0)
{
yVel2 = -yVel;
}

lemming->accY = accelArray[yVel2];
}

lemming->posX = xPos;
lemming->posY = newYPos;
}

I will come back to you with my findings to make sure it all works.

If all is well, that just leaves figuring out the initial velocity and acceleration values for each Flinger object etc. which you have already given me a good head start on.

Again, thanks for all your help and notes :)
« Last Edit: December 23, 2021, 12:59:04 PM by ravenix83 »

Offline exit

  • Posts: 197
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #11 on: December 26, 2021, 05:50:22 PM »
Great!
I must not have been careful enough when converting the code to make a mistake like that. I double checked the explosion flinger initialization code and made a couple changes, which I've now attached. It should be all correct.

I'm happy I was able to help, and I'm willing to help with anything else if you'd like me to.

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #12 on: December 27, 2021, 11:28:31 AM »
Cheers. I will have a go at integrating the explosion physics later this week :)

If you are looking for something to problem solve, there is still Projectile/Jetpack/Fan/Super Lemming physics to figure out.

Many thanks for your time.

Offline exit

  • Posts: 197
    • View Profile
Re: Lemmings 2 Data Formats
« Reply #13 on: January 06, 2022, 03:08:05 AM »
I reversed the flinger code, including the general air collision checking process, both of which I've attached. The collision handling is quite interesting, and it's actually a bit more complicated than just reflecting velocities, with some edge cases for specific terrain formations. Let me know if you notice anything off. Hope this helps.

I also took a look at how the projectiles work. In general, trajectories are calculated the same way as they are for lemmings, including using the same table for y acceleration. Each of the standard projectiles (bazooka, mortar, thrower, spearer) have an x acceleration of 9. These projectiles all seem to be instantiated a few frames before the lemming's animation actually makes it look like they've been released, but I haven't really analyzed their initialization to know the specifics.

Offline exit

  • Posts: 197
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #14 on: March 17, 2022, 10:38:33 PM »
I completely reversed the SuperLemming code and behavior, by far the most complicated part of the game I've looked at so far. I even found a bug, where a SuperLem can crash if there is terrain to the left of the lemming during the top part of the "pullup" in the landing sequence, when it should be checking above the lemming.

SuperLem uses the same memory and data structure as projectiles, so the code uses some of the projectile subroutines. This means that the game technically has the capacity for 10 SuperLems in a level at once, it just doesn't let you assign more than one. I do think it would be a nice feature if L2Player let you assign as many as you wanted to. I wrote the data structure and projectile subroutines just for SuperLem but eventually they can be generalized to all of the projectiles.
One thing I would suggest for your implementation is to heavily utilize the lemming counter variable for the graphics. Although I didn't do any analysis of the graphics, it definitely seems like the game uses this variable to determine which sprite to draw.

I hope the code is clean and understandable, I tried to add a lot of comments to clarify what's going on, but if you have any questions feel free to ask. I also hope it's easy to integrate with the rest of your L2Player code, and I'd like to know if you have any suggestions for how I could improve this integrability for any future code.

As always, let me know how your testing goes or if you find anything that's incorrect. I'm happy to help handle any discrepancies or other issues that come up.

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #15 on: March 23, 2022, 07:04:42 PM »
Sorry for the late reply. I will take a look and let you know how the integration goes. There will be no skill, lemming or projectile hard limits as per the original game as they had to deal with tight memory constraints. It's why you could only select certain skill combinations in practice levels for example. L2Player will let you fill all of the skill slots with any combination for practice levels. Been busy IRL last month or so, but hoping to get back into the flow very soon and get some more skills implemented. As always, thanks for your efforts and help.

Offline Simon

  • Administrator
  • Posts: 3860
    • View Profile
    • Lix
Re: Lemmings 2 Physics Research
« Reply #16 on: March 24, 2022, 11:05:34 PM »
Excellent research by both of you! Wonderful level of precision and thoroughness. I've followed the thread in detail since the beginning. :laugh:

The projectiles have felt like they share code, e.g., all projectiles have strong air resistance. But I wouldn't have guessed that even the Superlem reuses projectile code. Hmm, it makes sense for aiming. I'm really looking forward to more such surprising theory, and of course to L2Player.

Yes, ditching the memory restrictions in practice mode is a good idea, even if you're aiming at 100 % bug-compatible physics. IIRC, the L2 blocker also fails on vertically-scrolling levels, that might be another candidate to allow in L2Player.

-- Simon

Offline Ste Woz Ere

  • Lemmings 2 fan
  • Posts: 73
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #17 on: March 25, 2022, 11:14:20 PM »
Another candidate I'd like to see retained is the ice physics - where the lemmings slowly slip & slide their way across. (every back & forth cycle sees them end up 1 pixel further forward, in the direction they were facing when they first went onto the ice)

I found this very useful for designing Polar levels with, as it lets you auto-contain the crowd for a fixed amount of time.
Tribes of Steel - a whole new Lemmings 2 game! (120-level pack)
Currently a WIP - all tribes are complete, testing and feedback is welcome!

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #18 on: March 28, 2022, 12:27:03 PM »
@Simon - It's definitely a fun research project with many interesting aspects :laugh: Blockers work on any level in L2Player currently. So I can tick that one off the list.
@Ste Woz Ere - It's a good one to maintain when it's relied on for timing. I've not fully investigated ice physics yet. But I will add it to my list.

I temporarily paused development on skills to implement state rewinding. I'm getting to a point where it would be very beneficial for debugging new skills as I add them. Anything to speed up the iteration loop.

It's looking promising so far. Binary serialisation is working as expected, with the state snapshots stored in a queue structure. Well, three queues. Seconds, tens of seconds and minutes. New snapshots are pushed into the seconds queue every second, then the snapshots are then popped/pushed automatically into the tens/minutes queues to consolidate and discard snapshots as necessary. This should hopefully simplify rewinding by either 1 second, 10 seconds or 1 minute at a time.

Offline namida

  • Administrator
  • Posts: 12398
    • View Profile
    • NeoLemmix Website
Re: Lemmings 2 Physics Research
« Reply #19 on: March 28, 2022, 06:21:37 PM »
Is serialisation necessary? In Loap (which I feel implements this much more tidily than NeoLemmix - it should be noted that Loap was designed from the start with this capability in mind, whereas NeoLemmix it was hacked in much much later), I store all game state data in an instance of a GameState class. To create save states, I simply create another GameState with the same contents (and similarly, reverse this to restore one). I haven't tested both approaches, but I feel like compared to this, serialisation would both have more overhead and be easier to have oversights as you add new features.
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 RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #20 on: March 29, 2022, 11:22:55 AM »
I agree storing clones of objects in another class is perfectly valid. The main motivation for binary serialisation was to have the option for fast serialisation to disk if needed. It's currently implemented with a base class which can be inherited from to override its Read/Write methods. I have a set of BinaryReader/BinaryWriter extensions which have support for my low levels types like Vector2, Rect etc.

As you say, it has the potential for more bugs this way. But necessary for storing to disk.

To be honest, my method feels over engineered as disk serialisation is not really needed for rewind states as it only needs to persist for the current level. I don't really even need it to persist between debug sessions. It could be nice as a "Quit and finish playing this level later" feature maybe.

Hmm, now I'm torn between binary serialisation and object cloning... :laugh:

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #21 on: April 16, 2022, 04:27:11 PM »
@exit - The Super Lemming implementation is coming along nicely. The counter you mentioned seems to be used for both general state timing and determining the frame to use. I have updated the sprite structures to handle animation segments based on an angle. There is now a single interface for determining which frame of an animation to use based on a direction. It supports an arbitrary number of frames with a starting angle offset and a min/max angle. This is to support various animations which have directional frames. The frame totals for these animations vary from 16-64 frames with varying start/end angles.

Super Lemming has 32 directional frames and these are used to lookup acceleration and collision offsets. The offset point appears to be the top of the lemmings head.

See attached test gif (Red dot is origin, pink dot is collision offset)

Next step is to finish flight and landing states :)

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #22 on: April 17, 2022, 03:41:00 AM »
A quick preview of Super Lemming in action. Just in the process of comparing to DOSBox for accuracy.

A wall collision and a water collision bug has been corrected from the DOS version.

Video Link: https://youtu.be/ED1RIVn7DpI

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #23 on: April 18, 2022, 06:42:00 PM »
Super Lemmings now working as expected. This leaves Jetpack and Projectiles to finish.

I took the opportunity to do some clean-up, refactor level object rendering, fix some trigger issues and implement triggered traps.

I attached some gifs of some of them working. (Clicking image starts the animation)

Offline exit

  • Posts: 197
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #24 on: April 20, 2022, 03:30:31 PM »
Looks great. I'm happy that you've been able to get the SuperLemming working so quickly.

I've started to look at the projectiles, and I'll give an update when I have a full analysis.

Offline RavenNine

  • Moderator
  • Posts: 58
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #25 on: April 20, 2022, 09:10:03 PM »
Great stuff! Looking forward to it :)

Offline Ron_Stard

  • Posts: 312
    • View Profile
Re: Lemmings 2 Physics Research
« Reply #26 on: April 21, 2022, 11:20:20 AM »
Thank you all for this enormous effort! Lemmings 2 has always been my favourite game of all Lemmings saga. The possibility of playing some day an updated port of this game is innefable! :thumbsup: