9 Responses:

1. Wout says:

   6 years ago at 2:09 pm

   I want to eat this as a 3D printed noodle in pho

2. eSyr says:

   6 years ago at 2:11 pm

   But isn't the black part the actual maze?

   • jwz says:

     6 years ago at 4:51 pm

     I think that the way this maze is being generated, the white part is the maze and the black part is the wall, but I also think it's ambiguous: it's a maze both ways, just different ones!

     Though I think the translation from maze to tree still works if you consider the black part to be the maze, because with that perspective, each cell has 1 or 2 adjacent walls that are not shared with another cell, so those walls can unambiguously stand in for their corridor.

     The entrances and exits are not explicitly marked, but if I'm reading this right, this algorithm isn't guaranteed to have 2+ doors on the perimeter. The rightmost node in the tree isn't the exit, it's simply the longest path through the maze (arguably the "center").

     • eSyr says:

       6 years ago at 5:04 pm

       Well, I just meant that the black part makes more sense as a maze; of course, both of them can be treated as a maze.

       I'm not quite sure about the unambiguity, though, due to the difference in topologies of the black and white parts.

3. Mike says:

   6 years ago at 5:55 pm

   But mazes have cycles (loops), and trees don't!

   Which maybe this is why the tree(-like) graphic is mushy in some spots, and we're lucky that the maze doesn't have too many cycles? As far as spanning trees are concerned, the algorithm could just drop any edge when it links to a previously seen vertex. That wouldn't make for a good animation though. Don't know how to fix, but you can imagine a fully connected street-grid of a maze (not a very good maze) that becomes a real mess when this tries to tree-ify it.

   • jwz says:

     6 years ago at 6:01 pm

     Not all mazes have cycles. This kind don't.

     • Mike says:

       6 years ago at 6:57 pm

       Sure enough. I should've enabled javascript on the linked page, and I missed all the description. The Wilson's Algorithm visualization for maze/tree generation is great, and the property it exhibits is sort of shocking:

       Take any two vertices and perform loop-erased random walk from one to the other. Now take a third vertex (not on the constructed path) and perform loop-erased random walk until hitting the already constructed path. This gives a tree with either two or three leaves. Choose a fourth vertex and do loop-erased random walk until hitting this tree. Continue until the tree spans all the vertices. It turns out that no matter which method you use to choose the starting vertices you always end up with the same distribution on the spanning trees, namely the uniform one.

4. J. Peterson says:

   6 years ago at 12:26 am

   Definitely worth clicking through to the original, the JavaScript animation is wonderful.

   The author has cranked out an impressive array of graphics and visualization toys.

5. Chipaca says:

   6 years ago at 4:15 am

   You know I now want maze to do this, right?