Using GOAP to simplify FSMs

Tired of getting tangled up in messy Finite State Machines? Use Goal Oriented Action Planning to replace those pesky transitions with preconditions instead!

As a brief recap, a Finite State Machine, or FSM, is a behavioral tree of states and state transitions, allowing an AI to move to different states if the transition parameters are met.

In this figure, the blue blocks are states, and the green arrows are the transitions, which show which states can navigate to each other.

“One sign your FSM is getting too complex is when every state has a myriad of if-else statements testing what state they should go to next, and adding in a new state makes you groan at all the implications it might have”

(Brent Owens, TutsPlus).

Ironically enough, we’ll still be using an FSM as the foundation for our first GOAP example, in which we’ll replicate the original implementation of GOAP, as it was in Jeff Orkin’s work on Monolith Productions’ F.E.A.R. The example I created was made in Unity, using C#.

According to the textbook Artificial Intelligence for Games, Ian Millington describes GOAP as a system that…

“…allows characters to plan detailed sequences of actions that provide the overall optimum fulfillment of their goal”

(Millington 388).

With GOAP, we will clean up the tangles of transitions to make way for a list-based system that looks much cleaner and is much easier to manage.

In the words of Jeff Orkin from his article Applying Goal-Oriented Action Planning to Games,

“each action [itself] represents a state transition”

(Orkin 2).

This is how we get around FSM’s cumbersome connections.

In order to plan out these sequences of actions, our GOAP system contains:

• FSM
• FSM states: Goap, MoveTo, Animate
• GoapAgent
• GoapActions: GetAxe, ChopWood, EatFood, etc.

Starting with the FSM: The FSM runs through the same loop implemented in F.E.A.R. in 2005, which was based off of a simple yet profound realization about NPCs in games.

“ If you consider an enemy in a game, all they do is play animations in certain circumstances. It’s when that animation is played in the right place at the right time it appears clever and when several clever animations are played in a sequence, it appears intelligent”

(AIandGames, referencing Jeff Orkin).

GOAP FSM diagram, Jeff Orkin, 2006.

This loop constantly runs for every AI we have set up. We start with the “UseSmartObject” state, which involves the actual action itself. In my FSM, I simply named this state “GOAP,” since this is the state that runs GOAP to choose which action to run. After GOAP is the “GoTo” state, which moves the AI to wherever it needs to be to perform the action, then it will run the animation state.

The GOAP state itself simply chooses a GoapAction to run. To do so, it first sorts the GoapActions by cost, then runs through the list, starting with the lowest cost, and selects the first GoapAction where all of its preconditions are true, therefore selecting the GoapAction with the lowest cost.

The Goap state looping through the sorted list of GoapActions.

GoapActions are equivalent to FSM states. All of the GoapActions are inherited from the GoapAction class, which includes a cost, a list of preconditions, and an action. The GoapAction class also includes a CheckPreconditions() function, a RunAction() function, and a NextState() function.

CheckPreconditions() checks the action’s specific preconditions, and returns true if all of the preconditions are true. Preconditions is a dictionary created within the GoapAction class, consisting of a string key and a bool. Dictionaries are created by filling them with pointers:

public Dictionary<string, bool> preconditions = new Dictionary<string, bool>();

Specific preconditions can be set or accessed by typing

preconditions[“HasAxe”] = true, or

if (preconditions[“HasAxe”] == true)

Preconditions are also added to the list at the start of each GoapAction, by using the function preconditions.Add(“HasAxe”, false);

RunAction() is called in the Goap script, when the “Goap” state is active in the FSM. This contains the action itself.

NextState() triggers the next state, and is only used if CheckPreconditions() returns false. Otherwise, the next state is automatically triggered in Goap’s RunState().

The GoapAction class, which each GoapAction inherits from.

The Goap Agent manages the preconditions statuses, such as marking the NPC as hungry after enough time has elapsed, or setting “HasAxe” to true when the NPC collides with an Axe item.

Here is a visual overview of how the entire GOAP system interacts:

In summary, the NPC contains the GoapAgent script — which keeps track of the status of each relevant precondition — and the GOAP FSM, which loops through the three GOAP states: GOAP, MoveTo, and Animate. The GOAP state selects the lowest cost available GoapAction based on the status of each of their preconditions, then continues to the MoveTo state, which moves the NPC to the proper location if one exists, then continues to the Animate state, which runs the animation at that location. At this point, the Animate state continues on to the GOAP state, where the process begins again.

Here is GOAP in action:

Here, my test AI cycles through EatFood, GetAxe, and ChopWood, with EatFood being the lowest cost (as it’s the highest priority) and ChopWood requiring “HasAxe” to be true, which is a precondition set by GetAxe.

Special thanks to Brent Owens from TutsPlus, whose in-depth description of GOAP made it really easy to understand the concepts, particularly with his use of flow charts to depict his AI’s goals. And to AIandGames, whose YouTube video and accompanying article did a really good job explaining why F.E.A.R. used a three-state FSM as the foundation for their groundbreaking GOAP system. And to F.E.A.R. itself — specifically Jeff Orkin, whose original idea for GOAP and comprehensive documentation made it really easy to replicate. And to Ian Millington, whose AI in Games book, while not incredibly helpful with GOAP, is a great resource for game AI in general. And mostly, to Supergiant’s Hades, whose incredible dialogue inspired me to create my own reactive dialogue system!

Sources

TutsPlus GOAP Tutorial
https://gamedevelopment.tutsplus.com/tutorials/goal-oriented-action-planning-for-a-smarter-ai--cms-20793
AI and Games GOAP Video Article
https://www.aiandgames.com/2020/05/06/ai-101-goap-fear/
Fear Developer Articles
Applying Goal-Oriented Action Planning to Games
https://alumni.media.mit.edu/~jorkin/GOAP_draft_AIWisdom2_2003.pdf
file:///C:/Users/patri/Downloads/gdc2006_orkin_jeff_fear/gdc2006_orkin_jeff_fear.pdf
AI in Games Book
file:///C:/Users/patri/Desktop/Artificial%20Intelligence%20for%20Games.pdf
Hades Dialogue GDC
https://www.youtube.com/watch?v=m5KJSAj4afg&t=845s