Game Development Reference
Orkin's articles and presentations did the same thing for goal-oriented action
planning (GOAP) [Orkin03], [Orkin06]. For our purposes, GOAP (rhymes with
soap) can roughly be considered as STRIPS adapted to games and uses the same
vocabulary. We will look at how GOAP is typically applied to games.
When used in games, actors controlled by GOAP systems typically have multiple
goals, but only one goal active at a time. The active goal is the highest-priority goal
that has a valid plan. For independent agents, this single mindedness is not a
major drawback. Some games require that multiple goals be active at the same
time. In this case, the planner needs to be more sophisticated. It may want to
accept a higher-cost plan for one goal so that other goals can be pursued in
parallel. It may need to ensure that the many plans have no resource-contention
problems. It is up to the game designer to decide whether the game is better served
by having a wise AI that plans around these issues or a potentially more realistic
AI that correctly models the problems. Adding such a capability adds complexity
to an already complex algorithm, and it adds CPU demands to an algorithm that
is already demanding of uncomfortable amounts of processing power.
These are real-world problems; a full-scale review by the U.S. military many years ago found that
in one scenario, the combined demands of the worldwide commands collectively called for five
times the total airlift capacity of the Military Airlift Command and deployment of the Rapid
Deployment Force simultaneously to 10 different locations.
In games, GOAP actions are typically simplified so that each action can report a
cost value associated with it that can be used to compare that action to other
actions. These costs can be used to tune the AI's preference of one action over
another. The lowest-cost action might have a cost of 1. If costs tend to be roughly
comparable, the planner will prefer plans with fewer steps. It will accept Rube-
Goldberg-style plans only when there are no simpler means of accomplishing the
goal. The actions themselves are implemented with scripts or small FSMs that are
restricted to doing just the one action. FSMs work quite well because the
implementation of the action is often heavily tied to animation sequences, and
those sequences are often easily controlled by FSMs.
Given those simplifications to the actions, GOAP planners in games can use the
now-familiar A* algorithm to search the action space for a path between the goal
and the current state. With A*, the direction in which we search has an impact.
To use A* at all, we need a heuristic. We will examine both of these facets in