Slight modification of Mike Bostok's visualisation, using a single Cubehelix color scale.
A spanning tree of the canvas is generated using Prim’s algorithm and then flooded with color. Hue encodes Manhattan distance from the root of the tree.
Slight modification of Mike Bostok's visualisation, using a single Cubehelix color scale.
A spanning tree of the canvas is generated using Prim’s algorithm and then flooded with color. Hue encodes Manhattan distance from the root of the tree.
(function() { | |
var radians = 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 = d3_interpolateCubehelix(1); | |
d3.interpolateCubehelix.gamma = d3_interpolateCubehelix; | |
function d3_interpolateCubehelix(γ) { | |
return function(a, b) { | |
a = d3.hsl(a); | |
b = d3.hsl(b); | |
var ah = (a.h + 120) * radians, | |
bh = (b.h + 120) * radians - ah, | |
as = a.s, | |
bs = b.s - as, | |
al = a.l, | |
bl = b.l - al; | |
if (isNaN(bs)) bs = 0, as = isNaN(as) ? b.s : as; | |
if (isNaN(bh)) bh = 0, ah = isNaN(ah) ? b.h : ah; | |
return function(t) { | |
var h = ah + bh * t, | |
l = Math.pow(al + bl * t, γ), | |
a = (as + bs * t) * l * (1 - l); | |
return "#" | |
+ hex(l + a * (-0.14861 * Math.cos(h) + 1.78277 * Math.sin(h))) | |
+ hex(l + a * (-0.29227 * Math.cos(h) - 0.90649 * Math.sin(h))) | |
+ hex(l + a * (+1.97294 * Math.cos(h))); | |
}; | |
}; | |
} | |
function hex(v) { | |
var s = (v = v <= 0 ? 0 : v >= 1 ? 255 : v * 255 | 0).toString(16); | |
return v < 0x10 ? "0" + s : s; | |
} | |
})(); |
<!DOCTYPE html> | |
<html> | |
<head lang="en"> | |
<meta charset="UTF-8"> | |
<title>Prims Algorithm</title> | |
</head> | |
<body> | |
<canvas width="900" height="600"></canvas> | |
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js" charset="utf-8"></script> | |
<script charset="utf-8" src="cubeHelix.js"></script> | |
<script charset="utf-8" src="prims.js"></script> | |
<script charset="utf-8" src="main.js"></script> | |
</body> | |
</html> |
var canvas = d3.select("canvas"), | |
context = canvas.node().getContext("2d"), | |
width = canvas.property("width"), | |
height = canvas.property("height"); | |
var worker = new Worker("prims.js"); | |
worker.postMessage({width: width, height: height}); | |
worker.addEventListener("message", function onMessage(event) { | |
worker.terminate(); | |
var N = 1 << 0, | |
S = 1 << 1, | |
W = 1 << 2, | |
E = 1 << 3; | |
var c = d3.scale.cubehelix() | |
.domain([0, 3200]) | |
//.range([d3.hsl(270, .75, .35), d3.hsl(70, 1.5, .8)]) | |
//.range([d3.hsl(276, .6, 0), d3.hsl(96, .6, 1)]) | |
.range([d3.hsl(-120, .6, 0), d3.hsl(60, .6, 1)]); | |
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.rgb(c((distance += .5) % 25000)); | |
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 < 6 && !(done = flood()); ++i); | |
context.putImageData(image, 0, 0); | |
return done; | |
}); | |
}); |
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; | |
} |