3.4 – GOAP Architecture

3.4.0 – The Design
Different from all the previous architecture, GOAP, or Goal oriented action planner, is a planner–it is not only be responsive to the current scenario, but predicts future moves. To do that, it interpret the game world as small, atomic Variables. Variables make up a World State to describe the status of the world. It plans Actions with A* graph searching, where World State serves as nodes, and Actions as edges. Each Action has a cost. A*’s heuristic function calculates the “difference” between two World States–the number of Variables that are different. I use forward searching in this example to search a path from the current World State to the Goal–this is different from more traditional method where backward searching is preferred to limit the search space. But if the design of World State is simple enough, forward search works just fine.

3.4.1 – World State
World State contains a list of Variables to describe the world. Distance is calculated based on the difference between two World States. If Variable in the second World State has the same value as in the first World State, they are considered equivalent.

class WorldState
  std::map<int, bool> m_Variables;
  int distanceToState(const WorldState& _other) const;
  bool meetGoal(const WorldState& _goal) const;
  bool onUpdate(const std::vector<Variable*> _variables);

Variables are imported from XML, with an unique integer id, a name for debugging, a boolean value, and parameters to determine the boolean value. The XML for Variables is somewhat like this:
<Variable id="EnemyInRange" key="0" let="200"></Variable> <!-- when less than or equal to 200, return true -->

3.4.2 – Action
Action has Preconditions and Effects. Preconditions and Effects both are just a list of Variables. Preconditions need to be meet to declare an Action “valid”. Effects will be applied during planning to forecast the future World State.

class Action
  int m_iCost;
  std::map<int, bool> m_Preconditions;
  std::map<int, bool> m_Effects;
  bool isValid(const WorldState& _state) const;
  WorldState proceed(const WorldState& _state) const;

3.4.3 – Planner
Planner uses A* to find a path through State nodes and Action edges and returns a list of Actions. It keeps a list of open nodes and a list of closed nodes for A* search. Nodes contains a World State, and necessary information like the last edge, G and H. In this example, if a node is closed, it will not be re-opened.

class Planner
  std::vector<Node>::iterator inOpenList(const WorldState& _state);
  bool inClosedList(const WorldState& _state);
  int getHeuristic(const WorldState& _state1, const WorldState& _state2) const { return _state1.distanceToState(_state2); }
  std::vector<Action*> plan(const WorldState& _start, const WorldState& _goal, const std::vector<Action*>& _actions);

You May Also Like

Leave a Reply

Your email address will not be published. Required fields are marked *

The AI Project