Forum: Ruby Dungeon Generation (#80)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2006-06-01 17:25
(Received via mailing list)
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...
Giles B. (Guest)
on 2006-06-01 21:41
(Received via mailing list)
Although there was only one solution it seems to be a whopper! Wow. :-)
James G. (Guest)
on 2006-06-01 22:01
(Received via mailing list)
On Jun 1, 2006, at 12:38 PM, Giles B. wrote:

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

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

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

James Edward G. II
This topic is locked and can not be replied to.