Pathfinding

In the simplest terms, pathfinding is the computation and execution of a path from point p1 to goal p2, as shown in Figure 12.17. If there are no obstacles, the simple AI technique of vectoring toward the goal position will suffice. However, if there are obstacles, obstacle avoidance will have to come into play. This is where things get difficult…

Trial and Error

For simple obstacles that aren't large and are mostly convex, you can usually get away with an algorithm that, when the object hits an obstacle, backs it up, turns it right or left 45-90 degrees, and then moves it forward again for some fixed amount (AVOIDANCE_DISTANCE). When the object has moved that distance, the AI retargets the goal, turns the object toward it, and tries again. The results of this algorithm are traced out in Figure 12.18.

Although this algorithm surely isn't as robust as you'd like, it works because there's a randomness in the avoidance algorithm. It turns randomly each way to try again, so sooner or later the object will find its way around the obstacle.

Contour Tracing

Another method of obstacle avoidance is contour tracing. Basically, this algorithm traces the contour of the object that's blocking the object's path. You can implement this by following the outline of the obstacle and periodically testing if a line from your current position to the goal intersects the obstacle anymore. If not, you're clear; otherwise, continue tracing. A sample run of this algorithm is shown in Figure 12.19.

This works, but it looks a little stupid because the algorithm traces around things instead of going through the obvious shortest path. But it works. So what you might do is use the trial-and-error method first, and if that fails after a certain period of time, switch to the contour tracing algorithm and get out!

Of course, the player usually can't get a God's-eye view of a 3D game like Quake, so if the creatures don't look that smart when they're avoiding obstacles, it's not going to show up that much. It simply takes them longer than needed. On the other hand, a war game with a top-down view is going to look really bad when the AI-controlled armies look like they're tracing. Let's see if we can do better.

Collision Avoidance Tracks

In this technique, you create virtual tracks around objects, consisting of a series of points or vectors that trace out a fairly intelligent path. The path can be computed algorithmically using a shortest-path algorithm (which we will get to later) or manually created by you or your game designers with a tool.

Around each large obstacle you create is an invisible track that only the pathfinding bot AI can see. When a bot wants to get around an object, it asks for the nearest avoidance path for that obstacle and then takes it. This ensures that the pathfinder will always know how to get around obstacles. Of course, you might want to have more than one avoidance path for each obstacle or add some tracing "noise" so the bots don't all follow the path perfectly. An illustration of this is shown in Figure 12.20.

This leads us to another idea: Why not have dozens or hundreds of precomputed paths for all points of interest in the game? Then, when a bot wants to get from point pi to pj, instead of navigating and performing obstacle avoidance, it just uses a precomputed full path.

Waypoint Pathfinding

Let's say that you have a really complicated world and there are all kinds of obstacles. Sure, you could make a creature with enough intelligence to navigate itself around everything and get to a goal, but is all that necessary? No! You can set up a network of paths that connect all points of interest in the game via a connected network of nodes. Each node represents a waypoint, or point of interest, and the edges in the network represent the vector direction and length to get to other nodes in the network.

For example, let's say that you have a plan running and you need to move a bot from its current location over the bridge and into the city. Doesn't that sound like a lot of drama? But if you have a network of paths and you can find a path that goes to the city via the bridge, all you have to do is follow it! The bot is guaranteed to get there and avoid all obstacles. Figure 12.21 shows a top-down view of a world, along with a pathfinding network. The highlighted path is the one that you want to take. Remember, this network not only avoids obstacles, but it also has paths for important destinations. (Sorta like the wormhole network in our universe.)

There are two problems with this grand scheme: 1) following the path, and 2) the actual data structure that represents the network can be a bit tricky. First, let's handle following the path itself.

Assume for a moment that you have a path from p1 to p2 that consists of n nodes, represented by the following structure:

typedef struct WAYPOINT_TYP
{
int id;             // id of waypoint
char *name;         // name of waypoint
int x,y;            // the position of waypoint
int distance;       // distance to next waypoint on path
WAYPOINT_TYP *next; // next waypoint in list
}WAYPOINT

This is just an example; you might use something completely different. Now assume that there are five waypoints, including the start and end waypoints p1 and p2, as shown in Figure 12.21. Here they are:

WAYPOINT path[5] = {{0,"START", x0, y0, d0 ,&path[1]},
                     {1,"ONPATH", x1, y1,d1 ,&path[2]},
                     {2,"ONPATH", x2, y2,d2 ,&path[3]},
                     {3,"ONPATH", x3, y3,d3 ,&path[4]},
                     {4,"ONPATH", x4, y4,d4 ,NULL} } ;

The first thing to note is that although I statically allocated an array to hold the WAYPOINTs, I still linked their pointers together. Also, the last link is NULL because this is the terminus.

To follow the path, you have a few things to consider. First, you have to get to the first node of the path or a node along it. This can be a problem. Assuming that there are sufficient path entry points on the game grid, you can assume that one of the nodes from a desired path is within range. Therefore, you want to find the node that is closest and vector toward it. During this initial path alignment, you may have to avoid obstacles to get there! Once you're at the starting node or a node on the interior of the path, you're ready to go.

Following the Path

The path is a series of points that are guaranteed to have no obstacles from one point to another. Why? You made that path so you know this! As a result, you can simply move the bot from the current WAYPOINT in the path toward the next one, and keep doing so until you get to the last WAYPOINT, which is the goal:

find nearest WAYPOINT in desired path

    while(not at goal)
          {
          compute trajectory from current waypoint to next
          and follow it.

          if reached next waypoint then update current
          waypoint and next waypoint.

          } // end while

Basically you're just following a series of points until you run out of points. To find the trajectory vector from one WAYPOINT to the next, you would use something like the following:

// start off at beginning of path
WAYPOINT_PTR current = &path[0];

// find trajectory to next waypoint
trajectory_x = path->next.x – path->x;
trajectory_y = path0>next.y – path->y;

// normalize
normalize(&trajectory_x, &trajectory_y);

