5 ms·
Maze Tree
- Justen 12y agoThat animation is really freakin' sweet
- kin 12y agothe things people visualize w/ D3 never ceases to amaze me
- siddboots 12y agoThe dirty secret about D3 is that almost everything cool you have seen it used for was built by Bostock.
- misiti3780 12y agoJason Davies also: https://www.jasondavies.com/ https://www.jasondavies.com/
- k1w1 12y agoD3 can be used for a lot of things that are not considered traditional visualization. For example, this diagram [1] is built using D3. The beauty of D3 is that changes to the diagram can be make incrementally so you can have multiple users editing the same diagram in different browsers and have their changes seamlessly (mostly) merged. I also used D3 to create this [2] Gantt chart for the same reasons (though I later rewrote it in React.js, but that is a different story). If you want to write D3 code bost.ocks.org is an incredible resource. It has a broader set of example code than any other library I have seen, bar none. [1] http://www.aha.io/assets/screenshots/benefits/product-planning-and-strategy.png http://www.aha.io/assets/screenshots/benefits/product-planni... [2] http://www.aha.io/assets/screenshots/benefits/product-roadmap-planning.png http://www.aha.io/assets/screenshots/benefits/product-roadma...
- deleted 12y ago[deleted]
- thrownaway2424 12y agoMaybe you have a biased sample :-0 Where I work we use D3 extensively for internal dataviz tools and afaik none of us is Bostock.
- BrandonMarc 12y ago... this could be because D3.js was invented 3 years ago by Bostock, his Stanford professor, and his classmate ... maybe. http://en.wikipedia.org/wiki/D3js#Context http://en.wikipedia.org/wiki/D3js#Context
- UweSchmidt 12y agoI think the point was that D3 is incredibly powerful, but maybe a litte difficult to use, and counterintuitive at times, so only few people can get the full potential out of it.
- siddboots 12y agoI wasn't meaning to criticise the library. The point, if any, was just jabbing at how he is constantly gifting us with ingenious demos, but markets in such a way that people tend to think "D3 is a great library because it lets you do this" rather than "Mike Bostock is a genius for coming up with this."
- nilkn 12y agoI think the point of the grandparent post was to praise Bostock for his prodigious output, not harp on D3.
- icefox 12y agoIt would be even cooler if rather than it being all white it was colorized.
- prawn 12y agoReminded me of this little demo from the same author which did something like that: http://bl.ocks.org/mbostock/11167589 http://bl.ocks.org/mbostock/11167589 Amazing examples all over that site.
- roberthahn 12y agoIt's not clear to me whether the tree is mapping the paths of the maze or the walls - the transformation makes it appear as though the walls are being mapped but that doesn't make sense. I wonder if this works backwards - given a tree could you construct a maze? efficiently?
- mbostock 12y agoIt’s the paths. You can see another example of a maze here: http://bl.ocks.org/mbostock/11357811 http://bl.ocks.org/mbostock/11357811 I made the paths thin (1px instead of 4px) to make it easier to see the tree on top of the maze. But to avoid the path/wall ambiguity, maybe it’d be better to start the paths 4px wide, transition to 1px, and then transition to the tree layout…
- roberthahn 12y agoOh hey, mbostock - you did some good work! Thanks for sharing. Your idea sounds fantastic - the problem really was with how I perceived the maze (black paths, white walls)
- sinaa 12y agoGreat work Mike. It would be great if you could add more comments to the code, or a simple separate guide for each of the projects. They are all amazing, and I'm sure many would want to learn more.
- yaph 12y agoCheck out this page http://bost.ocks.org/mike/ http://bost.ocks.org/mike/ if you haven't yet, there are several in-depth posts on how to do things with D3, also read the fantastic D3 docs. I guess making a guide for every Gist Mike posts would be quite demanding regarding his output, in the end even his day only 24 has hours.
- yayadarsh 12y agoIncredible work here! Really love this stuff.
- ars 12y agoDoes this maze have a single unique path through it?
- roberthahn 12y agoYes, it's the node of the tree furthest away (at the far right) from the origin.
- mbostock 12y agoYes, there is a unique path between every pair of nodes because the maze is also a spanning tree. Here’s another view which shows the path between the node under the mouse and the root of the tree: http://bl.ocks.org/mbostock/6ba3a15c9f08742b3a80 http://bl.ocks.org/mbostock/6ba3a15c9f08742b3a80
- ars 12y agoI see tons of paths in this maze, not just one. The same code that generates the walls inside the maze must also generate the walls on the edge of the maze - you can't just put a solid border and declare the corners the start and end. (Well you can, but then there's not a single path.)
- lkfj43qlkfj34l 12y agoThere's only one path between any two points. Here's a script to verify that the result of the maze generator is indeed a tree (and thus has no redundant paths). https://gist.github.com/anonymous/4bbac3930e4a91a7c09f https://gist.github.com/anonymous/4bbac3930e4a91a7c09f
- TophWells 12y agoThe white lines are supposed to be the paths, not the walls.
- NamTaf 12y agoI don't understand this - I saw the Wilson's algorithm [1] generate huge loops as it hit the existing maze. Does it subsequently erase them? I couldn't see how the tree could possibly handle loops. [1]: http://bl.ocks.org/mbostock/11357811 http://bl.ocks.org/mbostock/11357811
- couchand 12y agoOne of the coolest things about this gist is how little code is used for the animation; basically just these lines: d3.selectAll(nodes).transition() .duration(2500) .delay(function() { return this.depth * 50; }) .ease("quad-in-out") .tween("position", function() { var d = this, i = d3.interpolate([d[0], d[1]], [d.y, d.x]); return function(t) { var p = i(t); d.t = t; d[0] = p[0]; d[1] = p[1]; }; }); The tree layout auto-magically gives every node a depth property, we delay the transition by an amount proportional to the depth, and then over the course of two-and-a-half seconds tween the line segment into the new position. Simple and effective. The hard part is generating the maze.
- Donch 12y agoFrankly, that is true art. Inspired.
- d0m 12y agoAnd that is how you get undergrad students interested in graph theory.
- soheil 12y ago'maze-balls!
- ShardPhoenix 12y agoLooks cool, but I'm a bit confused about the colorized examples. It seems like in some of the examples, there are blocks that are colored red that are further away in maze-distance than other blocks that are green, etc. Do the colors roll-over after a certain distance?
- sedev 12y agoYes, they do. The `c0 = d3.hsl(d0 % 360, 1, .5).rgb();` line (IIUC) is doing a modulo-360 operation, so the colors cycle.
- pmontra 12y agoI did something similar more than 20 years ago using Prim's algorithm for the minimal spanning tree. Spanning trees are not the most efficient way to generate a maze but I was studying CS and the maze generation was a good incentive to actually translate the textbook pseudocode into actual C (without the ++). I didn't do the fancy tree animation but you'll excuse me as all I had was a 80x25 ASCII terminal so it was probably a 40x12 maze :-) However I added a nethack style @ character and the hjkl keys to move from the entrance to the exit in the shorter time plus a leaderboard shared across all the users of our Unix system. Our terminals had a repeat key (i.e. keys didn't autorepeat, you had to press the repeat key as if it were a shift to make a key repeat) and that added to dexterity required to go through the maze quickly. The fastest time was in the 5-6 seconds range. I'm afraid the source algorithm has been lost on some tape long ago.
- xabi 12y agoOld simple maze generator algorithms: http://imgur.com/a/5miDZ http://imgur.com/a/5miDZ
- dazmax 12y agoI'd like to see the tree starting from the other end of the maze too.