I am submitting herewith a project written by David Lindsey Pittman entitled “Practical Development of Goal-Oriented Action Planning AI.” I recommend that it be accepted in partial fulfillment of the requirements for the degree of Master of Interactive Technology in Digital Game Development, with Specialization in Software Development.
Pittman, David L. BS, University of Nebraska-Lincoln, 2005
Practical Development of Goal-Oriented Action Planning AI Supervisor: Professor Jeff Wofford
Master of Interactive Technology degree conferred March 23, 2007
Project completed March 21, 2007
As real-time graphics continue to approach realism and gameplay systems become increasingly complex, game AI must progress in parallel to maintain the illusion of believable characters. The decision-making architecture known as Goal-Oriented Action Planning (GOAP) offers dynamic problem solving, which is a key ingredient in crafting AIs which appear to understand their environment and react in a logical manner. This project analyzes the development of a GOAP-based AI and its application to various game genres, with consideration to the practicality of the technology. In this context, practical is defined as being able to be implemented in an interpreted scripting language at production quality in a reasonable amount of time, performing efficiently, and producing equal or better results compared to traditional AI techniques. In the context of certain game genres such as tactical shooters and strategy games, coordinated character behavior is as important as individual behavior to the success of an AI system. Prior implementations of GOAP have used informal solutions to the problem of coordinated decision-making. This project proposes a scheme for implementing command and control hierarchies which use GOAP at every level to propagate orders from a commanding unit to atomic AI agents.
In the completion of this project, I owe a debt of gratitude to the faculty at The Guildhall at SMU, including Gary Brubaker, Jeff Wofford, and Wouter van Oortmerrsen. The success of the project owes a great deal to their knowledge and guidance. My thanks also go to Jeff Orkin, who freely gave his time and wisdom to assist this project.
For their support and camaraderie, I would like to thank my literal and figurative brothers, the programmers of Cohort 5. My greatest thanks go to Kyle for always pushing me to greater heights, Kim for her love and understanding, and to my parents for their unending love and support (both emotionally and monetarily).
1.3. A command and control hierarchy implemented with GOAP 4
3.1. A theoretically infinite state-space graph 14
3.2. The relationship between the debugger classes 16
3.3. Using the Mediator design pattern 18
3.4. The UnrealEd interface for editing GOAP AI properties 20
4.1. Profiler statistics for the first demo scene 22
4.2. Squad shooter demo 24
4.3. Room clearing demo 25
4.4. RPG demo 26
1.1Goal-Oriented Action Planning
As game graphics become increasingly realistic and believable, character artificial intelligence must continue to progress in parallel. Using static AI techniques in a modern game with lifelike models can create a jarring effect for the user (similar to the "uncanny valley" phenomenon described in the field of robotics [Mori70]). The player's suspension of disbelief is broken when a character behaves in a highly unnatural manner. Good game AI is not just about producing systems which can solve problems, it is about the compelling simulation of a living being. The AI should behave realistically and react dynamically to the player and to situations which may or may not have been specifically anticipated by a designer. Because game AI is a feature in which programmers, designers, and artists are all invested, it is desirable to develop an AI system that allows all disciplines to configure character behaviors in an intuitive and friendly way.
The purpose of this project is to evaluate the usefulness of the game AI technique known as Goal-Oriented Action Planning (GOAP) in terms of its cost to implement and runtime performance on an interpreted scripting language and its value for various game genres. Furthermore, the project proposes the use of GOAP for military-style "command and control" hierarchies, as might be found in a squad-based shooter or real-time strategy game. GOAP is a relatively new addition to the game AI vocabulary, having been introduced by the AIISC in 2003 [AIISC]. Fundamentally, the technique involves formulating a list of actions whose outcome will satisfy a goal.
GOAP is a technique for AI decision-making that produces a sequence of actions (called a plan) to achieve a desired goal state. The primary objects in GOAP are Goals and Actions. A Goal is described by relevant world state properties. An Action is described in terms of its effects on the world state and its world state preconditions. A plan of action (literally, an ordered array of Actions) is formulated by a component called a planner.
The input to the planner includes a current world state, a previously selected Goal, and a set of Actions. The Goal's properties are modulated with the current world state to produce the goal world state. The plan is then formulated by searching the state space graph for a minimal ordered set of Actions which produce the goal state from the current state. For our purposes, we can generally ignore world state side effects caused by Actions. This means that we actually only need to consider those properties of the world state which the Goal or an Action precondition specifies; all the other elements of the world state are ignored in the search.
Figure 1.2 An example of a plan formulated by GOAP