Adventures in A* pathfinding

A key part of nearly any video game involving things that move around in an intelligent fashion is an algorithm called A*.

Older games relied on fairly simple techniques for moving things around; patterns of movement, perhaps modified with random number generators, maybe moving towards the player’s position if an enemy or down the screen if a powerup. But once obstacles began to be introduced to the playing field it became necessary to figure out ways to move things around them, and A* fits the bill nicely. Give it a starting point and a destination, and it will happily build you a list of adjacent points between the two.

I guess I’m not really stating anything new here since the algorithm’s been around since the late 60s, but it’s really just an excuse to post some video of my own foray into implementing A*. It occurs to me that this could be the software developer’s equivalent of boring people with vacation pictures, but whatever.

It actually wasn’t too difficult to build a basic implementation of A* in Java, the language I’m writing the game in, using this brilliant tutorial. The Java Collections Framework offers a couple of classes that simplified the process, namely PriorityQueue to keep nodes in sorted order and HashMap to optimize node storage and lookups.

I did hit two of the major stumbling blocks the tutorial mentions.

The algorithm can be too slow for large maps unless it’s handled in two passes: one to pick out a rough path by examining a subset of the nodes, the second to pick the best path within the rough path. After that things worked fairly smoothly except for the occasional 4-5 second CPU spike and game freeze.

It turns out that if you have an island that a character can’t walk to the algorithm will search every walkable area of the map before failing to find a path. The solution? I generate a two-dimensional array of booleans along with the map to indicate which cells can be reached. So even if an island is technically walkable, if it can’t be reached from the mainland it is marked as blocked.

After that, I realized there was a simple thing missing. If the destination is a blocked tile, there’s no reason to even start the algorithm. Quick fix.

There is still one occasional CPU spike that occurs, but it’s natural. As these characters begin to walk away from each other they create increasingly complicated obstacles. Great stress test, actually. Sometimes these paths are so convoluted that they overload the pathfinder. My current solution is to have the pathfinder timeout after 50ms (most searches are completing within 20-30ms) with logged warnings if this seems to be occurring too frequently. It doesn’t feel like a totally robust solution, but at the same time the game won’t ever have this level of stress on it and it seems to work…

Leave a Reply

Your email address will not be published.