Pathfinding, lessons learned news - Driftmoon

By popular request, I will reveal you how we do pathfinding in Driftmoon. This might be interesting to you if you're making your own game and want to implement pathfinding, and also if you're making a Driftmoon mod. Pathfinding in Driftmoon has gone through a couple of iterations already, so I'll start at the beginning.

First of all, we use the A* search algorithm. That was pretty much the only thing that went right from the start. A* is easy to implement, and there are libraries available for it. All I needed to do was create some amount of location nodes, tell the algorithm where I want to go, and where I start, and that's it.

So how do we make the nodes? Driftmoon is a top-down game, so I figured we could make a grid. All of the examples I saw at the time were of grids. An automatically generated grid would be good, because modders would never have to worry about the pathfinding, it would just work. So I made a grid, and looped through all the points, and connected the ones which didn't have walls in between them. To make sure our AI could navigate small doors or cracks in dungeon walls, I had to make the grid pretty small. So I ended up with grids that amounted to about 10000*10000 points in them. You might spot the problem with that.

While A* is obviously a fast algorithm, it can't possibly cope with that amount of points in the graph. When my maps started getting bigger my AI churned about a minute looking for a new path. I had to reduce the amount of nodes in the pathfinding grid. So I tried it algorithmically. Make the grid sections bigger where there's nothing but open space, and smaller where there are gaps and doors. It worked, but it started taking minutes to create the grid when the map was saved in the editor. And I couldn't make the algorithm optimal, it still produced millions of nodes.

This is what I ended up with. The node painting tool. I realized that by using my brain for a few minutes I could come up with a few million times less pathfinding points than my algorithms did. You just click where you want the nodes to go. They are connected automatically, and the AI will look it's routes using those points. Now we're in the league of about 100-1000 points per map. Another way to do this would be to paint areas, and the AI could look for paths from one area to another. But I went with points because they are easier to paint by modders (and me).

After all that, the AI works like this: It knows where it is (here), and where it wants to go (eg. go talk to the player, or go kill the player). For both the start and the end points, it looks for a way to the nearest pathfinding nodes. And then it looks for the optimal path between those nodes. Here are some of the optimizations it uses: If it sees the end point straight away, it doesn't bother with pathfinding at all. If it sees a clear path to a pathfinding node one step ahead, it will skip any unnecessary pathfinding points. I've tuned the A* algorithm to prefer routes with no dynamic obstacles, but the AI goes through the obstacles like a bulldozer if it can't find an alternate route. From the above you probably reasoned, that a lot of the times the AI simply has to decide whether there is a clear path from A to B. If your making your own game, the most straight forward way to do that might be to use the raytracer in your physics library, but in Driftmoon, we're using our own spatial hash maps.

An important matter to realize is that inside dungeons, often there simply isn't a path from where you are to where you want to go. In this case, the A* algorithm hammers through the entire set of pathfinding nodes, and this is obviously the slowest possible case. We need the ability to quickly check if we ever could get from A to B, or is it completely impossible. This is done by marking each pathfinding node with an area number. If the area numbers are different between the start and the end nodes, that means they are on areas that are not accessible to each other. So now the nonexisting path case is the fastest one, we just check whether the area numbers match. I'm setting the area numbers simply by doing a flood fill for each node when we start the level.

Now I was left with a pretty snappy pathfinding, but as I added more monsters and townspeople, I started noticing that it was bogging down the framerate when the AI wanted to do pathfinding. The problem was that when the player moved, a lot of the monsters might decide to start looking for a new path at the same time. So I implemented a pathfinding queue with priority numbers. The monsters nearest to the player get their pathfinding done first, and monsters very far from the player might not get pathfinding at all, or might get it less than the others. And if the monster's pathfinding wasn't complete yet, it fakes it by just going on a direct path.

So that's how pathfinding in Driftmoon works. I've spent many months making it. My advice to people making their own games is this, skip pathfinding altogether. Make the monsters zombies, robots, or green slimes that don't need pathfinding, and you've saved yourself many weeks of development time!