From: Giles Bowkett Date: 2006-06-02T02:38:21+09:00 Subject: Re: [SUMMARY] Dungeon Generation (#80) Although there was only one solution it seems to be a whopper! Wow. :-) On 6/1/06, Ruby Quiz 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