Randomized Depth-First

This maze generation algorithm uses randomized depth-first traversal. Starting in the bottom-left corner, the algorithm keeps an array of the possible directions the maze could be extended (shown in pink). At each step, the maze is extended in a random direction from the previous cell, as long as doing so does not reconnect with another part of the maze.

Compare this algorithm to random traversal, Prim’s algorithm on a randomly-weighted graph, and Wilson’s algorithm for a uniform spanning tree. The global structure of the maze can be more easily seen by flooding it with color.

<!DOCTYPE html>
<meta charset="utf-8">
<style>

body {
  background: #000;
}

</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var width = 960,
    height = 960;

var N = 1 << 0,
    S = 1 << 1,
    W = 1 << 2,
    E = 1 << 3;

var cellSize = 4,
    cellSpacing = 4,
    cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
    cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
    cells = new Array(cellWidth * cellHeight), // each cell’s edge bits
    frontier = [];

var canvas = d3.select("body").append("canvas")
    .attr("width", width)
    .attr("height", height);

var context = canvas.node().getContext("2d");

context.translate(
  Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
  Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2)
);

context.fillStyle = "white";

// Add a random cell and two initial edges.
var start = (cellHeight - 1) * cellWidth;
cells[start] = 0;
fillCell(start);
frontier.push({index: start, direction: N});
frontier.push({index: start, direction: E});

// Explore the frontier until the tree spans the graph.
d3.timer(function() {
  var done, k = 0;
  while (++k < 50 && !(done = exploreFrontier()));
  return done;
});

function exploreFrontier() {
  if ((edge = frontier.pop()) == null) return true;

var edge,
      i0 = edge.index,
      d0 = edge.direction,
      i1 = i0 + (d0 === N ? -cellWidth : d0 === S ? cellWidth : d0 === W ? -1 : +1),
      x0 = i0 % cellWidth,
      y0 = i0 / cellWidth | 0,
      x1,
      y1,
      d1,
      open = cells[i1] == null; // opposite not yet part of the maze

context.fillStyle = open ? "white" : "black";
  if (d0 === N) fillSouth(i1), x1 = x0, y1 = y0 - 1, d1 = S;
  else if (d0 === S) fillSouth(i0), x1 = x0, y1 = y0 + 1, d1 = N;
  else if (d0 === W) fillEast(i1), x1 = x0 - 1, y1 = y0, d1 = E;
  else fillEast(i0), x1 = x0 + 1, y1 = y0, d1 = W;

if (open) {
    fillCell(i1);
    cells[i0] |= d0, cells[i1] |= d1;
    context.fillStyle = "magenta";

function fillCell(index) {
  var i = index % cellWidth, j = index / cellWidth | 0;
  context.fillRect(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing, cellSize, cellSize);
}

function fillEast(index) {
  var i = index % cellWidth, j = index / cellWidth | 0;
  context.fillRect((i + 1) * (cellSize + cellSpacing), j * cellSize + (j + 1) * cellSpacing, cellSpacing, cellSize);
}

function fillSouth(index) {
  var i = index % cellWidth, j = index / cellWidth | 0;
  context.fillRect(i * cellSize + (i + 1) * cellSpacing, (j + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
}

function shuffle(array, i0, i1) {
  var m = i1 - i0, t, i, j;
  while (m) {
    i = Math.random() * m-- | 0;
    t = array[m + i0], array[m + i0] = array[i + i0], array[i + i0] = t;
  }
  return array;
}

d3.select(self.frameElement).style("height", height + "px");

</script>

https://d3js.org/d3.v3.min.js