A*

The A* (a-star) algorithm will find a path between two nodes in a graph. It uses a cost function f(n) to estimate how close a node is to the goal select what nodes to explore for a way to the goal. The cost function is the sum of two parts, f(n) = g(n) + f(n).

Algorithm

• • g(n) is the cost to get from the start to node n.

  • h(n) is a guess of how costly it will go from the node n to the goal node.

  • f(n) is g(n)+h(n). The lower this is the better chance that the node is on or close to the final path so we should explore the nodes with the lowest f(n) first.

  • Open is a list of all the nodes that we have noticed but have not explored yet. We have calculated f(n) on it and when we are looking for the next node to check we take the one from the open list with the lowest f(n) value.

  • Closed list a list with all the nodes we have explored already. That is we have calculated f() for all nodes it is linked to.

• 1. Let P be starting node.

  2. Assign f,g and h values to P.

  3. Add P to the open list.

  4. Let B be the best node from the open list. Best is the node with the lowest f value.

     1. If there is no node in B, quit and there is no path.

     2. If B is the goal node, then quit and return the path.

  5. Loop all linked nodes to B and for each node C.

• • 1. Assign f,g and h values to P.

    2. If C is in open or closed list check

       1. if the new path is better (lower f) update the path

    3. else

• • • 1. Add C to open list.

• 6. Move B to the closed list.

Reference

• • Optimizing the A* algorithm - 2011

  • Clearance-based Pathfinding and Hierarchical Annotated A* Search - 2009

  • A* Pathfinding for Beginners - 2003

  • Basic A* Pathfinding Made Simple, AIGPW1 p105-113. - 2002.

  • Generic A* Pathfinding, AIGPW1 p114-121. - 2002.

  • Pathfinding Design Architecture, AIGPW1 p122-132. - 2002.

  • How to Achieve Lightning Fast A*, AIGPW1 p133-145. - 2002.

  • Practical Optimizations for A* Path Generation, AIGPW1 p146-152. - 2002.

• Introduction to A*