| license: gpl-3.0 |
A spanning tree of the canvas is generated using randomized depth-first traversal and then flooded with color. Hue encodes Manhattan distance from the root of the tree. (This is not an optimal visual encoding, but it suffices and is pretty.)
Spanning trees can also be used to generate mazes. See a maze generated with randomized depth-first traversal flooded with color, and compare color floods of spanning trees generated by random traversal, Prim’s algorithm, and Wilson’s algorithm.
| var N = 1 << 0, | |
| S = 1 << 1, | |
| W = 1 << 2, | |
| E = 1 << 3; | |
| self.addEventListener("message", function(event) { | |
| postMessage(generateMaze(event.data.width, event.data.height)); | |
| }); | |
| function generateMaze(cellWidth, cellHeight) { | |
| var cells = new Array(cellWidth * cellHeight), // each cell’s edge bits | |
| frontier = []; | |
| var start = (cellHeight - 1) * cellWidth; | |
| cells[start] = 0; | |
| frontier.push({index: start, direction: N}); | |
| frontier.push({index: start, direction: E}); | |
| shuffle(frontier, 0, 2); | |
| while (!exploreFrontier()); | |
| return cells; | |
| function exploreFrontier() { | |
| if ((edge = frontier.pop()) == 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 | |
| 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; | |
| var m = 0; | |
| if (y1 > 0 && cells[i1 - cellWidth] == null) frontier.push({index: i1, direction: N}), ++m; | |
| if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S}), ++m; | |
| if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W}), ++m; | |
| if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E}), ++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; | |
| } |
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <canvas width="960" height="500"></canvas> | |
| <script src="//d3js.org/d3.v3.min.js"></script> | |
| <script> | |
| var canvas = d3.select("canvas"), | |
| context = canvas.node().getContext("2d"), | |
| width = canvas.property("width"), | |
| height = canvas.property("height"); | |
| var worker = new Worker("generate-randomized-depth-first-traversal.js"); | |
| worker.postMessage({width: width, height: height}); | |
| worker.addEventListener("message", function(event) { | |
| worker.terminate(); | |
| var N = 1 << 0, | |
| S = 1 << 1, | |
| W = 1 << 2, | |
| E = 1 << 3; | |
| var cells = event.data, | |
| distance = 0, | |
| visited = new Array(width * height), | |
| frontier = [(height - 1) * width], | |
| image = context.createImageData(width, height); | |
| function flood() { | |
| var frontier1 = [], | |
| i0, | |
| n0 = frontier.length, | |
| i1, | |
| color = d3.hsl((distance += .5) % 360, 1, .5).rgb(); | |
| for (var i = 0; i < n0; ++i) { | |
| i0 = frontier[i] << 2; | |
| image.data[i0 + 0] = color.r; | |
| image.data[i0 + 1] = color.g; | |
| image.data[i0 + 2] = color.b; | |
| image.data[i0 + 3] = 255; | |
| } | |
| for (var i = 0; i < n0; ++i) { | |
| i0 = frontier[i]; | |
| if (cells[i0] & E && !visited[i1 = i0 + 1]) visited[i1] = true, frontier1.push(i1); | |
| if (cells[i0] & W && !visited[i1 = i0 - 1]) visited[i1] = true, frontier1.push(i1); | |
| if (cells[i0] & S && !visited[i1 = i0 + width]) visited[i1] = true, frontier1.push(i1); | |
| if (cells[i0] & N && !visited[i1 = i0 - width]) visited[i1] = true, frontier1.push(i1); | |
| } | |
| frontier = frontier1; | |
| return !frontier1.length; | |
| } | |
| d3.timer(function() { | |
| for (var i = 0, done; i < 20 && !(done = flood()); ++i); | |
| context.putImageData(image, 0, 0); | |
| return done; | |
| }); | |
| }); | |
| </script> |
The description says random traversal and the link points to the random traversal script, however the actual algorithm used seems to be randomized deep-first traversal, which has a different link (1ef3b1fb9eb35ca8ffff).