Pathfinding: Beyond A*

I am working on a navigation system for controlling parties of adventurers who will explore a dungeon, in search of the most treasure and honor with the least viscous beasties. To make life easier in a variety of ways, the navigation is broken down into two levels: room scale and dungeon scale. Having these operate separately limits the possible search space significantly, and makes it easier to have different large scale and small scale behavior patterns.

For room scale navigation, I used a pretty generic A* pathfinding, which worked great for these small grid-based rooms. It let me include various tile weight overlays as well, which gives a lot of room to easily make adventurers fear monsters, prefer paths, stay near friends, etc.

Dungeon scale navigation between different rooms could easily use A* as well; it’s a graph of connected rooms, which could get room weights based on distance as well as monsters present and room size. And I will likely have to make this eventually, as it works perfectly for the room scale navigation for monsters who know the dungeon layout. But, I just built an A* solver for room scale navigation and frankly, this seemed kind of boring.

So I got to thinking: adventurers rarely follow anything close to an optimal path, and don’t have any idea where they’re going. Why should my adventurers do any of that?

I ended up using a method called Ant Colony Optimization. Instead of calculating the correct solution, this algorithm uses successive attempts at exploring the search space, refining its solution each time. This has the nice quality of not giving adventurers any under the hood knowledge of how the dungeon is layed out before they explore it. This makes mazes and dead ends viable dungeon-design strategies.

The outline of the algorithm is as follows: When an adventurer walks into a room, they leave some mark on it. In the ant analogy this is pheromones, in this case it is an abstraction of adventurer detritus, from campfires to books to footprints and maybe pheromones, depending on the quality of the local sanitation.

When picking the next room to go to, the adventurer chooses randomly, but weights their choice by the cost of the room (something like size or monster count) and the amount of adventurer-pheromones in that room. Lower cost higher pheromone rooms are chosen more frequently.

In the event that an adventuring party finds treasure and survives their escape from the dungeon, their pheromone-trail will be slightly stronger than other paths, because they traversed it twice and were able to navigate the dungeon more quickly than their aimlessly-wandering colleagues. Thus, a new adventuring party is more likely to follow their trail, further reinforcing its strength, until all adventurers follow the well trod path to safe riches.

This has a number of advantages. Firstly, it’s dead simple and super performant to implement. There are no extra data structures needed to store a representation of the dungeon, and nobody needs to store a path in memory. Each adventurer makes simple choices as they go, and each door between room tracks just tracks its pheromone level.

Secondly, it gives adventurers much more interesting behavior and allows them to explore a shifting dungeon more naturally. They can intelligently react to player interference; Placing an unavoidable sea of spikes in the most common path through the dungeon might work in the short term, but if nobody return to reinforce the pheromone trail, a safer route will eventually be found. It also makes overall layout a more interesting choice; a single chain of difficult enemies will provoke very different behavior than a complex maze of smaller encounters.

I am considering beefing this system up somewhat, to allow adventurers to make more complex and well informed choices using a more complete picture of the dungeon. To do this, I’m thinking about using multiple kinds of pheromones. For example, some mark treasures, while others can mark dangerous monsters or traps or dead ends.

Right now, this is largely hypothetical, because the process of learning a dungeon and spreading that information among the adventurer community requires actual dungeon functionality, and that doesn’t quite exist yet. But, adventurers do now have the ability to wander aimlessly, and follow the aimless wandering of other adventurers.