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}**.

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