4 ms·
Solving a Maze with D3.js
- surfnerd 12y agoBrilliant. Never thought using D3 this way !
- shiift 12y agoIs 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.
- spikels 12y agoExactly - this seems like an obvious and easy improvement to the algorithm.
- tyotypic 12y agoImagine you're in a maze. Do you know where you are in relation to the maze's boundaries at any point?
- shiift 12y agoI 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.
- 140am 12y agovery cool. i am even more amazed by the other data virtualization examples on the author's page http://bl.ocks.org/mbostock http://bl.ocks.org/mbostock
- edavis 12y agoI 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.
- dsilver 12y agoPart of a whole family of maze visualizations created in the past day by Mike Bostock: Maze Generator: http://bl.ocks.org/mbostock/11159599 http://bl.ocks.org/mbostock/11159599 Maze Solver: http://bl.ocks.org/mbostock/11161648 http://bl.ocks.org/mbostock/11161648 Maze Flooder: http://bl.ocks.org/mbostock/11167589 http://bl.ocks.org/mbostock/11167589 Maze Solver with Best-First Search Algorithm: http://bl.ocks.org/mbostock/11189414 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.
- jay-anderson 12y agoA few years back Jamis Buck did a survey of maze generation algorithms: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap 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.
- elwell 12y agoMaze Flooder is mesmerizing.
- robinhouston 12y agoInteresting! I did a maze flooder last year http://bl.ocks.org/robinhouston/6023888/653206574a69127d7fa2c8eb59bc06f8b4e3d1e9 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.
- nthitz 12y agoI love d3. But that example doesn't really use d3 for either the solving or the displaying.
- ejstronge 12y agoI was thinking the same thing - it looks like the example used d3 mostly to simplify working with svg elements
- dsilver 12y agoThis 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 http://bl.ocks.org/mbostock/9539958 [1] http://bl.ocks.org/mbostock/1062544 http://bl.ocks.org/mbostock/1062544
- ejstronge 12y agoAh! 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.
- kylebrown 12y agoIME, 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.)