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

- Calculate the already-traveresed cost
- Add the source node to the Closed list

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 foundA 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.

## 1 comment:

Amit's page has a great overview of A*:

http://theory.stanford.edu/~amitp/GameProgramming/

Post a Comment