A star (A*) pathplanning

Previously I wrote about Dijkstra, this time I'm going to look at heuristic or "AI" style approach the A* algorithm. This is a single-source single-goal pathfinding algorithm. In essence this algorithm "guesses" or estimates the distance that remain to get from a node to the destination node. These estimates guide the direction of the path (i.e. search), with each node that is visited updating the true cost of the path, until a solution is found.

A* considers what to do at each node depending on an overall heuristic score. The total score is a function of the cost of the path that has already been traversed (the "g" cost) and the estimated cost of traveling from the node to the destination (the "h" cost). There are many ways to estimate the "h" cost, typically for pathfinding problems the euclidian distance is used, however it is always better to over-estimate the remaining cost (so you will explore more feasible solutions), and so a common measure used is the manhattan distance.

The A* algorithm works on two lists, a "Closed" list of already explored nodes, and an "Open" list of nodes yet-to-be-explored.

In essence the algorithm is:

• Select a source node to operate with (eg: the start node, or the node with the lowest overall cost)
  
• For each node connected to the source node:
  
  • Calculate the already-traveresed cost
    
  • If the node is on the closed list, and the newly calculated traversed cost exceeds the existing traversed cost for the node, skip the node, otherwise remove it from closed.
    
  • Calculate the estimate cost to find the total cost, and store all these costs with the node.
    
  • Add the node to the Open list
    
• Add the source node to the Closed list
  

In Pseudo-Code (from Bryan Stout):

priorityqueue Open
 list Closed 
s.g = 0 // s is the start node 
s.h = GoalDistEstimate( s ) 
s.f = s.g + s.h 
s.parent = null 
push s on Open 
while Open is not empty 
  pop node n from Open // n has the lowest f 
  if n is a goal node 
    construct path 
    return success 
  for each successor n' of n 
    newg = n.g + cost(n,n') 
    if n' is in Open or Closed, and n'.g < = newg 
      skip 
    n'.parent = n 
    n'.g = newg 
    n'.h = GoalDistEstimate( n' ) 
    n'.f = n'.g + n'.h 
    if n' is in Closed 
      remove it from Closed 
    if n' is not yet in Open 
      push n' on Open 
  push n onto Closed 
return failure // if no path found 

A great interactive demonstration program can be found here: http://www.policyalmanac.org/games/aStarTutorial.htm And some source code for A* is available from the GrinningLizard website (The same author as the fantastic tinyXML library!) Keep in mind that waypoint-based AI navigation for games is a very mid-nineties approach, nav-mesh's are certainly the way to go! For an example of issues with waypoint approaches take a look at this video: Your best bet for navmesh research is Mikko Mononen's blog.