A minimum spanning tree of the canvas is generated using randomized depth-first traversal. Hue encodes Manhattan distance from the start. (This is not an optimal visual encoding, but it suffices and is pretty.)
Randomized depth-first traversal 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 Prim’s algorithm, Wilson’s algorithm and random traversal.
| <!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> |
