Comparison of 3 implementations of the A* algorithm

This paper deals with a short presentation of the A* algorithm and the comparison of three different implementations of the algorithm. A* is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). It employs a ”heuristic estimate” that ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A* algorithm is, therefore, an example of a best-first search, which optimizes the depth-first search. What sets A* apart from best-first search is that it also takes the distance already traveled into account. This makes A* complete and optimal, i.e., A* will always find the shortest route if any exists. It is not guaranteed to perform better than simpler search algorithms. In a maze-like environment, the only way to reach the goal might be to first travel one way (away from the goal) and eventually turn around. In this case trying nodes closer to your destination first may cost you time. In addition to finding a path for a unit to move along, pathfinding can be used for several other purposes: exploration, spying, road building, terrain analysis, city building, puzzle solving. So the main application domain is game design.