Details

The A* algorithm is a path-finding algorithm that is widely used owing to its performance and accuracy. It can be seen as an extension of Dijkstra's algorithm, which it outperforms with the aid of a heuristic function to guide its search.

With an admissible heuristic, the algorithm is guaranteed to return the shortest path. If the heuristic is also monotonic, the algorithm is simplified considerably and the reconstruction of the shortest path becomes particularly easy. Otherwise, dynamic programming must be used to obtain the shortest path.

The number of nodes that the algorithm must visit depends, among other things, on the specific characteristics of the heuristic function as well as the manner in which the neighbors of a node are computed. This Demonstration allows you to try different combinations of neighboring nodes, computations and heuristic functions. Brief descriptions of these functions follow.

The function getNeighborsPlus returns all the non-obstacle nodes that are above, below, to the right and to the left of a given node.

The function getNeighborsPlusCross returns all the non-obstacle nodes that are returned by getNeighborsPlus, as well as the non-obstacle diagonal nodes to the top-right, top-left, bottom-left and bottom-right of a given node.

The heuristic function minOfXYDiff computes the and distances between a given node and the destination and returns the smaller of the two values as the estimate.

The heuristic function maxOfXYDiff computes the and distances between a given node and the destination and returns the larger of the two values as the estimate.

The better the heuristic estimates the actual distance between a node and the destination, the fewer the nodes that the algorithm must search in order to find a shortest path. It is easy to see that in this Demonstration, maxOfXYDiff is always the better estimate, as a result of which the algorithm expands fewer nodes than in the case of minOfXYDiff.