Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active May 4, 2024 21:57
Show Gist options
  • Save mbostock/70a28267db0354261476 to your computer and use it in GitHub Desktop.
Save mbostock/70a28267db0354261476 to your computer and use it in GitHub Desktop.
Random Traversal
license: gpl-3.0

This maze generation algorithm, sometimes misleadingly called randomized Prim’s algorithm, is more accurately described as a random traversal. Starting in the bottom-left corner, the algorithm keeps an array of the possible directions the maze could be extended (shown in pink). At each step, the maze is extended in one of these random directions, as long as doing so does not reconnect with another part of the maze.

While this algorithm also generates a spanning tree, its behavior is radically different from running Prim’s algorithm on a randomly-weighted graph! Random traversal generates mazes with a very predictable global structure which can be seen both in the above animation and by flooding the maze with color.

Random traversal behaves similarly to randomized breadth-first traversal, since typically the maze can only be extended without self-intersecting on a roughly-circular perimeter. Compare to randomized depth-first traversal.

<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
background: #000;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
var width = 960,
height = 960;
var N = 1 << 0,
S = 1 << 1,
W = 1 << 2,
E = 1 << 3;
var cellSize = 4,
cellSpacing = 4,
cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
cells = new Array(cellWidth * cellHeight), // each cell’s edge bits
frontier = [];
var canvas = d3.select("body").append("canvas")
.attr("width", width)
.attr("height", height);
var context = canvas.node().getContext("2d");
context.translate(
Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2)
);
context.fillStyle = "white";
// Add a random cell and two initial edges.
var start = (cellHeight - 1) * cellWidth;
cells[start] = 0;
fillCell(start);
frontier.push({index: start, direction: N});
frontier.push({index: start, direction: E});
// Explore the frontier until the tree spans the graph.
d3.timer(function() {
var done, k = 0;
while (++k < 50 && !(done = exploreFrontier()));
return done;
});
function exploreFrontier() {
if ((edge = popRandom(frontier)) == 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
context.fillStyle = open ? "white" : "black";
if (d0 === N) fillSouth(i1), x1 = x0, y1 = y0 - 1, d1 = S;
else if (d0 === S) fillSouth(i0), x1 = x0, y1 = y0 + 1, d1 = N;
else if (d0 === W) fillEast(i1), x1 = x0 - 1, y1 = y0, d1 = E;
else fillEast(i0), x1 = x0 + 1, y1 = y0, d1 = W;
if (open) {
fillCell(i1);
cells[i0] |= d0, cells[i1] |= d1;
context.fillStyle = "magenta";
if (y1 > 0 && cells[i1 - cellWidth] == null) fillSouth(i1 - cellWidth), frontier.push({index: i1, direction: N});
if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) fillSouth(i1), frontier.push({index: i1, direction: S});
if (x1 > 0 && cells[i1 - 1] == null) fillEast(i1 - 1), frontier.push({index: i1, direction: W});
if (x1 < cellWidth - 1 && cells[i1 + 1] == null) fillEast(i1), frontier.push({index: i1, direction: E});
}
}
function fillCell(index) {
var i = index % cellWidth, j = index / cellWidth | 0;
context.fillRect(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing, cellSize, cellSize);
}
function fillEast(index) {
var i = index % cellWidth, j = index / cellWidth | 0;
context.fillRect((i + 1) * (cellSize + cellSpacing), j * cellSize + (j + 1) * cellSpacing, cellSpacing, cellSize);
}
function fillSouth(index) {
var i = index % cellWidth, j = index / cellWidth | 0;
context.fillRect(i * cellSize + (i + 1) * cellSpacing, (j + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
}
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();
}
d3.select(self.frameElement).style("height", height + "px");
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment