January 20, 2005

The Ramble Chronicles: Maze Generation 1

I'm writing Ramble for my kids to play, but I'm also writing it for myself. If a game is to be appealing to its author, then it has to include a fair amount of unpredictability. In a game like Ramble, that means generating interesting but unpredictable levels. The problem has many aspects, but in this essay I'm going to focus on the issue of random terrain in general, and random mazes in particular.

Note: So happens, this is the 1,000th post on this blog; so you should click through to the rest of it, if only for the pretty pictures.

I owe some of the ideas that follow to two web sites. The first is Jamis Buck's Random Dungeon Design, which describes the algorithms behind a program he wrote to randomly generate dungeons for traditional pencil and paper role-playing games; the second is Think Labyrinth, a site dedicated to mazes and random maze generation algorithms.

The algorithm I'm going to describe is called a recursive backtracker. It belongs to a class of algorithms that all work more or less the same way. You begin with a rectangular array of rooms separated by walls. Given a randomly chosen starting room, these algorithms proceed by repeatedly selecting a room adjacent to a room in the maze and opening a door in the wall between the two. When the algorithm's done, you've got what's called a "perfect maze": one in which every room is connected to every other room by exactly one path, and in which there are no circular paths. The algorithms differ in how the new rooms are selected.

The recursive backtracker uses a simple pushdown stack; the algorithm is as follows:

  • Pick a room randomly, and push it onto the stack. This is the starting room.
  • Pick a room adjacent to the first room, and open a door between them. This room is the current room.
  • Push the starting room onto the stack.
  • While there's at least one room left on the stack, repeat the following steps:
    • If there are any unconnected rooms next to the current room,
      • Pick one randomly, and open a door between it and the current room.
      • Push the current room onto the stack; the new room becomes the current room.
      • Go back to the top of the loop.
    • If there are no unconnected rooms next to the current room,
      • Pop a room off of the stack; it becomes the current room.
      • Go back to the top of the loop.
  • When the stack is empty, the maze is complete.

Here's a simple example, using a 3*3 maze. The stack is shown under each picture of the maze.

  • D is the randomly chosen starting room. We could choose any of A, E, or G as the current room; we'll roll a die and choose A. We open a door and push D on the stack.
  • There's only one unattached room next to A, and that's B. We open a door to it, and push A on the stack.
  • From B we can pick E or C, and we pick E, pushing B on the stack.
  • From E we can pick F or H. We pick F, pushing E on the stack.
  • From F we can pick C or I. We pick C, pushing F on the stack.
  • C has nothing unattached next to it, so we pop F back off of the stack. From F we can pick I, and we do. F goes back on the stack.
  • From I we can only pick H, and we do. I goes on the stack.
  • From H we can only pick G, and we do. H goes on the stack.
  • G is a dead end. We pop rooms off of the stack one at a time, looking for a room with an unattached neighbor. When the stack is empty, we're done; we have a maze.

Here's a 10*20 maze generated using this algorithm:

As you can see, it has relatively few short dead-ends and lots of long and twisty corridors, which is part of what I was looking for. It's also one of the faster algorithms, which is another part of what I was looking for.

Now it's time to think about how to represent all this in Tcl.

A maze is a rectangular array of rooms, so we'll represent it as a matrix. In an earlier essay, Efficient Matrices, I talked about how I planned to do that in Tcl; feel free to review. So for a 3*3 maze, I'll want to have a 3*3 matrix; each element in the matrix describes one room in the maze. And we'll use matrix notation. The dimensions of the maze are m rows by n columns, which are numbered from 1 to m and from 1 to n respectively. Each room in the maze is named by a pair of indices, which I'll write in Tcl list format as {i j}. Thus, the upper left roomm is {1 1}.

Now, what do I store in each cell of the matrix?

Each room in the maze has four walls, which I'll identify as the north, south, east, and west walls, or n, s, e, and w respectively. Each wall can be open (missing) or closed, which means we need four Boolean flags for each room. There are any number of ways to do that; being an old-time C programmer, I chose to use a bit vector--a coded integer the bits of which correspond to the flags I need. Here's an array that relates the four walls and the related bits:

    array set mask {
        n   1
        e   2
        s   4
        w   8
    }

    puts "n's bit value is $mask(n)"

Thus, if the north and west walls of a room are open, the value stored in the matrix for the room will be 9 = 1 + 8. If the value is 0, that means that no walls are open. I can initialize my matrix to all zeroes, and that means that all the walls are closed, ready for the algorithm to begin.

Now, a wall has two sides; the north wall of one room is the south wall of another; when opening a wall, we need to update the value in both rooms. Given a wall, the following array lists the bit value of the other side of the wall within its room:

    array set revmask {
        n   4
        e   8
        s   1
        w   2
    }

    puts "The bit value of the opposite of n is $revmask(n)"

Given the coordinates of a room, {i j}, and a direction, I will frequently want to know the coordinates of the adjacent room in that direction. I've written elsewhere of some utility routines I wrote to make this easier; I wrote the maze code before I wrote those, so here will do it the hardway. I need the following two arrays, which show the coordinate offsets by direction:

    # Row offsets
    array set roff {
        n  -1   ne -1  
        e   0   se  1
        s   1   sw  1
        w   0   nw -1
    }

    # Col offsets
    array set coff {
        n   0   ne  1
        e   1   se  1
        s   0   sw -1
        w  -1   nw -1
    }

Our recursive backtracking algorithm is written in terms of three lower-level functions: pickfrom, freedirs, and removewall. The first, pickfrom, I described in the essay Randomness; given a list, it returns a randomly chosen entry from the list.

Given a maze and an {i j} coordinate pair, freedirs returns a list of the directions n, s, e, or w in which there are unattached (or "free") rooms. It looks like this:

proc maze::freedirs {maze i j} {
    variable roff
    variable coff

    set dirs {}

    foreach dir {n s e w} {
        # Get the tile in that direction
        set i2 [expr {$i + $roff($dir)}]
        set j2 [expr {$j + $coff($dir)}]

        # If it's over the edge, skip it.
        if {![minside $maze $i2 $j2]} {
            continue
        }


        # If it's free, add the direction to the list.
        if {[lindex $maze $i2 $j2] == 0} {
            lappend dirs $dir 
        }
    }

    return $dirs
}

The room is free if no walls are open, i.e., if the room's value has no bits set, i.e., if the room's value is zero. The minside function is one of the matrix routines; it simply does a range check on a coordinate pair to see if it lies "inside" the matrix. Here it's used to skip invalid directions from rooms on the edge of the maze.

The removewall function removes a wall between two rooms given a variable containing a maze, the {i j} coordinates of one of the rooms, and the direction dir to the other room. The routine assumes that both rooms exist in the maze, e.g., their coordinates are minside the matrix. It looks like this:

proc maze::removewall {mazevar i j dir} {
    upvar $mazevar maze
    variable mask
    variable revmask
    variable roff
    variable coff

    # FIRST, if there's no wall we don't need to do anything.
    set map [lindex $maze $i $j]

    if {$map & $mask($dir)} {
        return
    }

    # NEXT, add the wall on this side.
    set map [expr {$map | $mask($dir)}]
    lset maze $i $j $map

    # NEXT, add the wall on the other side.
    incr i $roff($dir)
    incr j $coff($dir)

    set map [lindex $maze $i $j]
    set map [expr {$map | $revmask($dir)}]
    lset maze $i $j $map
}

Finally, we put it all together in mkrecback, which takes the dimensions of the maze and returns the finished maze. It also takes an option, -inertia 0|1; if 1, the maze is generated with "inertia", and if 0 without. Having inertia means that when it comes time to pick the next room to add to the maze, we're likely to keep going in the same direction as last time (assuming we can). That gives us longer straight sections in the maze, which I happen to like.

proc maze::mkrecback {m n args} {
    variable roff
    variable coff
    variable mask
    variable revmask

    # FIRST, get the options
    array set opts {
        -inertia 1
    }
    array set opts $args

    # FIRST, make a maze of all free cells.
    set maze [matrix::new $m $n -type maze -init 0]

    # NEXT, pick the starting cell.
    set i [rand 1 [mrows $maze]] 
    set j [rand 1 [mcols $maze]]

    # NEXT, get a direction to a free cell; there will always be one.
    set dir [pickfrom [freedirs $maze $i $j]]

    # NEXT, remove the wall between them.
    removewall maze $i $j $dir

    # NEXT, push the starting cell on the stack, and move to the new
    # cell.
    set stack {}
    lappend stack [list $i $j]
    set lastdir $dir
    set i [expr {$i + $roff($dir)}]
    set j [expr {$j + $coff($dir)}]

    # NEXT, add cells until the stack is empty.
    while {[llength $stack] > 0} {
        # Are there any free cells next to the current cell?
        set dirs [freedirs $maze $i $j]
        
        # If not, pop a cell from the stack and continue.
        if {[llength $dirs] == 0} {
            set i [lindex $stack end 0]
            set j [lindex $stack end 1]
            set stack [lrange $stack 0 end-1]
            continue
        }

        # Make it more likely to continue in the same direction.
        if {$opts(-inertia) && [lsearch -exact $dirs $lastdir] != -1} {
            lappend $dirs $lastdir
        }

        # Otherwise, carve into one.
        set dir [pickfrom $dirs]
        removewall maze $i $j $dir

        # Now push the current cell onto the stack and go on to the next.
        lappend stack [list $i $j]

        set i [expr {$i + $roff($dir)}]
        set j [expr {$j + $coff($dir)}]
    }

    return $maze
}

And that's (ha!) all there is to it.

Well, actually there's a lot more I need to do to a maze like this before it becomes a real dungeon level; in future essays I'll be talking about some of the things I do to make that happen.

Posted by Will Duquette at January 20, 2005 07:41 PM