L1 update order & walker physics

[Simon]

Very nice. I want to move trigger areas. Imagine my jam glass here is a trigger area, and I will move the jam onto the bun. -- geoo

Hey all!

This is an essay about the L1 update order and walker physics. Part of the information is from ccexplore's emails to EricLang, other info is from my own experimentation.

We will begin with the main update loop. Each logic update, all lemmings perform their activity. (activity = action = currently performed skill) One important subtlety is the order in which the activities are performed. We shall number the lemmings with 0, 1, 2, ... in the order they spawn from the hatch. In a logic update, lemming 0 is updated first, then lemming 1, then lemming 2, and so on. Performing an activity may write or erase terrain pixels immediately. If lemming n changes the terrain during his update, lemming m will use the updated terrain if m > n, but will have already been updated based on the previous terrain if m < n.

http://asdfasdf.ethz.ch/~simon/etc/l1updatedigger0.png" alt="" class="bbc_img" /> http://asdfasdf.ethz.ch/~simon/etc/l1updatedigger1.png" alt="" class="bbc_img" />

We shall demonstrate this effect with a peaceful scene from Fun 1 (Just Dig). In the first slide above, lemming 0 is the digger, and lemming 1 is a walker inside the same pit. The digger has just taken out a row of pixels. Since the walker was updated after the digger, he has already moved down to the lower ground in the same frame. It's the other way around in the second slide above, where lemming 0 is the walker, and lemming 1 is the digger. Here, the walker appears to float for a single frame. He had already been updated when the digger took out the terrain, and will move down to the lower row in the next frame.

If you try to replicate these slides in Lemmix, you will note that the terrain image takes an additional frame to update there, but the lemmings images and (most importantly) the physics are the same as in DOS L1. This means that the digger's row of removed pixels remains visible for one frame after it's gone, and in the first slide above, both the digger and the walker would appear to stand inside the floor.

The lemmings are drawn onto the screen in the same order they're updated. Lemming 0 is drawn first, then 1, then 2, and so on, with later drawn lemmings overwriting the earlier ones on the screen.


Our next topic is the walker.

I will use the term "effective coordinate" to mean the position of a lemming inside the level -- more exactly, the coordinates at which the game considers a lemming to be. The effective coordinate is inside the floor, directly below the foot of a lemming. To determine its horizontal position, you probably have to learn it for each skill.

For a right-facing walker, it's always under the lemming's back, i.e. one pixel to the left of the two stacked white pixels of the head. For a left-facing walker, it's always under the lemming's belly, i.e. directly under the two stacked white head pixels. See this image for examples of effective coordinates, marked with crosses:

http://asdfasdf.ethz.ch/~simon/etc/l1effectivecoordinate.png" alt="" class="bbc_img" />

This assymetry is caused by the walker sprite. The right-facing walker is offset towards the right. If you watch a right-facing faller turning into a walker, the lemming's body seems to advance ahead immediately by one pixel on landing. If you watch a left-facing faller turn into a walker, it doesn't advance.

The faller and splatter are some of the few sprites which look symmetrical in relation to the effective coordinate. Actually, most right-facing sprites are offset horizontally like the walker sprite. The builder and terrain remover masks have also been fit to this behavior. This is the reason why you can stretch (milk) successive bridges further when going towards the right.

When a walker is updated, it does in this order:

0. Move ahead horizontally by one pixel, no matter how the terrain looks like.
1. Check the new effective coordinate for solidness, along with pixels exactly above and below it.
2. Move vertically and/or turn/climb/ascend/fall depending on the results (and maybe additional checks).

None of these checks are about pixels to the side of the updated effective coordinate. Thus, lemmings will actually move into walls. I call a lemming to be inside a wall when the pixel(s) above the effective coordinate are solid. The details of turning around are as follows. Imagine a perfectly even landscape without humps, but with one straight vertical wall. Walkers approaching this wall will continue forward until they are inside. On the update during which they move into the wall, they turn, but don't move out of the wall yet. They'll do that only on the next frame.

http://asdfasdf.ethz.ch/~simon/etc/l1lockupyourphysics.png" alt="" class="bbc_img" />

The above image demonstrates this behavior. This scene is taken from Fun 30, Lock up your Lemmings. There is a one-pixel gap between the walls. A walker in this gap takes 4 frames to complete an oscillation cycle in there. Take the visible frame (facing left, inside the wall) to be frame 0. On the upcoming frame 1, he'll be in the free space, facing left. On frame 2, he'll be inside the left wall, facing right. On frame 3, he'll be in the free space, facing right. Frame 4 is like frame 0.

Instead of turning when inside a wall, they can also ascend (Lemmix calls this jumping), move down, start to fall, or climb. A climber will not move horizontally when starting to climb, so it'll actually climb with the effective coordinate inside the wall. If you assign exploder to a climber, it won't fall during oh-noing, because it is standing on a solid pixel inside the wall.

You might have noted that a walker will always walk ahead horizontally first upon getting updated, no matter what his surroundings are. There's a solution of Crazy 1 (Quote: That's a good level) by ccexplore which takes advantage of this. The only skills used are 1 blocker and 1 exploder. Block with the first lemming under the hatch. Adjust the rate to cluster everyone into the same place, except the last lemming. Explode that lemming to pave the way. This must be done with absolute pixel precision. http://www.lemmingsforums.com/index.php?topic=181.msg11877#msg11877" class="bbc_link" target="_blank">Here's ccexplore's replay of Crazy 1, and here are screenshots of it:

http://asdfasdf.ethz.ch/~simon/etc/l1crazy1physics.png" alt="" class="bbc_img" />

The lower part of the image shows the very first frame featuring the bomb crater. The exploder had been the last lemming, so the walkers have all been updated before the crater has been generated. Thus, they're still walkers. Their effective coordinate is shown by the square. They haven't turned, since they still haven't reached the horizontal position where the wall was.

When the next update happens, their effective coordinate moves ahead unconditionally (shown by the crooked arrow that starts off towards the right), and they immediately realize they have no floor, so they start to fall in the same update.

Thanks for your attention! Corrections are welcome, as always.

-- Simon

[ccexplore]

Nice write-up! http://www.lemmingsforums.com/Smileys/lemmings/cool.gif" alt="8)" title="Cool" class="smiley" />  Now I'm curious as to the similarities and differences between Lemming's physics vs Lix's, with regards to what you've discussed above.

[Simon]

When I wrote the essay, I made a joke in IRC about how the only reply would be by ccexplore, and it'd be "Well, of course it's like this. How's the weather btw?" http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" />

The Lix behavior is similar, but differs in many details since I wrote it without knowledge of the exact Lemmings mechanics.

• All workers of all players are updated first, then all walkers/similar more neutral skills. The idea was to remedy the 1-frame floating walkers. The game also feels better this way, it's easier to predict what will happen in pixel precise situations. It also allows to spam builders into a walking crowd and save everyone.
  
• The walker checks are still move ahead, then check for floor/wall afterwards. This was made due to natural instinct. Even though Lemmings turns out to work similarly, I still wondered why the Crazy 1 replay worked. http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />
  
• The lix, just as a lemming, will appear to just turn and not move when walking into a wall. This is actually done by moving it back out of the wall immediately -- instead of assymetrical sprites in relation to the effective coordinate.
  
• The game is twice the resolution of Lemmings. Almost every skill will only check for 2x1-blocks (wide pixels) for physics, and considers a wide pixel solid if at least one is non-black.
  
• Physics details will sometimes get changed deliberately in favor of how the game looks and feels.
  
• The effective coordinate is inside the foot, not under the foot, but this is a technical detail.
  

-- Simon