Maze Tree | Hacker News Reader

Maze Tree

bl.ocks.org

414 pointsyaph38 comments

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?

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…

Oh 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)

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

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.

Incredible work here! Really love this stuff.

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

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

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.

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

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

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?

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

Frankly, that is true art. Inspired.

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

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

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

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

I think the point of the grandparent post was to praise Bostock for his prodigious output, not harp on D3.

Jason Davies also: https://www.jasondavies.com/

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.

[1] http://www.aha.io/assets/screenshots/benefits/product-planni...

[2] http://www.aha.io/assets/screenshots/benefits/product-roadma...

Maybe you have a biased sample :-0 Where I work we use D3 extensively for internal dataviz tools and afaik none of us is Bostock.

Does this maze have a single unique path through it?

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

I 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

Where do you see the loops?

The algorithm uses "loop-erased" random walks.

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.

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

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

https://gist.github.com/anonymous/4bbac3930e4a91a7c09f

The white lines are supposed to be the paths, not the walls.

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

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

'maze-balls!

That animation is really freakin' sweet

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

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.

Reply on news.ycombinator.com