top of page

Objectives

The goal of this mini project was to more thuroughly understand and evaluate the potential usages of the GOAP algorithm while also implementing my own unique functionality and features to the algorithm to better suit myfuture needs

 

Click Here To See Code Repository

 â€‹

Programming​​

  • Operator Overriding

  • Creating Custom Comparables

Skills Used

Concepts​​

  • A* search

  • Priority Queue / Min Heap Sort

  • Dijkstra's Search

  • Levenshtein Distance

  • GOAP

Overview

Property

Properties are the basic building block of GOAP. In the case of my GOAP system, properties contain a Property.Key which contains a name (string) and a taret (GameObject), which dictate what this property is as well as the ting on which this property exists. A property also contains a Property.Value which contains some form of data (object) and can contain other types of values which help with backend comparisons. An example of some properties is below.

Property - Example.jpg
World State

A WorldState defines what the world looks like from the algorithm's perspective and is made up of Properties. These Properties each represent some aspect of the world that the algorithm will pay attention to when considering how to get to point a from point B. 

Current State - Example.jpg
Action

An Action is something that can be performed on a WorldState. Actions have both a precondition, which determines what must be present in the world before an action can be done, and a postcondition, which determines what will change after an action is completed. Actions also have names and costs, the latter of which will be used later. In my implementation, they also contain delegates that can be called when the action plan is run. Below you can see the first WorldState which represents the precondition, followed by the second WorldState, the postcondition as well as the delegate for the Action. 

Action - Example.jpg
Goal State

The Goal State is a WorldState that contains the state that the GOAP algorithm wants to get to from it's current state. The goal state can contain comparison operators such as >=, >, <, ==, !=, etc such that the algorithm knows when the goal is fulfilled. An example Goal State is below.

Goal State - Example.jpg
GOAP Search Overview

This section is very technical and wordy, please feel free to ignore if that is not your thing.

​

In this section I would like to provide a brief overview of how the GOAP algorithm functions in my example. Note that the GOAP search searches from the Goal State toward the Current State, without this knowledge some steps of the process may seem confusing.

​

  1. The Search method is provided with the Current State of the thing that is searching, the Goal State that this thing wants to get to, and the list of Actions that can be performed. 

  2. The Current State is placed at the front of a Priority Queue which uses a Min Heap to take out highest priority items (1 = more important, 10 = less important).

  3. A loop beings running and will only stop if the search is finished or if there is nothing left to search.

  4. The state at the forefront of the priority queue is taken out for examination.

  5. If the state does not have any properties that disagree with the Current State, then the loop is finished as the plan that has been constructed will get to the Goal.

  6. All Actions are looped through and tested against the current state, if they pass a series of requirements, the state that existed "before" the action was used to get to the state being evaluated is "passed" on to the next step.

  7. The cost to get to this new state is then tested, if this cost is less than the previous cost to get to the new state, or if there is no recorded cost to get to this state, add it to the cost list.

    • The G-Cost is determined based on the cost value of the actions that have lead to that state.

    • The H-Cost is created using a modified Levenshtein distance formula. Unfortunately, I have not been able to create a 100% admissible distance formula for the distance of two integer values yet.

  8. Steps 3-7 repeat until the loop exits using the conditions described in step 3.

  9. If the path was found, rebuild the path and return it, if it was not, return an empty path.

​

These are the basics of how my GOAP algorithm functions. if you have any questions, feel free to reach out to me on LinkedIn.

bottom of page