From: Ruby Quiz <james@...>
Date: 2006-06-01T22:23:16+09:00
Subject: [SUMMARY] Dungeon Generation (#80)

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 '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...