AI Pathfinding in Games

When it comes to having units in games make their way from one waypoint to another, there are many different approaches for finding the optimal route. A* is definitely the most popular pathing algorithm that developers get to choose from, but the problem is slightly more complicated than that. A* is still a fairly generic algorithm and game developers still need to tune the algorithm to work best with what their game does. Every developer has their own different game and different requirements. A* is still the best starting point and is implemented in many games.

Take a game like Civilization V for example. Civ V is a turn-based strategy game. It requires you to move units around a map made up of a hexagonal grid. Players move one unit at a time and units can’t collide. An algorithm like A* would work very well in this situation because the map is always static from the point of view of the single unit being moved. That unit could easily try to map a way through a hexagonal grid towards the goal, which would be the location the player wanted the unit to move to. This implementation works well because the world is static, though. Games where everything is always moving would require a different algorithm.

Blizzard’s real-time strategy game, Starcraft, is a good example of a dynamic map. In Starcraft, players move units around the map nonstop, multiple players moving units at the same time. If a player tells a unit to move across the map, the developer could continue to use the A* algorithm to move the unit across the map. But that would require the A* algorithm to compute an entirely new path whenever the unit encounters a new obstacle that it didn’t know of before. That would be quite inefficient and there are better algorithms to do this. Enter “Dynamic A*”, or D* for short. D* is much better suited for dynamic maps because it can change the cost of an arc as the algorithm runs. If it encounters an obstacle, it can dynamically search for other options to get to the goal.

In short, developers can use whatever algorithms they want to use for their AI pathfinding. A* is the gold standard for static pathfinding. Developers can customize A* to be what they need. D* works very well for dynamic solutions and maps that are constantly changing because it can recalculate the best path as it receives new information.