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

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

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.