Pathfinding Visualizer, Explained
After reading this you will know how breadth-first search, Dijkstra's algorithm, greedy best-first and A* explore a grid, why A* usually touches fewer cells, and how to read the count of visited cells to compare them fairly.
What the visualizer shows
A grid of cells becomes a graph. Each open cell is a node. Two cells that share an edge are connected, so most cells have four neighbors (up, down, left, right). A wall cell has no connections. The start and goal are two chosen cells. Every algorithm here answers one question: what is the shortest sequence of steps from start to goal that avoids walls?
The screen splits into three states. Unvisited cells are blank. Visited cells (cells the algorithm has already pulled from its queue and examined) light up in the order they are touched. When the goal is reached, the visualizer traces the final path back from goal to start using the parent links each algorithm recorded.
Here is the hook. Put the start at the left, the goal at the right, and leave the space between them open. Dijkstra fans out in a growing diamond and may light up 400 cells before it reaches the goal. A* with the Manhattan heuristic drives almost straight across and lights up perhaps 60. Both return a path of the same length. The difference is entirely in how many cells they had to examine.
When each algorithm is the right choice
The four algorithms trade off three things: whether the path is guaranteed shortest, how many cells get expanded, and whether edge weights matter.
- Breadth-first search (BFS)
- Explores by distance in steps. Optimal when every move costs the same. Ignores weighted terrain, so a costly cell looks identical to a cheap one.
- Dijkstra's algorithm
- Explores by cheapest accumulated cost. Optimal even with weighted terrain. With uniform weights it behaves like BFS but uses a priority queue.
- Greedy best-first
- Expands whichever frontier cell looks closest to the goal by the heuristic alone. Fast, but the path it returns can be longer than optimal.
- A* (A-star)
- Combines Dijkstra's real cost so far with greedy's estimate of the cost remaining. Optimal when the heuristic never overestimates, and usually expands far fewer cells than Dijkstra.
Use BFS to teach the idea and when all moves cost 1. Use Dijkstra when terrain has weights and you still need the guaranteed shortest path. Use A* when you want that same guarantee with less work. Use greedy only when speed matters more than an exact answer.
The cost function and its intuition
A* ranks each cell by a single number:
Here g(n) is the exact cost of the cheapest path found so far from the start to cell n. The term h(n) is the heuristic: an estimate of the remaining cost from n to the goal. Their sum f(n) estimates the total cost of a route that passes through n. A* always expands the frontier cell with the smallest f.
Set h(n) = 0 and every cell is ranked by g alone. That is exactly Dijkstra. Drop g and rank by h alone and you get greedy best-first. A* sits between them, which is why it inherits Dijkstra's optimality and greedy's sense of direction.
The three heuristics differ in how they measure remaining distance on the grid. With cell coordinates (x_1, y_1) and goal (x_2, y_2):
Manhattan sums the horizontal and vertical gaps. It is the right estimate when moves are limited to four directions, because you cannot travel diagonally. Euclidean uses \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}, the straight-line distance. Chebyshev uses \max(|x_1-x_2|, |y_1-y_2|), correct when diagonal moves are allowed and cost the same as a straight move.
A heuristic must never overestimate the true remaining distance, or A* can miss the shortest path. On a four-direction grid, Euclidean is safe because a straight line is never longer than a stepped path, but Chebyshev can overestimate the reverse. Match the heuristic to the moves you allow.
A worked example on the demo grid
Run the demo with its default field values: an open grid, start and goal placed apart, and A* with the Manhattan heuristic. Take a small slice you can check by hand. Put the goal at coordinate (8, 4) and consider a frontier cell at (5, 4) reached after 5 steps from the start.
Computing f for one cell
- The path from start to
(5, 4)took 5 unit moves, so g = 5. - Manhattan distance to the goal: |5-8| + |4-4| = 3 + 0 = 3, so h = 3.
- Rank value: f = 5 + 3 = 8.
Now compare a detour cell at (5, 6), also 5 steps away but two rows off the goal's row. Its h = |5-8| + |6-4| = 3 + 2 = 5, giving f = 5 + 5 = 10. A* prefers (5, 4) because 8 < 10. That single comparison, repeated across the frontier, is why A* leans toward the goal instead of spreading evenly.
The chart below counts cells expanded on an open 40 by 40 grid with start and goal 30 columns apart. The path length is identical for BFS, Dijkstra and A*. Only greedy risks a longer path, though on an open grid it too finds the straight route.
Watching the frontier grow
Use the widget to feel how the h weight reshapes the search. When you scale the heuristic up, A* slides toward greedy: fewer cells, but a growing risk of a suboptimal path once walls appear.
Reading and interpreting the results
Two numbers matter after each run: path length and cells visited. Path length tells you whether the route is optimal. On the same grid, BFS, Dijkstra and A* with an admissible heuristic must report the same length. If greedy reports a longer number, that is the price of ignoring g.
Cells visited measures work. Compare A* against Dijkstra on the same maze. If A* visits 58 cells and Dijkstra visits 640, A* did about 640 / 58 = 11 times less expansion for the same answer. That ratio shrinks as walls force detours, because the heuristic's straight-line guess becomes less accurate.
| Algorithm | Uses g | Uses h | Shortest path | Handles weights |
|---|---|---|---|---|
| BFS | No (counts steps) | No | Yes, uniform cost | No |
| Dijkstra | Yes | No | Yes | Yes |
| Greedy | No | Yes | No | No |
| A* | Yes | Yes | Yes, if h admissible | Yes |
Common mistakes
The most frequent error is mixing a diagonal heuristic with a four-direction grid. If moves are limited to four directions but you use Chebyshev or Euclidean, the estimate can undershoot in a way that still works, or you accidentally allow diagonal moves and then Manhattan overestimates. Keep the heuristic and the move set consistent.
A second mistake is reading greedy's speed as superiority. Greedy expands few cells on open ground, but drop a U-shaped wall in front of the goal and greedy dives straight into the pocket, backtracks, and can return a path much longer than optimal. On that same maze A* still finds the shortest route.
A third is comparing algorithms on different grids. Cell counts only mean something when the walls, start and goal are identical. Draw one maze, then run all four without changing a wall.
To see A*'s advantage most clearly, build a maze with one long corridor and a few dead ends. Dijkstra explores every dead end fully; A* peeks into them and retreats as soon as the accumulated cost g makes their f worse than the corridor.
Related tools
If you want to see the same graph ideas without a grid, the Graph Algorithm Playground runs BFS, DFS, Dijkstra and Prim on a graph you build by clicking. For a different family of algorithms racing on shared input, try the Sorting Algorithm Visualizer. To feel why the expansion counts grow the way they do, the Big-O Complexity Race plots the same growth curves. And for optimal substructure of a different kind, the Dynamic Programming Visualizer fills shortest-edit and knapsack tables cell by cell.
Frequently asked questions
Why does A* visit fewer cells than Dijkstra?
Both track the real cost g, but A* adds the heuristic h that points toward the goal. Cells leading away from the goal get a larger f and wait in the queue. Dijkstra has no sense of direction, so it expands cells in all directions equally. On an open grid this is the difference between 58 cells and 640.
Does A* always find the shortest path?
Only when the heuristic is admissible, meaning it never overestimates the true remaining distance. Manhattan on a four-direction grid is admissible. Multiply the heuristic by a factor above 1 and A* can return a longer path, which the widget shows once a wall is present.
What is the difference between BFS and Dijkstra here?
With uniform weights they explore in the same order and return paths of the same length. BFS uses a simple queue and counts steps. Dijkstra uses a priority queue keyed on accumulated cost, so it also handles weighted terrain where a single cell can cost more than 1.
Why can greedy return a longer path?
Greedy ranks cells by h alone and ignores how far it has already traveled. It commits to whatever looks closest to the goal, so a wall that blocks the straight line sends it on a detour it never reconsiders optimally.
Which heuristic should you pick?
Match it to the allowed moves. Four directions: Manhattan. Eight directions with equal cost: Chebyshev. Diagonal moves that cost the true diagonal distance: Euclidean. Using the wrong one either slows the search or breaks the optimality guarantee.
Related tools
Dynamic Programming Visualizer
Watch edit distance and knapsack fill their tables cell by cell — dynamic programming with the lid off.
Graph Algorithm Playground
Build a graph by clicking, then watch BFS, DFS, Dijkstra and Prim explore it live.
Huffman Coding Visualizer
Type any text and watch the optimal prefix code assemble itself as a tree, rare letters sinking deepest.
Sorting Algorithm Visualizer
Watch bubble, insertion, merge, quick and heap sort race through the same shuffled bars.
Turing Machine Simulator
Watch a Turing machine read, write and shuffle along its tape — computation stripped to its atoms.
Hamming Code Playground
Flip any bit of a Hamming-encoded message and watch the parity checks point straight at the culprit.