Author Topic: Lemmings 2 Physics Research  (Read 9604 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.