block by mbostock 76da6085849bff8b6e03

Prim’s Algorithm IV

Full Screen

Color-cycling applied to a spanning tree generated by Prim’s algorithm. This version rotates hue; see what happens when you vary periodicity instead.

Updated Example →

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<style>

#wait {
  padding: 10px;
  position: absolute;
}

canvas {
  position: relative;
}

</style>
<div id="wait">Generating maze; please wait…</div>
<canvas width="960" height="500"></canvas>
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="cubehelix.min.js"></script>
<script>

var canvas = d3.select("canvas"),
    context = canvas.node().getContext("2d"),
    width = canvas.property("width"),
    height = canvas.property("height");

var colors = d3.range(360)
    .map((function() {
      var color = d3.scale.cubehelix()
        .domain([0, 180, 360])
        .range([
          d3.hsl(-100, 0.75, 0.35),
          d3.hsl(  80, 1.50, 0.80),
          d3.hsl( 260, 0.75, 0.35)
        ]);
      return function(i) {
        return d3.rgb(color(i));
      };
    })());

var worker = new Worker("generate-prims.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 d = 0,
      n = width * height,
      cells = event.data,
      distance = new Array(n),
      frontier = [(height - 1) * width],
      image = context.createImageData(width, height),
      imageData = image.data;

  distance[frontier[0]] = 0;

  for (var i = 0, c, i4 = 3; i < n; ++i, i4 += 4) {
    imageData[i4] = 255;
  }

  while (frontier.length) {
    var frontier1 = [],
        i0,
        n0 = frontier.length,
        i1;

    ++d;
    for (var i = 0; i < n0; ++i) {
      i0 = frontier[i];
      if (cells[i0] & E && distance[i1 = i0 + 1] == null) distance[i1] = d, frontier1.push(i1);
      if (cells[i0] & W && distance[i1 = i0 - 1] == null) distance[i1] = d, frontier1.push(i1);
      if (cells[i0] & S && distance[i1 = i0 + width] == null) distance[i1] = d, frontier1.push(i1);
      if (cells[i0] & N && distance[i1 = i0 - width] == null) distance[i1] = d, frontier1.push(i1);
    }

    frontier = frontier1;
  }

  d3.timer(function(elapsed) {
    for (var i = 0, c, r = Math.floor(elapsed / 20), i4 = 0; i < n; ++i, i4 += 4) {
      c = colors[(c = (distance[i] - r) % 360) < 0 ? c + 360 : c];
      imageData[i4] = c.r;
      imageData[i4 + 1] = c.g;
      imageData[i4 + 2] = c.b;
    }
    context.putImageData(image, 0, 0);
  });
});

</script>

cubehelix.min.js

!function(){function t(t){return function(e,i){e=d3.hsl(e),i=d3.hsl(i);var r=(e.h+120)*a,h=(i.h+120)*a-r,s=e.s,l=i.s-s,o=e.l,u=i.l-o;return isNaN(l)&&(l=0,s=isNaN(s)?i.s:s),isNaN(h)&&(h=0,r=isNaN(r)?i.h:r),function(a){var e=r+h*a,i=Math.pow(o+u*a,t),c=(s+l*a)*i*(1-i);return"#"+n(i+c*(-.14861*Math.cos(e)+1.78277*Math.sin(e)))+n(i+c*(-.29227*Math.cos(e)-.90649*Math.sin(e)))+n(i+c*1.97294*Math.cos(e))}}}function n(t){var n=(t=0>=t?0:t>=1?255:0|255*t).toString(16);return 16>t?"0"+n:n}var a=Math.PI/180;d3.scale.cubehelix=function(){return d3.scale.linear().range([d3.hsl(300,.5,0),d3.hsl(-240,.5,1)]).interpolate(d3.interpolateCubehelix)},d3.interpolateCubehelix=t(1),d3.interpolateCubehelix.gamma=t}();

generate-prims.js

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),
      frontier = minHeap(function(a, b) { return a.weight - b.weight; }),
      startIndex = (cellHeight - 1) * cellWidth;

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

  while ((edge = frontier.pop()) != 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, weight: Math.random()});
      if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S, weight: Math.random()});
      if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W, weight: Math.random()});
      if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E, weight: Math.random()});
    }
  }

  return cells;
}

function minHeap(compare) {
  var heap = {},
      array = [],
      size = 0;

  heap.empty = function() {
    return !size;
  };

  heap.push = function(value) {
    up(array[size] = value, size++);
    return size;
  };

  heap.pop = function() {
    if (size <= 0) return;
    var removed = array[0], value;
    if (--size > 0) value = array[size], down(array[0] = value, 0);
    return removed;
  };

  function up(value, i) {
    while (i > 0) {
      var j = ((i + 1) >> 1) - 1,
          parent = array[j];
      if (compare(value, parent) >= 0) break;
      array[i] = parent;
      array[i = j] = value;
    }
  }

  function down(value, i) {
    while (true) {
      var r = (i + 1) << 1,
          l = r - 1,
          j = i,
          child = array[j];
      if (l < size && compare(array[l], child) < 0) child = array[j = l];
      if (r < size && compare(array[r], child) < 0) child = array[j = r];
      if (j === i) break;
      array[i] = child;
      array[i = j] = value;
    }
  }

  return heap;
}