AI for Game Developers

Chapter 7. A∗ Pathfinding

In this chapter we are going to discuss the fundamentals of the A∗ pathfinding algorithm. Pathfinding is one of the most basic problems of game AI. Poor pathfinding can make game characters seem very brainless and artificial. Nothing can break the immersive effect of a game faster than seeing a game character unable to navigate a simple set of obstacles. Handling the problem of pathfinding effectively can go a long way toward making a game more enjoyable and immersive for the player.

Fortunately, the A∗ algorithm provides an effective solution to the problem of pathfinding. The A∗ algorithm is probably one of the most, if not the most used pathfinding algorithm in game development today. What makes the A∗ algorithm so appealing is that it is guaranteed to find the best path between any starting point and any ending point, assuming, of course, that a path exists. Also, it’s a relatively efficient algorithm, which adds to its appeal. In fact, you should use it whenever possible, unless, of course, you are dealing with some type of special-case scenario. For example, if a clear line of sight exists with no obstacles between the starting point and ending point, the A∗ algorithm would be overkill. A faster and more efficient line-of-sight movement algorithm would be better. It also probably wouldn’t be the best alternative if CPU cycles are at a minimum. The A∗ algorithm is efficient, but it still can consume quite a few CPU cycles, especially if you need to ...