Wilson’s Algorithm

Wilson’s algorithm uses loop-erased random walks to generate a uniform spanning tree — an unbiased sample of all possible spanning trees. Most other maze generation algorithms, such as Prim’s, random traversal and randomized depth-first traversal, do not have this beautiful property.

The algorithm initializes the maze with an arbitrary starting cell. Then, a new cell is added to the maze, initiating a random walk (shown in magenta). The random walk continues until it reconnects with the existing maze (shown in white). However, if the random walk intersects itself, the resulting loop is erased before the random walk continues.

Initially, the algorithm can be frustratingly slow to watch, as the early random walks are unlikely to reconnect with the small existing maze. However, as the maze grows, the random walks become more likely to collide with the maze and the algorithm accelerates dramatically.

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
    remaining = d3.range(cellWidth * cellHeight), // cell indexes to visit
    previous = new Array(cellWidth * cellHeight), // current random walk path
    i0, x0, y0; // end of current random walk

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)
);

// Add the starting cell.
context.fillStyle = "white";
var start = remaining.pop();
cells[start] = 0;
fillCell(start);

// While there are remaining cells,
// add a loop-erased random walk to the maze.
context.fillStyle = "magenta";
d3.timer(function() {
  for (var k = 0; k < 50; ++k) {
    if (loopErasedRandomWalk()) {
      return true;
    }
  }
});

function loopErasedRandomWalk() {
  var i1;

// Pick a location that’s not yet in the maze (if any).
  if (i0 == null) {
    do if ((i0 = remaining.pop()) == null) return true;
    while (cells[i0] >= 0);
    previous[i0] = i0;
    fillCell(i0);
    x0 = i0 % cellWidth;
    y0 = i0 / cellWidth | 0;
    return;
  }

// Perform a random walk starting at this location,
  // by picking a legal random direction.
  while (true) {
    i1 = Math.random() * 4 | 0;
    if (i1 === 0) { if (y0 <= 0) continue; --y0, i1 = i0 - cellWidth; }
    else if (i1 === 1) { if (y0 >= cellHeight - 1) continue; ++y0, i1 = i0 + cellWidth; }
    else if (i1 === 2) { if (x0 <= 0) continue; --x0, i1 = i0 - 1; }
    else { if (x0 >= cellWidth - 1) continue; ++x0, i1 = i0 + 1; }
    break;
  }

// If this new cell was visited previously during this walk,
  // erase the loop, rewinding the path to its earlier state.
  if (previous[i1] >= 0) eraseWalk(i0, i1);

// Otherwise, just add it to the walk.
  else {
    previous[i1] = i0;
    fillCell(i1);
    if (i1 === i0 - 1) fillEast(i1);
    else if (i1 === i0 + 1) fillEast(i0);
    else if (i1 === i0 - cellWidth) fillSouth(i1);
    else fillSouth(i0);
  }

// If this cell is part of the maze, we’re done walking.
  if (cells[i1] >= 0) {

// Add the random walk to the maze by backtracking to the starting cell.
    // Also erase this walk’s history to not interfere with subsequent walks.
    context.save();
    context.fillStyle = "#fff";
    fillCell(i1);
    while ((i0 = previous[i1]) !== i1) {
      fillCell(i0);
      if (i1 === i0 + 1) cells[i0] |= E, cells[i1] |= W, fillEast(i0);
      else if (i1 === i0 - 1) cells[i0] |= W, cells[i1] |= E, fillEast(i1);
      else if (i1 === i0 + cellWidth) cells[i0] |= S, cells[i1] |= N, fillSouth(i0);
      else cells[i0] |= N, cells[i1] |= S, fillSouth(i1);
      previous[i1] = NaN;
      i1 = i0;
    }
    context.restore();

previous[i1] = NaN;
    i0 = null;
  } else {
    i0 = i1;
  }
}

function eraseWalk(i0, i2) {
  var i1;
  context.save();
  context.globalCompositeOperation = "destination-out";
  do {
    i1 = previous[i0];
    if (i1 === i0 - 1) fillEast(i1);
    else if (i1 === i0 + 1) fillEast(i0);
    else if (i1 === i0 - cellWidth) fillSouth(i1);
    else fillSouth(i0);
    fillCell(i0);
    previous[i0] = NaN;
    i0 = i1;
  } while (i1 !== i2);
  context.restore();
}

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

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

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

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

</script>

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