[FIXED] [BUG] [PLAYER] Builder passes through flamethrower

[mobius]

more testing is needed to see the details of this but this video shows clearly what happened:
The builder passes through the trigger area unscathed while other walking lemmings die.

--this video is an mp4, let me know if you can't view it/need a different format.

https://dl.dropboxusercontent.com/u/72760678/fire%20glitch.mp4

[namida]

It's hard to tell with a video rather than a level + replay, but I have seen this before too, just never really looked into it.

At a glance, what I would guess is happening is that - the builder, when he moves, moves forward 2 pixels and up 1; during this there is no trigger check (there is before and after). The walker, on the other hand, would move only forward 1 and up 1 to step onto the new step. So it is possible to have a situation where the builder's movement by 2 pixels bypasses the trigger area, but a walker gets killed. I would think the same thing can probably happen with a miner too.

Even if there was a trigger check during the movement, this situation could still theoretically arise depending on the order of movement. However, if it followed the same pattern a walker would - up 1, right 1, trigger check, right 1, trigger check - then it should solve this issue. I'm not entirely sure how well the code currently would handle trigger checks mid-step. At the moment, Nepster is working on tidying up much of the physics code; once he's done with this (or perhaps simply when he works on the builder, if he's also willing to address bug fixing), this could be addressed.

[ccexplore]

Yeah, namida had the root cause exactly correct.  This quirk has actually been exploited in multiple challenge solutions of mine for the official levels.  For example I think the current min-skill solution to Mayhem 30 had a miner on the left side create a path where walkers on the path can still exit, but the miner himself will skip over the exit trigger and continue mining.  And some challenge variation for Tricky 21 (Feel the Heat) has a setup (with the use of steel glitches to remove enough steel in the way) such that you basically fall through the flamethrower without triggering it, due to the slightly unusual way the game handles the walker->faller transition (a lemming ends up moving down 4 pixels in that single frame, and the flamethrower's trigger area is only 4 pixels tall).

If you want to fix this class of exploits, you will probably have to find all the places in the current physics where you can move more than one pixel within a single frame, and add extra trigger checks like namida suggested.

[namida]

In this case, perhaps the best approach is to avoid manipulating LemX and LemY directly, but rather have some kind of Move function which takes relative coordinates (perhaps also taking into account direction at the same time), and perhaps in case there's a situation where we do want to bypass trigger checking, have a parameter to do so (function MoveLemming(L: TLemming; Dx, Dy: Integer; IgnoreTriggers: Boolean = false): Boolean, with the return value being whether or not any trigger area that requires ceasing further action was encountered). With that being said, there's still somewhat of a question of what order movements should be handled in - unless it's limited to moving one pixel at a time, and is called multiple times in case of extra movement needed, at which point the function that calls it can take responsibility for dividing the movement up into smaller, one-pixel-at-a-time movements. I would think this should probably also support diagonal movements. Exactly how to break up movements should be obvious in some cases (eg: for the builder, it should be (1, -1) and (1, 0)), but in other cases not so obvious (eg. a walker becoming a jumper).

[Simon]

Intermediate checks are honorful. Yet they take time to implement, and make for subtle bugs. They touch the heart of all mechanics.

The NL code does (move ahead, check for stuff here, if stuff: move back). This is equivalent to (check for stuff ahead, if no stuff there: move there), but will not be equivalent anymore with intermediate checks.

-- Simon

[namida]

The NL code does (move ahead, check for stuff here, if stuff: move back). This is equivalent to (check for stuff ahead, if no stuff there: move there), but will not be equivalent anymore with intermediate checks.

I believe Nepster's changed it to the former now. But if not - this is precisely where the IgnoreTriggers parameter would come in handy (they'd be caught on a general per-frame check anyway in case the move back does not occur).

[Nepster]

Some random comments (lower ones rather off-topic):
1) Apart from the builder and miner, this happens as well for the platformer. This is however not as prone to abusement, because it checks
  xoxxoxxoxxox
(where x = check, o = no-check). So unless we get trigger areas of width 1, platformers will always find the trigger areas. So the only problem is when different trigger areas overlap and the wrong one is chosen due to this behavior.
Regarding the faller I suspect that it is checked (apart from updrafts) only at the final position too, though I would have to look at the code to actually verify this. So we essentially hope that there will never be a trigger area with height at most 3 .

2) Regarding Introducing subtle bugs: Who volunteers to make lots of test maps for the various skills and positions of traps?

3) Regarding a MoveLem function: I think, it would actually be better to call the CheckObjectsTrigger+DoNecessaryObjectActions (or whatever it is called now) directly from the MoveLem function. Ceasing movement on encoutering an object trigger might not be wanted depending on the type of the trigger area (e.g. updrafts, buttons, already triggered traps, ...). So we would more or less end up doubling most of the code for object actions.

4) I haven't yet touched the HandleBuilding code (though maybe I already fixed the indentations).

5) The original code was "move - check - move - check - ...". If the implementation had been something like

