Making mazes

February 6th, 2010  |  Tags: , ,  |  Leave a comment

Part of a generated maze

When I was little, my dad would sometimes entertain me with miscellaneous software running on the VAX he had in his lab. One of the cooler things was a random maze generator, which probably came from the DECUS archives (we’ve both long since forgotten any details about the author or language) and would fill a whole page with twisting paths. This seemed pretty close to magic to me at the time.

Now that my son is old enough to enjoy mazes, I thought I’d replicate this old program so he could have random mazes of varying intricacy to solve. As far as I can tell, most common maze generation algorithms treat the grid of the maze as an undirected graph with edges between neighboring cells, build a spanning tree, and then place passageways between cells that are immediately connected in the spanning tree. The end result is guaranteed a path from the start to any other node in the maze, because the spanning tree must reach every node. (It’s a little sad that after spending more than a few years of grad school thinking about problems that boil down to graph reachability, this technique seems less like “magic” and more like “obvious.”)

I was able to write a program to build mazes very quickly, and have cleaned it up a bit for public release. You can download the gem package here (use sudo gem install willb-mazegen), or browse the source on github. It will make square-grid mazes to fill a sheet of letter paper, and can make a document consisting of one or many mazes. The code is fairly readable but not particularly fast, but you should be able to generate mazes at least as quickly as a small human can solve them. In the future, I would like to improve performance, optimize the generated PDF (it is currently pretty inefficient), and allow for mazes on non-square grids. (The technique itself is sufficiently general to allow for, e.g., hexagonal or triangular grid mazes, but other aspects of the code would have to change to enable this.)

If you’re just interested in seeing some mazes, here’s a set of twenty preschool-difficulty mazes to download: mazes.pdf. Or you can try this comically ridiculous example (but be warned that it is almost an 8mb file!): hugemaze.pdf.