NPC AI with GOAP 2: Implementation Of Framework

This article builds on the foundation established in the first article.

By now we have an idea of the building blocks of GOAP and how they will interact. It’s time to dig a little deeper and get our hands dirty to figure out how all these components will be implemented.

Starting Small With Design and Understanding

Implementing a complex AI system which lets us change behaviour on runtime is no easy task. It’s big, it’s complicated and requires too many challenges to tackle at once. So, we will break it down into manageable pieces and then build the whole system by assembling it back.

Also, to keep the focus on the system, we will first build the system as a console app and then we will use the system in Unity to create a small game.

But first, what does the system look like at low level?

This is the simple view of the whole system.

A simple view of the system

1. Our Main method will interact with AstarGoapPlanner and ask it to come up with a plan for an agent.
2. AstarGoapPlanner is the facade on top of Goap and Astar. Both Goap and Astar will be independent components and won’t have any knowledge of each other. Hence this component will be be the glue between the two components.
3. Goap will provide the framework of States and Actions.
4. Astar will provide a solution to finding a path between 2 states.

Makes sense?

Understanding the Agent

An agent is nothing more than a container which holds goals, actions and its current state.

Structure of an Agent

Construction of Pathfinder

For this implementation, we will be using the Astar algorithm which can find shortest path between 2 nodes of a graph. However, this article won’t go into details of how Astar algorithm works and will only cover how it can be used.

Graph

1. A graph needs nodes to represent different points where we could go. Those nodes are connected via edges which represents the path from one node to another.
2. The state in GOAP is the nodes of a graph and Actions are the edges.

Design of Graph

Design of a generic graph

1. it works on the interfaces of INode and IEdge.
2. It provides the methods to add and remove Nodes and Edges.
3. It’ll also provide an easy way to get all the edges which end at the given node.

Astar

We would need some additional data for maintaining cost of traversal and keeping track of the path which is being generated.

Every node of Astar will contain following properties

1. NodeCost: Every node will have a cost associated with it.
2. PreviousNode: Reference to the previous node in the shortest path.
3. PreviousEdge: Reference to the edge that connects previous node and current node in the shortest path.
4. Heuristic Cost: Assumed cost of reaching destination from the current node.

Every edge will also have a cost associated with traversing it.

1. Weight: Cost of traversing the edge.

There are 2 approaches to find the path between origin and destination.

1. Forward approach — Start from origin and find a path to the destination.
2. Backward approach — Start from destination and find a path to the origin.

In most of the cases, forward approach is preferred and is a little easier to understand. However, Goap works better with backwards approach. This is because of the Heuristic distance which will get covered later in the article.

Design of Astar

The algorithm is kept separate from the data by creating a separate class for the Astar specific graph. This gives us the flexibility to change to a different graph implementation if need be and switch the direction of search if need be.

Design of Astar Pathfinding system

GOAP Planner

Planner is the heart of this AI system and should not have strong couplings with any of the other component including Pathfinder!

At first it might look like that the Astar is a critical component but its not! Astar is only an algorithm which can be replaced with another algorithm in future. The algorithm we chose depends on many factors such as

1. Performance of the algorithm.
2. Is the algorithm CPU heavy or Memory heavy or I/O heavy? Depending on the device which needs planning, the algorithm might change.
3. It doesn’t have to be path finding. We can use a Min-Max algorithm instead to get a list of actions that our agent can take.

Design of GOAP

Design of Goap Framework

Fact
A fact is an atomic truth about the world as perceived by the agent. They are kept as a simple boolean value.

State
State is a collection multiple facts which together describe the whole world as perceived by the agent. For simplicity, in this implementation I have used a dictionary/map of facts where key is the name of the fact and value is the boolean value of the fact.

Goal
A goal is a desired state which the agent wants to achieve. Since an agent can have multiple goals, we need a way to prioritise and select 1 goal out of many. For this reason, we will have a Precondition state and priority as part of the goal.

1. Precondition State — For a goal to be active, the current state should satisfy the Precondition of the goal.
2. Goal Sate — The goal state.

Action
The unit of work that the Agent can do to change its current state. But not all actions are possible all the time. To configure when an action is possible, we will have a Precondition state in the action. Every action will have an effect on the current state of the world which will be captured in the Effects state.

1. PreConditions — State which should be satisfied by the current state for the action to be executable
2. Effects — Resulting state if the action executed successfully.

Heuristic distance between two states
Astar requires a heuristic distance between the current state and the destination state. A heuristic distance is nothing but a guess. As long as this guess is less than the actual distance, astar will be able to find the shortest path. It uses this heuristic distance to evaluate which node is closer to the destination, so it should not be same for all the nodes.

In Goap, we need to calculate heuristic distance between each state. The simplest way to calculate this distance would be = (difference in the size of states) + (difference in facts)

Because of the simple nature of this heuristic, its value could be misleading to the Astar algorithm.

For example — Let’s consider a simple problem, where an agent has to find a gun and shoot its enemy with the below starting states.

Example setup

Both the agents are in different state but their heuristic distance from the goal will be same.

Difference in the size of states: (Goal State size — Agent state size) = 3 for both the agents

Difference in facts: (Goal State Facts — Agent State Facts) = Since only EnemyDead fact is relevant to the goal, this distance is also same for both the agents with a value of 1.

Heuristic distance for both the states will be, 3 + 4 = 1

This will mislead our algorithm to assume that both the below paths are equal -

[Path 1] GetGun → PickUp → Shoot

[Path 2] PickUp → Shoot

And the path will be chosen based on which action it evaluates first. So the algorithm can pick Path 1 for Agent 2 even though it doesn’t make sense since Agent2 has already reached the gun.

This problem can be solved in 2 ways

1. With backwards search approach of path finding — Since we would be starting from destination, algorithm will stop as soon as it reaches PickUp action and won’t evaluate any path longer than that.
2. By setting cost for each action — If every action has a cost to it, then the above paths won’t have same cost.

I decided to go with both. Backwards search resolves the issue of finding shortest path when multiple paths with same cost are available and having cost associated with each action allows us to fine tune the path finding.

AstarGoapPlanner

This is the final component of the system. It’s the bridge between the two systems, GoapPlanner and Astar. It helps to keep the pathfinding separate from planner and provides loose coupling. Benefits of this lose coupling -

1. Astar won’t have any dependency on Goap planner and it can be used in different problems such as NPC pathfinding without any changes.
2. Goap won’t have any dependency on the pathfinding algorithm and can use different types of search algorithms without any changes.

Bridge between Goap and Astar

GoapPlannerFactory

This is a factory which will create a GoapPlanner that uses Astar for pathfinding. This factory also configures the Astar algorithm by injecting appropriate implementations of IFrontier and ICalculateHeuristicCost.

AstarAlgorithmWrapper

It’s an implementation of IFindActionPlan and gets injected into the GoapPlanner. It’s responsibilities include

1. Conversion of Goap State and Actions to Astar nodes and edges respectively.
2. Conversion of Astar path into the list of actions that Goap Planner expects.

AstarGoapEdge

Implementation of IWeightedEdge of Astar. It holds a reference to the GoapAction and translates GoapAction into an IWeightedEdge and vice-versa.

AstarGoapNode

Implementation of IAstarPathNode of Astar. It holds a reference to the Goap State and translates State into an IAstarPathNode and vice-versa.

FactsHeuristicCalculator

Implementation of ICalculateHeuristicCost. This returns the heuristic cost of state from another.

With all that said, let’s look at an example execution.

Example Execution of Framework

Github Link: AstarAlgo/GoapFramework at master · Pbasnal/AstarAlgo (github.com)