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

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.

Figure 12.22 A path network with common waypoints.

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

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.