|
<!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 |
|
remaining = d3.range(cellWidth * cellHeight), // cell indexes to visit |
|
previous = new Array(cellWidth * cellHeight), // current random walk path |
|
i0, x0, y0; // end of current random walk |
|
|
|
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) |
|
); |
|
|
|
// Add the starting cell. |
|
context.fillStyle = "white"; |
|
var start = remaining.splice(Math.floor(cells.length/2), 1); // choice of starting cell is arbitrary, but choosing the center minimizes hitting time. |
|
cells[start] = 0; |
|
fillCell(start); |
|
|
|
// While there are remaining cells, |
|
// add a loop-erased random walk to the maze. |
|
context.fillStyle = "magenta"; |
|
d3.timer(function() { |
|
for (var k = 0; k < 50; ++k) { |
|
if (loopErasedRandomWalk()) { |
|
return true; |
|
} |
|
} |
|
}); |
|
|
|
|
|
function getRandomInt(min, max) { // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random |
|
min = Math.ceil(min); |
|
max = Math.floor(max); |
|
return Math.floor(Math.random() * (max - min) + min); //The maximum is exclusive and the minimum is inclusive |
|
} |
|
|
|
function takeRandom(list) { |
|
const index = getRandomInt(0, list.length) |
|
return list.splice(index, 1)[0] |
|
} |
|
|
|
function loopErasedRandomWalk() { |
|
var i1; |
|
|
|
// Pick a location that’s not yet in the maze (if any). |
|
if (i0 == null) { |
|
do if ((i0 = takeRandom(remaining)) == null) return true; |
|
while (cells[i0] >= 0); |
|
previous[i0] = i0; |
|
fillCell(i0); |
|
x0 = i0 % cellWidth; |
|
y0 = i0 / cellWidth | 0; |
|
return; |
|
} |
|
|
|
// Perform a random walk starting at this location, |
|
// by picking a legal random direction. |
|
while (true) { |
|
i1 = Math.random() * 4 | 0; |
|
if (i1 === 0) { if (y0 <= 0) continue; --y0, i1 = i0 - cellWidth; } |
|
else if (i1 === 1) { if (y0 >= cellHeight - 1) continue; ++y0, i1 = i0 + cellWidth; } |
|
else if (i1 === 2) { if (x0 <= 0) continue; --x0, i1 = i0 - 1; } |
|
else { if (x0 >= cellWidth - 1) continue; ++x0, i1 = i0 + 1; } |
|
break; |
|
} |
|
|
|
// 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; |
|
fillCell(i1); |
|
if (i1 === i0 - 1) fillEast(i1); |
|
else if (i1 === i0 + 1) fillEast(i0); |
|
else if (i1 === i0 - cellWidth) fillSouth(i1); |
|
else fillSouth(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. |
|
context.save(); |
|
context.fillStyle = "#fff"; |
|
fillCell(i1); |
|
while ((i0 = previous[i1]) !== i1) { |
|
fillCell(i0); |
|
if (i1 === i0 + 1) cells[i0] |= E, cells[i1] |= W, fillEast(i0); |
|
else if (i1 === i0 - 1) cells[i0] |= W, cells[i1] |= E, fillEast(i1); |
|
else if (i1 === i0 + cellWidth) cells[i0] |= S, cells[i1] |= N, fillSouth(i0); |
|
else cells[i0] |= N, cells[i1] |= S, fillSouth(i1); |
|
previous[i1] = NaN; |
|
i1 = i0; |
|
} |
|
context.restore(); |
|
|
|
previous[i1] = NaN; |
|
i0 = null; |
|
} else { |
|
i0 = i1; |
|
} |
|
} |
|
|
|
function eraseWalk(i0, i2) { |
|
var i1; |
|
context.save(); |
|
context.globalCompositeOperation = "destination-out"; |
|
do { |
|
i1 = previous[i0]; |
|
if (i1 === i0 - 1) fillEast(i1); |
|
else if (i1 === i0 + 1) fillEast(i0); |
|
else if (i1 === i0 - cellWidth) fillSouth(i1); |
|
else fillSouth(i0); |
|
fillCell(i0); |
|
previous[i0] = NaN; |
|
i0 = i1; |
|
} while (i1 !== i2); |
|
context.restore(); |
|
} |
|
|
|
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); |
|
} |
|
|
|
d3.select(self.frameElement).style("height", height + "px"); |
|
|
|
</script> |