Code Select Expand


MoveLem
If TerrainCheck1 Then TurnLem
MoveLem
If TerrainCheck1 Then TurnLem

this would have been fine. However the code rather is somewhat along the lines of

Code Select Expand


MoveLem
If TerrainCheck1 Then (TurnLem + MoveLemBack)
MoveLem
// sometimes position of TerrainCheck2 depends on previous TerrainCheck1
If TerrainCheck2 Then TurnLem

which turned it into a very big chore to keep track of all the possible lemming positions and the checks made (especially when this was nested ). Moreover it had the risk of subtle bugs when changing the TerrainCheck2 and forgetting all the stuff done previously.
So for the basher code I changed it to:

Code Select Expand


Determine final position of Lemming
Move Lemming, once one knows the final position


[Nepster]

I started thinking about where the intermediate trigger checks should be placed. And the more I thought about it, the more complicated the rules got...

Rule 1: If the lemming moves only horizontally or only vertically, the pixels in the middle are checked.
Hopefully no explanation needed for this rule.

Rule 2: Whenever possible, the pixels checked should not depend whether a lemming moves over the terrain from the right or from the left.
This certainly cannot be satisfied for walls higher than 7 pixels, because climbers move inside the terrain, while fallers move outside. But otherwise we should strive for rule 2 to hold.

Rule 3: A skill-using lemming should check for the same pixels as a walking lemming coming after him.
This is much more restrictive than one would think - see the next rule.

Rule 4: A walker moving one pixel horizontally and one pixel upwards, should have an additional check at (LemX + LemDx, LemY), i.e. after moving one pixel horizontally and none upwards.
Why this? Because builders add terrain pixels at their current position! So if (according to Rule 3) a lemming walking up a builder stair should have the same checks as the builder, one has to check at (LemX + LemDx, LemY), instead of (LemX, LemY - 1).

Rule 5: A walker moving one pixel horizontally and one pixel down, should have an additional check at (LemX, LemY + 1), i.e. after moving just one pixel down.
This follows from applying rule 2 to the movement in rule 4.

Rule 6: Builders should check at (LemX, LemY - 1), (LemX + LemDx, LemY - 1) and (LemX + LemDx, LemY - 1), i.e. move up and then twice a pixel horizontally.
This follows from rule 3, because walkers walking on the final stair have these checks.

Rule 7: Miners should check at (LemX, LemY + 1), (LemX + LemDx, LemY + 1) and (LemX + LemDx, LemY + 1), i.e. move down and then twice a pixel horizontally.
This follows from rule 3, because walkers walking in the final tunnel have these checks.

Rule 8: Bashers should use the same rules as walkers when having a vertical component in their movement.
This again follows from rule 3.

Rule 9: If a builder or miner moved only part of the way before turning around, he should follow the path specified in rule 6 respectively rule 7 as long as possible.
Again implied by rule 3.

From here on the rules allow for a bit of flexibility:

Rule 10: A walker moving one pixel horizontally and two pixel upwards, should have additional checks at (LemX + LemDx, LemY) and (LemX + LemDx, LemY - 1), i.e. first move one pixel horizontally and then twice one pixel upwards.
Reason: Similarity to rule 4. Moreover a climber will move vertically up inside the wall, so it makes sense to finish the movement here with the vertical part.

Rule 11: A walker moving one pixel horizontally and two or three pixel down, should have additional checks at (LemX + LemDx, LemY) and (LemX + LemDx, LemY + 1) (and (LemX + LemDx, LemY + 2) if applicable), i.e. first move one pixel horizontally and then twice or three times one pixel downwards. Note that such a lemming will never transition into a faller.
Reason: Moving two pixels down should mirror the situation of rule 10 (by rule 2). Moving three pixels down is just an extension of the rule for two pixels.

Rule 12: A lemming that ends up as a faller, should first do all horizontal movements and then the vertical movements.
Reason: On a long drop, this feels to be the most natural path for a lemming to take.
Problem: If one shortens a drop from 4 to 3 pixels, the lemming path changes. So the lemmings may now reach a new trigger area or a save from a previously reached trigger area, depending on its position.

Exception to Rule 12: If the newly falling lemming was a miner previously, he should first move down one pixel, then do all the horizontal movements and then down one pixel again.
Reason: This is the closest one gets to satisfy rule 3 in this situation. Unless rule 11 is changed, the miner may reach pixels not lying in the path of walking lemmings (e.g. if moving two pixels down and two pixels horizontally), so rule 3 cannot be satisfied completely.

Rule 13: Swimmers and gliders don't have hard restriction, so they should move in some way that is conveniently to code.

All skills not mentioned here, should be caught by rule 1.

Are there any possible diagonal movements that I forgot? Any logical inconsistencies? And most importantly: Any simplifications?

PS: Contrary to what I wrote in my previous post, calling the trigger area check already in MoveLem seems not a good idea with the current code structure as it would likely mess with the order in which things are done.