Pathfinding Algorithms Visualization

Select search settings and press the green "Play" button to visualize the search. To edit the map, click and drag on the map with a tile type selected. You can also generate obstacles by selecting an option in the dropdown menu and pressing the "Generate Obstacles" button.

This is a visualization of a few of the most common pathfinding algorithms acting on a square grid with diagonal movement prohibited. A pathfinding algorithm, as you might expect, finds a path between two points (in this case, the blue and red squares). They have to consider obstacles which block them or slow them down. The two most important attributes of a pathfinding algorithm are its speed and the quality of the paths it generates. Typically, it is difficult to improve one without worsening the other, so each algorithm offers its own tradeoff.

The Algorithms

Dijkstra's Algorithm - Dijkstra's algorithm explores the environment incrementally from the start point. It maintains a "frontier" of points which it has yet to explore, all approximately the same distance from the start (in this case, distance refers to the time it takes to reach one point from another, considering obstacles which slow down or block movement). At each step of the algorithm, it selects the closest frontier point to the start and adds all that point's neighbors to the frontier. It records how it got to each point so it can produce a path later. When the end point is added to the frontier, the algorithm is finished and the path from start to end can be produced. Dijkstra's algorithm is guaranteed to find the shortest path between two points, even considering obstacles which would slow down but not halt movement along the path. Unfortunately, it is quite slow, but it can be improved fairly easily.

A* (A-star) - A* is a modification of Dijkstra's algorithm which is usually faster. Instead of always picking the closest frontier point to the start to expand upon, A* gives some priority to points which have a lower straight-line distance to the destination. Therefore, A* needs to have a rough idea of the destination's location, so that it can prioritize the search in that direction. Like Dijkstra's algorithm, A* guarantees the shortest path when configured correctly, and it's usually significantly faster.

Greedy Best-First Search - Greedy search maintains a frontier like A* and Dijkstra's, but it always explores the frontier node with the lowest straight-line distance to the destination. It always makes a beeline for the end point before considering other routes. Greedy search is very fast, but it does not guarantee the shortest path.

Breadth-First Search - Breadth-First Search, or BFS, is very similar to Dijkstra's algorithm. The main difference is that instead of recording the distance from each frontier point to the start, it records how many steps it takes to reach the frontier points, regardless of whether an area would slow down travel. This means all the frontier points are always the same number of steps away from the start. BFS is guaranteed to find the shortest path if none of the environment is weighted (in this visualization, that means no forests or water). It does not guarantee the shortest path if there are weighted nodes.

Depth-First Search - Depth-First Search, or DFS, finds paths in essentially the same way that a human would solve a maze. It travels as far as it can down a path until it reaches a place where it can't go anywhere it hasn't already been, a dead end. Then, it backtracks until it is next to an unexplored area and begins the process again. DFS generally finds pretty ridiculous paths, and it is only decent at solving mazes. However, it is quite useful in other contexts and it is fun to watch.

Colorful BFS - This is just BFS, but it colors each explored point based on how far it is from the start, unweighted. I added it after seeing this visualization while I was researching maze generation algorithms.

This Demo

This demo shows off how these algorithms work. The map is a square grid with diagonal movement prohibited. The "forest" and "water" tiles slow down movement by the "weight" displayed in the tooltips that appear over them. To execute a search, press the green play button. You can generate map obstacles automatically by selecting a setup using the dropdown and pressing "Generate Obstacles". You can also change the map size and search speed in "Advanced Settings".

During most of the searches, the unexplored areas of the map are darkened, the explored areas are light, and the frontier is a little bit dark. In DFS, red areas have been fully explored and ruled out as potential paths. The "Steps" counter below the play button keeps track of how long the algorithm has taken to find a path. In reality, a computer could perform hundreds of thousands of these steps every second, but seeing it slowed down shows how the algorithms balance efficiency and optimality. In real-world applications, finding a path could requre many millions of search steps, so efficiency is still important.

Some particularly interesting searches are DFS in a "Random Walls" or empty map and colorful BFS in a maze. DFS is interesting because it takes some very bizarre and snakelike routes and typically finds an extremely circuitous route to the destination. Colorful BFS in a maze looks good. Like I said earlier, I added it after seeing this visualization of Wilson's algorithm, the maze generation algorithm I ended up using. That algorithm is actually pretty entertaining to watch and is very nice because it generates an unbiased maze randomly selected from the universe of possible mazes.