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.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-05-26 14:30
(Received via mailing list)
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
9d0c4e1ee48f3e5a57388eafcb22abcb?d=identicon&s=25 David Brady (Guest)
on 2006-05-26 22:07
(Received via mailing list)
Oh, hell yes.

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

...aaaand my weekend now appears to be full.  :-)

-dB
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-05-26 22:35
(Received via mailing list)
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.  ;)

James Edward Gray II
25e11a00a89683f7e01e425a1a6e305c?d=identicon&s=25 Wilson Bilkovich (Guest)
on 2006-05-26 22:38
(Received via mailing list)
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.  ;)
>

I'm pretty booked this weekend, but I hope I can fit this in. I love
Angband, and I love Greater Hell Wyrms.
35b0b4029fd4387842ec88a8e99d84de?d=identicon&s=25 Jason Mayer (Guest)
on 2006-05-26 22:48
(Received via mailing list)
Wait wait.. where's the archives?  I just joined the list and can pwn
you at
angband :)
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-05-26 23:15
(Received via mailing list)
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 :)

Mailing list archives:

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

Ruby Quiz archives:

http://rubyquiz.com/

James Edward Gray II
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 Benjohn Barnes (Guest)
on 2006-05-27 10:03
(Received via mailing list)
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 :)

*whistles*

(Just about got away with that, I think).
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 Benjohn Barnes (Guest)
on 2006-05-28 02:16
(Received via mailing list)
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.

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

*sigh*

Come on, already. Tick-tock, tick-tock.
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 Benjohn Barnes (Guest)
on 2006-05-28 12:08
(Received via mailing list)
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? :)

Cheers,
	Benjohn
A9b6a93b860020caf9d2d1d58c32478f?d=identicon&s=25 Ross Bamford (Guest)
on 2006-05-28 12:32
(Received via mailing list)
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 :) 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)...
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 Benjohn Barnes (Guest)
on 2006-05-28 12:35
(Received via mailing list)
On 28 May 2006, at 11:30, Ross Bamford wrote:

> to do
> it again :) 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)...

:) 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.
3bb23e7770680ea44a2d79e6d10daaed?d=identicon&s=25 M. Edward (Ed) Borasky (Guest)
on 2006-05-29 03:06
(Received via mailing list)
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:
>     1) Completely ubiquitous. ASCII's degree here will be hard to
> ASCII does this wonderfully. You can't get much easier than "puts
> know how to behave and render themselves. We've got 3d, and scrollable
>
>

--
M. Edward (Ed) Borasky

http://linuxcapacityplanning.com
47b1910084592eb77a032bc7d8d1a84e?d=identicon&s=25 Joel VanderWerf (Guest)
on 2006-05-30 05:24
(Received via mailing list)
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.
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 unknown (Guest)
on 2006-05-31 10:07
(Received via mailing list)
<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>

:)

Regards,
  Benjohn
Bf6862e2a409078e13a3979c00bba1d6?d=identicon&s=25 Gregory Seidman (Guest)
on 2006-05-31 14:42
(Received via mailing list)
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>
}
} :)

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
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 Benjohn Barnes (Guest)
on 2006-05-31 21:45
(Received via mailing list)
On 31 May 2006, at 13:42, Gregory Seidman wrote:

> } </very_unsubtle_attempt_to_get_people_on_the_quiz>
> 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...

:) 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
912c61d9da47754de7039f4271334a9f?d=identicon&s=25 MenTaLguY (Guest)
on 2006-05-31 21:52
(Received via mailing list)
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
333efbd87bc3c04c16ca9fc5201ed9ab?d=identicon&s=25 Colin Mitchell (Guest)
on 2006-05-31 22:02
(Received via mailing list)
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 :(
81d609425e306219d54d793a0ad98bce?d=identicon&s=25 Matthew Moss (Guest)
on 2006-05-31 23:23
(Received via mailing list)
Agreed with all of the above...
I may try it this coming weekend, even if the quiz has moved onto
greener pastures.
Bbc4b3fca1ae3161257a8636145b424d?d=identicon&s=25 Elliot Temple (Guest)
on 2006-05-31 23:54
(Received via mailing list)
Hi all,

I did the quiz :) 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
http://www.curi.us/blog/
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-06-01 04:52
(Received via mailing list)
On May 31, 2006, at 4:51 PM, Elliot Temple wrote:

> Hi all,
>
> I did the quiz :) I am new to Ruby so any tips are appreciated.

Let me be one of the first to welcome you then.  Your code looks
nice.  Definitely ahead of my early attempts.  ;)

Don't take it personal, but I had the summary completed before this
made it in.  It's just a function of my schedule, no favoritism.  I
really wish I could have talked about both solutions.  :(

James Edward Gray II
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 unknown (Guest)
on 2006-06-01 09:57
(Received via mailing list)
> Hi all,
>
> I did the quiz :) I am new to Ruby so any tips are appreciated.

Hooray! :) I've had a quick squiz through your code, and I think I
understand what's going on. I'll play with it a bit more tonight.

Cheers,
  Benjohn
This topic is locked and can not be replied to.