Dungeon Generation (#80)


#1

This is a fun problem, probably hindered by the holiday weekend.
Luckily, we
did get a great solution from Benjohn B… (We got another great one
from
Elliot T. 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 'walker.rb'
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:

class Arena
  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:

# This class basically implements a random walk. I remember
# 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…


#2

Although there was only one solution it seems to be a whopper! Wow. :slight_smile:


#3

On Jun 1, 2006, at 12:38 PM, Giles B. wrote:

Although there was only one solution it seems to be a whopper!
Wow. :slight_smile:

There were two actually. Don’t miss the other one:

http://www.rubyquiz.com/quiz80.html

James Edward G. II