[QUIZ] Dungeon Generation (#80)

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Kev Jackson

This week's task is a dark and dangerous one. Since the late 1970's, a
particular type of game has appealed to a particular type of person. Games?
From the 70's? Yep, there can only be one type of (computer) game with that
lineage that's still going strong (ish) after all these years - the Rogue-like
game!

For those not in the know, a typical Rogue-like game uses ascii characters (and
sometimes extra/non-ascii characters) to represent the (Tolkienish) game world.
The object of each of the games is subtly different, some require you to
retrieve the Amulet of Yendor, some require you to kill the Serpent of Chaos.
In common, they all require you to descend into a (randomly generated) dungeon.

Here's the task for this week. To write a dungeon creation program that will
generate and display a typical Rogue-like dungeon

A sample of which could look something like:

  depth 50ft (lvl 1) (pretty much the most trivial dungeon possible)
  stairs back to surface ( < ) and stairs down to 100 ft/lvl 2 ( > )
  
  ##########
  # < >#
  ##########
  
  depth 100ft (lvl2)
  stairs back up to 50ft and stairs down to 150 ft
  
               ###
  ######## #>#
  # # # #
  ##### ## # #
     # <####### #
     # #
     ##+#+#######
  
  depth 150ft (lvl3) (example of an 'arena' style level, includes a
                      'vault' style room)
  stairs back up to 100 ft and down to 200ft
  
  #################################
  # #
  # #
  # ##### ####### #
  # # + # # #># #
  ######### ## # ## #
  # # # # # # #
  # # ###+### #
  # # #
  # < + #
  #################################

Each ascii character represents terrain, an object (dungeon furniture) or a
monster.

Each dungeon must have an < (up stairs) and one > (down stairs) and they must be
connected in some way (ie the player must be able to move from the < (start) to
the > (down to the next level). The simplest dungeon is simply a single room
with both an up stairs and a down stairs.

  ~ = liquid (water => blue, lava => red, acid => green)
  # = wall
  + = door
  < = up stairs (back to the town)
  > = down stairs (deeper into the dungeon)

To actually create an entire game would take far far too long (some of these
games have been in development for years), but feel free to add as much or as
little of the Rogue-like attributes as you feel like, for instance:

  % = vegetation
  [a-zA-Z0-9] = monsters (ie => o = Orc, U = Demon, d = little dragon,
                          D = Greater Hell Wyrm)
  @ = player
  , = slime mold (yummy)
  ^ = trap
  * = gold (found in walls, ie ##*##)

For those that can parse C source, the source files from Zangband (my personal
favourite Rogue-like) are freely available (you have to extract them from a
tar.gz bundle):

  http://www.zangband.org

Oh, hell yes.

I hereby preemptively declare this, Best. Quiz. EVER.

...aaaand my weekend now appears to be full. :slight_smile:

-dB

···

--
David Brady
ruby_talk@shinybit.com
"Every normal man must be tempted, at times, to spit on his hands, hoist the Jolly Roger, and start slitting throats." -- H. L. Mencken

Tip (not a spoiler):

  If you, like me, were about to ask why those dungeons seem a bit messy, and there's no route from the start to the end in a lot of cases, you might want to check that you're viewing with a fixed width font before you post :slight_smile:

*whistles*

(Just about got away with that, I think).

48 whole hours!??!??! How's a man supposed to last so long, damn it?!

*sigh*

Come on, already. Tick-tock, tick-tock.

···

On 26 May 2006, at 13:28, Ruby Quiz wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

This is a fantastic quiz. I find it very interesting that ASCII art is so effective for quickly generating basic graphics. I think the great thing about it is its supreme ubiquity. There can't be too many languages where you can't print out some monospace text with a handful of lines of code.

However, it seems a little sad that in today's world of stupendous graphical processing power, and lovely displays, we can't trivially go a little bit further. I'd really like to see a library that is:

  1) Completely ubiquitous. ASCII's degree here will be hard to match, but for a given set of platforms (say Ruby on Unix, Win, OS X, common hand-helds) it should be possible.
  2) Works out of the box. It _must_ come as part of a standard instal, and before that, be well packaged. It must not need lots of extra installation of components. It's got to be pure ease in a glass.
  3) Makes the easy things easy.
  4) Make hard things quite easy.

3) Making the easy things easy.

ASCII does this wonderfully. You can't get much easier than "puts ':)'". BBC BASIC did it too with: "MOVE 100,100; DRAW 200,100". Logo also did it well with "fd 100".

Right from the outset, you can start to draw things. You don't need to create contexts, add them to windows, create an event loop, blah blah blah. You just begin. Brilliant.

