by Kev Jackson
This week's task is a dark and dangerous one. Since the late 1970's, a particular type of game has appealed to a particular type of person. Games? From the 70's? Yep, there can only be one type of (computer) game with that lineage that's still going strong (ish) after all these years - the Rogue-like game!
For those not in the know, a typical Rogue-like game uses ascii characters (and sometimes extra/non-ascii characters) to represent the (Tolkienish) game world. The object of each of the games is subtly different, some require you to retrieve the Amulet of Yendor, some require you to kill the Serpent of Chaos. In common, they all require you to descend into a (randomly generated) dungeon.
Here's the task for this week. To write a dungeon creation program that will generate and display a typical Rogue-like dungeon
A sample of which could look something like:
depth 50ft (lvl 1) (pretty much the most trivial dungeon possible)
stairs back to surface ( < ) and stairs down to 100 ft/lvl 2 ( > )
##########
# < >#
##########
depth 100ft (lvl2)
stairs back up to 50ft and stairs down to 150 ft
###
######## #>#
# # # #
##### ## # #
# <####### #
# #
##+#+#######
depth 150ft (lvl3) (example of an 'arena' style level, includes a
'vault' style room)
stairs back up to 100 ft and down to 200ft
#################################
# #
# #
# ##### ####### #
# # + # # #># #
######### ## # ## #
# # # # # # #
# # ###+### #
# # #
# < + #
#################################
Each ascii character represents terrain, an object (dungeon furniture) or a monster.
Each dungeon must have an < (up stairs) and one > (down stairs) and they must be connected in some way (ie the player must be able to move from the < (start) to the > (down to the next level). The simplest dungeon is simply a single room with both an up stairs and a down stairs.
~ = liquid (water => blue, lava => red, acid => green)
# = wall
+ = door
< = up stairs (back to the town)
> = down stairs (deeper into the dungeon)
To actually create an entire game would take far far too long (some of these games have been in development for years), but feel free to add as much or as little of the Rogue-like attributes as you feel like, for instance:
% = vegetation
[a-zA-Z0-9] = monsters (ie => o = Orc, U = Demon, d = little dragon,
D = Greater Hell Wyrm)
@ = player
, = slime mold (yummy)
^ = trap
* = gold (found in walls, ie ##*##)
For those that can parse C source, the source files from Zangband (my personal favourite Rogue-like) are freely available (you have to extract them from a tar.gz bundle):
Quiz Summary
This is a fun problem, probably hindered by the holiday weekend. Luckily, we did get a great solution from Benjohn Barnes. (We got another great one from Elliot Temple after I wrote this. Sorry Elliot!) Let's dig into how that works.
First, it's good to see what we are building. When you execute Benjohn's program you get one level of a dungeon. Here's a small section of one of the levels it generated:
########### ######## ##################################
########### ######## ##################################
###################### ########### ##################################
###################### ########### ##################################
###################### ##### #############################
###################### ##### #############################
############## ### ##### #############################
########## ### ## #############################
########## ### ## #############################
########## #############################
########## ###### #########################
########## ##### #########################
########## ##### #########################
########## ##### #########################
########## ##### #########################
########## ##### #########################
########## ##### #######################
########## ## ##### #################
########## # ## ########### #################
########## # ### > ############ #################
########## # ### ############ #################
########## ##### ############ #################
########### ## ###### ############ #################
########### # # ############ #################
########### # ## #################### #################
########### ## #################### #################
##### ################ #################
##### ################ #################
##### ################ #################
##### ################ #################
##### ################ #################
############### ################ #################
############### #### # ##################### ##################
################## #### # #################### ##################
################## #### ## ############### ##################
################## #### ####### ############# ##################
################## #### ###### ###### ##################
################## ###### ####### ###### ##################
I love the "catacombey" feel of this. Let's see how it comes together. Here's the main executable:
require 'arena.rb'
def create_dungeon( arena, walk_length, have_stairs = true,
walker = Walker.new )
while(walk_length>0)
walk_length -=1
# Cut out a bit of tunnel where I am.
arena[*walker.position] = ' '
walker.wander
# Bosh down a room occasionally.
if(walk_length%80==0)
create_room(arena, walker)
end
# Spawn off a child now and then. Split the remaining walk_length
# with it. Only one of us gets the stairs though.
if(walk_length%40==0)
child_walk_length = rand(walk_length)
walk_length -= child_walk_length
if child_walk_length > walk_length
create_dungeon( arena, child_walk_length, have_stairs,
walker.create_child )
have_stairs = false
else
create_dungeon( arena, child_walk_length, false,
walker.create_child )
end
end
end
# Put in the down stairs, if I have them.
if(have_stairs)
arena[*(walker.position)] = '>'
end
end
def create_room(arena, walker)
max = 10
width = -rand(max)..rand(max)
height = -rand(max)..rand(max)
height.each do |y|
width.each do |x|
arena[x+walker.x, y+walker.y] = ' '
end
end
end
# Create an arena, and set of a walker in it.
arena = Arena.new
create_dungeon(arena, 400)
# Put in the up stairs.
arena[0,0] = '<'
# Show the dungeon.
puts arena
The application code at the end is trivial enough, except, of course, that we don't yet know what an Arena or a Walker are. We can see the primary work method that gets triggered here though and thus we know where to look next.
The create_dungeon() method is where all the action is. The parameters it takes are an Arena, a walk length and Walker, and a boolean involving stairs. We saw the Arena get printed in the application code, so it's probably safe to assume it is the canvas we intend to paint a dungeon onto at this point.
Ignoring the stair parameter for now, it's clear we need to know more about this Walker and what it does. If you browse through this method reading the comments and noticing calls like walker.position and walker.wander, you should get the idea pretty quickly.
Benjohn just turns a digital spelunker loose in the dungeon and carves out tunnels where ever it walks. Every so often, the code even carves out a room right around where our explorer is standing. That's what create_room() does. Because these rooms can overlap, the end result doesn't end up being all rectangles, which gives us the nice dungeon feel we saw earlier.
You can also see that the Walker sometimes splits and goes forward in two directions (via recursion). This is what the stairs parameter is for. Only one Walker is allowed to have them and the one that does will drop them just before the method exits.
Now that we have an idea of the process, we need to see the other pieces. Here's the Arena object:
attr_reader :left, :right, :top, :bottom
def initialize
@arena = Hash.new {|h,k| h[k]=Hash.new('#')}
@left = @right = @top = @bottom = 0
end
def [](x,y)
@arena[y][x]
end
def []=(x,y,v)
# I originally worked out the width and height at the end by scanning
# the map. I was also using a single map, rather than the 'map in a
# map' now used. I found that dungeon creation was slow, but almost
# all of it was the final rendering stage, so switched over to the
# current approach.
@arena[y][x]=v
@left = [@left, x].min
@right = [@right, x].max
@top = [@top, y].min
@bottom = [@bottom, y].max
end
def to_s
to_array.collect {|row| row.join}.join("\n")
end
def to_array
(top-1..bottom+1).collect do |y|
(left-1..right+1).collect do |x|
self[x,y]
end
end
end
end
This is just what we expected. A Hash of Hashes (indexed by x and y coordinates) is used to hold the final rendering. A Hash is used here, instead of an Array, so the Walker can literally wander() anywhere he chooses, expanding the world as he goes. The code tracks the boundaries of the map as the Walker moves and sets new areas and those boundaries are used to print the end result. Anything not set by the dungeon creation code is a wall.
One more piece left. Time to examine the Walker:
# my direction, and it's this that I randomly adjust, rather
# than simply jittering my position.
class Walker
attr_accessor :x, :y, :direction
def initialize(x=0, y=0, direction=0)
@x, @y, @direction = x, y, direction
end
# Handy for testing.
def position
[x,y]
end
# Adjust direction, and walk once.
def wander
perturb_direction
walk
end
# Make the child pointing of 90 degrees away from me.
def create_child
Walker.new(x, y, direction + 2*rand(2) - 1)
end
def perturb_direction
@direction += rand*wiggle_max - (wiggle_max/2)
end
def walk(d = direction_with_smoothing_fuzz)
# Ensure that the direction is correctly wrapped around.
d = (d.round)%4
@x += [1,0,-1,0][d]
@y += [0,1,0,-1][d]
self
end
# Adding some noise on to the direction "stocastically" samples
# it, smoothing off turns, and making it more catacombey.
def direction_with_smoothing_fuzz
@direction + rand*smoothing - smoothing/2
end
# How wiggley are the dungeons? Bigger numbers are more wiggly
# and compact.
def wiggle_max
0.5
end
# How smooth are tunnels? Larger numbers give smoother more
# 'catacombe' like tunnels (and smaller dungeons). Smaller
# numbers give more cartesian & straight tunnels.
def smoothing
0.9
end
end
Though that looks long, they are all very trivial methods and the comments are plenty and good. The short story is in the comment right at the beginning. I can't explain it any better than that.
Do look at the methods at the end of the Walker. You can get a feel from the comments here how this code was tuned into its current form as Benjohn tested it. Speaking of tests, did I mention the solution included test cases for Arena and Walker? I won't show them here since this is already lengthy, but they are good stuff and I recommend looking them over.
My thanks to Benjohn and Elliot for finding the time when the rest of us were too busy.
Tomorrow we have a trivial challenge, but one we've probably all thought about...
