Maze Generation: Algorithm Recap

Posted by Jamis on February 07, 2011 @ 11:02 AM

(Hello Minecrafters! If you’re looking for random mazes you can build in Minecraft, you might be better served by this page I wrote. It’ll give you block-wise schematics for the maze, and will require less mental translation than the demos here. Just don’t use IE—it won’t work right in that browser. If you want to learn more about random maze generation, though, read on!)

Over the last six weeks I documented eleven different maze generation algorithms. It’s been a blast. I’ve had so much fun researching and implementing these! It’s been great to see some of you taking my advice and applying these to learning a new programming language, as well; I really believe there is a lot of value to be had, there.

I intend to write more maze-related posts, too. Some possible topics include methods for rendering your mazes, ways to implement “weave” mazes (mazes where passages pass over and under other passages), non-rectangular tesselations, and so on. We’ll see where it all goes.

To wrap up the algorithm series, here’s a quick recap of each of the eleven algorithms:

(Note: if you’re using a feed-reader, or reading this on a parasite-blog, you’ll probably be missing out on the Javascript demos. I’m not just trying to drive traffic, here, I really do think you’ll get more out of the article by reading it at the source!)

The recursive backtracker was my go-to algorithm for years. It’s fast, easy to implement, and generates mazes that are (to my eyes, at least) quite esthetically pleasing. Of all the algorithms, it generates the fewest dead-ends, and as a result has particularly long and winding passages. It’s especially hypnotic to watch the algorithm in action!

Eller’s algorithm is perhaps the most challenging to understand and implement of the algorithms I covered. Its clever use of sets allow it to generate infinitely tall mazes while only needing to examine a single row at a time. Esthetically, it strikes a nice balance between “long and winding” and “lots of cul-de-sacs”.

Kruskal’s algorithm is actually an algorithm for generating a minimum spanning tree (MST) for a graph. What I covered is actually a variation on that, which selects edges at random instead of by weight. The resulting mazes tend to have a lot of short cul-de-sacs. Implementation-wise, this algorithm might rank second in difficulty, some distance behind Eller’s algorithm.

Prim’s algorithm is another MST algorithm. Like the variation I described for Kruskal’s, the Prim variant I covered also selects edges at random rather than by weight, allowing the creation of random mazes. Like Kruskal’s, the resulting mazes tend to be heavy on the cul-de-sacs, but the implementation is pretty straight-forward.

The recursive division algorithm is novel in that it is the only one I covered that uses a “wall adding” technique, rather than a “passage carving” one. It is also novel in its fractal-like method of growing the maze. Theoretically, you could use this algorithm to generate infinitely large mazes by building sections on-demand, increasing the resolution as needed by repeating the algorithm on the currently focused area.

I included the Aldous-Broder algorithm mostly for completeness; the algorithm is optimized for generating “uniform spanning trees” (spanning trees selected at random, and uniformly, from the set of all possible spanning trees). Sadly, this constraint means the algorithm itself is very inefficient!

Wilson’s algorithm is another method for generating uniform spanning trees. It converges more rapidly than Aldous-Broder, but still is much less effective as a general maze generator than any of the other algorithms I covered.

The Hunt-and-Kill algorithm is similar to the recursive backtracker (they both tend to generate long, winding passages), but this algorithm will search the grid, iteratively, looking for a new blank cell when it encounters a dead-end. A variation on this algorithm was my first introduction to maze generation, almost twenty years ago!

My new favorite, the Growing Tree algorithm, can work identically to the recursive backtracker when implemented one way, and with another small tweak can be made to work very similarly to Prim’s algorithm. It all depends on how cells are selected from its set of active cells. In fact, attributes of both algorithms can be gained by clever combinations of cell selection methods! It’s quite a flexible algorithm.

Cell selection method:

The Binary Tree algorithm is an almost-trivially simple one, but you pay for that simplicity. The mazes it generates tend to have blemishes (long corridors spanning two sides) and a notable bias (routes tend to run diagonally). Still, for some applications this can be quite appropriate. Besides, with this algorithm you could theoretically have an infinitely large maze by generating only the area you need, on demand!

Bias:

The last algorithm I covered was the Sidewinder algorithm. This is related to the Binary Tree algorithm, but does not have as noticable a bias, and there is only one long passage across the top.

Thanks to everyone who has followed along for the last six weeks. Thanks especially go to those who shared their own implementations; I love seeing how these algorithms translate into other languages.

