D3 Examples - Paletted Spanning Tree using Wilson's Algorithm

Paletted Spanning Tree using Wilson's Algorithm

Adapted from Mike Bostock's example (detailed below) by Tristan Davies and Andy Rossmeissl to cycle through a set of defined colors instead of a mathematically-generated rainbow. Particularly nice with divergent palettes, we recommend you try chroma.js to populate the colors array in index.html.

Original notes: A spanning tree of the canvas is generated using Wilson’s algorithm and then flooded with color. Hue encodes Manhattan distance from the root of the tree. (This is not an optimal visual encoding, but it suffices and is pretty.)

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

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<style>
​
#wait {
  padding: 10px;
}
​
</style>
<div id="wait">Please wait a moment; this is hard.</div>
<canvas width="960" height="500"></canvas>
<script src="https://d3js.org/d3.v3.min.js"></script>
<script>
​
var canvas = d3.select("canvas"),
    context = canvas.node().getContext("2d"),
    width = canvas.property("width"),
    height = canvas.property("height");
​
var worker = new Worker("generate-wilsons.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);
​
  d3.select("#wait").transition()
      .style("opacity", 0)
      .remove();
​
  function flood() {
    var frontier1 = [],
        i0,
        n0 = frontier.length,
        i1;
​
    var colors = ['#4682b4', '#6793bb', '#82a4c1', '#9cb5c8', '#b6c7ce', '#cedad4', '#e7ecda', '#ffffe0', '#e7ecda', '#cedad4', '#b6c7ce', '#9cb5c8', '#82a4c1', '#6793bb', '#4682b4'];
    distance += 0.5;
    var bandWidth = 100;
    var band = Math.floor((distance % (bandWidth * colors.length)) / bandWidth);
    var color = d3.rgb(colors[band]);
​
    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;
  }
​
  d3.timer(function() {
    for (var i = 0, done; i < 2 && !(done = flood()); ++i);
    context.putImageData(image, 0, 0);
    return done;
  });
});
​
</script>
​
    