Home About Recent Longsword Solo Drills - Meÿer Square Starting Historical European Martial Arts Group Historical European Martial Arts - Equipment D&D Journal: I Generic A* for Games Game development Generic A* for Games Procedural Island Generation Data-Oriented Design Matters Misconceptions of Component-Based Entity Systems Level of Detail Experiments Planet Generation - Part II Planet Generation - Part I Procedural Generation in Games Oculus Rift Integration Android Favorite Android Games NDK with Android Studio Android NDK Programming - Part III Android NDK Programming - Part II Android NDK Programming - Part I Personal Personal Stuff: Running! Global Game Jam 2014 Experiences Anime Claymore The Twelve Kingdoms Games Favorite Android Games Dungeons & dragons D&D Journal: I Historical european martial arts Longsword Solo Drills - Meÿer Square Starting Historical European Martial Arts Group Historical European Martial Arts - Equipment Longsword Longsword Solo Drills - Meÿer Square

The A* algorithm is most commonly used for pathfinding. However most developers neglect its ability to be used for other purposes.

In this post I will briefly go over the A* algorithm and then show how to generalize it and use it for purposes other than pathfinding, such as AI.

GOAP AI

Brief Introduction to A*

A* is an algorithm to find the shortest path from one node to another. It evaluates the current node and if it isn't the end node it finds all nodes linked from the current node, estimates their distance to the end node, sets the current node as a parent node, and adds them to a list called the open list.

The open list is then polled for the node evaluated as closest to the end and repeats the process until the end node is discovered or no more nodes are available in the open list, in which case there is no possible path to be found.

Heuristics

The estimation works by giving each node three heuristics, called the G, H and F costs:

G value is the cost of moving to this node from the start node. This is easily calculated by using the previous node's G cost plus the cost between the two nodes.

H value is an estimated cost to the end node. This is a naive guess of the distance you need to traverse to get to the end if there were no obstacles in-between.

F value is the combined sum of the G+H values.

Closed list

Now you may have noticed: Nothing prevents previous nodes from being added to the open list again. For that reason there is also a closed list that tracks which nodes were already evaluated and the current node is added to the closed list after each iteration.

If a node is in the closed list but is discovered again with a smaller estimated cost then its heuristic values are updated and its parent is set to the current node.

Additional reading

This was just a brief introduction, if you want to read more then I recommend these two very comprehensive guides:

Additional uses of A*

Now that we know the basics of the algorithm, let's see an example on how it can be used outside of classic pathfinding using a real world example.

In a game I am working on, I implemented Goal-Oriented Action Planning (GOAP) AI to allow for more interesting and customizable agent behaviors. Using GOAP, agents compute a path made of a set of actions to reach a goal which is described as a desired world state.

GOAP Example

In my game I have agents with a goal called satisfy hunger. This goal is described by a desired state of hunger = 0. Once that goal had been selected, the agents need to find a set of actions that will satisfy it. Here are some actions the agent has:

Action Effects Requires
Eat Hunger -= 1
Food -= 1
Food >= 1
Gather Berries Food += 1 See Berries >= 1
Search Berries See Berries += 1

If none of the requirements is set, the AI agent is expected to create a path that includes Search Berries, Gather Berries and Eat in that order. We also want the agent to pick the shortest path to the end goal, for that reason actions will have static or dynamic costs to distinguish them compared to others.

This is very similar to pathfinding. If we compare actions to pathfinding nodes, then we can use the required and effects columns as a way to find a node's neighbors and use the difference between two states as the H and F costs.

In this implementation we'll evaluate the state and add all possible actions, i.e. actions we fulfil the requirements for. Next we set the effects column to a local world state and unlock additional nodes.

To optimize the process we can find a list of requirements we do not fulfil and only poll actions that affect those attributes. Doing it recursively will ensure we get to the end actions.

Goal Planning Example

Starting with the goal satisfy hunger, the algorithm will find it needs to fulfil hunger = 0 and add all relevant actions. The action Eat which affects hunger is added to a list.

Next the list is evaluated. An action is removed and tested if it is usable by looking at its requirements. If the requirements aren't fulfilled, relevant actions are added to the list, for example gather berries. The loop continues until the list is empty, this allows search berries to be added after gather berries is evaluated.

Once a usable action is encountered, it is added to another list. This list includes all the possible actions the agent can take.

Next an action is picked and its effects are applied to the local world state. The process is repeated from there.

We should also add actions that were already evaluated into a second list and check against it to ensure we don't get stuck in an infinite loop.

