Wilson’s Algorithm II

This maze is generated using Wilson’s algorithm and then flooded with color. Hue encodes Manhattan distance from the starting cell. (This is not an optimal visual encoding, but it suffices and is pretty.)

Color is useful to visually compare the structure of mazes; without color, the black and white alternating cells are too noisy to offer any pre-attentive comparisons. Compare a maze generated by Wilson’s algorithm to Prim’s algorithm, random traversal and randomized depth-first traversal.

See this color flood applied directly to the pixel grid.

<!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 = generateMaze(cellWidth, cellHeight), // each cell’s edge bits
    distance = 0,
    visited = new Array(cellWidth * cellHeight),
    frontier = [(cellHeight - 1) * cellWidth];

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 = "#fff";
for (var y = 0, i = 0; y < cellHeight; ++y) {
  for (var x = 0; x < cellWidth; ++x, ++i) {
    fillCell(i);
    if (cells[i] & S) fillSouth(i);
    if (cells[i] & E) fillEast(i);
  }
}

d3.timer(function() {
  if (!(n0 = frontier.length)) return true;

context.fillStyle = d3.hsl(distance++ % 360, 1, .5) + "";

if (distance & 1) {
    for (var i = 0; i < n0; ++i) {
      fillCell(frontier[i]);
    }
  } else {
    var frontier1 = [],
        i0,
        i1,
        n0;

for (var i = 0; i < n0; ++i) {
      i0 = frontier[i];
      if (cells[i0] & E && !visited[i1 = i0 + 1]) visited[i1] = true, fillEast(i0), frontier1.push(i1);
      if (cells[i0] & W && !visited[i1 = i0 - 1]) visited[i1] = true, fillEast(i1), frontier1.push(i1);
      if (cells[i0] & S && !visited[i1 = i0 + cellWidth]) visited[i1] = true, fillSouth(i0), frontier1.push(i1);
      if (cells[i0] & N && !visited[i1 = i0 - cellWidth]) visited[i1] = true, fillSouth(i1), frontier1.push(i1);
    }

frontier = frontier1;
  }
});

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

function generateMaze(width, height) {
  var cells = new Array(width * height), // each cell’s edge bits
      remaining = d3.range(width * height), // cell indexes to visit
      previous = new Array(width * height); // current random walk

// Add the starting cell.
  var start = remaining.pop();
  cells[start] = 0;

// While there are remaining cells,
  // add a loop-erased random walk to the maze.
  while (!loopErasedRandomWalk());

return cells;

function loopErasedRandomWalk() {
    var i0,
        i1,
        x0,
        y0;

// Pick a location that’s not yet in the maze (if any).
    do if ((i0 = remaining.pop()) == null) return true;
    while (cells[i0] >= 0);

// Perform a random walk starting at this location,
    previous[i0] = i0;
    while (true) {
      x0 = i0 % width;
      y0 = i0 / width | 0;

// picking a legal random direction at each step.
      i1 = Math.random() * 4 | 0;
      if (i1 === 0) { if (y0 <= 0) continue; --y0, i1 = i0 - width; }
      else if (i1 === 1) { if (y0 >= height - 1) continue; ++y0, i1 = i0 + width; }
      else if (i1 === 2) { if (x0 <= 0) continue; --x0, i1 = i0 - 1; }
      else { if (x0 >= width - 1) continue; ++x0, i1 = i0 + 1; }

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

// 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.
        while ((i0 = previous[i1]) !== i1) {
          if (i1 === i0 + 1) cells[i0] |= E, cells[i1] |= W;
          else if (i1 === i0 - 1) cells[i0] |= W, cells[i1] |= E;
          else if (i1 === i0 + width) cells[i0] |= S, cells[i1] |= N;
          else cells[i0] |= N, cells[i1] |= S;
          previous[i1] = NaN;
          i1 = i0;
        }

previous[i1] = NaN;
        return;
      }

i0 = i1;
    }
  }

function eraseWalk(i0, i2) {
    var i1;
    do i1 = previous[i0], previous[i0] = NaN, i0 = i1; while (i1 !== i2);
  }
}

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

</script>

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