|
<!DOCTYPE html> |
|
<meta charset="utf-8"> |
|
<body> |
|
<script src="http://d3js.org/d3.v3.min.js"></script> |
|
<script> |
|
|
|
var width = 960, |
|
height = 500; |
|
|
|
var N = 1 << 0, |
|
S = 1 << 1, |
|
W = 1 << 2, |
|
E = 1 << 3; |
|
|
|
var cells = new Array(width * height), // 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"), |
|
image = context.createImageData(1, 1); |
|
|
|
// Add a random cell and two initial edges. |
|
var start = (height - 1) * width; |
|
cells[start] = 0; |
|
context.fillStyle = d3.hsl(0, 1, .5) + ""; |
|
context.fillRect(0, height - 1, 1, 1); |
|
frontier.push({index: start, direction: N, distance: 1}); |
|
frontier.push({index: start, direction: E, distance: 1}); |
|
|
|
// Explore the frontier until the tree spans the graph. |
|
d3.timer(function() { |
|
var done, k = 0; |
|
while (++k < 1000 && !(done = exploreFrontier())); |
|
return done; |
|
}); |
|
|
|
function exploreFrontier() { |
|
if ((edge = frontier.pop()) == null) return true; |
|
|
|
var edge, |
|
i0 = edge.index, |
|
d0 = edge.direction, |
|
i1; |
|
|
|
if (d0 === N) i1 = i0 - width; |
|
else if (d0 === S) i1 = i0 + width; |
|
else if (d0 === W) i1 = i0 - 1; |
|
else i1 = i0 + 1; |
|
|
|
if (cells[i1] == null) { // not yet part of the maze |
|
var x0 = i0 % width, |
|
y0 = i0 / width | 0, |
|
x1, |
|
y1, |
|
d1, |
|
z0 = edge.distance, |
|
z1 = z0 + 1, |
|
color = d3.hsl(z0 % 360, 1, .5).rgb(); |
|
|
|
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; |
|
|
|
cells[i0] |= d0, cells[i1] |= d1; |
|
|
|
image.data[0] = color.r; |
|
image.data[1] = color.g; |
|
image.data[2] = color.b; |
|
image.data[3] = 255; |
|
context.putImageData(image, x1, y1); |
|
|
|
var m = 0; |
|
if (y1 > 0 && !cells[i1 - width]) frontier.push({index: i1, direction: N, distance: z1}), ++m; |
|
if (y1 < height - 1 && !cells[i1 + width]) frontier.push({index: i1, direction: S, distance: z1}), ++m; |
|
if (x1 > 0 && !cells[i1 - 1]) frontier.push({index: i1, direction: W, distance: z1}), ++m; |
|
if (x1 < width - 1 && !cells[i1 + 1]) frontier.push({index: i1, direction: E, distance: z1}), ++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; |
|
} |
|
|
|
</script> |