This post originated from an RSS feed registered with .NET Buzz
by David Cumps.
Original Post: A* Algorithm
Feed Title: David Cumps
Feed URL: http://weblogs.asp.net/cumpsd/rss?containerid=12
Feed Description: A Student .Net Blog :p
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 start to end.
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)
Previous Topic
