Dijkstra's and A* Search Algorithms for Pathfinding with Obstacles

This Demonstration finds the shortest path between two green points across a field of black obstacles using either Dijkstra's algorithm or A* search. The process of the search algorithm is shown stepwise, with tiles becoming highlighted as they are scanned. The final path, after the process is complete, is shown in red. You can vary the positions of the starting and end points, the layout of the obstacles and the search algorithm.

This problem is illustrated on a array, with one green cell specified as the start, another as the end, and other black cells occupied by inaccessible obstacles. Movement is allowed in the four cardinal directions as well as diagonally, except past sharp corners of obstacles. The shortest path is found by converting this array to a graph with one vertex for each node of the array, with vertices adjacent if the corresponding tiles are adjacent. Edge costs correspond to Euclidean distance, with a cost of for taking one step in a cardinal direction and for taking a diagonal step.

The two search algorithms, Dijkstra's algorithm and A* search, are common algorithms used for finding shortest paths on a graph (see [1] for detailed descriptions of both).

Dijkstra's algorithm is an iterative process that attempts to find the shortest path from a start vertex to every other vertex. It has been modified in this Demonstration to halt early if it finds the finish vertex. It maintains a list of permanent distances for some vertices and tentative distances for others. Each iteration consists of making one tentative distance permanent and then calculating tentative distances for all neighbors of the new permanent vertex. The animation produced displays the permanent set as dark blue, the tentative set as light blue and the unvisited set as white.

A* search is a modified version of Dijkstra's algorithm. It is a directed search that uses a distance heuristic to preferentially select vertices likely to be closer to the finish vertex. In this case, that heuristic is the Euclidean distance from each vertex to the finish vertex. In general, A* does a good job of moving directly toward the finish over an open area, but because the heuristic does not take obstacles into account, it may take longer to navigate around them.

Reference

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Englewood Cliffs, NJ: Prentice Hall, 1993.