AI for Game Developers

Chapter 6. Basic Pathfinding and Waypoints

Many different types of pathfinding problems exist. Unfortunately, no one solution is appropriate to every type of pathfinding problem. The solution depends on the specifics of the pathfinding requirements for any given game. For example, is the destination moving or stationary? Are obstacles present? If so, are the obstacles moving? What is the terrain like? Is the shortest solution always the best solution? A longer path along a road might be quicker than a shorter path over hills or swampland. It’s also possible that a pathfinding problem might not even require reaching a specific destination. Perhaps you just want a game character to move around or explore the game environment intelligently. Because there are so many types of pathfinding problems, it wouldn’t be appropriate to select just one solution. The A∗ algorithm, for example, although an ideal solution for many pathfinding problems, isn’t appropriate for every situation. This chapter explores some of the techniques you can use for situations in which the A∗ algorithm might not be the best solution. We’ll cover the venerable A∗ algorithm in Chapter 7.

Basic Pathfinding

At its most basic level, pathfinding is simply the process of moving the position of a game character from its initial location to a desired destination. This is essentially the same principle we used in the basic chasing algorithm we showed you in Chapter 2. Example 6-1 shows how you can use this algorithm for basic ...