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

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

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

Figure 12.25 Breadth-first search in action.

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.

Figure 12.26 Bidirectional breadth-first search in action.

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.

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

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.

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.

### Advanced AI Scripting

At this point, you should be quite the AI expert and things should be starting to gel. I’ve waited to talk about advanced AI scripting until now so you can see what I’m getting at with more of a foundation.

You already saw that a scripted instruction language can be used for AI when you learned about using a simple `[OPCODE OPERAND]` language and a virtual interpreter earlier in the chapter. This is a form of scripting, of course. Then I showed you yet another way to create decision trees with a scripted language based on logical productions and a set of inputs, operators, and action functions. This technology can be taken to any limits you want. QUAKE C is a good example, as well as UNREAL Script. Both of these actually allow you to program game code with a high-level English-like language that is processed by the engine.

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.