Forked from Mike Bostock's Prim's Algorithm block.
I've just tweaked a few things to make it look like slow-moving clouds.
height: 960 |
Forked from Mike Bostock's Prim's Algorithm block.
I've just tweaked a few things to make it look like slow-moving clouds.
var N = 1 << 0, | |
S = 1 << 1, | |
W = 1 << 2, | |
E = 1 << 3; | |
var northBias = 0.7, | |
eastBias = 0.9; | |
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: northBias * Math.random() }); | |
frontier.push({index: startIndex, direction: E, weight: eastBias * 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: northBias * 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: eastBias * 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; | |
filter: blur(2px); | |
-webkit-filter: blur(2px); | |
} | |
</style> | |
<div id="wait">Generating maze; please wait…</div> | |
<canvas width="960" height="960"></canvas> | |
<script src="//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 blueish = "#D6DDEE", | |
whiteish = "#F9F5F8" | |
var colors = d3.range(360) | |
.map((function() { | |
var color = d3.scale.linear() | |
.domain([0, 180, 360]) | |
.range([whiteish, blueish, whiteish]); | |
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, | |
r = -1, | |
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, i4 = 0, s = 1.1 - Math.cos(elapsed / 40000); i < n; ++i, i4 += 4) { | |
c = colors[(c = Math.floor(distance[i] * s) % 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> |