4 ms·

Maze Algorithms (2011)

116 points by Timothee 6y ago

mycall 6y ago
Are there any algorithms that are not squares or include line art?
- fxtentacle 6y ago
  I believe most of these algorithms work on graph structures internally, which means you can use them on any topology as long as you have connectivity information. So if you want really random maze shapes, sprinkle random points, then use voronoi to get a topology, then use backtracking on that. Your maze will be built out of randomly shaped polygons. BTW, what do you need the maze algorithm for?
- sigjuice 6y ago
  http://mazesforprogrammers.com/#mazes http://mazesforprogrammers.com/#mazes
- aprinsen 6y ago
  Yes! As a matter of fact Jamis's book includes an extensive section on non-grid mazes.
- TuringNYC 6y ago
  Does anyone have book/website recommendations for maze generation/solving in Python? All the links so far are awesome, but i'd love a 1-axis challenge (i.e., learn the algos) rather than a 2-axis challenge (i.e., learn ruby while learning the algos)
aprinsen 6y ago
I got interested in mazes late last year and found Mr. Buck's resources invaluable. In fact, I received his book for Christmas. I highly recommend it, definitely worth the paperback purchase to support his work. I implemented several of the algorithms for my Rust maze generation tools (https://github.com/animate-object/mazes https://github.com/animate-object/mazes, https://github.com/animate-object/maze-cli https://github.com/animate-object/maze-cli), (and the game I built on top of them https://github.com/animate-object/followed https://github.com/animate-object/followed)
Sohcahtoa82 6y ago
Several years ago, I wrote a maze generator using POV-Ray [0]. It's interesting trying to write a queue in a language that only has simple fixed-length arrays. IMO, the recursive backtracking algorithm looks the best, and I'd probably use that if I were to ever return to this quick little project. [0]https://youtu.be/VwuA2Z1tCaw https://youtu.be/VwuA2Z1tCaw
xabi 6y ago
My maze algorithms done in perl more than 10 years ago https://github.com/xa-bi/mazes https://github.com/xa-bi/mazes
jarrell_mark 6y ago
Wilson's algorithm creates the best mazes by having a variety of short and long passages.
yellowapple 6y ago
The Aldous-Broder algorithm sure is somethin'.
- whycombagator 6y ago
  I wonder if I can ace my next technical interview after learning it's intricacies
hamsterbooster 6y ago
This might be a stupid question but how can the site run multiple maze generation algorithm at the same time? My understanding is that javascript is single thread.
- ChrisAntaki 6y ago
  By using the event loop, with functions like setTimeout
- jbattle 6y ago
  Really good question actually! I peeked at the javascript and it looks like when you hit `run`, it is calling the step at a setInterval (if I'm reading this right, as fast as the browser can call run) So at the end of each run call, the interpreter figures out which setInterval timer to execute next and has the chance to pick other mazes. (I don't know much about how the JS engine resolves which "not quite thread" gets run next when there are multiple candidates)
  - hamsterbooster 6y ago
    Thanks! I ran multiple maze at the same time and time it and it seems like the maze ran just as fast as running only one maze at a time. If the interpreter can pick other maze, should it take longer? Did I miss anything here?
    - rejschaap 6y ago
      The maze generation is slowed down to visualize what is going on. Most of those mazes can be generated in a few of milliseconds.
diziet 6y ago
If you are interested in mazes and maze solving in general, check out https://www.pathery.com/ https://www.pathery.com/
deleted 6y ago
[deleted]
kebman 6y ago
Amazeing!
user2994cb 6y ago
Generating mazes on 3d polyhedra & other surfaces: http://matthewarcus.github.io/polyjs/maze.html http://matthewarcus.github.io/polyjs/maze.html
ivhilaire 6y ago
I got so interested in mazes after the last HN post on Eller's algorithm that I actually created and published a real mobile game based on it! (shameless plug: it's called "Squashy Squares")
rejschaap 6y ago
I feel mazes are a nice hello world project for learning a new programming language. I made one in JavaScript last month when I was setting up a personal web site. I added a maze to the 404 page to show how truly lost you are when you end up there. It is the most interesting page on my web site so far. https://www.schaap.io/404.html https://www.schaap.io/404.html
fjfaase 6y ago
Recently, I have been working on a maze program (in C++) that generates SVG files that can be used to cut mazes with a laser cutter. I also have been trying to do some statistical analyses on the various algorithms. https://github.com/FransFaase/MazeGen https://github.com/FransFaase/MazeGen Because this program is for my own experiments, I simply modify the 'main' function if I want to change some parameters or select another combination of algorithms. See 'all_tests' for some examples of how the various methods can be called.

