Hacker News new | comments | show | ask | jobs | submit login
Wilson’s Algorithm (ocks.org)
212 points by bemmu 11 months ago | hide | past | web | favorite | 15 comments

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/

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

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

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.

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/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

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

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

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?

It's being pulled as a gist from github

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

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

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.

This is a maze generator, not a solver. Once the maze is created, you decide where the starting/end points are.

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.

wondering the same

Perhaps exit == entrance.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact