I was working on performance optimizations for a turn-based tactical RPG. There was a noticeable hang when showing the movement highlights after clearing a level, when characters could move freely over the whole map. After fixing the graphics bottleneck in movement highlighting, performance was greatly improved, but there were still occasional hiccups. I also received reports that sometimes ranged unit AIs would cause the game to hang for a while, sometimes long enough to trigger the Flash “unresponsive script” warning. Digging into the AI issue, I realized that both issues were caused by the pathfinding–or rather, how the pathfinding code was used.
A* is the gold standard algorithm for finding a path from one point to another point. We were using the Dauntless.be A* library, which is a nice solid implementation. The AI and highlighting shared a subsystem we called the Searcher. The Searcher let you specify criteria for tiles and would then find all tiles which matched those criteria. Many of the criteria were simple, like “Within X range of tile Y,” or “Contains an enemy.” One of the more complex criteria was “Can be reached from tile X within Y steps.” These were the criteria used by the move highlighting. The criteria were applied like filters, in this order:
- Within range X of unit’s current tile
- Can be walked on (not a rock or other barrier)
- Can be occupied (allied units can pass through each other while moving, but can’t end their move on a tile occupied by another unit)
- Can be pathed to within X steps from unit’s current tile
#4 used A* to find a path, then confirmed if the path length was short enough. When checking for a path from one tile to another, this makes perfect sense. The problem came from using it in aggregate.
This animation shows what happened when using the Searcher with the above criteria:[kml_flashembed publishmethod="static" fversion="10.0.0" movie="http://selenetan.com/wp-content/uploads/2013/02/AStar.swf" width="176" height="206" targetclass="flashmovie"]
Orange highlights show path progress, beige highlights show candidate tiles, and green outlines show known-pathable tiles. Filter #1 limits the grid to all tiles within 5 steps of the center. Filters #2 and #3 find that all tiles in range can be walked on and occupied, which is the worst case for this algorithm. Finally, Filter #4, the pathfinding test, is applied to every tile from left to right, top to bottom. Since the filter was written in a way that considers just one tile at a time, when it looks at a new tile it forgets the intermediate paths it found for previous tiles.
So the problem is that the code is doing a lot of extra work when we want to check pathability all tiles within a range. If we were only checking a few tiles, testing for paths one tile at a time would make sense. With the average movement range of 5, we’re checking 120 tiles, and that goes up drastically at the end of a level when the movement range restrictions are lifted. We need to revise the code so that it checks pathability for all tiles at once.
A* has a close cousin called Dijkstra’s algorithm. Where A* is designed to find the single shortest path from X to Y, Dijkstra’s is designed to find all the shortest paths from X to everything else. That’s exactly what we want! Even better, you can quickly turn an A* implementation into Dijkstra’s by making the heuristic always return 0. I also changed the loop end condition so that instead of finishing when it reached the “goal” tile, it finished when it ran out of tiles to consider. I then had the algorithm cache all the intermediate paths it found in a two-dimensional array for easy lookup and return that cache with the results. Finally, I rewrote the Searcher’s pathability filter so it would check for the path cache, and either generate it or use it.
This animation shows the result of the changes:[kml_flashembed publishmethod="static" fversion="10.0.0" movie="http://selenetan.com/wp-content/uploads/2013/02/Dijkstra.swf" width="176" height="206" targetclass="flashmovie"]
The cache of known paths starts from the center and grows outwards in a rough circle, taking a fraction of the time needed by the old implementation. As a bonus, the caching sped up the AI when considering multiple goal types from the same starting location. It went from sometimes triggering the 15-second “unresponsive script” notice to a barely noticeable pause. A quick profiling check confirmed that the game was taking a tenth of the old time to calculate possible paths.
This kind of situation is why it’s so important to understand algorithms. It’s easy to look up pathfinding techniques online and conclude “A* is the best,” without considering the context and usage. It also highlights the benefit of caching. Modifying the A* to cache all partial and complete paths, and look them up during its search, would get many of the performance improvements I saw. The benefit to using Dijkstra is that we don’t waste time checking paths to areas that have been blocked off, saving CPU cycles.