Tricks of the Windows Game Programming Gurus:Making Silicon Think with Artificial Intelligence

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

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

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

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

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

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 `WAYPOINT`’s, 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.

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.