Advertisement
  1. Game Development
  2. Unity 3D
Gamedevelopment

Goal Oriented Action Planning for a Smarter AI

by
Difficulty:IntermediateLength:LongLanguages:

Goal Oriented Action Planning (GOAP) is an AI system that will easily give your agents choices and the tools to make smart decisions without having to maintain a large and complex finite state machine.

View the Demo

In this demo, there are four character classes, each using tools that break after being used for a while:

  • Miner: Mines ore at rocks. Needs a tool to work.
  • Logger: Chops trees to produce logs. Needs a tool to work.
  • Wood Cutter: Cuts up trees into usable wood. Needs a tool to work.
  • Blacksmith: Forges tools at the forge. Everyone uses these tools.

Each class will figure out automatically, using goal oriented action planning, what actions they need to perform to reach their goals. If their tool breaks, they will go to a supply pile that has one made by the blacksmith.

What is GOAP?

Goal oriented action planning is an artificial intelligence system for agents that allows them to plan a sequence of actions to satisfy a particular goal. The particular sequence of actions depends not only on the goal but also on the current state of the world and the agent. This means that if the same goal is supplied for different agents or world states, you can get a completely different sequence of actions., which makes the AI more dynamic and realistic. Lets look at an example, as seen in the demo above.

We have an agent, a wood chopper, that takes logs and chops them up into firewood. The chopper can be supplied with the goal MakeFirewood, and has the actions ChopLog, GetAxe, and CollectBranches.

The ChopLog action will turn a log into firewood, but only if the wood cutter has an axe. The GetAxe action will give the wood cutter an axe. Finally, the CollectBranches action will produce firewood as well, without requiring an axe, but the firewood will not be as high in quality.

When we give the agent the MakeFirewood goal, we get these two different action sequences:

  • Needs firewood -> GetAxe -> ChopLog = makes firewood
  • Needs firewood -> CollectBranches = makes firewood

If the agent can get an axe, then they can chop a log to make firewood. But maybe they cannot get an axe; then, they can just go and collect branches. Each of these sequences will fulfill the goal of MakeFirewood

GOAP can choose the best sequence based on what preconditions are available. If there is no axe handy, then the wood cutter has to resort to picking up branches. Picking up branches can take a really long time and yield poor quality firewood, so we don’t want it to run all the time, only when it has to.

Who GOAP is For

You are, by now, probably familiar with Finite State Machines (FSM), but if not, then take a look at this terrific tutorial

You might have run into very large and complex states for some of your FSM agents, where you eventually get to a point where you do not want to add new behaviours because they cause too many side effects and gaps in the AI.

GOAP turns this:

Finite State Machine states: connected everywhere.

Into this:

GOAP: nice and manageable.


By decoupling the actions from each other, we can now focus on each action individually. This makes the code modular, and easy to test and to maintain. If you want to add in another action, you can just plunk it in, and no other actions have to be changed. Try doing that with an FSM!

Also, you can add or remove actions on the fly to change the behaviour of an agent to make them even more dynamic. Have an ogre that suddenly started raging? Give them a new "rage attack" action that gets removed when they calm down. Simply adding the action to the list of actions is all you have to do; the GOAP planner will take care of the rest.

If you find you have a very complex FSM for your agents, then you should give GOAP a try. 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.

If you have a very simple agent that just performs one or two tasks, then GOAP might be a little heavy-handed and an FSM will suffice. However, it is worth looking at the concepts here and seeing whether they would be easy enough for you to plug into your agent.

Actions

An action is something that the agent does. Usually it is just playing an animation and a sound, and changing a little bit of state (for instance, adding firewood). Opening a door is a different action (and animation) than picking up a pencil. An action is encapsulated, and should not have to worry about what the other actions are.

To help GOAP determine what actions we want to use, each action is given a cost. A high cost action will not be chosen over a lower cost action. When we sequence the actions together, we add up the costs and then choose the sequence with the lowest cost.

Lets assign some costs to the actions:

  • GetAxe Cost: 2
  • ChopLog Cost: 4
  • CollectBranches Cost: 8

