Notes about A*

A* (AStar) is a relatively easy to implement pathfinding algorithm. There are good resources that explain the algorithm, so I won't go into detail here:

• A* Pathfinding for Beginners
• Informed Search (A*)
• A* Pathfinding Tutorial

I find the following particulary interesting:

• Closed list does not mean pure path list. It contains the path nodes and all the nodes that were considered as path nodes some of which not being on final path.
• Once the end node is reached, path is constructed by starting from end node and going backwards to parent nodes until start node is reached, i.e. until parent node == null.
• If open list becomes empty (i.e. no more nodes left to consider) before end node is reached, it means there is no path from start to end.
• Switch parent according to G cost.
• If h is admissable (i.e. if h >= hOptimal), A* will find shortest path.

For Java implementation, check out my GitHub repository. Also check out my game Save My Cheese where the mice use A* to find the path to the cheese.

Here is an example demonstrating steps the algorithm takes: