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

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

    UPDATES *update;    // a link to a record that describes

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

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.