How a computer draws a perfect maze (without cheating)

The other day I was stuck in a boring line, my phone almost dead, and I did the most analog thing imaginable: I grabbed the little notebook I always carry and started doodling a maze by hand. You know, the kind from a puzzle magazine. And then came the usual frustration: either I left a dead end stranded in the middle of nowhere, or — worse — I accidentally drew a path so obvious you could solve the maze before I'd finished drawing it. I stared at it and thought: "how does a computer get this right, every single time, without cheating?"

I got home and couldn't let the idea go. I dug in, rewrote the algorithm from scratch, and the result is right below — you'll watch the computer knocking the walls down one by one, live. But first let me show you the trick, because it's simpler (and prettier) than it looks.

What a "perfect" maze actually is

Maze theory has a precise term for the thing I kept trying (and failing) to draw by hand: the perfect maze. The definition is elegant: between any two points in the maze there is exactly one path. Not zero (no isolated, unreachable areas), not two or more (no shortcuts or loops). One, and only one.

This has a beautiful consequence: a perfect maze has no cycles and no isolated pockets. If you're a math person, you already smell it — this is literally a tree. Each cell is a node, and the passages are the edges connecting nodes without ever closing a loop. The problem "draw a perfect maze" is really the problem "grow a tree that covers every cell." Mathematicians call that a spanning tree.

When I drew by hand, this is exactly where I failed: without realizing it, I'd close a loop (creating two paths to the same place) or leave a region floating. The computer isn't "more careful" — it just follows a rule that makes mistakes impossible.

The idea: start with everything blocked, then carve

The most intuitive way to generate a perfect maze starts from the opposite of what you'd expect. Instead of drawing paths, you start with a grid where every wall exists — each cell is a sealed cell, walled off on all sides. Nothing connects to anything.

Then you "carve." The most charming algorithm for this is recursive backtracking (a depth-first search, or DFS). It goes like this:

1. Pick a starting cell and mark it visited.
2. Look at its neighbours that have not been visited yet.
3. If there's at least one, pick a random one, knock down the wall between the two cells, move there, and push the previous cell onto the stack.
4. If there's no unvisited neighbour (you're at a dead end), backtrack by popping the stack until you find a cell that still has a new path to explore.
5. Repeat until the stack is empty. When it empties, every cell has been visited — and the maze is done.

The secret that guarantees perfection is a single rule: you only knock down a wall toward an unvisited cell. Since each cell is visited exactly once, you never create a second path to it. No second path, no loop. No loop, a tree. A tree = a perfect maze. It's nearly impossible to get wrong — and that's exactly what my notebook was missing.

It's counterintuitive but it works: to guarantee one path between any two points, you never think about the two points. You just follow the local rule "never revisit anyone" — and the global property comes out for free.

Why "recursive," but with a stack?

The textbook version is recursive: the function calls itself for each new cell. Pretty on paper, but on big mazes the browser's call stack overflows (Maximum call stack size exceeded — I've taken that one to the face). The solution I used here swaps JavaScript's recursion for an explicit stack (an array). It's the same algorithm, the same visit order, except I drive the stack by hand — and as a bonus it's easy to animate: each frame I take one tiny step and draw where the current cell and the stack are.

Two curiosities I loved

• The algorithm's "bias" has a look. Recursive backtracking produces mazes with long, winding corridors and few junctions — a very recognizable style. Other methods have other "signatures": Prim's algorithm makes mazes full of short dead ends; Wilson's generates perfectly "unbiased" mazes with no bias at all. You can recognize which algorithm built a maze just by looking at its texture. I think that's beautiful.
• Solving is easier than generating. Because a perfect maze is a tree, finding the path from start to finish is trivial: there's no costly wrong turn, because there are no loops to trap you walking in circles. A simple search finds the one path. I added a "solve" button to the toy so you can see it — it lights up the single route.

My honest take

This is, by far, one of my favorite algorithms to show beginners — and there's no heavy math in it. It captures an idea I use all the time in real work: simple local rules produce correct global structures. You don't have to orchestrate the whole outcome from above; you define the small step well and the guarantee emerges. It's the same principle behind procedural level generation in games, automatic circuit layout, even network routing.

And there's the human side: I failed by hand not from lack of intelligence, but from lack of a rule that stopped me from accidentally cheating. A big part of programming well is exactly that — designing constraints that make the mistake impossible, instead of hoping you won't make it.

Enough talk — generate one 👇

Below is the generator I wrote: pure JavaScript, on a <canvas>, with no libraries at all. Play with the size and speed sliders, hit "generate again" as many times as you like, and — if you want to watch the algorithm work — keep it in animated mode to follow the current cell (highlighted) and the stack (the trail) knocking down wall after wall. When it's done, click "solve" to watch the single path light up.

If you generated a maze or two up there, thanks for making it this far. This is more or less how I work: I take a silly everyday frustration — a doodle that wouldn't close — and turn it into a tool that actually works, teaches something, and is fun to play with. If you have a project in mind that needs to work right, every time, without cheating, I'd love to hear about it. Want to chat?