NPCs can walk through other NPCs that are trying to move into an obstacle

[ohrrpgce-bugbot]

[sf#2034]

Consider two NPCs, A is trying to walk onto the tile occupied by B, and B is also trying to move to a third tile, but can't because it's blocked by something. If the engine processes A before B, then it doesn't know yet that B can't move, assumes that B will vacate its tile, and lets A walk onto it.

This bug was discussed at length, with various testcases and gifs, here: https://www.slimesalad.com/forum/viewtopic.php?t=7638

When an NPC is holding still, collision considers its actual position-- but when an NPC is trying to walk, then collision considers the NPC to be on the tile where the NPC is trying to move to.

For each NPC, we don't know whether it will move or not until after the same determination for all the other NPCs. So I think that we would need to do the NPC collision checking and movement using a depth-first search. However, there can also be loops, so something trickier is required. So this is a very difficult bug to fix.
I described a possible algorithm to resolve NPC movements, but I haven't confirmed it's correct. The consensus is that this bug may just be too hard to bother fixing. Noone has complained previously.

Note: this bug is distinct from another very similar NPCs-walking-through-each-other bug reported by sheamkennedy (which I'm fixing now). That bug concerns pushable NPCs: if you're pushing against a pushable NPC but it can't move, then if the "Simulate Pushable NPC obstruction bug" backcompat bitset is off, other NPCs will be able to walk through it. The bug is that that bit only fixes the case they're you're pushing the NPC against another NPC, not if you're pushing against a wall or zone.

From: @rversteegen
Reported version: 20171201 Etheldreme
Labels: collision detection, movement

[rversteegen]

Related to (or duplicate of) #330 "Pushed npcs are obstructionless"