So, that’s it for the algorithms, but stay tuned for more maze-related topics in the coming weeks!

Posted in Under the Hood

Comments

Have something to add? Click here to leave a comment.

07 Feb 2011

1. olivier said...

a mazing! great! thank you

2. Wyatt Carss said...

This has been a fantastic read to keep along with – thanks for all the excellent work!

3. Gordon said...

Hi Jamis! I really enjoyed these posts, and I think it would be great if you discussed a bit your javascript implementations! Thanks!

4. TechNeilogy said...

Thanks for the series; blogging at its best!

5. jim said...

you are officially the King of Mazes!

6. Jamis said...

Thanks, everyone, for the kind words and encouragement! It means a lot to me that you are enjoying what I’m writing; it keeps me wanting to write more. :)

08 Feb 2011

7. Pedro Arthur Duarte said...

Like Olivier said, the post was just “a mazing” =D

09 Feb 2011

8. Nekogui said...

“a mazing” \o/ Great post :)

9. gulput said...

The RoR front-end is almost done and quick contribution I gave was a Perl script that receives a folder as input and analyzes all the source code available inside the folder (recursive). You can find the README.markdown under the same folder. This analysis is just oriented to quantity of lines of code.

10. chris said...

The whole series of posts were “a mazing.” Hehe. Thanks for the time and effort. I have a sort of ill-formed question. I’ve been wondering about labyrinths. That is, one winding path. Usually, at least in how I visualize a labyrinth, the end of the labyrinth is in the center of the structure. These algorithms seem to be “hit two walls down” and those are the ends. Are there biases one can introduce to generate increased path distance between certain sets of points, and shorter distance between others? Or something similar? Like, the further one approaches the center of the maze, the harder it becomes. Forgive me, if this sounds ill-phrased it is because it is ill-formed in my own thoughts.

11. Jamis said...

Hey @chris, good questions. I honestly don’t know the answers. :) But it sounds like a fun challenge. If you figure anything out, let me know.

Also, so you know, the term “labyrinth” is often to describe a “maze” with no junctions. That is to say, it’s a maze where you go in at the start point, and walk and walk and walk until you get out. There are no intersections, no choices to make, etc. Just a long windy passage. It’s fairly easy to turn any perfect maze (on a rectangular grid) into such a labyrinth: you just choose a starting point, and then follow the maze, splitting each passage in half lengthwise as you go. So deadends become u-turns, passages become two-way streets, etc. When you’re done, you’ll have a labyrinth that enters at one point, winds over every cell in the maze, and exits at a point neighboring the entrance. It will be exactly twice the dimensions of the original maze.

Not sure if that gives you any ideas or not. :) But it’s a fun trick!

11 Feb 2011

12. Axolotl said...

Thank you very much for this great series of articles. Looking forward to implementing one or more of these algorithms :D

13. chris said...

Hey @jamis: That is a cool trick, very clever – how easily converted from maze to labyrinth! I’ll be sure to keep you informed of anything interesting (doubtful, hehe) I come up with. Thanks again.

16 Feb 2011

14. Srini said...

Awesome set of articles. Thanks a ton Jamis. You’re an inspiration.

24 Feb 2011

15. dent said...

I also wanted to say thanks for this series; I was inspired to re-implement Primm’s algorithm on a hexagonal grid (like http://www-cs-students.stanford.edu/~amitp/Articles/HexLOS.html shows) and had a great time doing it!

07 Apr 2011

16. WagonRepairer said...

Hi there! Thank you very much for outlining these algorithms. This has been very helpful.

Linked below is my port of three of them (Recursive Backtracker, Hunt&Kill and Recursive Division) in Lua (using one of Lua’s many pseudo-OOP styles) for a game project using the SpringRTS engine.

http://code.google.com/p/spring-engine-dungeon/source/browse/trunk/mods/mazecraft-pre.sdd/LuaRules/Gadgets/mazecode.lua#

The Recursive Division turns out to be the best suited for our game as it allows control over corridor sizes, rooms and even easy doors. But I enjoyed this so much I think I just might implement the Growing Tree for fun even if we don’t use it.

08 Apr 2011

17. Jamis said...

@WagonRepairer, thanks for sharing your Lua version of those algorithms! You’ll have to let us know when the game project is ready for consumption :)

04 May 2011

18. hey_yoro@yahoo.com said...

What a nice and helpfull site… Congrats!