Another variation of color-cycling a spanning tree generated by Prim’s algorithm. Here the periodicity of the color scale by tree depth is varied over time, alternating between emphasis of micro and macro structure. This idea was suggested in a Hacker News comment.
Last active
November 28, 2019 00:39
-
-
Save mbostock/aa7edeac67253ea5de7f to your computer and use it in GitHub Desktop.
Prim’s Algorithm V
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| redirect: https://observablehq.com/@mbostock/prims-algorithm-v |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| !function(){function t(t){return function(e,i){e=d3.hsl(e),i=d3.hsl(i);var r=(e.h+120)*a,h=(i.h+120)*a-r,s=e.s,l=i.s-s,o=e.l,u=i.l-o;return isNaN(l)&&(l=0,s=isNaN(s)?i.s:s),isNaN(h)&&(h=0,r=isNaN(r)?i.h:r),function(a){var e=r+h*a,i=Math.pow(o+u*a,t),c=(s+l*a)*i*(1-i);return"#"+n(i+c*(-.14861*Math.cos(e)+1.78277*Math.sin(e)))+n(i+c*(-.29227*Math.cos(e)-.90649*Math.sin(e)))+n(i+c*1.97294*Math.cos(e))}}}function n(t){var n=(t=0>=t?0:t>=1?255:0|255*t).toString(16);return 16>t?"0"+n:n}var a=Math.PI/180;d3.scale.cubehelix=function(){return d3.scale.linear().range([d3.hsl(300,.5,0),d3.hsl(-240,.5,1)]).interpolate(d3.interpolateCubehelix)},d3.interpolateCubehelix=t(1),d3.interpolateCubehelix.gamma=t}(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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), | |
| frontier = minHeap(function(a, b) { return a.weight - b.weight; }), | |
| startIndex = (cellHeight - 1) * cellWidth; | |
| cells[startIndex] = 0; | |
| frontier.push({index: startIndex, direction: N, weight: Math.random()}); | |
| frontier.push({index: startIndex, direction: E, weight: Math.random()}); | |
| while ((edge = frontier.pop()) != null) { | |
| 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; | |
| if (y1 > 0 && cells[i1 - cellWidth] == null) frontier.push({index: i1, direction: N, weight: Math.random()}); | |
| if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S, weight: Math.random()}); | |
| if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W, weight: Math.random()}); | |
| if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E, weight: Math.random()}); | |
| } | |
| } | |
| return cells; | |
| } | |
| function minHeap(compare) { | |
| var heap = {}, | |
| array = [], | |
| size = 0; | |
| heap.empty = function() { | |
| return !size; | |
| }; | |
| heap.push = function(value) { | |
| up(array[size] = value, size++); | |
| return size; | |
| }; | |
| heap.pop = function() { | |
| if (size <= 0) return; | |
| var removed = array[0], value; | |
| if (--size > 0) value = array[size], down(array[0] = value, 0); | |
| return removed; | |
| }; | |
| function up(value, i) { | |
| while (i > 0) { | |
| var j = ((i + 1) >> 1) - 1, | |
| parent = array[j]; | |
| if (compare(value, parent) >= 0) break; | |
| array[i] = parent; | |
| array[i = j] = value; | |
| } | |
| } | |
| function down(value, i) { | |
| while (true) { | |
| var r = (i + 1) << 1, | |
| l = r - 1, | |
| j = i, | |
| child = array[j]; | |
| if (l < size && compare(array[l], child) < 0) child = array[j = l]; | |
| if (r < size && compare(array[r], child) < 0) child = array[j = r]; | |
| if (j === i) break; | |
| array[i] = child; | |
| array[i = j] = value; | |
| } | |
| } | |
| return heap; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| #wait { | |
| padding: 10px; | |
| position: absolute; | |
| } | |
| canvas { | |
| position: relative; | |
| } | |
| </style> | |
| <div id="wait">Generating maze; please wait…</div> | |
| <canvas width="960" height="500"></canvas> | |
| <script src="//d3js.org/d3.v3.min.js"></script> | |
| <script src="cubehelix.min.js"></script> | |
| <script> | |
| var canvas = d3.select("canvas"), | |
| context = canvas.node().getContext("2d"), | |
| width = canvas.property("width"), | |
| height = canvas.property("height"); | |
| var colors = d3.range(360) | |
| .map((function() { | |
| var color = d3.scale.cubehelix() | |
| .domain([0, 180, 360]) | |
| .range([ | |
| d3.hsl(-100, 0.75, 0.35), | |
| d3.hsl( 80, 1.50, 0.80), | |
| d3.hsl( 260, 0.75, 0.35) | |
| ]); | |
| return function(i) { | |
| return d3.rgb(color(i)); | |
| }; | |
| })()); | |
| var worker = new Worker("generate-prims.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 d = 0, | |
| r = -1, | |
| n = width * height, | |
| cells = event.data, | |
| distance = new Array(n), | |
| frontier = [(height - 1) * width], | |
| image = context.createImageData(width, height), | |
| imageData = image.data; | |
| distance[frontier[0]] = 0; | |
| for (var i = 0, c, i4 = 3; i < n; ++i, i4 += 4) { | |
| imageData[i4] = 255; | |
| } | |
| while (frontier.length) { | |
| var frontier1 = [], | |
| i0, | |
| n0 = frontier.length, | |
| i1; | |
| ++d; | |
| for (var i = 0; i < n0; ++i) { | |
| i0 = frontier[i]; | |
| if (cells[i0] & E && distance[i1 = i0 + 1] == null) distance[i1] = d, frontier1.push(i1); | |
| if (cells[i0] & W && distance[i1 = i0 - 1] == null) distance[i1] = d, frontier1.push(i1); | |
| if (cells[i0] & S && distance[i1 = i0 + width] == null) distance[i1] = d, frontier1.push(i1); | |
| if (cells[i0] & N && distance[i1 = i0 - width] == null) distance[i1] = d, frontier1.push(i1); | |
| } | |
| frontier = frontier1; | |
| } | |
| d3.timer(function(elapsed) { | |
| for (var i = 0, c, i4 = 0, s = 1.1 - Math.cos(elapsed / 20000); i < n; ++i, i4 += 4) { | |
| c = colors[(c = Math.floor(distance[i] * s) % 360) < 0 ? c + 360 : c]; | |
| imageData[i4] = c.r; | |
| imageData[i4 + 1] = c.g; | |
| imageData[i4 + 2] = c.b; | |
| } | |
| context.putImageData(image, 0, 0); | |
| }); | |
| }); | |
| </script> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is awesome. Thanks.