Free JavaScript Editor Ajax Editor

↑

Main Page

## PathfindingIn 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… ## Figure 12.17. Finding a path from point to point.## Trial and ErrorFor 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 ( ## Figure 12.18. The "Bump-n-Grind" object avoidance algorithm.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 TracingAnother 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. ## Figure 12.19. Contour tracing in action.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 TracksIn 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. ## Figure 12.20. Object avoidance paths.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 PathfindingLet'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.) ## Figure 12.21. A pathfinding network with a path highlighted.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 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 PathThe 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 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 // 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 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 ## Figure 12.22. A path network with common waypoints.## A Racing ExampleA 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 ## Robust PathfindingLast 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. ## Figure 12.23. A typical graph network.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. ## Figure 12.24. Creating a graph by using a regular grid network on the game universe.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 SearchThis 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 ## Figure 12.25. Breadth-first search in action.## Bidirectional Breadth-First SearchThe 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. ## Figure 12.26. Bidirectional breadth-first search in action.## Depth-First SearchThis 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. ## Figure 12.27. Depth-first search in action.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 SearchDijkstra'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* SearchThe 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. TIP Genetic algorithms can also be used to search for a best path. They may not be as real-time as you'd like, but they're definitely more natural than any of these algorithms. |

↓

Ajax Editor JavaScript Editor