Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active February 1, 2020 08:53
  • Star 1 You must be signed in to star a gist
  • Fork 4 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mbostock/6ba3a15c9f08742b3a80 to your computer and use it in GitHub Desktop.
Maze Hover
license: gpl-3.0
<!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)),
marginLeft = Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
marginTop = Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2),
cells = generateMaze(cellWidth, cellHeight), // each cell’s edge bits
parents = computeParents(cells, cellWidth, cellHeight),
hoverIndex = cellWidth - 1;
var canvas = d3.select("body").append("canvas")
.attr("width", width)
.attr("height", height)
.on("ontouchstart" in document ? "touchmove" : "mousemove", mousemoved);
var context = canvas.node().getContext("2d");
context.translate(marginLeft, marginTop);
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);
}
}
context.fillStyle = "#f00";
fillPath(hoverIndex);
function mousemoved() {
var m = d3.mouse(this),
x = Math.max(0, Math.min(cellWidth - 1, Math.floor((m[0] - marginLeft - cellSpacing) / (cellSize + cellSpacing)))),
y = Math.max(0, Math.min(cellHeight - 1, Math.floor((m[1] - marginTop - cellSpacing) / (cellSize + cellSpacing))));
context.fillStyle = "#fff";
fillPath(hoverIndex);
context.fillStyle = "#f00";
fillPath(hoverIndex = y * cellWidth + x);
}
function fillPath(i0) {
var i1;
while (true) {
i1 = parents[i0];
fillCell(i0);
if (i1 === i0 - 1) fillEast(i1);
else if (i1 === i0 + 1) fillEast(i0);
else if (i1 === i0 - cellWidth) fillSouth(i1);
else if (i1 === i0 + cellWidth) fillSouth(i0);
else break;
i0 = i1;
}
}
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 computeParents(cells, width, height) {
var parents = new Array(width * height),
i0 = (height - 1) * width,
i1,
frontier = [i0];
parents[i0] = i0;
while ((i0 = frontier.pop()) != null) {
if (cells[i0] & E && isNaN(parents[i1 = i0 + 1])) parents[i1] = i0, frontier.push(i1);
if (cells[i0] & W && isNaN(parents[i1 = i0 - 1])) parents[i1] = i0, frontier.push(i1);
if (cells[i0] & S && isNaN(parents[i1 = i0 + width])) parents[i1] = i0, frontier.push(i1);
if (cells[i0] & N && isNaN(parents[i1 = i0 - width])) parents[i1] = i0, frontier.push(i1);
}
return parents;
}
function generateMaze(width, height) {
var cells = new Array(width * height), // each cell’s edge bits
remaining = d3.range(width * height), // cell indexes to visit
previous = new Array(width * height); // current random walk
// Add the starting cell.
var start = remaining.pop();
cells[start] = 0;
// While there are remaining cells,
// add a loop-erased random walk to the maze.
while (!loopErasedRandomWalk());
return cells;
function loopErasedRandomWalk() {
var i0,
i1,
x0,
y0;
// Pick a location that’s not yet in the maze (if any).
do if ((i0 = remaining.pop()) == null) return true;
while (cells[i0] >= 0);
// Perform a random walk starting at this location,
previous[i0] = i0;
while (true) {
x0 = i0 % width;
y0 = i0 / width | 0;
// picking a legal random direction at each step.
i1 = Math.random() * 4 | 0;
if (i1 === 0) { if (y0 <= 0) continue; --y0, i1 = i0 - width; }
else if (i1 === 1) { if (y0 >= height - 1) continue; ++y0, i1 = i0 + width; }
else if (i1 === 2) { if (x0 <= 0) continue; --x0, i1 = i0 - 1; }
else { if (x0 >= width - 1) continue; ++x0, i1 = i0 + 1; }
// If this new cell was visited previously during this walk,
// erase the loop, rewinding the path to its earlier state.
if (previous[i1] >= 0) eraseWalk(i0, i1);
// Otherwise, just add it to the walk.
else previous[i1] = i0;
// If this cell is part of the maze, we’re done walking.
if (cells[i1] >= 0) {
// Add the random walk to the maze by backtracking to the starting cell.
// Also erase this walk’s history to not interfere with subsequent walks.
while ((i0 = previous[i1]) !== i1) {
if (i1 === i0 + 1) cells[i0] |= E, cells[i1] |= W;
else if (i1 === i0 - 1) cells[i0] |= W, cells[i1] |= E;
else if (i1 === i0 + width) cells[i0] |= S, cells[i1] |= N;
else cells[i0] |= N, cells[i1] |= S;
previous[i1] = NaN;
i1 = i0;
}
previous[i1] = NaN;
return;
}
i0 = i1;
}
}
function eraseWalk(i0, i2) {
var i1;
do i1 = previous[i0], previous[i0] = NaN, i0 = i1; while (i1 !== i2);
}
}
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