Carve And Escape

What it is

Watch it carve, watch it search, watch it find the way out. Then it does it again with a new maze.

The nice part is that carving and escaping are the same algorithm. A depth-first walk that pushes forward while it can and backtracks when it can’t. Point it at unvisited cells and it digs a maze, point it at an exit and it solves one.

How it works

The carver keeps a stack. Look at the cell on top, pick a random unvisited neighbour, knock down the wall between them, push it. If there are no unvisited neighbours, pop and try the cell below.

That’s the recursive backtracker, and it produces a perfect maze: every cell reachable, and exactly one route between any two of them.

The solver is the same stack with a different stopping condition, remembering where it came from so it can reconstruct the route once it arrives.

The core returns the sequence of cells each phase touched rather than just the finished maze, so the animation is a replay of a list. None of the timing or drawing code knows anything about mazes.

What surprised me

Not a surprise so much as a satisfying consequence I hadn’t thought through.

Depth-first search is famously not a shortest-path algorithm. It commits to a direction and can wander enormously far out of its way. BUT in a perfect maze there’s only one route between any two cells, so there’s no shorter path for it to miss. Its answer is forced to be optimal, and the test says exactly that: the path length has to equal the breadth-first distance.

That’s a property of the maze rather than of the search, and it stops being true the instant you add a single loop.

That’s a good way to remember what “perfect maze” actually buys you: exactly one passage fewer than there are cells. One more and there’s a loop, one fewer and part of the maze is sealed off. The test for that is a single comparison and it would catch almost any mistake in the carver.

What I would do next

Add a few loops on purpose and watch depth-first stop being optimal.