4) Make the Harder things quite easy.

Ok, so full on GUI packages have useful things in them. Widgets that know how to behave and render themselves. We've got 3d, and scrollable surfaces and particle systems... All sort of great stuff. I think these things shouldn't be so much harder though, and their presence should not stop the easy things being easy. It's important to have a gentle progression from simple stuff to harder stuff.

Anyone got any thoughts in this area? :slight_smile:

Cheers,
  Benjohn

I'm glad to see some interest. I thought if was a great problem too, but got worried when no one was talking about it. :wink:

James Edward Gray II

···

On May 26, 2006, at 3:07 PM, David Brady wrote:

Oh, hell yes.

I hereby preemptively declare this, Best. Quiz. EVER.

Ouch. My earliest programming experiences were with basic and logo on
the Amstrad CPC, and later the Spectrum. They did this kind of thing and
I have to say, in the twenty years since then, I've never yearned to do
it again :slight_smile: It's all well and good until you have a thousand lines (or
more) of 'move here, draw this, select this pen, move here...' and find
an errant green pixel in the middle of the screen...

Hmm, this may be why I still have a strong aversion to all forms of
graphical programming (including GUI)...

···

On Sun, 2006-05-28 at 19:05 +0900, Benjohn Barnes wrote:

ASCII does this wonderfully. You can't get much easier than "puts
':)'". BBC BASIC did it too with: "MOVE 100,100; DRAW 200,100". Logo
also did it well with "fd 100".

--
Ross Bamford - rosco@roscopeco.REMOVE.co.uk

This probably fits more into "coordination languages" than with "ASCII
art", but what *I've* always wanted was a programming language that
would let me draw arbitrary shapes and connectors on a canvas, like
XFig, Dia or Visio, and then let me assign more or less arbitrary
behaviors to them. One such behavior would be animation -- objects need
to move about.

There are specialized tools that sort of do this: Max/MSP and its open
source clones Jmax and PureData will let you design basic digital signal
processing systems this way, but the shapes aren't necessarily
customizable, and the behavior of the objects is mostly limited to
things that make sense in computer music and digital signal processing.

QTDesigner, Korundum and Kommander will let you design GUIs with
"standard" things like list boxes, buttons, etc., but again, the shapes
are given. And there are plenty of graphical languages, UML-based tools,
etc. Hypercard was close, actually, except for its metaphor of a stack
of cards.

What I'd like is a single graphical language that would let me build,
for example, Petri nets, queuing networks, Mind Maps, dialog maps,
entity-relationship diagrams, clouds of tags -- about any kind of
graphical tool you could think of -- and have the elements all be active
objects/actors, with methods, etc. And, of course, it needs to be open
source.

I'm probably going to revisit Kommander to see if it can do what I want,
because it's compatible with QTRuby. I also think Blender might be able
to do it, although I'm not all that interested in "physical realism" --
I don't want cars or people, but abstract symbolic diagrams. Anybody
here have any ideas on tools I might be overlooking?

Benjohn Barnes wrote:

···

This is a fantastic quiz. I find it very interesting that ASCII art is
so effective for quickly generating basic graphics. I think the great
thing about it is its supreme ubiquity. There can't be too many
languages where you can't print out some monospace text with a
handful of lines of code.

However, it seems a little sad that in today's world of stupendous
graphical processing power, and lovely displays, we can't trivially go
a little bit further. I'd really like to see a library that is:

    1) Completely ubiquitous. ASCII's degree here will be hard to
match, but for a given set of platforms (say Ruby on Unix, Win, OS X,
common hand-helds) it should be possible.
    2) Works out of the box. It _must_ come as part of a standard
instal, and before that, be well packaged. It must not need lots of
extra installation of components. It's got to be pure ease in a glass.
    3) Makes the easy things easy.
    4) Make hard things quite easy.

3) Making the easy things easy.

ASCII does this wonderfully. You can't get much easier than "puts
':)'". BBC BASIC did it too with: "MOVE 100,100; DRAW 200,100". Logo
also did it well with "fd 100".

Right from the outset, you can start to draw things. You don't need to
create contexts, add them to windows, create an event loop, blah blah
blah. You just begin. Brilliant.

4) Make the Harder things quite easy.

Ok, so full on GUI packages have useful things in them. Widgets that
know how to behave and render themselves. We've got 3d, and scrollable
surfaces and particle systems... All sort of great stuff. I think
these things shouldn't be so much harder though, and their presence
should not stop the easy things being easy. It's important to have a
gentle progression from simple stuff to harder stuff.

