Maze generators

I'm working on another game for the kids, called "Mr. Floppypants", of which I'll say no more in this article, except that I'm using node.js, and that for it I required some code to generate a maze.  For once not wanting to write my own code for that particular subfeature, I searched around npm for "maze generator" packages.  There were a few.

Watch out for bull-men!

I set about looking into each one in turn to see if it would suffice, but I discovered for each one a reason not to use it.  One of them simply didn't run, another used Ecmascript 6 (and so wouldn't work in some browsers without being transpiled), one only worked for square mazes, and some (and I admit I was a bit picky) just weren't written to my taste.  Maze generation is a fun little project, and it's natural that many people have made their own generators, in varying degrees of quality.  Yes, I gave up and wrote my own.

Here's what I learned about mazes... wait, no.  Instead let me point you at some much better sources of information:

Jamis Buck writes a mostly-programming blog, and wrote a great series on maze generators in 2010 and 2011.  This in-browser presentation sums up the whole maze generation concept very nicely, and this recap of the blog series is a great place to get more details.  He describes how to implement a handful of algorithms, and provides in-browser demos so you can watch the algorithm run.

Walter Pullen has such a variety of interests that I refuse to summarize his site, in one part of it you can find a very thorough maze generator program he wrote, and he has written extensively about maze generation.  Also I just can't keep myself from mentioning his extensive files about the movie Labyrinth.

Now you know everything about mazes.  But just in case you didn't spend hours reading through all that stuff, here are some highlights:

A maze is basically equivalent to a spanning tree of a graph based on a rectangular grid.  Consequently, algorithms that compute spanning trees can be adapted to make mazes.  Kruskal's algorithm is like this, and builds mazes in an seemingly magical way:  It connects random adjacent cells, taking care not to create a loop, until a maze basically appears out of the noise.

Speaking of Kruskal's, the hardest part is quickly deciding whether two adjacent cells are already connected.  It can be done with a disjoint-set forest, and the tricks they use to make that fast (union by rank and path compression) are neat.

One of the simplest algorithms, recursive-backtracking, is my pick for making the best-looking mazes.  While generators like Kruskal's tend to make lots of clustered dead-ends, recursive-backtracking prefers meandering passages.  It works as basically a randomized depth-first-search of the grid.

Eller's algorithm can generate the maze one entire row at a time.  It works by keeping track of which cells connected to the previous row have already been connected (possibly by an earlier, now forgotten row).  On the very last row, it patches up any not-yet-connected regions of the maze.  In doing so, it may end up with a long straight passage along the bottom.

The Aldous-Broder algorithm generates all possible mazes with equal probibility, but you probably don't want to use it because it's very slow.  It's interesting to think about though: Start in a random cell and perform the well-named  "drunkard's walk", digging a passage when (and only when) you walk into a cell you've never visited before.  Assuming you have enough patience, you'll eventually visit every cell and oh hey, there's a maze!

It's not a generator, but "dead end filler" is an amusing way to solve some mazes without ever visiting cells in the solution path.  Find all the dead ends in the maze and fill them in.  Then find any new dead ends you created, and fill those in too.  Repeat until there are no more dead ends.  The remaining unfilled spaces are the solution.

Back to my project:  I implemented three algorithms (recursive-backtracking, modified Prim's, and Kruskal's).  I also used this as an opportunity to learn about node and npm, so the algorithm packages also have unit tests, benchmarks, and demos, and I spent some time trying to optimize them for speed and also make them easy to plug in to another project without needing to bring a lot of dependencies along.

Demos of my maze generator algorithms

@sbj42/maze-generator npm package

Update (10/15): I added a maze "puzzle" to Probably Puzzles.
Update (6/17): Added a link to Mr. Floppypants