Sketch · 2026-05-11
Recursive maze, carved and solved.
A maze, carved one cell at a time, then solved. The carver walks a grid, knocking down walls between cells it hasn't seen yet and backing up whenever it paints itself into a corner. When the grid is full, a breadth-first search floods out from the opening in the top-left corner until it reaches the one in the bottom-right, and the shortest route between them lights up in amber.
How it carves
The generator is a recursive backtracker, also called a depth-first carve. It keeps a stack of cells. At the top of the stack it looks for a neighbour it hasn't visited; if it finds one, it removes the wall between them and pushes the neighbour onto the stack. If every neighbour has already been visited, it pops back to the previous cell and tries again from there. The run ends when the stack empties, which happens only after every cell has been reached exactly once.
Because the carver commits to a direction until it gets stuck, this method produces mazes with long, winding corridors and not many short dead ends. People who study these things call the result a "river" maze: high in passages that meander, low in branching. Other algorithms have other textures. Kruskal's spreads junctions more evenly across the grid, and Wilson's draws an unbiased sample from every maze that grid could hold.
How it solves
The solver is plain breadth-first search. Moving from one cell to an adjacent one always costs the same here, so the first time the search touches the exit it has already found a shortest path there, and there is nothing cleverer left to do. The faint fill marks every cell the search visited before it arrived. The amber line is the path it kept.
Source
The algorithm names and the "river" description follow Jamis Buck, "Mazes for Programmers" (Pragmatic Bookshelf, 2015), and his maze articles at weblog.jamisbuck.org. Breadth-first search is textbook; see Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms".