Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active November 26, 2016 01:35
Show Gist options
  • Save mbostock/83d1073cb0a45ac158fb to your computer and use it in GitHub Desktop.
Save mbostock/83d1073cb0a45ac158fb to your computer and use it in GitHub Desktop.
Prim’s Algorithm II
license: gpl-3.0

This maze is generated using Prim’s algorithm and then flooded with color. Hue encodes Manhattan distance from the starting cell. (This is not an optimal visual encoding, but it suffices and is pretty.)

Color is useful to visually compare the structure of mazes; without color, the black and white alternating cells are too noisy to offer any pre-attentive comparisons. Compare a maze generated by Prim’s algorithm to random traversal, randomized depth-first traversal and Wilson’s algorithm.

See this color flood applied directly to the pixel grid.

<!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 = generateMaze(cellWidth, cellHeight), // each cell’s edge bits
distance = 0,
visited = new Array(cellWidth * cellHeight),
frontier = [(cellHeight - 1) * cellWidth];
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 = "#fff";
for (var y = 0, i = 0; y < cellHeight; ++y) {
for (var x = 0; x < cellWidth; ++x, ++i) {
fillCell(i);
if (cells[i] & S) fillSouth(i);
if (cells[i] & E) fillEast(i);
}
}
d3.timer(function() {
if (!(n0 = frontier.length)) return true;
context.fillStyle = d3.hsl(distance++ % 360, 1, .5) + "";
if (distance & 1) {
for (var i = 0; i < n0; ++i) {
fillCell(frontier[i]);
}
} else {
var frontier1 = [],
i0,
i1,
n0;
for (var i = 0; i < n0; ++i) {
i0 = frontier[i];
if (cells[i0] & E && !visited[i1 = i0 + 1]) visited[i1] = true, fillEast(i0), frontier1.push(i1);
if (cells[i0] & W && !visited[i1 = i0 - 1]) visited[i1] = true, fillEast(i1), frontier1.push(i1);
if (cells[i0] & S && !visited[i1 = i0 + cellWidth]) visited[i1] = true, fillSouth(i0), frontier1.push(i1);
if (cells[i0] & N && !visited[i1 = i0 - cellWidth]) visited[i1] = true, fillSouth(i1), frontier1.push(i1);
}
frontier = frontier1;
}
});
function fillCell(i) {
var x = i % cellWidth, y = i / cellWidth | 0;
context.fillRect(x * cellSize + (x + 1) * cellSpacing, y * cellSize + (y + 1) * cellSpacing, cellSize, cellSize);
}
function fillEast(i) {
var x = i % cellWidth, y = i / cellWidth | 0;
context.fillRect((x + 1) * (cellSize + cellSpacing), y * cellSize + (y + 1) * cellSpacing, cellSpacing, cellSize);
}
function fillSouth(i) {
var x = i % cellWidth, y = i / cellWidth | 0;
context.fillRect(x * cellSize + (x + 1) * cellSpacing, (y + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
}
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;
}
d3.select(self.frameElement).style("height", height + "px");
</script>
@SpencerDawson
Copy link

fancy!

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