Pathing in Much Dungeon

This post is about how we use pathing algorithms in Much Dungeon. We’ll be staying away from implementation details and focusing on application. There are plenty of articles out there that explain the algorithms much better than we can.

The two main algorithms we use are A* (wiki) and BFS (wiki). These are very common and our implementations aren’t anything unique.

A*

All classic “pathing” done by characters is calculated using A*. This finds the best path through the world from one tile to another. Initially, the “best” path was just the “shortest” path. However, as we added elements to the world like fire and lava, we needed smarter pathing.

Each of our non-character world elements (decorators) have flags tracking if they should always be avoided, be avoided only by npcs, or only be avoided if possible. This is in addition to flags tracking if the decorator can be walked or flown through. This makes the “best” path the shortest possible path that includes the least amount of avoid-if-possible tiles. This allows your player to walk around a fire instead of through it to get to the other side, but still have the option to walk through it if other routes are blocked.

We use a pluggable ‘control‘ object to change what tiles should be considered or ignored while building the path. This allows us to use the same pathing algorithm but end up with different paths for a character that can fly vs a character that can walk through walls. This is also how we can apply player vs npc pathing or conditionally check for various decorator flags.

BFS

While we don’t use BFS for actual path calculation, it is included because it’s similar (and packaged with our pathing code). Unlike A*, BFS is a search algorithm and not a pathing algorithm. It processes tiles in an expanding range from some source tile.

We use a similar pluggable control object to determine what tiles should be considered, but increase the restrictions based on what we’re searching for. This allows us to find all possible search criteria matches within a given tile range or to just find the first and closest match.

Worth noting, the same behavior could be obtained by simply iterating all decorators, items, or npcs within a chunk that we may be searching for. However, a BFS search from a source tile usually has to perform fewer checks and executes much faster.

Putting it Together

The most common pathing usage is fairly simple, find a path from a start tile to an end tile and avoid anything bad.

We also use pathing when spawning things that the player must be able to reach. Before an item or a portal is spawned, a path is calculated to make sure the tile is actually reachable by the player from their current position.

BFS searching comes in to play with events and some npc behavior. Npcs may want to find a specific decorator or tile nearby to move to instead of just marching towards the player. Similarly, some events want to find all nearby decorators or npcs of a certain type to run against.

#pathing #algorithm