O'Reilly logo

AI for Game Developers by David M Bourg, Glenn Seemann

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required