﻿ Game Programming Gurus

Free JavaScript Editor     Ajax Editor ﻿

Main Page

### Planning and Decision Trees

Thus far, all the AI techniques have been fairly reactionary and immediate—meaning that there isn't much planning or high-level logic going on. Although you've learned how to implement low-level AI, I want to talk about high-level AI. This is usually referred to as planning.

A plan is simply a high-level set of actions that are carried out to arrive at a goal. The actions are the steps that are performed in a certain order to arrive at the goal. In addition to the actions, there may be conditionals that must be satisfied before any particular action can be carried out. For example, the following list is an example plan for going to the movies:

1. Look up the movie that you want to see.

2. Get in the car and drive to the theater at least 30 minutes before the movie starts.

3. Once at the theater, buy the tickets.

4. Watch the movie. When it's over, drive home.

Well, that looks like a reasonable plan. However, there are a lot of details I left out. For example, where do you look up the movie? How do you drive the car? What if you don't have any money? And so forth. These details may or may not be needed depending on how complex you want the plan to be, but in general there are conditionals and subplans that you can use to specifically detail this plan so that there's absolutely no question about what to do.

Implementing planning algorithms for game AI is based on the same concept. You have an object that's AI-controlled, and you want it to follow some plan to reach some goal. Therefore, you must model the plan with some kind of language—usually C/C++, but you might use a special high-level script. In any case, in addition to modeling the plan, you must model all the objects that are part of the plan: the actions, the goals, and the conditionals for the actions and goals to take place. Each one of these items might simply be a C/C++ structure or class and have a number of fields in it. For example, a goal might look like this:

```typedef struct GOAL_TYP
{
int class;     // the class of goal
char *name;    // the name of goal "kill leader"
int time;      // time until goal expires
int *subgoals; // pointer to sub goal list that must be
// satisfied
int (* eval)(void); // function pointer to determine if
// goal has been satisfied

// more data

}GOAL, *GOAL_PTR;
```

Of course, this definition is just an example and yours might have many more fields, but you get the idea. You have to create a structure that can generically represent any goal in your game, from "blowing up the bridge" to "searching for food."

The next structure you might need is a generic action structure that represents something an object must do as part of a plan to reach a goal. Again, this is up to you, but it must reflect anything and everything you want the AI to be able to do. For example, here's a possible action structure:

```typedef struct ACTION_TYP
{
int class; // class of action
int *name; // name of action
int time;  // time allotted to perform action
RESOURCE *resource; // a link to a record that describes
// the resources that this action might
// need

CONDITIONS *cond;   // a link to a record that describes
// all the conditions that must be met
// before this action can be made

// all the updates and changes that
// should be made when this action is
// complete

int (*action_functions)(void); // a function ptr(s) to an
// action function that does
// the work of the action

} ACTION, *ACTION_PTR;
```

As you can see, we're getting pretty abstract here. The point is that these structures may be completely different in your implementation. As long as they impart the functionality of the plan, action, and goal, that's all that matters.

#### Coding Plans

There are a number of ways to code a plan. You might code it as pure hard code that implements the actions, the goals, and the plan itself as pure C/C++. This was a very common technique in the old days. A game programmer would just start writing code that performed conditions, set variables, and called functions. This was in essence a hard-coded plan.

A more elegant method of encoding a plan is to use production rules and decision trees. A production rule is simply a logical proposition with a number of antecedents and a consequence:

```IF X OP Y THEN Z
```

X and Y are the antecedents, and Z is the consequence. OP could be any logical operation, like AND, OR, and so on. In addition, X or Y might be composed of other production rules; that is, they might be nested. For example, take a look at the following logic statement:

```if (P > 20) AND (damage < 100) THEN consequence
```

Or, in C/C++-speak:

```if (power > 20) && (damage < 100)
{
consequence();
}// end if
```

So a production rule is really a conditional statement. The hard-coded plan was really just a bunch of production statements along with actions and goals, all mashed together. The point of writing a "planner" is to model these things a little more abstractly. Although you could use hard-code C/C++, it would be better to create a structure that can read production rules, contain actions and goals, and represent a plan.

One structure that may help you implement this system is called a decision tree. As shown in Figure 12.15, a decision tree is nothing more than a tree structure in which each node represents a production rule and/or an action.

##### Figure 12.15. A decision tree encoding production rules.

However, instead of using hard code to implement the tree, the tree is built from a file or data that is fed to the AI engine by the game programmer or the level designer. This way the tree is generic and needs no recompilation to work. Let's create a little AI planning language to control a bot with some input variables and a set of actions.

Inputs that can be tested by the AI bot:

 DISPLY Distance to player (0–1000) FUEL Fuel left (0–100) AMO Ammo left (0–100) DAM The current damage (0–100) TMR Current game time in virtual minutes PLAYST The state of the player (attacking, not attacking)

Actions that the AI bot can perform:

 FW Fire weapons at player SD Self-destruct SEARCH Search for player EVADE Evade player

Now let's make up the decision tree structure. Assume that one or two antecedents can be tested with an AND, OR at each node, and that you can negate them with NOT. And the antecedents themselves can be comparisons with >, <, ==, or != between inputs or a constant. In addition, at any node there is a TRUE branch as well as a FALSE branch, along with an action list that holds eight actions that can be performed. Refer to Figure 12.15 to see this abstractly. Here's a structure that might be used to implement the node:

```typedef struct DECNODE_TYP
{
int operand1, operand2; // the first operands
int comp1;              // the comparison operator

int operator;           // the conjuctive operator

int operand3, operand4   // the second pair of operands
int comp2;               // the comparison to perform

ACTION *act_true;        // action lists for true and false
ACTION *act_false;

DECNODE_PTR *dec_true;   // branches to take if true or
// false
DECNODE_PTR *dec_false;

}DECNODE, *DECNODE_PTR;
```

As you can see, once again there are a lot of little details. If there is only one antecedent:

```if (DAM <  100) then...
```

Or the difference between variables and constants:

```if (DAM == FUEL) then...
```

or

```if (DAM == 20) then...
```

And determining if there are two antecedents or one:

```if (DAM > 50) and (AMO < 30) then
```

These are all relatively basic programming problems, so I'm not going to go into them. Just be aware that you have to take them into consideration when you make the engine read the decision nodes and process them. Anyway, now that you have your language, write a little decision tree that can determine what to do in a number of settings.

For example, let's make a firing control tree. Remember that you aren't really doing full plans, but you can think of the next example as a plan because the implicit goal is to determine when to fire. Granted, there isn't a goal other than the firing itself. In any case, here's my rough plan in plain English:

If the player is close and damage is low then fire at player

If the player is far and fuel is high then search for player

If damage is high and player is close then evade player

If damage is high and ammo is 0 and player is close then self destruct

That's my little AI pseudo-plan for the bot. Of course, a complete plan might have dozens or hundreds of these clauses. But the cool thing is that the game designer enters them with a graphical tool rather than having to program them in code! The results of this plan have been converted into your planning language, and the final decision tree is shown in Figure 12.16.

##### Figure 12.16. The final decision tree for your planning language.

Isn't that neato? You just write a processor that follows the tree and performs the branches, and that's it. Now that you have an idea about how to create a decision tree that can process decisions and carry out an action, let's finish up with a formal planning algorithm that takes goals into consideration and also performs planning analysis.

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

﻿

Ajax Editor     JavaScript Editor