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.
Think Labyrinth is an amazing resource here [1]. Specifically, look for the table in the "Perfect Maze Creation Algorithms" that breaks down a bunch of different maze generation algorithms.
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.
For a while my kids have been obsessed with mazes, and when we're at any sort of restaurant that has crayons, they want me to make mazes for them to solve.
My initial designs for doing it by hand (since my stack space is limited) was to draw the outline of the correct solution and then fill in dead ends and other passages. If they watched me making it, though, it became very easy to solve, and the complexity of the maze depended on how well I did at designing the main solution.
So I did a bunch of research on maze algorithms and some experimentation of my own. Eller's was one I considered but without being able to take notes it was hard to keep track of the set structure. Recursive division is fairly easy to do by hand but creates ugly mazes.
The other constraint that I had was that I was designing mazes that were created by wall addition, rather than passage carving (limitations of the media) so many of the algorithms just couldn't apply (like recursive backtracking), or were tricky to figure out how to translate to a wall addition version.
The algorithm I settled on is what Think Labyrinth calls the "Perfect" wall addition algorithm. It generates perfect mazes and is capable of generating all mazes (and depending on how you choose segments, it can be made uniform, but my human brain based random number generator is limited). Basically you choose a spot on any wall at random, and start drawing a line from there. The line can fork, and turn, and wind all around, but it can never touch another wall. Then, at some point, you pick up the crayon and start again at another random point. Now whenever I see a maze I can't help but look at the structure of the walls, and see the forest of trees rooted on the outer edge rather than the open passages in the maze itself.
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!
I 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.
Anything based on graph traversal generalized trivially. And any maze-generation algorithm by definition will generate a spanning tree, so you can always post-process the generated trees to re-embed the graph in an arbitrary number of dimensions.
For https://github.com/gliese1337/M4ZE.js (a prototype 4D maze navigation game), I used a 4D specialization of Prim's algorithm. There is no time travel involved--it's just straight-up 4 fully equivalent spatial dimensions, with full 4D maneuverability and no privileged directions. At any given time, the maze is visualized as a 2D projection of a 3D hyperplanar slice through the maze, and one type of control action is to rotate your viewing hyperplane.
It is actually far easier to navigate than I initially thought it would be when I started working on it. I recently implemented a 4pi-steradian all-around view to make it a little bit easier, but the bump in navigation ease is minor (though I kept it because it's cool, and allows for tricks like running the maze entirely backwards). User testing so far indicates that kids and teenagers adapt to it quite quickly, while most adults have significantly more trouble.
Having slept on this, the biggest issue I have with my idea is that there's no easy way to have an overarching view of the whole maze, across all time. In the classic 2D maze you can view the whole thing at once which makes finding the solution easier. If you restrict a 2D maze so that you can only see one cell at a time, that already ramps the difficulty way up without any need for extra dimensions.
But, presumably, you might end up with a maze that you can't get from the left edge to the right edge because the joining hole in the middle hasn't been generated. Which would be less than fun to play.
(I had the same thought and wondered if e.g. PacMan256 etc. were using this.)
You could, but if you ever terminate the maze then it will join up the two halves... so it ought to be fairly trivial to add a modification that enforces merging all sets periodically, or at specific points, without finalizing the maze.
I went ahead and implemented it in TypeScript (https://www.npmjs.com/package/lazy-eller) and that would only require a minor modification to the final row sub-algorithm to permit additional downward connections.
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.
If it's a "correct" maze with exactly one way to get from any one square to any other square (as Eller's mazes are), then it doesn't matter where your entry and exit points are -- there's always one solution for any entry/exit pair you choose.
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 what are some good properties of a maze, this blog post does a pretty comprehensive and exhaustive job: http://datagenetics.com/blog/november22015/index.html
Just in case we're not doing perfect 2D mazes but some variation, the following two pages cover different kinds of mazes:
http://www.astrolog.org/labyrnth/algrithm.htm
http://mazesforprogrammers.com/#mazes
$.02