Anyone got any thoughts in this area? :slight_smile:

Cheers,
    Benjohn

--
M. Edward (Ed) Borasky

http://linuxcapacityplanning.com

<very_unsubtle_attempt_to_get_people_on_the_quiz>
So no one else knows how to go about building up a random dungeon, huh?
I Guess I'll have to put that on my resume: "only memeber of the Ruby
community able to automatically build random mazes". I didn't know I was
_that_ good. In fact, as we've got appraisals here at work, I think
it'll be good material to try out for a pay rise.
</very_unsubtle_attempt_to_get_people_on_the_quiz>

:slight_smile:

Regards,
  Benjohn

I'm pretty booked this weekend, but I hope I can fit this in. I love
Angband, and I love Greater Hell Wyrms.

···

On 5/26/06, James Edward Gray II <james@grayproductions.net> wrote:

On May 26, 2006, at 3:07 PM, David Brady wrote:

> Oh, hell yes.
>
> I hereby preemptively declare this, Best. Quiz. EVER.

I'm glad to see some interest. I thought if was a great problem too,
but got worried when no one was talking about it. :wink:

:slight_smile: Ah. I love graphics programming, although I do agree that it could get hairy back then. I think that's before I learnt about "abstraction" though. I've noticed that I've been doing less and less graphics though, and I think it's down to the barrier to entry that currently exists. That's what I want from this hypothetical library. The smallest barrier to entry possible, and the smoothest learning curve possible... I think those two properties are the reason that I like Ruby too.

···

On 28 May 2006, at 11:30, Ross Bamford wrote:

On Sun, 2006-05-28 at 19:05 +0900, Benjohn Barnes wrote:

ASCII does this wonderfully. You can't get much easier than "puts
':)'". BBC BASIC did it too with: "MOVE 100,100; DRAW 200,100". Logo
also did it well with "fd 100".

Ouch. My earliest programming experiences were with basic and logo on
the Amstrad CPC, and later the Spectrum. They did this kind of thing and
I have to say, in the twenty years since then, I've never yearned to do
it again :slight_smile: It's all well and good until you have a thousand lines (or
more) of 'move here, draw this, select this pen, move here...' and find
an errant green pixel in the middle of the screen...

Hmm, this may be why I still have a strong aversion to all forms of
graphical programming (including GUI)...

M. Edward (Ed) Borasky wrote:
...

What I'd like is a single graphical language that would let me build,
for example, Petri nets, queuing networks, Mind Maps, dialog maps,
entity-relationship diagrams, clouds of tags -- about any kind of
graphical tool you could think of -- and have the elements all be active
objects/actors, with methods, etc. And, of course, it needs to be open
source.

IIRC TkCanvas lets you put general Tk widgets on a canvas, connect them
with stretchy lines and arrows, move them about, scroll them, etc.

···

--
      vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

} <very_unsubtle_attempt_to_get_people_on_the_quiz>
} So no one else knows how to go about building up a random dungeon, huh?
} I Guess I'll have to put that on my resume: "only memeber of the Ruby
} community able to automatically build random mazes". I didn't know I was
} _that_ good. In fact, as we've got appraisals here at work, I think
} it'll be good material to try out for a pay rise.
} </very_unsubtle_attempt_to_get_people_on_the_quiz>
}
} :slight_smile:

Heh. Well, the thing about the Ruby Quiz is that unless your day job is not
terribly demanding or your weekend is not thoroughly allocated, there just
isn't time. I'd love to dedicate a few hours to generating random dungeons,
but I was away for the weekend, the house is a mess, the AC is broken,
two of the sinks are clogged, the dishes need doing, and we're on a
production push at work. The Ruby Quiz is lower priority than any of those,
I'm afraid, so...

} Regards,
} Benjohn
--Greg

···

On Wed, May 31, 2006 at 05:05:58PM +0900, benjohn@fysh.org wrote:

Wait wait.. where's the archives? I just joined the list and can pwn you at
angband :slight_smile:

···

On 5/26/06, Wilson Bilkovich <wilsonb@gmail.com> wrote:

On 5/26/06, James Edward Gray II <james@grayproductions.net> wrote:
> On May 26, 2006, at 3:07 PM, David Brady wrote:
>
> > Oh, hell yes.
> >
> > I hereby preemptively declare this, Best. Quiz. EVER.
>
> I'm glad to see some interest. I thought if was a great problem too,
> but got worried when no one was talking about it. :wink:
>

I'm pretty booked this weekend, but I hope I can fit this in. I love
Angband, and I love Greater Hell Wyrms.

