The Buckblog

(Hello Minecrafters! Looking for random mazes you can build in Minecraft? Try this page I wrote. It’ll give you block-wise schematics for the maze, and will require less mental translation than the demos here.)

Update (Sep 2015): If you want to know more about the algorithms described here, including how to employ them on hex grids, circle grids, triangle grids, and 3D and 4D surfaces, check out my book, "Mazes for Programmers", available now from The Pragmatic Programmers, Amazon.com, Barnes & Noble, and all other purveyors of fine programming books!

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: Newest (Recursive Backtracker) Random (Prim's) Newest/Random, 75/25 split Newest/Random, 50/50 split Newest/Random, 25/75 split Oldest Middle Newest/Oldest, 50/50 split Oldest/Random, 50/50 split

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: Northwest Northeast Southwest Southeast

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!

Update (Sep 2015): If you want to know more about the algorithms described here, including how to employ them on hex grids, circle grids, triangle grids, and 3D and 4D surfaces, check out my book, "Mazes for Programmers", available now from The Pragmatic Programmers, Amazon.com, Barnes & Noble, and all other purveyors of fine programming books!