Introduction

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.

Carve a Maze

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">Each square is a room; every wall could be a door. Press <b>Generate</b> and watch randomized depth-first search carve a maze — it knocks down a wall only when it steps into an <b>unvisited</b> room, so it can never close a loop. The result is a <b>spanning tree</b> of the grid.</p>
<div id="maze" class="maze"></div>
<div class="status" id="status">Press Generate to carve a maze.</div>
<div class="btns">
  <button id="gen" type="button">Generate</button>
  <button id="step" type="button" class="ghost">Step</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A "perfect" maze on an N x N grid is exactly a SPANNING TREE of the grid graph: connect every room with no loops. Randomized depth-first search builds one in O(V+E) — linear time. It carves a door only when moving to an UNVISITED room, so the opened doors can never form a cycle, and every room ends connected.
const N = 10, S = 30;
const maze = document.getElementById('maze');
maze.style.setProperty('--n', N);
maze.style.setProperty('--s', S + 'px');

let visited, stack, head, doors, done, rooms, doorEls;
const idx = (r,c) => r*N + c;
const inB = (r,c) => r>=0 && r<N && c>=0 && c<N;

function build(){
  maze.innerHTML = '';
  rooms = []; doorEls = {};
  for(let r=0;r<N;r++) for(let c=0;c<N;c++){
    const d = document.createElement('div');
    d.className = 'room';
    d.style.left = (c*S)+'px'; d.style.top = (r*S)+'px';
    maze.appendChild(d); rooms[idx(r,c)] = d;
  }
  visited = new Set(); stack = []; doors = new Set(); done = false;
  head = idx(0,0); visited.add(head); stack.push(head);
  rooms[head].classList.add('visited');
}

function carveDoor(a,b){
  const ra=(a/N)|0, ca=a%N, rb=(b/N)|0, cb=b%N;
  const top = Math.min(ra,rb), left = Math.min(ca,cb);
  const d = document.createElement('div'); d.className = 'door';
  if(ra===rb){ // horizontal neighbors -> vertical door slot
    d.style.left = (left*S + S - 2)+'px'; d.style.top = (top*S + 4)+'px';
    d.style.width = '4px'; d.style.height = (S-8)+'px';
  } else {     // vertical neighbors -> horizontal door slot
    d.style.left = (left*S + 4)+'px'; d.style.top = (top*S + S - 2)+'px';
    d.style.width = (S-8)+'px'; d.style.height = '4px';
  }
  maze.appendChild(d);
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }

// One DFS step. Returns false when the maze is complete (spanning tree built).
function step(){
  if(done) return false;
  if(stack.length===0){
    done = true; rooms[head] && rooms[head].classList.remove('head');
    setStatus(fmt('Done: %size% rooms connected by %size2% doors — a spanning tree (V−1 doors).', { size: visited.size, size2: doors.size }), 'ok');
    return false;
  }
  const cur = stack[stack.length-1];
  const r=(cur/N)|0, c=cur%N;
  rooms.forEach(el=>el.classList.remove('head'));
  rooms[cur].classList.add('head');
  const nbrs = [[r-1,c],[r+1,c],[r,c-1],[r,c+1]]
    .filter(([nr,nc]) => inB(nr,nc) && !visited.has(idx(nr,nc)));
  if(nbrs.length===0){ stack.pop(); return true; }
  const [nr,nc] = nbrs[(Math.random()*nbrs.length)|0];
  const next = idx(nr,nc);
  visited.add(next); rooms[next].classList.add('visited');
  const key = cur<next ? cur+'-'+next : next+'-'+cur;
  doors.add(key); carveDoor(cur,next);
  stack.push(next);
  setStatus(fmt('Carving… %size% / %v% rooms reached.', { size: visited.size, v: N*N }));
  return true;
}

let timer = null;
function generate(){
  if(timer){ clearInterval(timer); timer=null; }
  build();
  timer = setInterval(()=>{ if(!step()){ clearInterval(timer); timer=null; } }, 18);
}

document.getElementById('gen').addEventListener('click', generate);
document.getElementById('step').addEventListener('click', ()=>{ if(timer){clearInterval(timer);timer=null;} if(!visited){build();} step(); });
document.getElementById('reset').addEventListener('click', ()=>{ if(timer){clearInterval(timer);timer=null;} build(); setStatus('Press Generate to carve a maze.',''); });
build();
Result
Console

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.

The Real Complexity

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)O(V + E) time — proportional to the number of rooms and possible doors. For a grid that's just O(n)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/maze-generation/Content licensed under CC BY-NC 4.0.