A* Algorithm

The A* algorithm works with two lists, an open-list and a closed-list. The open-list is the list of nodes to be checked, while the closed-list already has been checked. Each node also gets scored with F, G and H-scores.

 

·         F-score:   Total cost for a node (G-score + H-score).

·         G-score:   Movement cost.

·         H-score:   Estimated movement cost.

In my demonstration program I used pixels as nodes in a grid-based map. A rule the pathfinder had to obey was it could only move horizontally and vertically.

We start with a begin point and an endpoint, a map and we know which nodes are not passable.



The first step in A* is to add the start point to the closed list, and examine its neighbors.

We ignore it if it’s an obstacle or already on the closed list. When it’s not yet on the open-list, we add it to the open-list, and when it’s already on the list, we check of the G-score isn’t lower than the current G-score. If the score is lower, we change the parent of the node.



These steps are repeated until the goal-node is added to the open-list.

Thanks to the parent information of each node it is possible to reconstruct the shortest path from end to start.



The most important information for the algorithm is that it has to know the node with the lowest F-score, because this is most likely the one leading to the shortest path, and the one which will be added to the closed-list during the next iteration.

Because the pathfinder has to be fast, the data structure used to store these values has to be very fast as well. That’s why a binary heap is used in combination with A*.

(Other data structures can be used, but this solution proved to be the fastest on a 200 * 200 map)

4 Comments

  • I recall implementing the A* in LISP for a grad course in AI - it helped a mouse find cheese in a maze..

    :-)

  • "Thanks to the parent information of each node it is possible to reconstruct the shortest path from start to end."



    shouldn't that be from end to start :p



    Great tutorial!

  • Nice blog! Some comments on A*:



    When you use an admissible heuristic (in your example, the Manhattan distance is probably best), you end up with an interesting situation that you can use for optimization:



    At every step you are removing the node with the best F value and inserting new nodes. What are their F values? They have an F value which is the original F minus the change in H from the old node to the new plus the cost of moving one node. An admissible heuristic underestimates, so the change in H has to be no greater than the cost of moving one node.



    Therefore F never decreases.



    Furthermore, the most F can decrease is bounded by the movement cost + maximum change in H between adjacent nodes. Let's call the bound B.



    So you have a queue where you're pulling out the best one (where F=F0) and you're pushing on new nodes that are at most B worse (F<=F0 + B).



    That means the priority queue (which you have implemented with a binary heap) only has to handle F values from F0 to F0+B. You can do this with buckets, and it can be faster than a priority queue. Neat, eh? (This is similar to radix sort being faster than quicksort -- you can take advantage of your data.)



    In practice (especially in games), you may not have an admissible heuristic, and F may decrease. If F is decreasing most of the time, then you may be better off with a sorted linked list. Insertions are fast because they're mostly at the head of the list; removals are fast because they're always at the head of the list. Another trick is to avoid sorting until necessary (keep a sorted or heap structure for the "good" nodes and an unsorted structure for the "bad" nodes, and when you run out of "good" nodes, you sort the bad ones and move the best ones into the good structure).

  • Correction: I wrote above, "Furthermore, the most F can decrease is ....." when I meant to say "Furthermore, the most F can *increase* is .....".

Comments have been disabled for this content.