curlup · August 29, 2015 14:03 · Jun 28, 2014 · Jun 18, 2014 · Jun 18, 2014 · May 9, 2014
diff --git a/index.html b/index.html
@@ -30,7 +30,7 @@
         i0,
         n0 = frontier.length,
         i1,
-        color = d3.hsl((distance += .5) % 360, 1, .5).rgb();
+        color = d3.hsl((distance += .0015) % 360, .5 + (distance/10) % .5, .25 + (distance) % .5).rgb();
 
     for (var i = 0; i < n0; ++i) {
       i0 = frontier[i] << 2;

diff --git a/thumbnail.png b/thumbnail.png
diff --git a/README.md b/README.md
@@ -1,3 +1,3 @@
-A minimum spanning tree of the canvas is generated using [randomized depth-first traversal](/mbostock/1ef3b1fb9eb35ca8ffff). Hue encodes [Manhattan distance](http://en.wikipedia.org/wiki/Taxicab_geometry) from the start. (This is not an optimal visual encoding, but it suffices and is pretty.)
+A [spanning tree](http://en.wikipedia.org/wiki/Spanning_tree) of the canvas is generated using [random traversal](/mbostock/70a28267db0354261476) and then flooded with color. Hue encodes [Manhattan distance](http://en.wikipedia.org/wiki/Taxicab_geometry) from the root of the tree. (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](/mbostock/97f1cdb9e0a695cd8df4), and compare color floods of spanning trees generated by [Prim’s algorithm](/mbostock/11377353), [Wilson’s algorithm](/mbostock/11363008) and [random traversal](/mbostock/11337835).
+Spanning trees can also be used to generate mazes. See a maze generated with randomized depth-first traversal [flooded with color](/mbostock/97f1cdb9e0a695cd8df4), and compare color floods of spanning trees generated by [random traversal](/mbostock/11337835), [Prim’s algorithm](/mbostock/11377353), and [Wilson’s algorithm](/mbostock/11363008).
diff --git a/generate-randomized-depth-first-traversal.js b/generate-randomized-depth-first-traversal.js
@@ -0,0 +1,61 @@
+var N = 1 << 0,
+    S = 1 << 1,
+    W = 1 << 2,
+    E = 1 << 3;
+
+self.addEventListener("message", function(event) {
+  postMessage(generateMaze(event.data.width, event.data.height));
+});
+
+function generateMaze(cellWidth, cellHeight) {
+  var cells = new Array(cellWidth * cellHeight), // each cell’s edge bits
+      frontier = [];
+
+  var start = (cellHeight - 1) * cellWidth;
+  cells[start] = 0;
+  frontier.push({index: start, direction: N});
+  frontier.push({index: start, direction: E});
+  shuffle(frontier, 0, 2);
+  while (!exploreFrontier());
+  return cells;
+
+  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
+
+    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;
+
+      var m = 0;
+      if (y1 > 0 && cells[i1 - cellWidth] == null) frontier.push({index: i1, direction: N}), ++m;
+      if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S}), ++m;
+      if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W}), ++m;
+      if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E}), ++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;
+}
diff --git a/index.html b/index.html
@@ -1,94 +1,62 @@
 <!DOCTYPE html>
 <meta charset="utf-8">
-<body>
+<canvas width="960" height="500"></canvas>
 <script src="http://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);
+var canvas = d3.select("canvas"),
+    context = canvas.node().getContext("2d"),
+    width = canvas.property("width"),
+    height = canvas.property("height");
+
+var worker = new Worker("generate-randomized-depth-first-traversal.js");
+worker.postMessage({width: width, height: height});
+worker.addEventListener("message", function(event) {
+  worker.terminate();
+
+  var N = 1 << 0,
+      S = 1 << 1,
+      W = 1 << 2,
+      E = 1 << 3;
+
+  var cells = event.data,
+      distance = 0,
+      visited = new Array(width * height),
+      frontier = [(height - 1) * width],
+      image = context.createImageData(width, height);
+
+  function flood() {
+    var frontier1 = [],
+        i0,
+        n0 = frontier.length,
+        i1,
+        color = d3.hsl((distance += .5) % 360, 1, .5).rgb();
+
+    for (var i = 0; i < n0; ++i) {
+      i0 = frontier[i] << 2;
+      image.data[i0 + 0] = color.r;
+      image.data[i0 + 1] = color.g;
+      image.data[i0 + 2] = color.b;
+      image.data[i0 + 3] = 255;
+    }
+
+    for (var i = 0; i < n0; ++i) {
+      i0 = frontier[i];
+      if (cells[i0] & E && !visited[i1 = i0 + 1]) visited[i1] = true, frontier1.push(i1);
+      if (cells[i0] & W && !visited[i1 = i0 - 1]) visited[i1] = true, frontier1.push(i1);
+      if (cells[i0] & S && !visited[i1 = i0 + width]) visited[i1] = true, frontier1.push(i1);
+      if (cells[i0] & N && !visited[i1 = i0 - width]) visited[i1] = true, frontier1.push(i1);
+    }
+
+    frontier = frontier1;
+    return !frontier1.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;
-}
+  d3.timer(function() {
+    for (var i = 0, done; i < 20 && !(done = flood()); ++i);
+    context.putImageData(image, 0, 0);
+    return done;
+  });
+});
 
 </script>
diff --git a/thumbnail.png b/thumbnail.png
diff --git a/README.md b/README.md
@@ -0,0 +1,3 @@
+A minimum spanning tree of the canvas is generated using [randomized depth-first traversal](/mbostock/1ef3b1fb9eb35ca8ffff). Hue encodes [Manhattan distance](http://en.wikipedia.org/wiki/Taxicab_geometry) 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](/mbostock/97f1cdb9e0a695cd8df4), and compare color floods of spanning trees generated by [Prim’s algorithm](/mbostock/11377353), [Wilson’s algorithm](/mbostock/11363008) and [random traversal](/mbostock/11337835).
diff --git a/index.html b/index.html
@@ -0,0 +1,94 @@
+<!DOCTYPE html>
+<meta charset="utf-8">
+<body>
+<script src="http://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>
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,3 @@
		A minimum spanning tree of the canvas is generated using [randomized depth-first traversal](/mbostock/1ef3b1fb9eb35ca8ffff). Hue encodes [Manhattan distance](http://en.wikipedia.org/wiki/Taxicab_geometry) 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](/mbostock/97f1cdb9e0a695cd8df4), and compare color floods of spanning trees generated by [Prim’s algorithm](/mbostock/11377353), [Wilson’s algorithm](/mbostock/11363008) and [random traversal](/mbostock/11337835).