The normalization just makes sure that the length of trajectory is 1.0. This is done by dividing each component by the length of the vector (look at Appendix C,"Math and Trigonometry Review)." Just point the object in the direction of trajectory, wait for it to get to the next WAYPOINT, and continue the algorithm. Of course, I've glossed over the details about what happens when a WAYPOINT is reached. I suggest checking the distance of the object to the WAYPOINT. If it's within some delta, that's close enough, and it's time to select the next WAYPOINT.

There are problems with having paths. First, finding a path to follow might be as difficult as trying to get from point to point! This is an issue, of course, but with the proper network data structure, you can ensure that for any given game cell, a game object needs to travel less than 100 units or so to pick up a path. Granted, the data structure representing the path network will be complex because some links may be used by other paths, but this is more of a data structure problem and depends on how you want to do it. You may simply have 1,000 different paths that don't reuse waypoints even if they're the same for many paths.

Or you might use a connected graph that reuses waypoints, but has logic and data links to follow a path and won't switch tracks. This can be accomplished with clever pointer arithmetic and logic to select the correct links that make up a specific path.

For example, take a look at Figure 12.22, which shows two paths through the same waypoints. You might have to encode in a list the possible waypoints that can be arrived at and the associated link to take—if you're trying to get to goal HOUSE and you're on a path waypoint that has 16 outgoing links, take the one that has HOUSE on its list of stops. Again, this is up to you, and your implementation will depend on the circumstances of the game.

A Racing Example

A good example of using paths is in racing games. Imagine that you want to have a number of cars on a racetrack, and you want them to drive around the track while avoiding the player and looking somewhat intelligent. This is a good place for paths.

What you might do is create, say, eight or 16 different paths that follow the road. Each of the paths might be equidistant or have slightly different properties, like "tight and short" or "long and wide." Each AI car starts off on a different path, and as the game runs, it follows the path by vectoring toward it. If a car gets in a crash, it picks up on the next nearest path, and so on.

In addition, if a car's AI wants to change lanes to a more aggressive path, it does so. This helps you because you don't have to worry about keeping the cars from bunching up as much, and you don't have to make them steer as much because they're on paths. Controlling their speed and braking time will be more than enough to make them seem real.

For an example of this, take a look at DEMO12_8.CPP|EXE (16-bit version, DEMO12_8_16B.CPP|EXE) on the CD, which creates a little racing demo with a single waypoint path. The cars try to avoid each other, but if they touch they don't crash. This is a DirectX application, so you need to add the libraries and so forth to compile.

Robust Pathfinding

Last but not least, I want to talk a little about real pathfinding; in other words, using computer science algorithms to find paths from p1 to p2. There are a number of algorithms that can do this. The problem is that none of them are for real-time and thus don't lend themselves to games easily. However, you can use them in real-time if you employ some tricks, and of course you can use them to compute paths for you in your tools.

All of the algorithms work on graph-like structures, which are representations of your game universe that consist of nodes, along with edges made up of nodes that can be reached from any particular node. There's usually a cost associated with each edge. Figure 12.23 shows a typical graph.

Because you're dealing with 2D and 3D games, you might decide that the graph is just a grid laid down on the game field with each cell implicitly connected to its eight neighbors, and that the cost is just the distance. This is shown in Figure 12.24.

In any case, once you've come up with a way to represent the game world that is graph-like, you can run the algorithm(s) on the problem of finding a short path, or the shortest path, from p1 to p2 that avoids obstacles. Obstacles aren't allowed in the graph, so they can't possibly be part of the path—that's a relief <G>.

There are a number of pathfinding algorithms that are well known in computer science. They're shown in the following list and are briefly described in more detail:

• Breadth-first search

• Bidirectional breadth-first search

• Depth-first search

• Dijkstra's search

• A* search

Breadth-First Search

This search fans out in all directions at the same time, visiting each node one unit away, then two units away, then three units away, and so on—a growing circle. It's crude because it doesn't focus on the actual direction of the goal. See Figure 12.25 and the algorithm that follows:

void BreadthFirstSearch(NODE r)
{
NODE s; // used to scan
QUEUE q; // this is a first in first out structure FIFO

// empty the queue
EmptyQ(q);

// visit the node
Visit(r);
Mark(r);

// insert the node r into the queue
InsertQ(r, q);

// while queue isn't empty loop
while (q is not empty)
      {
      NODE n = RemoveQ(q);

      for (each unmarked NODE s adjacent to n)
          {
          // visit the node
          Visit(s);
          Mark(s);

          // insert the node s into the queue
          InsertQ(s, q);
          } // end for

      } // end while
} // end BreadthFirstSearch

Bidirectional Breadth-First Search

The bidirectional breadth-first search is similar to the breadth-first search, except that two different searches are started: one at the start and one at the goal. When they overlap, the shortest path is computed. See Figure 12.26.

Depth-First Search

This is the converse of the breadth-first search. The depth-first search searches one direction all the way until it runs out of space or finds the goal. Then it searches the next direction, and so on. The problem with depth-first is that it needs a stopping limit that says, "If the goal is 100 units away and you've already tried a path that has a cost 1000, it's time to try another path." See Figure 12.27 and the algorithm that follows.

void DepthFirstSearch(NODE r)
{
NODE s; // used to scan
// visit and mark the root node
visit(r);
mark(r);

// now scan along from root all the nodes adjacent
while (there is an unvisited vertex s adjacent to r)
      {
      DepthFirstSearch(s);
      }  // end while
} // end DepthFirstSearch

Dijkstra's Search

Dijkstra's search stems from the same algorithm used to find the minimum spanning tree of a graph. At each iteration, the algorithm determines what the shortest path to the next point is and then works on it rather than shooting out blindly in a random direction.

A* Search

The A* search (pronounced A-star) is similar to Dijkstra's search, except that it uses a heuristic that not only looks at the cost from the start to the current node, but also makes an estimate to the goal from the current node, even though it hasn't visited the nodes along the way.

Of course, there are modifications and mixtures of these algorithms that have mutated names, but you get the picture. Their actual implementations are well documented in many other books, so I'll leave it up to you to find them.