Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active March 30, 2024 00:26
Show Gist options
  • Save mbostock/949c772b81296f8e4188 to your computer and use it in GitHub Desktop.
Save mbostock/949c772b81296f8e4188 to your computer and use it in GitHub Desktop.
Randomized Depth-First 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), // each cell’s edge bits
frontier = [];
var start = (cellHeight - 1) * cellWidth;
cells[start] = 0;
frontier.push({index: start, direction: N});
frontier.push({index: start, direction: E});
shuffle(frontier, 0, 2);
while (!exploreFrontier());
return cells;
function exploreFrontier() {
if ((edge = frontier.pop()) == null) return true;
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;
var m = 0;
if (y1 > 0 && cells[i1 - cellWidth] == null) frontier.push({index: i1, direction: N}), ++m;
if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S}), ++m;
if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W}), ++m;
if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E}), ++m;
shuffle(frontier, frontier.length - m, frontier.length);
}
}
}
function shuffle(array, i0, i1) {
var m = i1 - i0, t, i, j;
while (m) {
i = Math.random() * m-- | 0;
t = array[m + i0], array[m + i0] = array[i + i0], array[i + i0] = t;
}
return array;
}
<!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-randomized-depth-first-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 < 20 && !(done = flood()); ++i);
context.putImageData(image, 0, 0);
return done;
});
});
</script>
Copy link

ghost commented Dec 10, 2014

The description says random traversal and the link points to the random traversal script, however the actual algorithm used seems to be randomized deep-first traversal, which has a different link (1ef3b1fb9eb35ca8ffff).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment