Makin’ Mazes

After my previous post on the subtleties of CSS subpixel rendering, Andrew pointed out that readers might be more interested in how to dynamically generate mazes. It sounded crazy, but here we are.

First of all, if you’re interested in this stuff, there’s a great slideshow on maze generation here and more resources on the procedural content generation wiki.

Basically, your maze is made up of boxes:

You create the maze by making a grid of these boxes, and then Kool-Aid-maning your way through certain walls.

How do you choose which walls? That’s where the algorithm comes in.

First, you choose a square to start the maze at. You add this square to an “active set,” which is the set of squares that you’re currently enmazing:

this.active_set_.push(startNode);

Then you choose one of the square’s neighbors at random. If that square isn’t part of the maze yet, you connect it to the starting square and add it to the active set. If it is already part of the maze, you choose a different neighbor. If all of the neighbors are already part of the maze, you remove the starting square from the active set.

var new_node = startNode.getNeighbor();
if (new_node) {
    this.active_set_.push(new_node);
} else {
    goog.array.remove(this.active_set_, startNode);
}

Now choose a member from the active set and repeat until the active set is empty.

Putting this all together, this looks like the following:

Maze.prototype.generate = function() {
    this.active_set_.push(this.startNode_);
    while (this.active_set_.length > 0) {
        this.run_();
    }
};

Maze.prototype.run_ = function() {
    var node = this.pickActiveNode();
    var new_node = node.getNeighbor();
    if (new_node) {
        this.active_set_.push(new_node);
    } else {
        goog.array.remove(this.active_set_, node);
    }
};

The actual full code for this is a couple hundred lines long and you can get it from my Github repo. However, the two functions above are the “meat,” the rest is just details.

The most interesting part of the code above is the var node = this.pickActiveNode(); line. Depending on how you pick nodes from the active set, you get different “shaped” mazes. For example, here’s random:

30% choosing the first square in the active set:

60% choosing the first square in the active set:

Each maze has a different “character.” Pretty cool!