If we look at this process in A* terms:

  • We initially find all linked nodes from our current state and add them to the open list. These are our neighbors, or linked nodes.
  • Next we pick the action that seems closest to the end, apply its world's state and repeat the process finding possible nodes from there.

This is exactly what happens in A* pathfinding! Let's see how we can generalize A* for this use case.

Generic A*

Comparing grid-based pathfinding to AI action planning we can draw the following similarities which will allow us create a generalized implementation of A*.

Nodes neighbors Costs
Grid Pathfinding Grid Cells / Coordinates Spatially connected nodes, immediate neighbors Distance function, sqrt(x*x+y*y)
GOAP Actions Other actions with effects relevant to an action's requirements Difference in world state, plus possible dynamic or static cost

This allows us to generalize A* to take any type of node and two functions. A distance evaluation function and a linked node search function.

The Distance Evaluation function

This function basically returns the cost between two nodes. It is used to evaluate the H and G costs and determine if we have reached the end goal.

In grid-based pathfinding this can be a simple distance function using pythagoras theorem sqrt(x*x+y*y).

For GOAP the function will evaluate the amount of change needed between two nodes.

Linked Node Search function

To find a path we need to find all possible nodes to be evaluated. This function handles finding all the neighbors and linked nodes.

For grid-based pathfinding it will simply return all neighboring nodes and specially linked portals.

In GOAP the function will go over the current node's requirements and find actions with relevant effects, these actions are then added to a list. For example Eat has a Food requirement and therefore Gather Berries will be added. It will then repeat the process for the returned actions if their requirements are not fulfilled, until it will find usable actions or a dead-end. This behaves like the Search Berries, Gather Berries, Eat example from before.

Defining the function

Now that we identified what part of the logic needs to be abstracted we can start creating our implementation. To make things somewhat more flexible we will also allow for a custom heuristic type.

template <typename heuristic_type, typename node_data_type>
bool astar_plan( 
    const node_data_type start_node,
    const node_data_type end_node, 
    std::stack<node_data_type>& out_path,
    std::function<heuristic_type ( const node_data_type&,
                                  const node_data_type& )> evaluate_cost_func,
    std::function<void ( const node_data_type&, const node_data_type&,
                          std::vector<node_data_type>& )> find_linked_nodes )

Let's go over this quickly:

heuristic_type is our custom heuristic. It'll most likely be a float for pathfinding and it might be an int for AI.

node_data_type is the node type. For pathfinding it can be a Vector3 or a grid index. For AI it's likely to be an action and/or world state.

out_path will contain the calculated path. It is a stack because A* paths are usually traced from the end node back to the starting node.

evaluate_cost_func is a function that evaluates the costs between two nodes and returns a value of the heuristic_type. 0 distance means the nodes are identical.

find_linked_nodes finds all possible nodes to go to from the current node. It also takes the end node to allow for optimizations.

Note I used std::function for simplicity. If you do not need to use lambda variable captures like passing local objects by reference or pointer, then it is better to use a function pointer. The std::function has an additional indirection, making them slower compared to generic function pointers.

The next thing left to do is to implement A* itself using the variable evaluate_cost_func and find_linked_nodes functions instead of strictly implementing distance checks or iterating a node's links in the code.

Usage example

Given the above implementation, it is very easy to use the function for both GOAP and pathfinding. Here is an example on how to use it for pathfinding on a square grid.

bool FindPath( const vec2& start_pos, const vec2& end_pos,
                              std::stack< vec2 >& out_path ) { 
  if (astar_plan<float, vec2>( 
    start_pos, end_pos, out_path,

    ///////////////////////
    //   Cost function   //
    ///////////////////////
    [&]  ( const vec2& node0, const vec2& node1 ) {
      vec2 diff = node1 - node0;

      // Pythagoras theorem
      return sqrt(diff.x*diff.x + diff.y*diff.y);
    },

    //////////////////////
    // Adding neighbors //
    //////////////////////
    [&] ( const vec2& current_node, const vec2& end_node,
                            std::vector<vec2>& out_nodes ) {
      // End node is not relevant here
      out_nodes.push_back( current_node + vec2( 1.0f, 0.0f ) );   // Right
      out_nodes.push_back( current_node + vec2( 0.0f, 1.0f ) );   // Up
      out_nodes.push_back( current_node + vec2( -1.0f, 0.0f ) );  // Left
      out_nodes.push_back( current_node + vec2( 0.0f, -1.0f ) );  // Down

      // Consider also adding diagonals
    })) {
      // Consider transforming out_path into a different container type

      return true;
    }

    return false;
}   

This will look similar for GOAP except for the custom functions. In my implementation I created a struct that holds the GOAP world state and action identifier so I can avoid recalculating the data every iteration.

