Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active Aug 7, 2019
Embed
What would you like to do?
Prim’s Algorithm IV
license: gpl-3.0
redirect: https://observablehq.com/@mbostock/prims-algorithm-iv
!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}();
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment