Eller’s Algorithm (2012)

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

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.

Basically, you can lazily generate a maze of infinite length. That's pretty cool.

As such, I wonder if you could restate Hindley-Milner type inference in terms of solving "perfect" mazes?