[NO-FIX] [BUG] [LOW PRIORITY] Order of lemmings can have impact on results

[namida]

Bitbucket: https://bitbucket.org/namida42/neolemmixplayer/issues/73/seemingly-identical-lemmings-can-be-split

Suppose we have two identical lemmings - same action, same permanent skills, same position, even same animation frame. This could be achieved by placing two pre-placed lemmings in the same spot; unless one is given a skill that the other isn't, or encounters an object that only affects one lemming at a time, these two lemmings will be identical at all times. Or, so you'd expect.

But let's suppose these lemmings aren't just placed two in a row like this. Suppose that you place the first one, place a second lemming somewhere else, then place a third one in exactly the same position as the first. So we now have lemming 1 and 3 (the two "identical" lemmings), and lemming 2 (the odd one out).

Can you seperate lemming 1 and 3 without making use of a trap / teleporter / etc or assigning any skill to either of them?

You probably shouldn't be able to. But in fact, you can. If lemming 2 uses a constructive or destructive skill, and lemmings 1 and 3 are in the right position at the right time, they may end up seperated.

Why does this happen? To help illustrate this, I've attached a sample level. The solution is extremely obvious - having lemming 2 build right at the edge.

The interesting part here is not the level itself, but the behaviour you'll see during it. Why does this happen?

Explanation

We only need to look at the frame where the split happens.

NL handles the lemmings one at a time. So, the following occurs:

1. Lemming 1 checks for terrain in front of him. He sees something to stand on, but nothing to step up onto, so he steps forward.
2. Lemming 2 is on the frame at which he places the next builder brick. So, at this point, the brick is placed.
3. Lemming 3 performs the same check as Lemming 1. However, he's seeing different terrain because of the brick just placed by Lemming 2; there is something to step up onto, so he steps up.

This would be almost unnoticable; in many situations, Lemming 1 would rejoin with Lemming 3 on the next frame. However, in this case, it is visible because of what happens on the following frame - Lemming 1, currently one pixel lower than Lemming 3, has nothing in front of him to stand on, so he begins falling. Lemming 3 on the other hand does have something to stand on, so continues walking.

This will probably be quite tricky to fix, so is much more of a long-term thing.

[mobius]

very nerdy and fun stuff

I'll say what I've said before; even if this sort of thing would matter in the long run; I don't take much liking to a level that would rely on such pedantic behavior.

Btw, another great title; Schrodinger's Lemming. Also great title by Simon; Wheel of Misfortune

[namida]

I'll say what I've said before; even if this sort of thing would matter in the long run; I don't take much liking to a level that would rely on such pedantic behavior.

I absolutely would advise against making levels that rely on it, especially since the intention is to fix it eventually. It's just low priority at this stage, because (a) you're generally going to need to go out of your way to set up such a situation, it isn't a common occurance, and (b) it's probably going to be a major pain in the ass to fix.

The level in the original post was specifically made to illustrate the issue.

[Simon]

it isn't a common occurance

I expect several replays to depend on the ordering.

In basher or miner tunnels, the crowd bumps against the tunnel's tip. Early lems turn at the tip, then the basher performs, then late lems have more space to walk.

Digger tunnels during production are more resilient. Early crowd lowering by 1 pixel has the same outcome as late lowering. But we rely on ordering while the pit becomes too deep to walk out. And when breaking through the bottom, we give a head start to the late-updating crowd.

-- Simon

[namida]

Hm, yes, good point.

In that case, perhaps it is best to try and fix this at the same time as the other physics fixes. I wonder if simply caching changes to the physics map and only applying them after all lemmings have updated is sufficient...

[ccexplore]

It's often quite tricky to make game physics truly and completely order independent, not just in terms of implementation but also conceptually in some cases.  Here's a simple example illustrating the sort of thing you can end up dealing with:  two lemmings opposite facing directions walking towards each other, simultaneously hitting a triggered trap (that normally only kills one lemming upon being triggered) as they meet.  Order independence will force one of the following options:

1) Kill both lemmings (or more generally, at least one left-facing lemming and one right-facing lemming will be killed), even though that's not normally how the trap is meant to work.  It's interesting that this is unlike the case where multiple lemmings are compressed to the same position facing the same direction--you also have to pick one lemming to kill there, but if the physics is truly and completely order independent, it would not matter to future evolution of the game state which lemming the trap picks.  But here, since they are facing opposite directions, clearly the choice of kill will affect how the game state evolves going forward.

2) Purposely introduce a symmetry-breaking rule.  For example you can arbitrarily decide that left-facing lemmings are always chosen over right-facing ones.  It is a little unnatural and arbitrary, but it is necessary to avoid something like #1 above.  You are basically replacing using order as the symmetry breaker with some other criteria that is independent to order.

[Nepster]

To add a few more points to ccexplore's list:

3) Let two lemmings facing the same direction hit a trap together. One is a glider and the other one is a floater. Which one gets killed?

4) If you cache changes to the physics map, in which order do they get applied? First all terrain removals, then all terrain additions? Or the other way around?

5) All levels relying on nuking will no longer work: The nuke must start all lemmings at the same time, because we cannot use the lemming order to determine the nuking order. So all lemmings will die during one frame and nuking finally becomes totally useless. (Of course this may be seen as a positive side-effect...)

Currently I see only lots of new arbitrary rules, lots of broken replays and only a very minor advantages in very special cases.

[namida]

Hm, yes, there's a lot of great points here. Maybe it really is best to simply keep things as they are, while discouraging levels that rely on such behaviours.