Monster pathfinding is one of the more complex and potentially confusing things in DROD. Most people have a general idea of how brained monsters work, but ask about Citizens or Stalwarts and most will be confused. And how do Halph and Slayers fit into all of this? And what does Imperative Pathfinding even do? In this post, I'll be illuminating how exactly the various pathfinding algorithms of DROD are meant to work, and more importantly, how they actually work.
Each pathing type will a have a simple explanation, and more in depth explanation. I've also made a reference image for some of the complex stuff, as unicode diagrams only go so far.
Brained Monsters
Lorewise, Brains are the diabolical directors of the various hordes that fill the Beneath. Their whispers in the minds of monsters guide them towards their target, no matter where they are. The actual game logic is somewhat less glamorous. When a brain is present in the room and can detect the player, monsters will perform a "
Brain Directed Move"
instead of whatever stupid variation of "
charge straight at the target"
they would usually perform. Like all monsters, brains can always detect a visible player, but need be in 'smell range' to detect an invisible player. Brained monsters ignore all targets other than the player and decoys - monsters in range of a decoy will target it instead of making a brained move.
So what exactly is a brained move? To answer that, we need to understand what a
Brain Pathmap is, and how it is constructed. A Brain Pathmap functions by giving every tile in the room a score, based on its distance from the player. Tiles with lower scores are closer to the player, and tiles with sufficiently high scores don't have a path to the player. A room can have multiple Brain Pathmaps, depending on the movement capabilities of the monsters in the room. A pathmap for a roach might be terrible for a spider or Wraithwing, and will be completely useless for a Waterskipper. However, they are all created using the same algorithm.
In simple terms, a Brain Pathmap is built outwards from the player. The player's tile gets a score of zero. All open tiles adjacent to the player get a score of one. All open tiles adjacent to those tiles get a score of two. All open tiles adjacent to those tiles get a score of three. This repeats, giving a score to tiles reachable from the player, until no such tiles remain. Brained monsters pick the best move available to them, based on which tile has the lowest score.
A Brain Pathmap for a movement type is constructed using a breadth-first search, starting from the player's position. The origin square is given a score of zero, and then each adjacent tile is checked for an obstacle. Obstacle free tiles are given a score of one, and then added to queue. Once all adjacent tiles have been checked, the next tile in the queue, T, is processed in a similar way. The adjacent tiles to T are checked for obstacles, as before. Additionally, each obstacle free tile has its score checked. For an adjacent tile, T', if Score(T) + 1 <
Score(T'), we give T' a score of Score(T) + 1, and add T' to the queue. This process is repeated until the queue of tiles is empty, at which point all tiles with a path to the player using the given movement will have a score. Of course, even the relatively simpler brain pathing algorithm has an exception. Paths for seep and waterskippers will still consider floor tiles passable. However, moving across inappropriate tiles incurs a large score penalty, so paths going through appropriate terrain are preferred.
To make a brained move, a monster looks at the scores of the tile in the 3x3 area around it, and sorts them by score. For tiles with the same score, the direction of the move is used as a tie-breaker. Orthogonal moves have the highest priority, followed by staying on the monster's tile, followed by diagonal moves. If the best scoring move is blocked, lower scoring moves will be tried, unless the monster is a Wubba, Rock Golem or Gel Baby. These three monsters will not move if their preferred move is blocked, much like when unbrained. Finally, if a monster's best move is to stay still, it will ignore the Brain Pathmap and make an unbrained move.
Halph, Wisps, Citizens and Engineers
For the original version of DROD, the Brain Pathmap was good enough. There was only ever one target, Beethro, and monsters treating arrows as obstacles worked as an interesting game feature. But for the plucky orb striking Halph, and the unyielding 39th Slayer, the Brain Pathmap is not enough. A door could have many valid connecting orbs, and the Slayer would be much less impressive if he couldn't deal with arrows or orthosqaures. Citizens and Engineers face similar problems, since they often have multiple targets, and are meant to be intelligent.
And so, the need for smarter, multi-target pathfinding led to the creation of the worst function in DROD - FindOptimalPathTo(). In theory, it takes a starting tile, a set of goal tiles, and creates a
Smart Path to the nearest goal tile. And if there's only one nearest goal, it presents a believable illusion of something that works. But once there a many nearest targets, or you want to know the exact path the monster will take, things rapidly fall apart.
In simple terms, a Smart Path is built outwards from the starting tile, which is usually the monster's location. If the monster can move from the starting tile to an adjacent tile, that tile is connected to the starting tile. Once all adjacent tiles are connected, each of the connected tiles will connect to any adjacent unconnected tiles, provided the monster could make a move along the connection. The search ends once a goal tile is connected to the search tree. The Smart Path is then created by following the connections back to the starting position, adding each tile in the chain to the path. The monster can then move to the first tile in the path. Tiles closer to the start are always processed before tiles further from the starting position, so if a single closer goal exists, it will be chosen. If there are multiple closest goals, faults in the algorithm implementation mean it is effectively impossible to determine which target will be picked. Additionally, these faults make it equally impossible to determine the specific path that will be take to a goal.
Like Brain Pathmaps, Smart Paths are constructed using a breadth-first search. However, Smart Paths originate from individual entities, instead of being constructed from the player's position for multiple monsters. A Smart Path starts life as a tree of
PathNodes, with the root node being the monster's position. A PathNode is a bundle of information about a tile - it contains an x and y position, the length of the path to the node from the origin and a score. A PathNodes score is the sum of the node's current distance and the minimum distance to the nearest goal. Thus, a node's score represents the length of the shortest path from the origin to a goal that passes through the node. These PathNodes are stored in a priority queue, where nodes with lower scores go before nodes with higher scores.
To expand the Smart Tree, we taken the first node, N, in the queue. This node has an associated tile, T. Like in the Brain Pathmap's construction, we look at the tiles adjacent to T. If the monster can move from T to an adjacent tile, T', and if T' does not already have a node in the tree, we will create a PathNode for it. This new nodem N', is a child node of N. N' is given the co-ordinates of T', Dist(N') = Dist(N) + 1, and Score(N') is calculated by adding the minimum distance to the closest goal to T' to Dist(N'). N' is then added to the queue, and we repeat the process for the next node in the queue. The tree is expanded until a goal tile is added to the tree, or the queue is emptied. If a goal tile is found, the chain of path nodes leading to the goal is used to created the Smart Path. The monster will then make the first move along the path.
However, the algorithm as described so far has a minor issue - the actual path that is found is based on the order that the PathNodes are processed in. Consider the left hand graph in Figure 1, where the monster's tile has been processed, and its adjacent tiles are waiting in the queue.
As we can see, the monster's eight directions can each be expanded to search for goals. But since tiles are added to potential paths on a first-come-first-serve basis, there are multiple ways this situation could grow (see Figure 1 for a diagram).
The tree on the left is the result of processing the orthogonally adjacent nodes first, while the tree on the right is what we get if we process them following the internal direction ordering. In fact, processing orthogonal nodes first, followed by diagonal nodes is the order that was intended to be followed. However, an implementation error means this is not followed. Instead, chaos happens. But why?
PathNodes can be compared. Specifically, for any two path nodes, A and B, you can find if A <
B. A <
B evaluates to true if Score(A) <
= Score(B), and false otherwise. Now, there is a small issue with this. If Score(A) = Score(B), both A <
B and B <
A evaluate to true. However, the implementation of the priority queue that is used by the pathfinding algorithm considers A equal to B only when A <
B and B <
A both evaluate to false. This leads to equally scored nodes being rearranged whenever the queue is sorted. And the queue is sorted whenever a PathNode is added. This is why changing a single tile that is near a Smart Path can cause it to change - weather or not that node is added to the queue how many times the queue is shuffled, and thus changes the order that the nodes are expanded in.
This error is also the reason for why it's effectively impossible to know which target will be picked if two or more are equally close. The algorithm will stop as soon as it finds a target, but which target is found depends on the order of expansion. Consider Figure 2.
If we expand the red node, the goal on the left will be found. But if the blue node is expanded, the goal on the right will be found. And since we don't know which node is first in the queue, we can't know which goal will be found.
The moral of this story is simple: If an object asks for a strict weak ordering, give it one. It can't hold its end of the contract if you don't hold up yours. The other moral: Don't reuse the same broken algorithm you know is broken, even after fixing it.
Stalwarts and Soldiers
One of the many things that make Stalwarts a less than enjoyable element is that fact that they use Smart Paths. As covered above, Smart Paths are unpredictable, and would be somewhat so even without the implementation problem. However, Stalwarts and Soldiers have another thing to cover.
While Stalwarts and Soldiers use Smart Paths, they do so differently from other monsters. Stalwarts know that they have a sword. And they know that stabbing Beethro, Halph, explosives and other allies is a Bad Thing. So a Stalwart will consider any move that causes them to stab something they shouldn't an invalid move. Overall, this is a good thing - they'd be much more annoying if they killed the player (or each other) through sheer ignorance. However, this avoidance only uses the Stalwart's current direction. This means that if a Stalwart finds a target, with a valid path for their current direction, turning towards that target could invalidate the path. This could happen at any point along the path, meaning a Stalwart could end up running half way to a target, turning, running to another, turning again and deciding the first target was better.
All safety features fail when oremites are involved, as Stalwarts believe objects on oremites are safe to stab, and do not understand that moving while disarmed will re-orient them. This leads to questionable pathing decisions and likely contributes to Stalwart's reputation of being a bit dim.
Imperative Pathfinding
So, FindOptimalPathTo() is broken. This is an actual Computer Science fact. But there is another pathfinding algorithm in DROD - FindOptimalPath2(). This is used to create paths for NPCs using Imperative Pathfinding. For lack of a better term, I'll call these paths
Smarter Paths.
In simple terms, Smarter Paths are Smart Paths, but programmed correctly. Various implementation improvements mean that certain directions are preferred to others. The priority, from higher to lowest, is: N, E, S, W, NE, SE, SW, NW. Additionally, Smarter Paths slightly prefer to continue in the direction they are going rather than change direction. Otherwise, the same generally strategy is used for constructing both Smart and Smarter Paths.
Like Smart Paths, Smarter Paths start life as a tree. But Smarter Paths used a working PathNode - a
PathNode2, in fact. The single difference is that for two PathNode2s, C and D, C <
D if Score(C) <
Score(D). This is a strict weak ordering, and thus things do not horribly fall apart. But the story doesn't stop there!
As mentioned in the simple explanation, Smarter Paths have a directional preference. This is directly built into the algorithm, reducing the effect of a rogue equals sign. The eight directions are weighed according to the desired priority - a move North has a distance of one, while a move North-West has distance of 15. Additionally, Smarter Paths have a bonus complexity - a move that causes the NPC to 'change direction' costs one more than a move that does not. This slightly biases the path towards moving the same direction for as long as possible. Figure 3 shows the costs of the tiles in a 5x5 area around an NPC using Imperative Pathfinding, with N as the origin. It's worth noting that some nodes end up with the same score. In this case, the one with the lower scoring parent will be expanded first.
Figure four shows an NPC making a path around a wall. The left graph shows the cost of each node, while the right graph shows the score. We can see that the orange path will be taken, as it contains the node with the lowest score adjacent to the goal. The blue connected nodes end up being dead ends, as they are unable to expand due to the presence of other nodes.
Unfortunately, while FindOptimalPath2() makes Smarter Path generation much more consistent than Smart Path generation, it does so at a cost. FindOptimalPath2() is only able to generate a path to single, pre-specified target. It's mostly a victim of its own complexity - giving each direction a different cost means it can't find the nearest of many goals - a goal three spaces west will be ignored for one four spaces north.
Closing Remarks
Finding paths through graphs is a generally solved problem in Mathematics. But for all of DROD's mathematical elegance, it was brought into this world via Software Engineering, which is not elegant in the slightest. But understanding the strange inner workings of DROD can be useful, especially in the case of Imperative Pathfinding. It's completely deterministic, far less chaotic than Stalwart or Citizen pathing, yet still entirely unpredictable if you don't know how it's finding those paths.
If you have any questions, post them and I'll try to answer.
Reference Image
Click here to view the secret text
×
____________________________
[Insert witty comment here]
Qzvlkx?
[Last edited by hyperme at 06-01-2017 07:30 PM]
.