After taking a series of coding challenges focused on graph problems, I was inspired to dig a little into the most common pathfinding algorithms. To help getting a better understanding of exactly how they work, I build a visualization tool to help show how they work.
The tool shows how depth-first, breadth-first, Dijkstra, and A* searches function on a connected grid. Nodes are drawn in different colors to represent unvisited, queued, and visited nodes. The user can click on nodes to deactivate them and turn them into obstacles. If a path can be found, it will be highlighted.
All of these algorithms work by recursively popping a node from the queue, checking whether it's the end node, then enqueuing its children to be examined in the next step. They differ in one primary aspect: the type of queue used to select the next node for processing.
Depth-First and Breadth-First search each use simple queues, LIFO and FIFO respectively. LIFO ensures that Depth-First will prioritize moving farther away from the starting point over circling around it. FIFO, in contrast, prioritizes nodes fewer moves from the start. How efficient they are depends greatly upon the relative positions of the start and end. Depth-First may start searching in the opposite direction of the goal and Breadth-First always spirals around the graph, even if the goal is very far away.
Dijkstra and A* are more sophisticated in that they attempt to prioritize checking nodes that are closer to the goal. Dijkstra does this by tracking how far each node is from the start. On a simple grid, where adjacent nodes are all unit 1 away from each other, this behaves the same as breadth-first search. But on a graph with weighted edges, it will prioritize paths whose edges total to the shortest length.
A* takes things a step further. It accounts for not only a node's distance from the start, but also its distance from the goal. To do so, it needs a heuristic function. In this example, it uses the Euclidean distance between the two points. Consequently, it always searches in the direction of the goal. If an obstacle is placed in its way, it can't predict that, but when it runs into said obstacle, it will intelligently prioritize which nodes to check to try and get around it.