NPC AI with GOAP 2: Implementation Of Framework

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.

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.

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.

  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.
  1. Weight: Cost of traversing the edge.
  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.

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!

  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
  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.
  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.
Example setup
  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.

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.

Example Execution of Framework

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store