Pathfinding
Pathfinding seems simple. Find the shortest, or a least a good path from point A to point B. As humans we do this all the time. We do it unthinking while driving in the car, walking through a city, or looking at a map of roads. Making it work in a game is not so easy.[1]
Pathfinding is the one system in the game that I am constantly fixing and making better. I’ll think I’ve gotten it right, and two months later the game grinds to single digit frame rates because the pathfinder is working overtime, or an AI will stand dumbly in the forest and freeze to death.
The core of the pathfinding system is A*. It’s fairly easy to implement and works well. When a path exists from point A to point B, A* finds it fast. When the path doesn’t exist A* searches a huge section of the map, only to fail. Because my maps are large, even an optimized implementation can’t run fast enough to handle the failing case, especially when hundreds of AI’s need to move from place to place.
Let take an example scene. This area has a bunch of buildings, roads, trees, bridges, and water. The AI’s need to navigate the area to get from their home to the market and to their jobs.
Besides finding a valid path around buildings, A* allows you assign weights to movement in different areas. This makes some areas easier to pass than others. When searching for a path, it makes the people prefer roads, but if cutting across a large farm is faster than following a road around it, the people will do it. It also makes people avoid tight clusters of trees or rocks, but if that’s the only way to go, they’ll go through them.
I can dynamically set these weights in game. For wild animals like deer, the weights are very high for roads and buildings, so they’ll generally stick to the wilderness, avoid settlements, and have no problem crossing a river.
The path weights look like this.
In this image, the roads have the lowest weight (orange), open areas are next (green), then farming/stockpile areas (yellow), then trees, rocks, and other obstacles (grey). Water (blue) and buildings (black) are not passable.
I worked hard to optimize this whole system. From my initial implementation to what I have now was probably a 20x speedup. A* needs a whole lot of record keeping. It needs to keep a bunch of sets and priority queues of information. Since the map is constant size, much of this data can be preallocated. However there is a dynamic priority queue that uses a custom AVLTree with a constant time memory allocator for high performance. After all the optimization it’s still too slow to handle the failure case quickly.
After researching a bunch of other pathfinding optimizations, I came to the realization that I was trying to optimize the wrong thing. Most of the time the game engine wants to know if an AI can get from point A to point B. I was using A* to make this determination, and throwing the path information away. The only time A* is important is when an AI actually starts walking, otherwise I just need to know that a path does or doesn’t exist.
I went with the simplest thing possible: a large table that can be used to lookup the A to B accessibility. For this I turned back to my software graphics rendering roots, and implemented a fast flood fill. The code flood fills all regions that are connected with an identifier. When the fill is complete, any unvisited areas are then flood filled with a different identifier. This continues until the entire map is filled.
The colors in the image above represent the different identifiers. Before pathing from point A to point B, the game simply looks in the accessibility map at points A and B. If they have the same identifier an AI can make the trip. If not, they’ll move onto doing something else. This is very fast and takes so much less time than running A*.
When a building, bridge, or something else is placed that could change the accessibility information, the flood fill is simply performed again. This is fast and doesn’t show up on any profiling I’ve done.
There are other things to consider while pathfinding. For example, an AI could already be walking from A to B when the route is cut off, so AI’s constantly have to check the accessibility map, and either re-path or cancel the current task.
All that pathing and flood fill code I just described is only about 350 lines of C++. Strange that a small amount of code has caused me so many performance issues and headaches….
