block by mbostock 11167589

Random Traversal II

Full Screen

This maze is generated by random traversal 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 random traversal to randomized depth-first traversal, Wilson’s algorithm and Prim’s algorithm.

See this color flood applied directly to the pixel grid.

index.html

<!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(cellWidth, cellHeight) {
  var cells = new Array(cellWidth * cellHeight),
      frontier = [],
      startIndex = (cellHeight - 1) * cellWidth;

  cells[startIndex] = 0;
  frontier.push({index: startIndex, direction: N});
  frontier.push({index: startIndex, direction: E});

  while ((edge = popRandom(frontier)) != null) {
    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

    if (d0 === N) x1 = x0, y1 = y0 - 1, d1 = S;
    else if (d0 === S) x1 = x0, y1 = y0 + 1, d1 = N;
    else if (d0 === W) x1 = x0 - 1, y1 = y0, d1 = E;
    else x1 = x0 + 1, y1 = y0, d1 = W;

    if (open) {
      cells[i0] |= d0, cells[i1] |= d1;
      if (y1 > 0 && cells[i1 - cellWidth] == null) frontier.push({index: i1, direction: N});
      if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S});
      if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W});
      if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E});
    }
  }

  return cells;
}

function popRandom(array) {
  if (!array.length) return;
  var n = array.length, i = Math.random() * n | 0, t;
  t = array[i], array[i] = array[n - 1], array[n - 1] = t;
  return array.pop();
}

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

</script>