A
ReadyBFS
Shortest pathVisited cells0
Frontier0
Path length—
Compute time0 ms
Animation0.00 s
Choose Visualize, or step through one expansion at a time.21 × 35
THE PATHFINDING LABORATORY
Every wall is a question.
Find your way through.
Build a maze. Follow the search. See why the algorithm matters.
06 ALGORITHMSOne maze.
Different minds.4 directions · 1 move = 1 cost
Different minds.4 directions · 1 move = 1 cost
S StartF Finish Wall Frontier Explored PathDrag markers · Paint walls · Editing resets the search
B
ReadyA*
Shortest pathVisited cells0
Frontier0
Path length—
Compute time0 ms
Animation0.00 s
Both panels use the same maze and markers.21 × 35
SAME MAZE. SAME ENDPOINTS.
The results, side by side.
| Algorithm | Visited | Frontier | Path (moves) | Compute | Animation | Result |
|---|
Identical input, one expansion per playback step for each algorithm. Different shortest paths can have the same optimal length. Timings are measured locally and are not a rigorous benchmark.
UNDER THE HOOD
Breadth-first, one layer at a time.
READ THE EXPERIMENT
Speed is a playback setting.
Compute time counts algorithm work and trace recording in a background worker. It excludes animation delays and drawing. Animation counts active playback time and excludes pauses.
Visited counts unique expanded cells; frontier counts unique cells waiting in either search direction. A cell can be explored by one direction and still wait in the other. A path’s length is its number of moves, not cells.
On mobile, choose Pan to scroll a wide grid, then switch back to Draw. Keyboard: arrows move the cursor, Space changes a wall, S / F place markers.
Why Bidirectional A* is still optimal
Let hₜ(v) and hₛ(v) be Manhattan distances to the finish and start. Define p(v) = (hₜ(v) − hₛ(v)) / 2. The forward queue uses gF(v) + p(v); the backward queue uses gB(v) − p(v). These are balanced potentials.
For adjacent cells, |p(v) − p(u)| ≤ 1. Reweighting an edge to 1 + p(v) − p(u) therefore gives a nonnegative cost. Both searches are Dijkstra searches on the same reweighted graph, in opposite directions. Every start-to-finish path receives the same added constant p(t) − p(s), so shortest paths are preserved.
Each shared discovered cell supplies an upper bound μ on route length. Stop only when min(gF + p) + min(gB − p) ≥ μ, or a frontier is exhausted. This is the usual bidirectional Dijkstra lower-bound rule after canceling the potential constants. A first meeting updates μ; it does not bypass the bound. The implementation doubles all keys so these comparisons use exact integers.
BFS variants use distance-ordered queues. Bidirectional BFS applies the corresponding rule min(gF) + min(gB) ≥ μ. A* uses a consistent Manhattan heuristic; Dijkstra uses nonnegative unit costs. DFS promises reachability, not optimality.
V is the number of open cells and E the number of links between four-directional neighbors. E ≤ 4V, so the queue/stack algorithms take O(V) on this grid and the binary-heap implementations take O(V log V). Algorithm state and the recorded trace each use O(V) space on this grid.
Further reading: Goldberg’s point-to-point shortest-path lecture (Princeton PDF) ↗.