Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active September 11, 2024 10:57
Show Gist options
  • Save mbostock/11337835 to your computer and use it in GitHub Desktop.
Save mbostock/11337835 to your computer and use it in GitHub Desktop.
Random Traversal III
license: gpl-3.0
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 = [],
startIndex = (cellHeight - 1) * cellWidth;
cells[startIndex] = 0;
frontier.push({index: startIndex, direction: N});
frontier.push({index: startIndex, direction: E});
while ((edge = popRandom(frontier)) != 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});
if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S});
if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W});
if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E});
}
}
return cells;
}
function popRandom(array) {
if (!array.length) return;
var n = array.length, i = Math.random() * n | 0, t;
t = array[i], array[i] = array[n - 1], array[n - 1] = t;
return array.pop();
}
<!DOCTYPE html>
<meta charset="utf-8">
<canvas width="960" height="500"></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 worker = new Worker("generate-random-traversal.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 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.hsl((distance += .5) % 360, 1, .5).rgb();
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 < 1 && !(done = flood()); ++i);
context.putImageData(image, 0, 0);
return done;
});
});
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment