And now for something completely different: mazes

Generating random mazes with a computer is pretty easy, but generating “interesting” mazes is an open-ended problem. I came across a blog full of information about maze generation algorithms a while back (thanks, I believe, to Hacker News), and immediately wasted an afternoon implementing the slickest algorithm in JavaScript.

The problem with your typical random computer maze is that it’s just too pathological. They’re great mazes for kids to solve in books of mazes, but kind of a pain to walk around in a first person shooter, say. So the question is how to make mazes that make a nice “dungeon map”.

Maze Generator UI
Maze Generator UI

Anyway, I’ve come up with what I think is a pretty nice pragmatic solution (which you can play with here). It uses a variation of the flexible tree algorithm to generate a base maze (but with a variable fill) and then performs a post-processing path that allows you to limit the “isolation” of individual cells, allowing the creation of everything from conventional mazes to city-like grids.

Rendered Maze Detail
The generator shows the isolation of each cell numerically.

Isolation is an interesting and useful concept. E.g. if you want to place goals such as “treasures” or “bosses” on a map, the obvious spot to put them is the most isolated cells. To place obstacles in the path of a player trying to reach a goal simply follow connections to less isolated cells and insert the obstacle.

My next plan is to support “templates” (which can also be randomly generated — e.g. use a maze generated with one set of parameters to create base structure and then use that as a template which fills out details) which should let me generate pretty nice “dungeon maps” — or levels for Project Weasel.