Hmm, how does NetHack generate mazes in Gehennom? This is making me want to look.
Eller’s Algorithm (2012)
11–20 of 29 posts
Re: Eller’s Algorithm (2012)
#12Hey, this reminds me of the Advent of Code problem today (day 18)! It featured a similar kind of maze.
I had a lot of fun on that one (as I wanted to animate it) making a version that follows all the forks one step per render loop. The output was really satisfying!
Re: Eller’s Algorithm (2012)
#13This algorithm strikes me as seemingly having something in common with a https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
As such, I wonder if you could restate Hindley-Milner type inference in terms of solving "perfect" mazes?
Re: Eller’s Algorithm (2012)
#14Looking at the output of Eller's algorithm, I have to say that it's not the one I'd go with. Here's a visualisation of many maze algorithms: https://www.jamisbuck.org/mazes/ - the "recursive backtracker" algorithm featured at the top of the list (comes in a parallelizable variant) is the most popular answer for this StackOverflow Q&A: https://stackoverflow.com/questions/38502/whats-a-good-algor... To get a sense of w…
Does anyone happen to know which of those algorithms are equivalent, under the following definition of equivalent?
• Maze generation algorithms A and B are equivalent if for any maze that A can generate, it is possible for B to generate that maze too, and vice versa.
For those pairs of algorithms that are equivalent, what pairs are equivalent under this stronger definition?
• Maze generation algorithms A and B are equivalent if for any maze that A generates, B can generate it too, and vice versa, and the probability that A generates that maze on any given run is the same as the probability that B does so.
Re: Eller’s Algorithm (2012)
#15Looking at the output of Eller's algorithm, I have to say that it's not the one I'd go with. Here's a visualisation of many maze algorithms: https://www.jamisbuck.org/mazes/ - the "recursive backtracker" algorithm featured at the top of the list (comes in a parallelizable variant) is the most popular answer for this StackOverflow Q&A: https://stackoverflow.com/questions/38502/whats-a-good-algor... To get a sense of w…
It lets you bias the maze to make interesting designs at least: https://jsbin.com/betediceyu/edit?html,output (you might have to click "Run with JS" to make it work properly)
Re: Eller’s Algorithm (2012)
#16Looking at the output of Eller's algorithm, I have to say that it's not the one I'd go with. Here's a visualisation of many maze algorithms: https://www.jamisbuck.org/mazes/ - the "recursive backtracker" algorithm featured at the top of the list (comes in a parallelizable variant) is the most popular answer for this StackOverflow Q&A: https://stackoverflow.com/questions/38502/whats-a-good-algor... To get a sense of w…
Jamis Buck's Mazes for Programmers is a really fun book to work through. Helped me break out of some doldrums when web development really got me down.
Re: Eller’s Algorithm (2012)
#17This algorithm strikes me as seemingly having something in common with a https://en.wikipedia.org/wiki/Disjoint-set_data_structure . As such, I wonder if you could restate Hindley-Milner type inference in terms of solving "perfect" mazes?
It does indeed. A full disjoint-set implementation is probably overkill, though, since you can throw away the information about the previous row whenever you finish the next row.
Re: Eller’s Algorithm (2012)
#18Looking at the output of Eller's algorithm, I have to say that it's not the one I'd go with. Here's a visualisation of many maze algorithms: https://www.jamisbuck.org/mazes/ - the "recursive backtracker" algorithm featured at the top of the list (comes in a parallelizable variant) is the most popular answer for this StackOverflow Q&A: https://stackoverflow.com/questions/38502/whats-a-good-algor... To get a sense of w…
Ellers algorithm is quite efficient though not the most beautiful to watch being created. Thanks for the links. I like the Prim’s and binary tree algorithms. The recursive division is quite interesting as well, the paterns it generates are peculiar.
Re: Eller’s Algorithm (2012)
#19I wonder which algorithms are most easily generalised to three or more dimensions. Also what would be the best way to visualise and navigate a 4d maze? I can imagine one where the maze structure changes as you go forwards or backwards in time, and in each cell you may or may not be able to time travel. The number of time coordinates wouldn't have to be very large to make this fiendishly difficult.
Re: Eller’s Algorithm (2012)
#20can anyone tell where eller's algorithm is used in some real world applications?