If we look at the sequence of actions again and add up the total costs, we will see what the cheapest sequence is:

  • Needs firewood -> GetAxe (2) -> ChopLog (4) = makes firewood (total: 6)
  • Needs firewood -> CollectBranches (8) = makes firewood (total: 8)

Getting an axe and chopping a log produces firewood at the lower cost of 6, while collecting the branches produces wood at the higher cost of 8. So, our agent chooses to get an axe and chop wood.

But won’t this same sequence run all the time? Not if we introduce preconditions...

Preconditions and Effects

Actions have preconditions and effects. A precondition is the state that is required for the action to run, and the effects are the change to the state after the action has run.

For example, the ChopLog action requires the agent to have an axe handy. If the agent does not have an axe, it needs to find another action that can fulfill that precondition in order to let the ChopLog action run. Luckily, the GetAxe action does that—this is the effect of the action.

The GOAP Planner

The GOAP planner is a piece of code that looks at actions' preconditions and effects, and creates queues of actions that will fulfill a goal. That goal is supplied by the agent, along with a world state, and a list of actions the agent can perform. With this information the GOAP planner can order the actions, see which can run and which can’t, and then decide which actions are the best to perform. Luckily for you, I’ve written this code, so you don’t have to.

To set this up, lets add preconditions and effects to our wood chopper’s actions:

  • GetAxe Cost: 2. Preconditions: "an axe is available", "doesn’t have an axe". Effect: "has an axe".
  • ChopLog Cost: 4. Preconditions: "has an axe". Effect: "make firewood"
  • CollectBranches Cost: 8. Preconditions: (none). Effect: "make firewood".

The GOAP planner now has the information needed to order the sequence of actions to make firewood (our goal). 

We start by supplying the GOAP Planner with the current state of the world and the state of the agent. This combined world state is:

  • "doesn’t have an axe"
  • "an axe is available"
  • "the sun is shining"

Looking at our current available actions, the only part of the states that are relevant to them is the "doesn’t have an axe" and the "an axe is available" states; the other one might be used for other agents with other actions.

Okay, we have our current world state, our actions (with their preconditions and effects), and the goal. Let’s plan!

The planner will run through the other actions, too, and it won’t just stop when it finds a solution to the goal. What if another sequence has a lower cost? It will run through all possibilities to find the best solution.

When it plans, it builds up a tree. Every time an action is applied, it is popped off the list of available actions, so we don’t have a string of 50 GetAxe actions back-to-back. The state is changed with that action’s effect.

The tree that the planner builds up looks like this:

We can see that it will actually find three paths to the goal with their total costs:

  • GetAxe -> ChopLog (total: 6)
  • GetAxe -> CollectBranches (total: 10)
  • CollectBranches (total: 8)

Although GetAxe -> CollectBranches works, the cheapest path is GetAxe -> ChopLog, so this one is returned.

What do preconditions and effects actually look like in code? Well, that's up to you, but I have found it easiest to store them as a key-value pair, where the key is always a String and the value is an object or primitive type (float, int, Boolean, or similar). In C#, that could look like this:

When the action is performing, what do these effects actually look like and what do they do? Well, they don’t have to do anything—they are really just used for planning, and don’t affect the real agent’s state until they run for real. 

This is worth emphasising: planning actions is not the same as running them. When an agent performs the GetAxe action, it will probably be near a pile of tools, play a bend-down-and-pick-up animation, and then store an axe object in its backpack. This changes the state of the agent. But, during GOAP planning, the state change is just temporary, so that the planner can figure out the optimal solution.

Procedural Preconditions

Sometimes, actions need to do a little more to determine whether they can run. For instance, the GetAxe action has the precondition of "an axe is available" that will need to search the world, or the immediate vicinity, to see whether there is an axe the agent can take. It might determine that the nearest axe is just too far away or behind enemy lines, and will say that it cannot run. This precondition is procedural and needs to run some code; it's not a simple Boolean operator that we can just toggle.

Obviously, some of these procedural preconditions can take a while to run, and should be performed on something other than the render thread, ideally as a background thread or as Coroutines (in Unity).

You could have procedural effects too, if you so desire. And if you want to introduce even more dynamic results, you can change the cost of actions on the fly!

GOAP and State

