Building a Perfect Maze Generator with DFS Recursive Backtracker#

Maze generation is one of those problems that looks simple until you actually implement it. I recently built an online maze generator on JsonKit using the classic DFS recursive backtracker algorithm. Here’s how it works under the hood.

What is a “Perfect Maze”?#

In computational maze generation, a “perfect maze” has three properties:

• Simply connected: exactly one path between any two cells
• Acyclic: no loops or cycles
• Fully connected: every cell is reachable

Every wall in a perfect maze matters — removing any single wall creates a loop.

The Data Structure#

A maze is just a 2D grid where each cell has four walls:

interface Cell {
  top: boolean      // top wall exists
  right: boolean    // right wall
  bottom: boolean   // bottom wall
  left: boolean     // left wall
  visited: boolean  // visited flag
}

All walls start as true and all cells as unvisited. The algorithm carves paths by knocking down walls until every cell is visited.

DFS Recursive Backtracker: The Algorithm#

How it works#

1. Start at the top-left cell [0,0], mark it visited
2. Collect unvisited neighbors of the current cell
3. If unvisited neighbors exist, pick one at random:
   • Remove the shared wall between current and neighbor
   • Mark neighbor as visited
   • Push neighbor onto the stack
4. If no unvisited neighbors remain, backtrack (pop from stack)
5. Repeat until the stack is empty

The key is using an explicit stack instead of actual recursion. JavaScript’s call stack is limited — a 50×50 maze has 2500 cells, which would overflow real recursion:

function generateMaze(width: number, height: number): Cell[][] {
  const grid = Array.from({ length: height }, () =>
    Array.from({ length: width }, () => ({
      top: true, right: true, bottom: true, left: true,
      visited: false,
    }))
  )

  const stack: [number, number][] = []
  grid[0][0].visited = true
  stack.push([0, 0])

  while (stack.length > 0) {
    const [cx, cy] = stack[stack.length - 1]
    const neighbors: [number, number, number, number][] = []

    if (cy > 0 && !grid[cy - 1][cx].visited)
      neighbors.push([cx, cy - 1, 0, 2])  // up, direction pair 0↔2
    if (cy < height - 1 && !grid[cy + 1][cx].visited)
      neighbors.push([cx, cy + 1, 2, 0])  // down, direction pair 2↔0
    if (cx > 0 && !grid[cy][cx - 1].visited)
      neighbors.push([cx - 1, cy, 3, 1])  // left, direction pair 3↔1
    if (cx < width - 1 && !grid[cy][cx + 1].visited)
      neighbors.push([cx + 1, cy, 1, 3])  // right, direction pair 1↔3

    if (neighbors.length > 0) {
      const [nx, ny, d1, d2] = neighbors[Math.floor(Math.random() * neighbors.length)]
      removeWall(grid[cy][cx], d1)
      removeWall(grid[ny][nx], d2)
      grid[ny][nx].visited = true
      stack.push([nx, ny])
    } else {
      stack.pop() // dead end, backtrack
    }
  }
  return grid
}

The direction encoding trick#

The last two elements of each neighbor tuple encode wall directions (0=top, 1=right, 2=bottom, 3=left), paired so that dir1 on the current cell and dir2 on the neighbor always remove the same shared wall. This avoids four separate if-else blocks.

SVG Rendering: One Path to Rule Them All#

The grid is rendered as SVG. All walls merge into a single <path> element instead of individual <line> elements — smaller file size, better performance:

function renderMazeSVG(grid: Cell[][], width: number, height: number, 
                       cellSize: number): string {
  let paths = ''

  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      const cell = grid[y][x]
      const x1 = x * cellSize, y1 = y * cellSize
      const x2 = (x + 1) * cellSize, y2 = (y + 1) * cellSize

      if (cell.top && !(y === 0 && x === 0))
        paths += `M${x1},${y1} L${x2},${y1} `
      if (cell.right)
        paths += `M${x2},${y1} L${x2},${y2} `
      if (cell.bottom)
        paths += `M${x2},${y2} L${x1},${y2} `
      if (cell.left && !(y === 0 && x === 0))
        paths += `M${x1},${y1} L${x1},${y2} `
    }
  }
  // ...
}

Notice the !(y === 0 && x === 0) guard — the entry cell’s top and left walls stay open so the player can actually enter. The exit (bottom-right) is left open by the same logic.

Why DFS over Other Algorithms?#

DFS wins for a general-purpose tool:

• O(W×H) time: each cell is visited exactly once
• ~50 lines of code: minimal to maintain
• Visually “hard”: long corridors and deep dead-ends make mazes look challenging

A 50×50 maze generates in under a millisecond — no Web Worker needed.

Edge Cases and Polish#

Download as SVG: the tool wraps the SVG string in a Blob and triggers download as maze-20x20.svg. The exported file opens natively in Figma, Illustrator, or any vector editor.

Re-generation: clicking “Regenerate” forces a new random maze by triggering a React state seed update. No page reload required.

Responsive scaling: the SVG uses a fixed viewBox but the container uses max-width and overflow-auto, so large mazes scroll naturally on mobile screens.

Summary#

DFS recursive backtracker is the perfect algorithm for an online maze generator tool: simple to implement, fast to execute, and produces visually satisfying results. The generated SVG files are lightweight, editable, and easy to export.

Try it live at JsonKit Maze Generator — tweak the size and hit generate.

Related tools: JSON Formatter | Base64 Encoder/Decoder | CSS Grid Generator