Yeah, that's been around for a while. And it boils down to something we were kinda always iffy about, but nevertheless use: our priority_queue used there does not use strict weak ordering (don't worry if you don't know what that means). (
EDIT: Actually, I'm blaming the wrong thing here - it's more to do with the fact that priority_queues don't internally have a way of deciding ties between equal priorities... and since we don't give it one, we can't expect anything good from it.)
Essentially, a Stalwart works out what path to take as follows:
1) Starting at the square it stands on, it compares each square around it in turn with a particular priority: N, E, S, W, NE, SE, SW, NW.
2) From each of *those* squares, it checks the squares around them in the same priority. It never revisits squares that have already been defined though, and always takes the lowest scores (the amount of steps it took to reach that square).
3) The search ends when a monster is found or all reachable tiles are exhausted. Squares are checked in turn as the expansion happens, with priority given in the following way:
* Tiles that are closest to the Stalwart along the path have highest priority: so we work out all tiles that are 2 steps away before touching any that are 3 steps away.
* Tiles that we got via a certain direction from the previous tile have higher priority than other directions: again, we go over all tiles we went N to get to before checking those that we went E to get to, and so forth.
* If any ties exist after those two (and many *many* ties will), then we just rely on the ordering system to deal with it. However, instead of always picking the last or first tile to be found, we're at the mercy of the algorithm, and so there is *no* such predictable ordering system to break this tie. It relies completely on things like how many ties there are to break and how big the queue is that we're trying to sort. In essence: it's psuedo-random.
Here's the map of the room for the first four squares + goal around the Stalwart for both rooms, using - and | for cardinal and \/ for diagonal directions, and with the "
chosen path"
bolded:
Room 1:
#####/###
\\\\|/|//
\\\\|/|//
\\\\|//--
\\\\|///\
----S----
########\
#######
Room 2:
#####\###
\\|\|/|//
\\\\|/|//
-\\\|//--
\\\\|///\
----S----
#######\\
#######|\
Of course, it'll only follow that path for the *first* step, and then recalculate it again next turn, so that won't be the complete path it follows. But there's no way we can predict this.
===
And here's the kicker. This is the same algorithm that Slayer Wisps use. And Halph uses to find orbs. As crazy as this system is, it is *deeply* entrenched into the game. It will affect *every* room with either of these three elements that you can think of - it's not even like the Seep/Waterskipper pathmapping issue I brought up, which only comes into play semi-rarely.
This style of pathmapping is also the reason why Wisps and Stalwarts don't like walking directly alongside walls (and instead prefer staying one square away while they're following it)... and since that aspect has already been used as puzzle fodder....
That's all I can really say, I'm afraid. I've made an example of this sort of behaviour before, but this is a particularly simple and glaring example you've come up with, so thank you for that.
[Last edited by TFMurphy at 05-11-2008 04:42 PM]