:slight_smile: Yeah yeah, a fine excuse.

At least you have one. - feeling like a school master here.

Ah well, shame, it's a really cool quiz too.

Cheers,
  Benjohn

···

On 31 May 2006, at 13:42, Gregory Seidman wrote:

On Wed, May 31, 2006 at 05:05:58PM +0900, benjohn@fysh.org wrote:
} <very_unsubtle_attempt_to_get_people_on_the_quiz>
} So no one else knows how to go about building up a random dungeon, huh?
} I Guess I'll have to put that on my resume: "only memeber of the Ruby
} community able to automatically build random mazes". I didn't know I was
} _that_ good. In fact, as we've got appraisals here at work, I think
} it'll be good material to try out for a pay rise.
} </very_unsubtle_attempt_to_get_people_on_the_quiz>
}
} :slight_smile:

Heh. Well, the thing about the Ruby Quiz is that unless your day job is not
terribly demanding or your weekend is not thoroughly allocated, there just
isn't time. I'd love to dedicate a few hours to generating random dungeons,
but I was away for the weekend, the house is a mess, the AC is broken,
two of the sinks are clogged, the dishes need doing, and we're on a
production push at work. The Ruby Quiz is lower priority than any of those,
I'm afraid, so...

Mailing list archives:

http://ruby-talk.org/ruby/ruby-talk/index.shtml

Ruby Quiz archives:

http://rubyquiz.com/

James Edward Gray II

···

On May 26, 2006, at 3:47 PM, Jason Mayer wrote:

Wait wait.. where's the archives? I just joined the list and can pwn you at
angband :slight_smile:

I'm in pretty much the same boat, really. I might have something by the weekend, but I don't feel very motivated if I'm just going to miss the summary.

-mental

···

On Thu, 1 Jun 2006 04:43:42 +0900, Benjohn Barnes <benjohn@fysh.org> wrote:

The Ruby Quiz is lower priority than any of those, I'm afraid, so...

This quiz in particular is a painful one because it's so darned cool, but
takes a little more brainpower than I can possibly apply right now :frowning:

···

-----Original Message-----
From: MenTaLguY [mailto:mental@rydia.net]
Sent: Wednesday, May 31, 2006 3:50 PM
To: ruby-talk ML
Subject: Re: [QUIZ] Dungeon Generation (#80)

On Thu, 1 Jun 2006 04:43:42 +0900, Benjohn Barnes <benjohn@fysh.org> wrote:

The Ruby Quiz is lower priority than any of those, I'm afraid, so...

I'm in pretty much the same boat, really. I might have something by the
weekend, but I don't feel very motivated if I'm just going to miss the
summary.

-mental

!DSPAM:447df3b84817746714366!

Agreed with all of the above...
I may try it this coming weekend, even if the quiz has moved onto
greener pastures.

Hi all,

I did the quiz :slight_smile: I am new to Ruby so any tips are appreciated.

View at

http://curi.us/code/dungeon.html

or below:

# dungeon.rb Version 1.0
# Elliot Temple
# May 31, 2006

···

#
# This is my first Ruby Quiz entry
#
# For Ruby Quiz #80
# http://rubyquiz.com/quiz80.html
#
# Generates an ASCII dungeon with an evolutionary algorithm. Makes random
# changes and calls undo if the evaluate method returns a lower number.
# Continues for a while, then makes sure to get valid output.
#
# It works but could benefit from tuning various numbers and some new features
# in the evaluate function. It could also be faster. Sample output at bottom.

class Tile
   attr_accessor :x, :y
   @@TileType = Struct.new(:graphic, :frequency, :walkable)
   @@data = {
   :wall => @@TileType.new("#", 250, false),
   :open => @@TileType.new(" ", 120, true),
   :water => @@TileType.new("~", 10, true),
   :stairs_up => @@TileType.new("<", 1, true),
   :stairs_down => @@TileType.new(">", 1, true)
   }
   def initialize x, y, type = :any
     @x = x
     @y = y
     if type == :any
       @type_history = [get_rand_tile]
     else
       @type_history = [type]
     end
   end
   def type
     @type_history.last
   end
   def to_s
     @@data[@type_history.last].graphic
   end
   def get_rand_tile
     total = @@data.inject(0) { |total, pair| total + pair[1].frequency }
     @@data.each do |k,v|
       return k if rand(total) < v.frequency
       total -= v.frequency
     end
   end
   def random_change
     @type_history << get_rand_tile
   end
   def undo(n=1)
     n.times do
       @type_history.pop
     end
   end
   def walkable?
     @@data[@type_history.last].walkable
   end
end

class Map
   def initialize(height,width)
     @height = height
     @width = width
     @map = []
     @changeable_tiles = []
     @last_changed = []
     width.times do |i|
       column = []
       height.times do |j|
         if (j == 0) or (j == width - 1) or (i == 0) or (i == width - 1)
           column << Tile.new(i, j, :wall)
         else
           tmp = Tile.new(i, j)
           column << tmp
           @changeable_tiles << tmp
         end
       end
       @map << column
     end
     @changeable_tiles = @changeable_tiles.sort_by {rand}
     # x = @changeable_tiles.shift
     # x.become_stairs_up
     # x = @changeable_tiles.shift
     # x.become_stairs_down
   end
   def to_s
     # old version that put # around the output
     # '#' * (@width+2) + "\n" + (@map.collect { |row| '#' + row.collect {|tile| tile.to_s}.join("") + '#' }.join "\n") + "\n" + '#' * (@width+2)
     @map.collect { |row| row.collect {|tile| tile.to_s}.join("") }.join "\n"
   end

   def update n=1
     n.times do
       x = @changeable_tiles[rand(@changeable_tiles.length)]
       x.random_change
       @last_changed << x
     end
   end

   def undo n=1
     n.times do
       @last_changed.pop.undo
     end
   end

   def path_between start, destination, exclude = []
     return false if start.nil?
     return true if start == destination
     return false unless start.walkable?
     return false if exclude.include?(start)
     exclude << start
     path_between(self.down(start), destination, exclude) or path_between(self.up(start), destination, exclude) or path_between(self.left(start), destination, exclude) or path_between(self.right(start), destination, exclude)
   end

   def path_between2 start, destination
     g = find_group(start)
     g.include?(destination)
   end

   def find_group start, walkable = true, group = []
     return group if start.nil?
     return group unless start.walkable? == walkable
     return group if group.include?(start)
     group << start
     find_group(self.down(start), walkable, group)
     find_group(self.up(start), walkable, group)
     find_group(self.left(start), walkable, group)
     find_group(self.right(start), walkable, group)
     return group
   end

   def count_groups walkable = true
     tiles = @map.flatten.select { |tile| tile.walkable? == walkable }
     count = 0
     while tiles.any?
       count += 1
       tiles -= find_group(tiles[0], walkable)
     end
     count
   end

   def left tile
     @map[tile.x - 1][tile.y] rescue nil
   end
   def right tile
     @map[tile.x + 1][tile.y] rescue nil
   end
   def down tile
     @map[tile.x][tile.y - 1] rescue nil
   end
   def up tile
     @map[tile.x][tile.y + 1] rescue nil
   end

   def stair_distance
     (find_one(:stairs_up).x - find_one(:stairs_down).x).abs + (find_one(:stairs_up).y - find_one(:stairs_down).y).abs
   end

   def find_one tile_type
     @map.flatten.detect {|tile| tile_type == tile.type}
   end

   def number_of tile_type
     @map.flatten.inject(0) do |total, tile|
       tile.type == tile_type ? total + 1 : total
     end
   end

   def valid?
     return false unless number_of(:stairs_up) == 1
     return false unless number_of(:stairs_down) == 1
     return false unless path_between(find_one(:stairs_up), find_one(:stairs_down))
     true
   end

   def evaluate
     score = 0
     score -= 200 unless valid?
     if (number_of(:stairs_up) == 1) && (number_of(:stairs_down) == 1)
       score += 200 * stair_distance
     end
     score -= 100 * count_groups(true)
     score -= 70 * count_groups(false)
   end
end

map = Map.new 15,15

tmp = map.to_s
map.update 50
map.undo 40
map.update 50
map.undo 60
raise "undo bug" unless tmp == map.to_s

valid_steps = 0
e = map.evaluate
n = 25
undos = 0

2000.times do
   map.update n
   if map.evaluate >= e
     e = map.evaluate
   else
     map.undo n
     undos += 1
   end
end

until map.valid?
   map.update 1
   valid_steps += 1
end

puts map
puts "steps to validate #{valid_steps}"
puts "undos #{undos}"
puts "stair distance is #{map.stair_distance}"
puts map.count_groups
puts map.count_groups(false)
puts map.evaluate

=begin
Sample Output:

###############
## ##### ## #
## ## ## ### ##
# # ##
## > ## #######
## ## #######
####### ## # ##
### ### ## #
### ## # #
# #### #~~###
### #### ## ##
####~ #####
##### # #### #
# <## ######
###############
steps to validate 0
undos 1959
stair distance is 11
4
1
1730
=end

-- Elliot Temple