| license: gpl-3.0 |
A spanning tree of the canvas is generated using Wilson’s algorithm 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 Wilson’s algorithm flooded with color, and compare color floods of spanning trees generated with Wilson’s algorithm to random traversal, randomized depth-first traversal and Prim’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(width, height) { | |
| var cells = new Array(width * height), // each cell’s edge bits | |
| remaining = 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); | |
| } | |
| } | |
| function range(n) { | |
| var range = new Array(n), i = -1; | |
| while (++i < n) range[i] = i; | |
| return range; | |
| } |
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| #wait { | |
| padding: 10px; | |
| } | |
| </style> | |
| <div id="wait">Please wait a moment; this is hard.</div> | |
| <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-wilsons.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); | |
| d3.select("#wait").transition() | |
| .style("opacity", 0) | |
| .remove(); | |
| 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 < 3 && !(done = flood()); ++i); | |
| context.putImageData(image, 0, 0); | |
| return done; | |
| }); | |
| }); | |
| </script> |
@Ryfteh It uses https://github.com/d3/d3-timer, which is fixed to the framerate of requestAnimationFrame (typicaly 60 frames per sec). The code itself only walks three layers per frame.
If you want it to go faster, just change i < 3 to something like i < 100 and you'll see it finishes very quickly.
@mbostock: This is not an optimal visual encoding, but it suffices and is pretty.
You could try swapping out d3.hsl((distance += .5) % 360, 1, .5) with d3.hcl((distance += .5) % 360, 40, 74).
What is it that slows the drawing down? Is it artifiicially slowed via D3? If so where? Or is the algorithm just so expensive that it takes as long as it does to compute each branch/edge?