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 contains the nodes already 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 that it could only move horizontally and vertically.

We start with a start point, an end point and 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 if the G-score through the current node is lower than its current G-score. If it is, we change the parent of the node to the current 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 thing for the algorithm is knowing 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.