2d:null 2e:["$","title",null,{"children":"Wilson’s Algorithm | Thomas Preusse | Observable"}] 33:T924,canvas = { const scale = 3000 / width const height = Math.round(width * 0.52) const scaledCanvas = DOM.canvas(scale * width, scale * height) const scaledContext = scaledCanvas.getContext("2d"); scaledContext.scale(scale, scale) scaledCanvas.style.width = `${width}px` const canvas = document.createElement("canvas"); canvas.width = width; canvas.height = height; const context = canvas.getContext("2d"); const blob = new Blob([generateWilsons], {type: 'text/javascript'}); const worker = new Worker(URL.createObjectURL(blob)); 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.rgb(d3.interpolateBlues(0.3 + ((distance += .0018) % 0.7))); 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; } mutable download = null const t = d3.timer(function() { let done for (var i = 0; i < 3 && !(done = flood()); ++i); context.putImageData(image, 0, 0); scaledContext.drawImage(canvas, 0, 0); if (done) { (new Promise(resolve => scaledCanvas.toBlob(resolve))).then(object => { mutable download = DOM.download(object) }) t.stop() } return done; }); }); return scaledCanvas }34:Ta2b,generateWilsons = `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; }`35:[] 31:{"id":"deb1c696b4c4c720","slug":"wilsons-algorithm","title":"Wilson’s Algorithm","thumbnail":"c86ca00e05d3fadf332816566426127cd7d53421ee688e16aa250413e5d7c221","access_level":"public","create_time":"$D2018-06-20T07:53:42.530Z","update_time":"$D2018-06-20T21:51:52.032Z","view_time":null,"first_public_time":"$D2018-07-10T15:07:57.185Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"37829517efb06ab9","login":"tpreusse","name":"Thomas Preusse","avatar_url":"https://avatars-next.observableusercontent.com/46a7c93d53a38c9ba8fd14db2602bd48d9fa0c8a5ec4151f1f69d1cca9983959","tier":"starter_2024"},"version":95,"publish_version":95,"role":null,"authored":false,"authors":[{"type":"individual","id":"c4e93a5033368f9d","login":"tpreusse","name":"Thomas Preusse","avatar_url":"https://avatars-next.observableusercontent.com/46a7c93d53a38c9ba8fd14db2602bd48d9fa0c8a5ec4151f1f69d1cca9983959","tier":null}],"members":[{"type":"individual","id":"c4e93a5033368f9d","login":"tpreusse","name":"Thomas Preusse","avatar_url":"https://avatars-next.observableusercontent.com/46a7c93d53a38c9ba8fd14db2602bd48d9fa0c8a5ec4151f1f69d1cca9983959","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Wilson’s Algorithm","cells":[{"id":0,"value":"md`# Wilson’s Algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"md`A flooded spanning tree generated using Wilson’s algorithm.\n\n[Ported from Mike Bostock’s Block 11363008](https://bl.ocks.org/mbostock/11363008), license: [GPLv3](https://opensource.org/licenses/GPL-3.0).\n\nScaled up and blue colors for export.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"mutable download = null","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"d3 = require('d3@5.5.0')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"