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