Math
Breadth and depth
Two copies of one maze, two traversals, one cell per tick. The layer breadth-first finds a cell on is the shortest distance - an identity. Depth-first is never shorter, and how much longer depends on where you are going.
What happens
One maze, two searches, one discovery per step. On the left breadth-first search takes cells from a QUEUE - first in, first out - so it spreads in rings, and the ring at which it finds a cell is that cell's shortest distance: in an unweighted maze breadth-first IS the shortest-path search. On the right depth-first search takes them from a STACK - last in, first out - so it dives into the first turn and backs out only at a dead end; its route is a route, with no promise of being short. Blue cells wait in the structure, grey-green ones are finished, the gold square is being expanded, and under each maze the real queue and stack are listed with the next cell first. Draw walls, click in a maze to predict where that search goes next, then step. If the goal is walled off, both searches end at the edge of the start's component and say so.
Equations used in the module
Equations maze on an m x m grid, four neighbours, start in the top left corner; neighbour order up, right, down, left - the same in both searches breadth-first: the layer a cell is found on IS the length of the shortest path - an identity, checked against an INDEPENDENT relaxation to a fixed point and, on small grids, against a full enumeration of simple paths empty grid: distance to (i, j) = i + j; cells at distance d = min(d, m−1) − max(0, d−m+1) + 1; widest layer = m at d = m − 1; far corner = 2(m−1) = 40 at m = 21 both searches cover the SAME set - the component of the start, counted independently by a disjoint-set forest - and each looks at every edge twice: 2|E| = 1196 at 21x21 with 20 % walls depth-first is never shorter, and how much longer depends on the CELL: to the far corner of an empty grid it takes the same 2(m−1) steps, to the cell one step below the start it takes 421 at m = 21 on an empty grid the depth-first tree is a HAMILTONIAN PATH - every cell has at most one child, the deepest sits at m²−1, and parity decides where the snake ends: (1,0) for even m, (m−1,0) for odd m 21x21, 20 % walls, goal in the far corner: breadth 40 steps after touching 370 cells; depth 50 steps after touching 53 - both pay, in different coin the same maze, goal in the centre: breadth 20, depth 156; and on 297 of the 371 reachable cells the depth-first route is at least three times longer
