5 ms·

Wilson’s Algorithm

212 points by bemmu 9y ago

TwoFx 9y ago
This is part of a very nice larger article by the same author on visualizing algorithms [0]. It covers sampling, shuffling, sorting, and maze generation. [0]: https://bost.ocks.org/mike/algorithms/ https://bost.ocks.org/mike/algorithms/
d--b 9y ago
Ah, it's been a long time since we heard from Mike. I wonder how d3.express is coming along...
logicallee 9y ago
Very nice. I see the "entrance" but where is the "exit" to the maze? Doesn't it need one?
- jerrygoyal 9y ago
  wondering the same
  - yitchelle 9y ago
    Perhaps exit == entrance.
- pxndx 9y ago
  You can select any arbitrary tile. The opposite corner tile, or any random one in the edge if it's a maze you need to traverse.
- d--b 9y ago
  This is a maze generator, not a solver. Once the maze is created, you decide where the starting/end points are.
- dmurray 9y ago
  The "flooding it with colour" link leads to an algorithm which will identify far away parts of the maze. You might, for example, pick a faraway (in travelling distance) point that is also on the other side of the maze physically.
LoSboccacc 9y ago
> an unbiased sample of all possible spanning trees this also makes the mazes generated by the algorithm the most annoying to solve without a computer, but they are the most resistant to be searched in reverse of all the forward building algorithms (without explicit honeypots for trapping reversers)
- phkahler 9y ago
  >> this also makes the mazes generated by the algorithm the most annoying to solve without a computer Came to say that. I see a lot of what looks like the letter E in there. Many tiny dead ends. Really hard to visually follow a path through, and I can only imagine how not-fun it would be to play a first person game in there.
  - LoSboccacc 9y ago
    given the complexity I an see them being useful for decorative garden mazes (as in, very very tiny) - lot of complexity but actually small could give an interesting run without being overwhelming.
catpolice 9y ago
Ah, this is very similar to some old maze generation toys I was working on a few years back. I was experimenting with adding a little extra stochasticity to the mix. E.g. selecting from the last ~30 neighbors added creates interesting mazes with "multiple growth fronts" rather than one tendril or a uniform expansion at the edge. You can see a GIF example here: https://raw.githubusercontent.com/j-s-n/mazes/master/examples/algorithm3-thickness4-128x128.gif https://raw.githubusercontent.com/j-s-n/mazes/master/example... (My code uses toroidal topology, which is why you can see things going off the edge and coming back on the other side.) And things like varying whether new neighbors are added to the head or tail of the list adds a little perceptible chaos. It's too bad it looks like my demo site is down right now. There's a (old, badly documented) JS demo here with about 6 variant algorithms: https://github.com/j-s-n/mazes-js https://github.com/j-s-n/mazes-js And a better documented but still out of date Python example (that hand-encodes an animated gif here): https://github.com/j-s-n/mazes https://github.com/j-s-n/mazes
jimktrains2 9y ago
Aside: The text doesn't show up without JavaScript. I wouldn't expect to see the animation, but why can't I read the text?
- jjaredsimpson 9y ago
  It's being pulled as a gist from github
WoodenChair 9y ago
Even Richard Stallman doesn't agree with releasing such small snippets of code under the GPL. See his essays in "Free Software, Free Society."

212 points by bemmu 9y ago

This is part of a very nice larger article by the same author on visualizing algorithms [0]. It covers sampling, shuffling, sorting, and maze generation. [0]: https://bost.ocks.org/mike/algorithms/ https://bost.ocks.org/mike/algorithms/

d--b 9y ago

Ah, it's been a long time since we heard from Mike. I wonder how d3.express is coming along...

logicallee 9y ago

Very nice. I see the "entrance" but where is the "exit" to the maze? Doesn't it need one?

jerrygoyal 9y ago
wondering the same
- yitchelle 9y ago
  Perhaps exit == entrance.
pxndx 9y ago
You can select any arbitrary tile. The opposite corner tile, or any random one in the edge if it's a maze you need to traverse.
d--b 9y ago
This is a maze generator, not a solver. Once the maze is created, you decide where the starting/end points are.
dmurray 9y ago
The "flooding it with colour" link leads to an algorithm which will identify far away parts of the maze. You might, for example, pick a faraway (in travelling distance) point that is also on the other side of the maze physically.

LoSboccacc 9y ago

> an unbiased sample of all possible spanning trees this also makes the mazes generated by the algorithm the most annoying to solve without a computer, but they are the most resistant to be searched in reverse of all the forward building algorithms (without explicit honeypots for trapping reversers)

phkahler 9y ago
>> this also makes the mazes generated by the algorithm the most annoying to solve without a computer Came to say that. I see a lot of what looks like the letter E in there. Many tiny dead ends. Really hard to visually follow a path through, and I can only imagine how not-fun it would be to play a first person game in there.
- LoSboccacc 9y ago
  given the complexity I an see them being useful for decorative garden mazes (as in, very very tiny) - lot of complexity but actually small could give an interesting run without being overwhelming.

catpolice 9y ago

Ah, this is very similar to some old maze generation toys I was working on a few years back. I was experimenting with adding a little extra stochasticity to the mix. E.g. selecting from the last ~30 neighbors added creates interesting mazes with "multiple growth fronts" rather than one tendril or a uniform expansion at the edge. You can see a GIF example here: https://raw.githubusercontent.com/j-s-n/mazes/master/examples/algorithm3-thickness4-128x128.gif https://raw.githubusercontent.com/j-s-n/mazes/master/example... (My code uses toroidal topology, which is why you can see things going off the edge and coming back on the other side.) And things like varying whether new neighbors are added to the head or tail of the list adds a little perceptible chaos. It's too bad it looks like my demo site is down right now. There's a (old, badly documented) JS demo here with about 6 variant algorithms: https://github.com/j-s-n/mazes-js https://github.com/j-s-n/mazes-js And a better documented but still out of date Python example (that hand-encodes an animated gif here): https://github.com/j-s-n/mazes https://github.com/j-s-n/mazes

jimktrains2 9y ago

Aside: The text doesn't show up without JavaScript. I wouldn't expect to see the animation, but why can't I read the text?

jjaredsimpson 9y ago
It's being pulled as a gist from github

WoodenChair 9y ago

Even Richard Stallman doesn't agree with releasing such small snippets of code under the GPL. See his essays in "Free Software, Free Society."