3 ms·

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 unde

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 http://bl.ocks.org/mbostock/6ba3a15c9f08742b3a80

ars 12y ago
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.)
- lkfj43qlkfj34l 12y ago
  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 https://gist.github.com/anonymous/4bbac3930e4a91a7c09f
- TophWells 12y ago
  The white lines are supposed to be the paths, not the walls.
NamTaf 12y ago
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 http://bl.ocks.org/mbostock/11357811
- robinhouston 12y ago
  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.
- yelnatz 12y ago
  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.

ars 12y ago

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

lkfj43qlkfj34l 12y ago
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 https://gist.github.com/anonymous/4bbac3930e4a91a7c09f
TophWells 12y ago
The white lines are supposed to be the paths, not the walls.

NamTaf 12y ago

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 http://bl.ocks.org/mbostock/11357811

robinhouston 12y ago
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.
yelnatz 12y ago
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.