Maze Tree

[couchand]

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.

[roberthahn]

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?

[mbostock]

It’s the paths. You can see another example of a maze here:

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…

[TophWells]

>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.

[albertyw]

Invert the colors - white is paths, black is walls.

[pmontra]

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.

[d0m]

And that is how you get undergrad students interested in graph theory.

[xabi]

Old simple maze generator algorithms: http://imgur.com/a/5miDZ

[ShardPhoenix]

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?

[sedev]

Yes, they do. The `c0 = d3.hsl(d0 % 360, 1, .5).rgb();` line (IIUC) is doing a modulo-360 operation, so the colors cycle.

[Donch]

Frankly, that is true art. Inspired.

[kin]

the things people visualize w/ D3 never ceases to amaze me

[siddboots]

The dirty secret about D3 is that almost everything cool you have seen it used for was built by Bostock.

[ars]

Does this maze have a single unique path through it?

[mbostock]

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:

http://bl.ocks.org/mbostock/6ba3a15c9f08742b3a80

[roberthahn]

Yes, it's the node of the tree furthest away (at the far right) from the origin.

[dazmax]

I'd like to see the tree starting from the other end of the maze too.

[soheil]

'maze-balls!

[Justen]

That animation is really freakin' sweet

[icefox]

It would be even cooler if rather than it being all white it was colorized.

[prawn]

Reminded me of this little demo from the same author which did something like that:

http://bl.ocks.org/mbostock/11167589

Amazing examples all over that site.