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.
The View from the Foothills 