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

#### Implementing a Real Planner

You’ve seen how you might implement the conditional part of a planner, and even the action part. The goal part is really nothing more than formalizing that a particular plan has a goal and then assigning the goal as the end point of the plan. Moreover, when a plan is completed, the goal must be tested before any remaining parts of the plan can be executed. You may have subplans that run in parallel with a primary plan, and they must all have their goals met to allow a master goal to be met.

For example, you may have a global plan that “All bots meet at waypoint (x,y,z).” However, this goal can’t be reached until each bot executes the plan “Go to waypoint (x,y,z).” Furthermore, if one of the bots can’t make it, the planner should figure this out and respond. This is the idea of plan monitoring and analysis. I’ll talk more about this later in this section. At this point, let’s take a look at how you might represent the plans.

The plan itself might be represented implicitly in the decision/action tree, or it could be a list of decisions/actions, each of which represents a tree or a sequence. It’s up to you. The point is that you want to be able to formulate a plan, a sequence of actions, and a goal. The actions themselves usually involve conditional logic and subactions that are low-level, like moving from one (x,y,z) to another or firing a weapon. The term actions, in the highest-level sense, means “kill the leader” or “take over the fort,” whereas actions in a low-level sense are directly executable by the engine. Get it? I hope so—I’m running out of Snapple. :)

So, assuming that a plan is made up of some sort of array or linked list and that you can traverse it, a planner might look like this:

    while(plan not empty and haven't reached goal)

         {

         get the next action in the plan

         execute the action

         } // end while

Of course, you should understand that this is just an abstract implementation of the planner. In a real program, this needs to occur in parallel with everything else. You surely can’t sit in a `while` loop waiting for a single plan to reach its goal; you have to implement the planner with a finite state machine or similar structure and keep track of the plan as the game runs.

The problem with this planning algorithm is that it’s pretty stupid. It doesn’t take into consideration that an action in the future may already be impossible to satisfy, and thus the plan is useless. As a result, the planner needs to monitor or analyze the plan and make sure that it makes sense. For example, if the plan is to blow up a bridge and along the way someone else blows up the bridge, the planner needs to figure this out and stop the plan. This can be accomplished by looking at the goals of the plan and testing if any future goal has been attained by another process. If this goal negates the plan or makes it futile, the plan should stop.

The planner should look at events or states that might make the plan impossible. For example, at some point the plan may call for a blue key, but the blue key has been lost. Thus, the goal of finding the blue key is moot. This kind of problem can be monitored at the current level or the future level, meaning that the planner can look at the situation where it is when it gets there, or it can project forward into the future. For example, say that a plan is to “Walk 1,000 miles east and then blow up the fort.” I don’t want to walk 1,000 miles to blow up a fort and then realize I’m out of bombs when I get there! The planner should look at the goal, backtrack all the prerequisites, and test if the object following the plan has bombs or could get them along the way.

On the other hand, this can backfire. Even though the bot may not have a bomb right now, it may find one during the 1,000 mile trek, so terminating a plan prematurely because of a lack of resources at the current point may be a bad idea. This leads us to classifying prerequisites with priorities. For example, if I need the laser gun in the future, and there’s only one in the game and it’s been destroyed, there’s no need to continue with the plan. On the other hand, if I need 1,000 gold pieces and I only have 50, but I’m going to travel a long distance and there will be a lot of other ways to find gold along the way, I want to keep moving on with my plan.

Finally, when a plan goes awry, you don’t necessarily need to terminate it. You can replan, or maybe select a different plan. You might have three plans for each goal so that there are two backup plans if the primary plan fails.

Planning is a very powerful AI tool and is totally applicable to any type of game. Although you may write a Quake clone that is mostly shoot-’em-up, you still need a global planner that influences the creatures with a general goal of “Stay in this area and kill the player.” On the other hand, in a war simulation like Command and Conquer, planning is the only way to write a game that makes any sense at all!

The best way to get planning to work in real game development is to write a planning language and then give the designer a set of variables and objects that can be part of the plans. This allows the designer to come up with things that you never would have thought of—and surely wouldn’t want to hard-code!

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

Figure 12.17 Finding a path from point to point.

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.