Maze Generation

A maze looks like the product of devious planning: twisting corridors, dead ends, exactly one path from start to finish. You'd guess that making one is a delicate craft. It isn't. Generating a random maze is one of the easiest, fastest things a computer can do — and it is genuinely beautiful once you see why.

The trick is a change of view. Picture the grid not as walls but as rooms connected by doors. Every cell is a room; between two neighboring rooms there could be a door. A "perfect" maze — one with no loops and exactly one route between any two points — is simply a way of opening just enough doors to connect every room without ever creating a loop.

That object has a name in mathematics: a spanning tree of the grid. And once you realize a maze is a spanning tree, building one stops being mysterious. It becomes a textbook task you can finish in a single sweep.

Below is a blank grid of rooms, every wall still standing. Press Generate and watch randomized depth-first search wander from room to room, knocking down a wall only when it steps into an unvisited room — never into one already reached.

<p class="hint">{{hint}}</p>
<div id="maze" class="maze"></div>
<div class="status" id="status">{{press_generate}}</div>
<div class="btns">
  <button id="gen" type="button">{{btn_generate}}</button>
  <button id="step" type="button" class="ghost">{{btn_step}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.maze { --n: 10; --s: 30px; position: relative; width: calc(var(--n) * var(--s));
        height: calc(var(--n) * var(--s)); margin: .4rem 0; background: #0d1b2a;
        border: 3px solid #0d1b2a; }
.room { position: absolute; width: var(--s); height: var(--s); background: #1d3557; }
.room.visited { background: #e8eef3; }
.room.head { background: #e63946; }
.door { position: absolute; background: #e8eef3; z-index: 2; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice two things. First, it never backtracks into a loop: a wall falls only on the way to a fresh room, so the opened doors can never close a cycle. Second, when it finishes, every room has been visited and they are all connected — that is exactly a spanning tree. The cell counter shows the work is linear: visit each room once, done. No search, no backtracking blowup, no guessing.

How hard is it to make a maze? The honest answer: easy, and provably so.

• It's a spanning tree. A perfect maze on an n-cell grid is a spanning tree of the grid graph: a connected, loop-free subset of doors touching every room. This is a solved, classical object — spanning trees were understood long before computers.
• Linear time. Randomized DFS and randomized Kruskal both build one in $O(V + E)$ time — proportional to the number of rooms and possible doors. For a grid that's just $O(n)$. You touch each room a constant number of times and stop.
• No combinatorial explosion. There is nothing to search. Greedy local moves are guaranteed to succeed because any maximal loop-free set of doors automatically spans the whole grid.

Contrast this with the opposite question. Generating a maze is trivial; finding the shortest path through a given maze is the classic shortest-path problem (still easy, but more work), and asking the hardest routing questions — visit-every-room-once optimally — lands you on the Traveling Salesman Problem, which is NP-hard. Building structure can be far cheaper than optimizing over it, the same gap that defines P vs NP.

"Connect everything, cheaply, with no redundant loops" is a pattern that shows up far beyond puzzles, and maze generation is its most playful face:

• Procedural game worlds: dungeons, levels and road networks are carved by exactly these spanning-tree algorithms, often with a few loops added back for fun.
• Network bootstrapping: spanning trees keep packets from circling forever; the Spanning Tree Protocol that runs in real switches is the same idea applied to Ethernet.
• Image segmentation: building a minimum spanning tree over pixels groups an image into regions — a workhorse in computer vision.
• Clustering and infrastructure: laying cable or pipe to reach every site with no wasteful loop is a spanning-tree problem at heart.

Understand why a maze is easy to build and you've met the spanning tree — one of the most useful and well-behaved structures in all of graph algorithms.

Maze generation is a quiet reminder that not every interesting problem is hard. Strip away the walls and a perfect maze is just a spanning tree of a grid — and growing a spanning tree is one of the cleanest, fastest tasks we know, finished in a single linear sweep with no backtracking and no guessing.

That's the real lesson hiding behind the corridors: the difficulty of a problem lives in its structure, not its appearance. A maze looks fiendish and builds itself in a blink, while a simpler-looking question about optimal routes can be intractable. The same line that makes maze generation effortless is the one we keep running into — the boundary mapped out by P vs NP.