116 points by Timothee 6y ago

mycall 6y ago

Are there any algorithms that are not squares or include line art?

fxtentacle 6y ago
I believe most of these algorithms work on graph structures internally, which means you can use them on any topology as long as you have connectivity information. So if you want really random maze shapes, sprinkle random points, then use voronoi to get a topology, then use backtracking on that. Your maze will be built out of randomly shaped polygons. BTW, what do you need the maze algorithm for?
sigjuice 6y ago
http://mazesforprogrammers.com/#mazes http://mazesforprogrammers.com/#mazes
aprinsen 6y ago
Yes! As a matter of fact Jamis's book includes an extensive section on non-grid mazes.
TuringNYC 6y ago
Does anyone have book/website recommendations for maze generation/solving in Python? All the links so far are awesome, but i'd love a 1-axis challenge (i.e., learn the algos) rather than a 2-axis challenge (i.e., learn ruby while learning the algos)

aprinsen 6y ago

I got interested in mazes late last year and found Mr. Buck's resources invaluable. In fact, I received his book for Christmas. I highly recommend it, definitely worth the paperback purchase to support his work. I implemented several of the algorithms for my Rust maze generation tools (https://github.com/animate-object/mazes https://github.com/animate-object/mazes, https://github.com/animate-object/maze-cli https://github.com/animate-object/maze-cli), (and the game I built on top of them https://github.com/animate-object/followed https://github.com/animate-object/followed)

Sohcahtoa82 6y ago

Several years ago, I wrote a maze generator using POV-Ray [0]. It's interesting trying to write a queue in a language that only has simple fixed-length arrays. IMO, the recursive backtracking algorithm looks the best, and I'd probably use that if I were to ever return to this quick little project. [0]https://youtu.be/VwuA2Z1tCaw https://youtu.be/VwuA2Z1tCaw

xabi 6y ago

My maze algorithms done in perl more than 10 years ago https://github.com/xa-bi/mazes https://github.com/xa-bi/mazes

jarrell_mark 6y ago

Wilson's algorithm creates the best mazes by having a variety of short and long passages.

yellowapple 6y ago

The Aldous-Broder algorithm sure is somethin'.

whycombagator 6y ago
I wonder if I can ace my next technical interview after learning it's intricacies

hamsterbooster 6y ago

This might be a stupid question but how can the site run multiple maze generation algorithm at the same time? My understanding is that javascript is single thread.

ChrisAntaki 6y ago
By using the event loop, with functions like setTimeout
jbattle 6y ago
Really good question actually! I peeked at the javascript and it looks like when you hit `run`, it is calling the step at a setInterval (if I'm reading this right, as fast as the browser can call run) So at the end of each run call, the interpreter figures out which setInterval timer to execute next and has the chance to pick other mazes. (I don't know much about how the JS engine resolves which "not quite thread" gets run next when there are multiple candidates)
- hamsterbooster 6y ago
  Thanks! I ran multiple maze at the same time and time it and it seems like the maze ran just as fast as running only one maze at a time. If the interpreter can pick other maze, should it take longer? Did I miss anything here?
  - rejschaap 6y ago
    The maze generation is slowed down to visualize what is going on. Most of those mazes can be generated in a few of milliseconds.

diziet 6y ago

If you are interested in mazes and maze solving in general, check out https://www.pathery.com/ https://www.pathery.com/

deleted 6y ago

[deleted]

kebman 6y ago

Amazeing!

user2994cb 6y ago

Generating mazes on 3d polyhedra & other surfaces: http://matthewarcus.github.io/polyjs/maze.html http://matthewarcus.github.io/polyjs/maze.html

ivhilaire 6y ago

I got so interested in mazes after the last HN post on Eller's algorithm that I actually created and published a real mobile game based on it! (shameless plug: it's called "Squashy Squares")

rejschaap 6y ago

I feel mazes are a nice hello world project for learning a new programming language. I made one in JavaScript last month when I was setting up a personal web site. I added a maze to the 404 page to show how truly lost you are when you end up there. It is the most interesting page on my web site so far. https://www.schaap.io/404.html https://www.schaap.io/404.html

fjfaase 6y ago

Recently, I have been working on a maze program (in C++) that generates SVG files that can be used to cut mazes with a laser cutter. I also have been trying to do some statistical analyses on the various algorithms. https://github.com/FransFaase/MazeGen https://github.com/FransFaase/MazeGen Because this program is for my own experiments, I simply modify the 'main' function if I want to change some parameters or select another combination of algorithms. See 'all_tests' for some examples of how the various methods can be called.