4 ms·

Maze-generation algorithms, with JS demos

57 points by ujeezy 16y ago

clyfe 16y ago
This should be called the weekly link, every week it gets to the first page.
- vyrotek 16y ago
  Its funny how that works. Since I would consider myself a pretty regular reader and haven't seen this yet.
- gjm11 16y ago
  No, every week one of his algorithm descriptions gets to the front page, and now he's finished posting those and this is the summary. I don't see anything wrong with that; do you?
- Jach 16y ago
  I only saw a few of them. And what's wrong with maze algorithms? I want to see 3D maze algorithms next!
  - jamis 16y ago
    Nearly all of the algorithms I described extend well into multiple dimensions. I'm not sure how Eller's would work in 3D, but there is probably a way. And the Binary Tree and Sidewinder algorithms seem like they ought to be possible to adapt to 3D, but I don't immediately see how. The others, though, are all trivially expandable to n-dimensions (just add "up", "down" and any other directions you like to the list of possible moves).
jaekwon 16y ago
Why is maze generation so interesting to people? I'm trying to read between the links.
- jamis 16y ago
  For me, it is interesting because fairly simple means can produce complex (and to me, beautiful) results. It's intrigues me to explore this and see what can be done with it. It is also particularly interesting to me as a way to explore the features and syntax of a programming language. Maze algorithms are handy (and entertaining), but any algorithm would do. The idea is to implement the algorithm in the language of your choice (preferably one you are are not experienced in) and see how the language lends itself to the implementation. Naturally, not everyone will share either of these interests with me. But I'm okay with that. :)
- boyter 16y ago
  Probably because it looks like magic unless you know the trick. I remember making crappy mazes by using a ruler and erasor in primary school. At the time I was sure there was a better way and once I knew it I felt enlightened.
boyter 16y ago
Ah maze generation. I remember doing this back in my Uni days in Java. Its interesting to see some other implementations of the maze generation itself though. I think I only implemented Kruskal’s algorithm... two different ways, one poorly and the other somewhat better. That said my implementation was faster then most of the other ones in the class. I even gave it a nice GUI. I even got bored one evening and ported it to my J2ME phone which impressed most of the people in my class. For those interested here is the code, http://www.boyter.org/0/code/maze/Maze.zip http://www.boyter.org/0/code/maze/Maze.zip http://www.boyter.org/0/code/phonemaze/Phonemaze.zip http://www.boyter.org/0/code/phonemaze/Phonemaze.zip

57 points by ujeezy 16y ago

clyfe 16y ago

This should be called the weekly link, every week it gets to the first page.

vyrotek 16y ago
Its funny how that works. Since I would consider myself a pretty regular reader and haven't seen this yet.
gjm11 16y ago
No, every week one of his algorithm descriptions gets to the front page, and now he's finished posting those and this is the summary. I don't see anything wrong with that; do you?
Jach 16y ago
I only saw a few of them. And what's wrong with maze algorithms? I want to see 3D maze algorithms next!
- jamis 16y ago
  Nearly all of the algorithms I described extend well into multiple dimensions. I'm not sure how Eller's would work in 3D, but there is probably a way. And the Binary Tree and Sidewinder algorithms seem like they ought to be possible to adapt to 3D, but I don't immediately see how. The others, though, are all trivially expandable to n-dimensions (just add "up", "down" and any other directions you like to the list of possible moves).

jaekwon 16y ago

Why is maze generation so interesting to people? I'm trying to read between the links.

jamis 16y ago
For me, it is interesting because fairly simple means can produce complex (and to me, beautiful) results. It's intrigues me to explore this and see what can be done with it. It is also particularly interesting to me as a way to explore the features and syntax of a programming language. Maze algorithms are handy (and entertaining), but any algorithm would do. The idea is to implement the algorithm in the language of your choice (preferably one you are are not experienced in) and see how the language lends itself to the implementation. Naturally, not everyone will share either of these interests with me. But I'm okay with that. :)
boyter 16y ago
Probably because it looks like magic unless you know the trick. I remember making crappy mazes by using a ruler and erasor in primary school. At the time I was sure there was a better way and once I knew it I felt enlightened.

boyter 16y ago

Ah maze generation. I remember doing this back in my Uni days in Java. Its interesting to see some other implementations of the maze generation itself though. I think I only implemented Kruskal’s algorithm... two different ways, one poorly and the other somewhat better. That said my implementation was faster then most of the other ones in the class. I even gave it a nice GUI. I even got bored one evening and ported it to my J2ME phone which impressed most of the people in my class. For those interested here is the code, http://www.boyter.org/0/code/maze/Maze.zip http://www.boyter.org/0/code/maze/Maze.zip http://www.boyter.org/0/code/phonemaze/Phonemaze.zip http://www.boyter.org/0/code/phonemaze/Phonemaze.zip