One 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.
It'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?
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…
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.
Check out this page 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.
>I wonder if this works backwards - given a tree could you construct a maze? efficiently?
There are trees for which no rectangular maze exists - for example, any tree with a vertex of degree greater than 4. Or the tree with 4 vertices arranged in a T, which can't be fit into a 2x2 space. If there is such an algorithm, it'll have to account for the possibility that there is no solution, so I wouldn't expect it to be very efficient.
I 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.
Looks 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?
I 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.
I 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."
D3 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.
Yes, 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:
It starts at a node that isn't in the tree and randomly walks.
If it hits itself while randomly walking (remember it isn't part of the tree yet), it erases the loop that it created and continues walking from that node again.
If the walk hits the tree, connect the walked path to the tree, pick another node and start again.
If you look closely at the huge loops Wilson’s algorithm is generating, you'll see they are not really loops at all: they only join up to the existing maze at the end, and there is a small gap at the start.
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.)
There'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).
