Solving a Maze with D3.js | Hacker News Reader

Solving a Maze with D3.js

bl.ocks.org

136 pointsrunlevel119 comments

Open articleView on HN

Part of a whole family of maze visualizations created in the past day by Mike Bostock:

Maze Generator: http://bl.ocks.org/mbostock/11159599

Maze Solver: http://bl.ocks.org/mbostock/11161648

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

Maze Solver with Best-First Search Algorithm: http://bl.ocks.org/mbostock/11189414

(Edit: Best-First Search, not A*.)

It's awesome to see interesting algorithm visualizations in D3 (or other web standards) as opposed to Java applets. Especially as a student who has to do algorithm visualizations... in Java applets.

A few years back Jamis Buck did a survey of maze generation algorithms: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit.... The different algorithms seem to create mazes with different 'feels' to them. For instance recursive division algorithm appears more blocky and some have more dead ends than others. This d3 generator appears to be toothy (lots of short dead ends) on the right edge of the maze.

Interesting! I did a maze flooder last year http://bl.ocks.org/robinhouston/6023888/653206574a69127d7fa2... using uniformly random mazes[★], and the flood-filling is much less uniform. The uniformity here must be a reflection of the way the maze was generated.

★ There are algorithms that generate each possible maze with equal probability, if by maze you mean a spanning tree of the grid graph. I used such an algorithm, Wilson's algorithm.

Maze Flooder is mesmerizing.

Is there a reason why it will continue searching "down" once it hits the right edge (and "left" if it hits the top edge)? I'm just curious.

Imagine you're in a maze. Do you know where you are in relation to the maze's boundaries at any point?

I guess that makes sense. I was thinking of it as a maze that someone would using a pencil on paper, but if it were a real maze with high walls it would make sense that you wouldn't necessarily know when you've reached a side.

Exactly - this seems like an obvious and easy improvement to the algorithm.

I love d3. But that example doesn't really use d3 for either the solving or the displaying.

I was thinking the same thing - it looks like the example used d3 mostly to simplify working with svg elements

This one actually uses the canvas element instead of svg. Just another awesome thing about D3: it works equally well with both. You can draw svg paths just as easily as you can draw them on a canvas.

Cool example of canvas[0] vs svg[1]. The canvas renders heavy animation a bit better. Both are around the same number of lines of code.

[0] http://bl.ocks.org/mbostock/9539958

[1] http://bl.ocks.org/mbostock/1062544

Ah! Thanks so much - I was wondering how this maze would work as a collection of svg elements. I'll look into using d3 with canvas for a project I'm doing.

IME, it gets pretty laggy beyond a few hundred svg elements. The catch to using canvas with d3 is that you lose the ability to bind event handlers to the canvas "elements" (since on a canvas they're not DOM elements, just pixels).

For my latest project I used a kineticjs canvas to get handlers on the canvas shapes. That's positioned on top of a d3-bound svg container. Best of both worlds, reasonable speed up to a couple thousand canvas shapes. Though it was quite tricky getting the same input events to trigger separate handlers on sibling dom elements. (Can't just let the events bubble up unless you make the canvas a child of the svg or vice-versa, but that approach creates more problems.)

Brilliant. Never thought using D3 this way !

I still remember the days when Javascript was regarded as a toy language. A glue script for image rollovers and drop-down menus and little else.

Now there are a dozen new Javascript creations each week on HN that make my jaw drop.

It's amazing how far it's come.

very cool. i am even more amazed by the other data virtualization examples on the author's page http://bl.ocks.org/mbostock

He's pretty much a demigod of data visualization at this point.

@mbostock is the creator of d3.js.

and bl.ocks.org/

Reply on news.ycombinator.com