Goal Oriented Action Planning (GOAP)

Game AI
by Cedric Brownewell

The technique this blog post is going to cover is Goal Oriented Action Planning (GOAP).  GOAP is a version of Finite State Machine (FSM) that aims to decouple and simplify the predefined loop in the FSM.  When applying GOAP to a FSM the FSM should only have about three to four states it cycles through.  These states are Idle, Move and Perform (sometimes Animation is its own state or is done in the same step as Move).  With this limited selection of states you might be wondering how you actually get the agent to do anything, well that’s because in GOAP you define the actions the agent might take separately.  The actions are not part of the FSM for a very good reason, having them decoupled from the FSM allows them to be used in any order.  This is where another part of GOAP comes into play, the planner.

The GOAP planner’s goal is to iterate through all available actions for the agent it is assigned to and find the best set of actions to allow it to reach its goal.  Actions are normally given to each agent individually and on a need to know basis to help with organization and memory consumption.  For instance say you had a Fight_Enemy action and a Harvest_Wheat action defined.  You would assign the Fight_Enemy action to the soldier agent and not the Harvest_Wheat action since if the soldiers goal is to kill enemies the Harvest_Wheat action would never be used, but still considered slowing down the planning time and consuming memory that shouldn’t be needed in the first place.  Proper action assignment sees each agent have a list of actions specific to their function in your game.

Once you have a list of actions the GOAP planner will create a decision tree that will take into account all actions available to the agent it’s attached to.  It will iterate through all actions linking them together until it has reached the goal that is supplied to the agent.  The next question you might ask is how does the planner know which actions link together if the actions know nothing about each other?  GOAPs solution to this problem is that it uses a centralized World State to help determine how to reach the goal.  The World State is simply an easily accessible script or data structure that holds onto all of the information in the game.  The scope of this World State can change though depending on the context of the implementation.  Sometimes it can refer to the entire game or it can refer to only the state of the assigned agent.  Regardless of the scope it is very helpful to make the World State simple and easily copied.  The planner will create a copy of the World State to help determine how each action would affect the world in order to help string together a sequence of actions to the goal.  In addition to the World state each action will have a set of preconditions and effects.  Preconditions are conditions that need to be met before this action can be used in the planner’s action sequence.  Effects are what happens after the sanction has been performed and are essential to finding the goal since they mutate the World State, allowing other action’s preconditions to be fulfilled.

Once the planner has created a list of actions they are put into a queue (to help preserve the order) and then passed to the agent.  This is where the FSM comes back into play.  The planner activates and runs during the Idle state, then the Move state moves the agent within range of the action, then performs the top action from the queue.  The FMS will then switch between Move and Perform until the queue is empty.  When the queue is empty the FSM will return to the idle state and search for a way to find the goal it’s been assigned.  In this case the previous goal would be searched for and repeated until a new goal is supplied.

GOAP can be used on console and PC, but would most likely be too memory and processor intensive to be used on a mobile platform due to its dynamic nature.  Additionally this technique works best when you need a variety of agents or agents that need to be able to adapt to many different scenarios.  This could prove to be a point of complication on platforms with limited processor and memory.

As said previously this technique is best suited for games that require a variety of agents to perform multiple tasks with a level of automation.  Game genres such as Supply Chain management games are one such genre where the functionality of GOAP could be useful for worker AI.  Strategy games in general are a great place to use GOAP since the user doesn’t need to micromanage everything all the time.  The user mostly issues orders and the units do their best to fulfill those orders.  Another place where GOAP would be useful is in games where adaptable enemies are needed/wanted.  First Person Shooters are one such game genre.  GOAP has already been used in games such as F.E.A.R. First Encounter Assault Recon.  All of the enemies in that game use some form of GOAP in order to make the enemies more unpredictable and dangerous.

Resources Used during this Project:

Chaudhari, Vedant. Goal Oriented Action Planning. medium.com, December 12th 2017. https://medium.com/@vedantchaudhari/goal-oriented-action-planning-34035ed40d0b

A great article that explains the GOAP technique. Was used in conjunction with an article written by Brent Owen’s to help my understanding of GOAP’s implementation. Chaudhari’s article helped fill in some of the code gaps in Owen’s article such as an explicate way to define goals. Chaudhari talked about more about the methods application in some games. In fact Chaudhari cited Owen’s article in his sources.

Bevilacqua, Fernando. Finite State Machines: Theory and Implementation. gamedevelopment.tutsplus.com, October 24th 2013. https://gamedevelopment.tutsplus.com/tutorials/finite-state-machines-theory-and-implementation–gamedev-11867

This resource was linked in Brent Owen’s article. I was having trouble understanding Owen’s implementation of the Finite State Machine and this was a link that he said was a good refresher/starting point for the FSM. The article had some good concepts that I could see in Owen’s example project, but uses Flash as its code examples. Overall it’s concepts helped me get farther in interpreting Owen’s methodology for GOAP.

Nystrom, Robert. State. gameprogrammingpatterns.com, 2009-2014. https://gameprogrammingpatterns.com/state.html

This is a site I’ve used in the past during my time in a Game Architecture class and was very insightful. I used to as a refresher on many of the base Finite State Machine systems as it had been awhile since I had implemented one from scratch and in the Unity Engine so less.

Owens, Brent. Goal Oriented Action Planning for a Smarter AI. gamedevelopment.tutsplus.com, April 23rd 2014. https://gamedevelopment.tutsplus.com/tutorials/goal-oriented-action-planning-for-a-smarter-ai–cms-20793

Brent Owens article was very helpful on explaining the overall method with some code examples. The examples were given in Unity C# which helped me with my implementation of the technique in Unity. Owens also included a link to their own repository with an example project for those who wanted to see a full implementation of GOAP. Some parts of the article were a little abstract, but with the inclusion of the link to the repository it was very helpful in understanding the GOAP technique.

Thompson, Tommy. Building the AI of F.E.A.R with Goal Oriented Action Planning. www.gamasutra.com, May 7th 2020. https://www.gamasutra.com/blogs/TommyThompson/20200507/362417/Building_the_AI_of_FEAR_with_Goal_Oriented_Action_Planning.php

This article breaks down how GOAP was used in the F.E.A.R game. The breakdown allows me to get a better understanding of the circumstances in which this technique would be useful in when you need an AI. It also briefly convers it methodology, but not as in depth as some of the other articles I found. The value of this article is in the description of how its used in gameplay and the reasons it was used as an AI.