struct knowledge_action_pair {
  KnowledgeGraph knowledge_;
  ActionID action_;
};

A slightly simplified version of my GOAP find linked nodes implementation:

/////////////////////////////////////
//  Find actions affecting a fact  //
/////////////////////////////////////
void FindRelevantActions( stack<ActionID>& actions_to_test,
                          vector<ActionID>& tested_actions,
                          const unordered_map<string, int>& requirements ) {
  // Iterate relevant facts
  for ( const auto& it : requirements ) {
    // Find actions that affect the relevant fact
    const auto& effect_to_action_it = action_effect_to_action_.find( it.first );
    if ( effect_to_action_it != action_effect_to_action_.cend() ) {
      // Iterate the relevant actions
      for ( const auto& action_it : effect_to_action_it->second ) {
        // Ensure the action wasn't evaluated yet
        if ( std::find( tested_actions.cbegin(), tested_actions.cend(), action_it ) 
                                                        == tested_actions.cend() ) {
          // Add action to tested actions
          tested_actions.push_back( action_it );

          // Add action for testing
          actions_to_test.push( action_it );

  } } } } // initial for loop
}

///////////////////////
//  Lambda function  //
///////////////////////
[&] ( const knowledge_action_pair& node,
      const knowledge_action_pair& end_node,
      vector<knowledge_action_pair>& out_nodes ) {
  // List of tested actons and actions to evaluate
  stack<ActionID> actions_to_test;
  vector<ActionID> tested_actions;

  // Find relevant facts
  FindRelevantActions( actions_to_test, tested_actions, 
                              end_node.knowledge_.facts ); 

  // Evaluate the actions
  while ( actions_to_test.size() ) {
    // Current action
    ActionID action_index = actions_to_test.top();
    actions_to_test.pop();

    // Are the action's requirements met?
    if ( EvaluatePreconditions( node.knowledge_, 
            action_conditions_[ action_index ] ) ) {
      // Construct a new pair and add it to the out vector
      knowledge_action_pair pair;
      pair.action_ = action_index;
      pair.knowledge_ = node.knowledge_;

      // Apply facts to local world state
      ApplyFacts( node.knowledge_.facts, 
                  action_effects_[ action_index ],
                  pair.knowledge_.facts );

      // Push pair to out vector
      out_nodes.push_back( pair );
    }

    else {
      // Action's requirements not met,
      // Find relevant facts
      FindRelevantActions( actions_to_test, tested_actions, 
                            action_conditions_[ action_index ] );
    }
  } // while
} // lambda

This function finds all facts required by a goal and then finds all actions which affect those facts. It then evaluates an action to see if its requirements are met and if not, it adds actions that affects its requirements. This process should eventually find some actions with fulfilled or no requirements.

These are the basics of general A* and how to use it for both GOAP and standard pathfinding.

One more trick

During playtesting I added an AI goal for happiness which could be fulfilled by multiple actions with the same cost. Due to the nature of the algorithm, it would only ever choose the first action found with the lowest cost.

This can be fixed with a few lines of code in the A* part that finds the node with the lowest F value. Instead of strictly looking for a single node, add all nodes with an equal (or similar) value to a list. If a node with a lower cost is found, clear the list and add that node and all other nodes with the same cost.

When you are done looking for the lowest cost node simply get a random node from the list and use that as the node to evaluate. This will cause AI agents to pick different paths even if their cost is the same.

Please give me feedback

I hope this tutorial was helpful and easy to read! Please give me feedback about this post by emailing me stream+feedback@shanee.io or via Twitter @Lunarsong.

Also check out my other posts by going back to the main page.

Back
Home About Recent Longsword Solo Drills - Meÿer Square Starting Historical European Martial Arts Group Historical European Martial Arts - Equipment D&D Journal: I Generic A* for Games Game development Generic A* for Games Procedural Island Generation Data-Oriented Design Matters Misconceptions of Component-Based Entity Systems Level of Detail Experiments Planet Generation - Part II Planet Generation - Part I Procedural Generation in Games Oculus Rift Integration Android Favorite Android Games NDK with Android Studio Android NDK Programming - Part III Android NDK Programming - Part II Android NDK Programming - Part I Personal Personal Stuff: Running! Global Game Jam 2014 Experiences Anime Claymore The Twelve Kingdoms Games Favorite Android Games Dungeons & dragons D&D Journal: I Historical european martial arts Longsword Solo Drills - Meÿer Square Starting Historical European Martial Arts Group Historical European Martial Arts - Equipment Longsword Longsword Solo Drills - Meÿer Square