mbostock/.block

## .block
license: gpl-3.0
redirect: https://observablehq.com/@mbostock/prims-algorithm-iv

## README.md

      
    Raw
  

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

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

## 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>

## preview.jpg

      
    Raw
  

              preview.jpg
            
          
## thumbnail.png

      
    Raw
  

              thumbnail.png
	license: gpl-3.0
	redirect: https://observablehq.com/@mbostock/prims-algorithm-iv
	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;
	}
	<!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>