Announcement: Be excellent to each other.


Caravel Forum : Caravel Boards : General : A Detailed Guide to DROD Pathfinding (Or: The Forbidden Truth about Stalwarts and Citizens)
New Topic New Poll Post Reply
Poster Message
hyperme
Level: Smiter
Avatar
Rank Points: 451
Registered: 06-23-2006
IP: Logged

File: pathmapreference.png (9.9 KB)
Downloaded 291 times.
License: Public Domain
icon A Detailed Guide to DROD Pathfinding (+9)  
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]
06-01-2017 at 07:29 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
ErikH2000
Level: Legendary Smitemaster
Avatar
Rank Points: 2161
Registered: 02-04-2003
IP: Logged
icon Re: A Detailed Guide to DROD Pathfinding (+2)  
This a wonderful write-up--really well-considered.

Historical note--I wrote the brain pathmap in the 90s, and it was heavily optimized to work fast enough with hardware of the time. People were telling me "just use A*", but A* and other pathfinding algorithms were designed to calculate paths for just one set of endpoints at a time. If the code did that for moving a hundred monsters in a room, this would create multi-second delays each time you moved Beethro. Clearly unacceptable!

One night, it hit me that I could just calc all the paths to Beethro at once. I was so happy when that clicked.

Thanks for getting deep into the code and writing such a nice description.

-Erik

____________________________
The Machine Court podcast - Scifi comedy about the horrible and ridiculous future. http://seespacelabs.com/machine-court/
06-01-2017 at 10:39 PM
View Profile Send Email to User Show all user's posts This architect's holds Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 2322
Registered: 12-28-2004
IP: Logged
icon Re: A Detailed Guide to DROD Pathfinding (+1)  
quote:
ErikH2000 wrote:
One night, it hit me that I could just calc all the paths to Beethro at once. I was so happy when that clicked.

I remember the first time I was implementing a pathfinding algorithm by myself. When I finally figured out/understood that you can just check all the tiles from around the player and go outwards numbering tiles by the number of moves it takes to get to them.

But then when I had this all well and working I was like "wait a second, all the tiles around the player are #1, where do I move, it doesn't work!".

I admit I don't remember if I figured out the answer myself or someone helped me, but boy, back in the day pathfinding felt like such a complex thing and now I could do it with my eyes closed :).

____________________________
I am a skelliopath.
06-01-2017 at 11:43 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
ErikH2000
Level: Legendary Smitemaster
Avatar
Rank Points: 2161
Registered: 02-04-2003
IP: Logged
icon Re: A Detailed Guide to DROD Pathfinding (+1)  
quote:
skell wrote:
back in the day pathfinding felt like such a complex thing and now I could do it with my eyes closed :).

Yeah, similarly, I got into it at a time when a lot of data structures and algorithms people used were a little new to me. It seemed complicated at the time to me too.

But the optimization truly was laborious. I considered adding assembly code in to DROD a few times, and had to do ugly stuff like unrolling loops. I'm glad that level of optimization is seldom needed in programming now, since it is hard work, and almost always a tradeoff with readability/maintainability.

-Erik

____________________________
The Machine Court podcast - Scifi comedy about the horrible and ridiculous future. http://seespacelabs.com/machine-court/
06-02-2017 at 12:06 AM
View Profile Send Email to User Show all user's posts This architect's holds Quote Reply
TFMurphy
Level: Smitemaster
Rank Points: 3021
Registered: 06-11-2007
IP: Logged
icon Re: A Detailed Guide to DROD Pathfinding (+2)  
quote:
hyperme wrote:
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.
You've come to the wrong conclusion here, as you've neglected a rather critical part of FindOptimalPath2.

By the algorithm you've listed, it would appear that a route that goes (N, N, N, E) => (1+1+1+4) is better than a route that goes (NE, NE, NW) => (9+9+16). This is not the case.

If you look closer at the STEP_INC constant that the FindOptimalPath2 function creates, you should instead find that the function has two more important priorities: the number of obstacles the path goes through (unless the Open Only Pathfinding imperative is used), and the number of tiles the path traverses. A 3-tile path will always beat a 4-tile path (assuming no obstacles are traversed), no matter what directions are used.

(The obstacle consideration also shows that a visited node can be overwritten by a yet unexpanded node -- this is particularly critical for Arrow Mazes where we do not yet know if there is an open path through the maze, and if there is not, which "alternative" path chosen goes through the least number of obstacles.)


EDIT: Oh, and if you're doing a full document on Pathmapping, you may want to be a bit more thorough on the differences that Seep and Waterskippers have from normal enemies. Brained pathmapping through obstacles is not as simple as it first appears.

[Last edited by TFMurphy at 06-02-2017 05:05 AM]
06-02-2017 at 02:29 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : Caravel Boards : General : A Detailed Guide to DROD Pathfinding (Or: The Forbidden Truth about Stalwarts and Citizens)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.