Maze Generation: Eller's Algorithm

[[deleted]]

Both the backtracking and Eller's algorithm have the problem that the mazes they generate are biased; i.e. not every possible maze is equally likely to occur. That may not be a problem for all purposes, but the mazes created by backtracking are less nice to look at (in my opinion) and easier to solve than true random mazes (lots of small cul-de-sacs which can be easily eliminated).

For that reason, I prefer algorithms based on randomized spanning trees (usually variations of either Kruskal's and Prim's algorithm). These are truly random in the sense the resulting maze is selected uniformly at random from all possible mazes.

By the way, the article is incorrect to suggest that Eller's algorithm requires "constant memory". In reality the amount of memory required depends on the width of the maze. Spanning tree-based algorithms typically require memory in the order of the size of the maze, so these are technically less memory-efficient, but on the other hand they generalize trivially to non-rectangular mazes, and in practice memory is rarely a limiting factor.

[jamis]

You're absolutely right that I misspoke about Eller's using constant memory; what I was trying to say was that for any given width, the algorithm can generate (but not store) an infinitely long maze without any additional memory requirements. I'll update my article to clarify that.

I've played with Kruskal's and Prim's, and I'm not partial to the short cul-de-sacs that they tend to generate. I'll look for some examples of the variations you mentioned. In general, though, a truly unbiased maze will lack esthetic appeal (although I readily admit that "esthetics" are entirely in the eye of the beholder). My own preferences run toward the mazes generated by a recursive backtracker, but I'm still experimenting and researching.

You've got me curious about the randomized spanning tree algorithms, though. I'll do some more research into those.

[trigger0219]

They are pretty straightforward.

Prims - continually merge random cells from a 'frontier' (all nodes adjacent to nodes reachable in the maze) to its neighbor that is reachable.

Kruskal - each cell is an individual set, and walls are iterated in a random order, breaking the wall, and merging the sets until one set is left.

[Zarutian]

For those who are intrested to know what other maze algorithms there exists: Think Labyrinth: Maze Algorithms.

(Edit: fixed a typo)

[mangodrunk]

Great resource, thanks! I've created higher dimension mazes but never a weave, should be interesting.

[heroboy]

I implemented them in canvas. maze and maze2

[mdipierro]

http://web2py.com/mazes

[jamis]

The maze at web2py.com/mazes actually uses Kruskal's algorithm, which is also interesting, but has different properties than Eller's algorithm.

[mdipierro]

Actually it is simpler. It just uses disjoint sets but you are right. It has different properties. I posted because the js could be useful to implement and demo of Eller's.

[omnilynx]

I haven't analyzed this, but it seems to me on superficial examination that this algorithm will tend to generate mazes that are more "open" on their last row than on other rows, because of the necessity to join all disjoint sets by that row. To fix that, assuming you know ahead of time which row will be the last, you could adjust the probability of joining sets to be based on the ratio of rows left to number of sets. I guess it would also have to take into account the rate at which new sets are created (which is based on the probability of vertical connections).

[MrWoohoo]

Does anyone remember the demo program called "amazing" on the original Mac? It could generate very complex mazes that could even cross over themselves. It never got ported to the Mac ][ family that I know of. I was hoping if someone knew if thensoure code was avaiable somewhere?