(note: this is how I made pathfinding fast, your mileage may vary)
A central component of my game is pathfinding. Since the only way to interact with your minions is by giving them commands, they have to figure out how to actually carry out those commands by themselves. A big part of this is finding out how to get to/from places, e.g. pathfinding. For instance, if you give them a command to build a wall, the typical process is this: locate an available resource, pathfind to it, pick it up, pathfind to the building site, and place the wall block. Leaving aside finding the resource, clearly the bottleneck of this action is pathfinding.
A star
The most basic pathfinding algorithm is essentially this:
- Start at a point on the graph
- If the current point is the goal, stop
- For each point adjacent to the current one, repeat steps 2 and 3.
Unfortunately, this won't really work. Consider pathfinding from A to D in the following 2x2 graph:
A B
C D
- Start at A
- The current point is not the goal, so continue
- Check adjacent point B 2. The current point is not the goal, so continue 3. Check adjacent point A 2. The current point is not the goal, so continue 3. Check adjacent point B 2. The current point is not the goal, so continue 3. Check adjacent point A ...
In order to avoid this infinite sequence, we have to keep track of which points we have already checked. Adding this to our basic algorithm, we have:
- Start at a point on the graph
- If the current point is the goal, stop
- For each point adjacent to the current one that has not been checked already, repeat steps 2 and 3.
This still isn't very good, mainly because it picks the next adjacent point to check arbitrarily. One way to improve this is to choose the next point that is closest to the goal. E.g., given the following 2x3 graph:
A B C
D E F
If F is the goal, then when picking adjacent nodes at B, C would be chosen over A since it is closer. Adding this to our algorithm, we esentially have what is known as the "A star" algorithm, and it is very popular for good reason. It is simple and performs reasonably well.
And so, in my first attempt at implementating a pathfinding system, I too used A star.
Growing pains
My naiive A star worked great for just a few entites, but querying a few hundred paths at the same time invariably caused the server to freeze. It was especially bad if you tried to pathfind into an unreachable location, an island for example. In this case, the entire landmass had to be searched, because A star must search every valid move to ensure there is no bridge or roundabout way to get to the island.
The first thing I did to improve my system was run it under callgrind, a popular performance analyzer. This showed me what I already knew: the majority of my games time was spent pathfinding. However, what I did not know was that the majority of time inside of pathfinding was spent manipulating what is known as the priority queue.
Remember when I said earlier that you always want to pick the next closest point to the goal to explore? The way this is usually accomplished is with a datastructure called a priority queue. It basically provides a very quick way to look up the minimum-valued item in a list. Everywhere I read about A star, people were always using these priority queues, and citing their theoretical performance, so when I implemented my algorithm, it wasn't even a question wether I would use one too. Additionally, I was not that far down the "make everything from scratch" path at the time, so instead of writing my own, I used a simple library, and never thought much more about it. Now that I was looking at my program's callgrind output though, I wondered if I could to better.
The first thing I did, as a sanity check, was replace the priority queue with a simple linear search. I was shocked. My algorithm more than doubled in performance. This isn't what they taught me in school!! Satisfied, I just left it at that.
Another improvement came from implementing a path-sharing system. Only one entity needed to pathfind all the way to the goal. Other entities could then pathfind to any point along that path and merge with it. The more shared paths the better, as this reduced duplicate computation.
In order to improve the worst-case performance induced by pathfinding to an invalid area, I could think of no good solution that did not require a total overhaul which I didn't want to do at the time. I could think of a bad solution however, which was to set a hard limit on the amount of area that the pathfinding was allowed to explore. This meant that the worst-case scenario was not so bad, but also meant that there was now a hidden pathfinding range, that would cause inexplicable failure from the point of view of the user. Nontheless, it solved the immediate problem so I decided to stick with it.
lots of paths
As my ideas for the game developed, I began to test the limits of my pathfinding system again. Instead of hundreds, I wanted thousands of entities to be able to be moving around without noticable drops in performance. Looking at my current system in a profiler, it was clear that the bottleneck was still pathfinding. It was time to read some papers and do an overhaul. After much trial and error, I finally settled on the technique described here.
The new system uses what is called heirarchical pathfinding. If you consider a road map of the United States, navigating between San Francisco and Miami using traditional A star involves looking at each individual road on the map and trying to find an exact path all the way between goal and destination. Heirarchical pathfinding, on the other hand, looks at things on multiple levels. First, say at the state level, it makes a plan of which states to go through in order to get to the destination. Next, as you get to each state, you use good old A star to find your route inside of the state. In this way pathfinding is broken into two levels, and a lot of effort is saved. Especially if you have to change the path when you are half-way down it, you don't need to throw away as much work.
There are numerous other techniques I have used as well, like caching of high level paths, using local connectivity graphs to instantly determine if a path is possible between two points, and taking advantage offline computation wherever possible. Using all of these techniques I was able to get smooth performance with around 10,000 entities. We'll see if that is good enough!
The source for my implementation can be found here:
git.mochiro.moe/crts/tree/shared/pathfind
With a simple test program here: