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

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

···

On 6/1/06, Ruby Quiz <james@grayproductions.net> wrote:

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

--
Giles Bowkett
http://www.gilesgoatboy.org

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

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

James Edward Gray II

···

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

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