11520

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2018 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+