block by milroc ddf59aef0c377b27b781

ddf59aef0c377b27b781

Full Screen

A minimum spanning tree of the canvas is generated using randomized depth-first traversal. Hue encodes Manhattan distance from the start. (This is not an optimal visual encoding, but it suffices and is pretty.)

Randomized depth-first traversal can also be used to generate mazes. See a maze generated with randomized depth-first traversal flooded with color, and compare color floods of spanning trees generated by Prim’s algorithm, Wilson’s algorithm and random traversal.

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var width = 960,
    height = 500;

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

var cells = new Array(width * height), // 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"),
    image = context.createImageData(1, 1);

// Add a random cell and two initial edges.
var start = (height - 1) * width;
cells[start] = 0;
context.fillStyle = d3.hsl(0, 1, .5) + "";
context.fillRect(0, height - 1, 1, 1);
frontier.push({index: start, direction: N, distance: 1});
frontier.push({index: start, direction: E, distance: 1});

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

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

  var edge,
      i0 = edge.index,
      d0 = edge.direction,
      i1;

  if (d0 === N) i1 = i0 - width;
  else if (d0 === S) i1 = i0 + width;
  else if (d0 === W) i1 = i0 - 1;
  else i1 = i0 + 1;

  if (cells[i1] == null) { // not yet part of the maze
    var x0 = i0 % width,
        y0 = i0 / width | 0,
        x1,
        y1,
        d1,
        z0 = edge.distance,
        z1 = z0 + 1,
        color = d3.hsl(z0 % 360, 1, .5).rgb();

    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;

    cells[i0] |= d0, cells[i1] |= d1;

    image.data[0] = color.r;
    image.data[1] = color.g;
    image.data[2] = color.b;
    image.data[3] = 255;
    context.putImageData(image, x1, y1);

    var m = 0;
    if (y1 > 0 && !cells[i1 - width]) frontier.push({index: i1, direction: N, distance: z1}), ++m;
    if (y1 < height - 1 && !cells[i1 + width]) frontier.push({index: i1, direction: S, distance: z1}), ++m;
    if (x1 > 0 && !cells[i1 - 1]) frontier.push({index: i1, direction: W, distance: z1}), ++m;
    if (x1 < width - 1 && !cells[i1 + 1]) frontier.push({index: i1, direction: E, distance: z1}), ++m;
    shuffle(frontier, frontier.length - m, frontier.length);
  }
}

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

</script>