Our GOAP system will need to live in a small Finite State Machine (FSM), for the sole reason that, in many games, actions will need to be close to a target in order to perform. We end up with three states:

  • Idle
  • MoveTo
  • PerformAction

When idle, the agent will figure out which goal they want to fulfill. This part is handled outside of GOAP; GOAP will just tell you which actions you can run to perform that goal. When a goal is chosen it is passed to the GOAP Planner, along with the world and agent starting state, and the planner will return a list of actions (if it can fulfill that goal).

When the planner is done and the agent has its list of actions, it will try to perform the first action. All actions will need to know if they must be in range of a target. If they do, then the FSM will push on the next state: MoveTo.

The MoveTo state will tell the agent that it needs to move to a specific target. The agent will do the moving (and play the walk animation), and then let the FSM know when it is within range of the target. This state is then popped off, and the action can perform.

The PerformAction state will run the next action in the queue of actions returned by the GOAP Planner. The action can be instantaneous or last over many frames, but when it is done it gets popped off and then the next action is performed (again, after checking whether that next action needs to be performed within range of an object).

This all repeats until there are no actions left to perform, at which point we go back to the Idle state, get a new goal, and plan again.

A Real Code Example

It's time to take a look at a real example! Don’t worry; it isn’t that complicated, and I have provided a working copy in Unity and C# for you to try out. I will just talk about it briefly here so you get a feel for the architecture. The code uses some of the same WoodChopper examples as above.

If you want to dig right in, head here for the code: http://github.com/sploreg/goap

We have four labourers:

  • Blacksmith: turns iron ore into tools.
  • Logger: uses a tool to chop down trees to produce logs.
  • Miner: mines rocks with a tool to produce iron ore.
  • Wood cutter: uses a tool to chop logs to produce firewood.

Tools wear out over time and will need to be replaced. Fortunately, the Blacksmith makes tools. But iron ore is needed to make tools; that’s where the Miner comes in (who also needs tools). The Wood Cutter needs logs, and those come from the Logger; both need tools as well.

Tools and resources are stored on supply piles. The agents will collect the materials or tools they need from the piles, and also drop off their product at them.

The code has six main GOAP classes:

  • GoapAgent: understands state and uses the FSM and GoapPlanner to operate.
  • GoapAction: actions that agents can perform.
  • GoapPlanner: plans the actions for the GoapAgent.
  • FSM: the finite state machine.
  • FSMState: a state in the FSM.
  • IGoap: the interface that our real Labourer actors use. Ties into events for GOAP and the FSM.

Lets look at the GoapAction class, since that is the one you will subclass:

Nothing too fancy here: it stores preconditions and effects. It also knows whether it must be in range of a target, and, if so, then the FSM knows to push the MoveTo state when needed. It knows when it is done, too; that is determined by the implementing action class.

Here is one of the actions:

The largest part of the action is the checkProceduralPreconditions method. It looks for the nearest game object with an IronRockComponent, and saves this target rock. Then, when it performs, it gets that saved target rock and will perform the action on it. When the action is re-used in planning again, all of its fields are reset so that they can be calculated again.

These are all components that are added to the Miner entity object in Unity:


In order for your agent to work, you must add the following components to it:

  • GoapAgent.
  • A class that implements IGoap (in the above example, that's Miner.cs).
  • Some actions.
  • A backpack (only because the actions use it; it is unrelated to GOAP).
You can add whatever actions you want, and this would change how the agent behaves. You could even give it all actions so it can mine ore, forge tools, and chop wood.

Here is the demo in action again:

Each labourer goes to the target that they need to fulfill their action (tree, rock, chopping block, or whatever), performs the action, and often returns to the supply pile to drop off their goods. The Blacksmith will wait a little while until there is iron ore in one of the supply piles (added to by the Miner). The Blacksmith then goes off and makes tools, and will drop off the tools at the supply pile nearest him. When a labourer’s tool breaks they will head off to the supply pile near the Blacksmith where the new tools are.

You can grab the code and the full app here: http://github.com/sploreg/goap.

Conclusion

With GOAP, you can create a large series of actions without the headache of interconnected states that often comes with a Finite State Machine. Actions can be added and removed from an agent to produce dynamic results, as well as to keep you sane when maintaining the code. You will end up with a flexible, smart, and dynamic AI.



Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.