Author Topic: Filling Irregular Shaped Rooms  (Read 11623 times)

penguin_buddha

  • Newcomer
  • Posts: 19
  • Karma: +0/-0
    • View Profile
    • Email
Filling Irregular Shaped Rooms
« on: August 31, 2012, 06:46:49 PM »
Hey guys, I've been working on my first roguelike over the past couple of days and I've hit a snag in map generation. I'm using a hybrid of these two algorithms.

http://roguebasin.roguelikedevelopment.org/index.php/Basic_BSP_Dungeon_generation
http://roguebasin.roguelikedevelopment.org/index.php/Irregular_Shaped_Rooms

So I'm currently trying to fill the rooms creating using the Irregular Shape method. It describes a method to do so but it seems like there are times when that method would fail. For example...

# = wall
O = open space

#########
###O#####
##O#O####
#O###OOO#
#O#####O#
#O####O##
##O#O#O##
###OXO###
#########

Would fill the area marked "X", when it shouldn't. Any ideas on how what could work?

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Filling Irregular Shaped Rooms
« Reply #1 on: August 31, 2012, 07:19:45 PM »
Make sure the irregularly shaped room is in an area with nothing else in it, and with a border at least one tile thick. Like this:

#########
###O#####
##O#O####
#O###OOO#
#O#####O#
#O####O##
##O#O#O##
###O#O###
#########

But not like this:

##O####
#O#O###
O###OOO
O#####O
O####O#
#O#O#O#
##O#O##

Then, for that section of the map (or for a separate map that you'll paste onto the relevant section), Use floodfill starting from one of the corners (G):

G########
###O#####
##O#O####
#O###OOO#
#O#####O#
#O####O##
##O#O#O##
###O#O###
#########

The result is:

GGGGGGGGG
GGGOGGGGG
GGO#OGGGG
GO###OOOG
GO#####OG
GO####OGG
GGO#O#OGG
GGGOGOGGG
GGGGGGGGG

And then the set of tiles not covered by the floodfill is the irregularly shaped room. You could do the floodfill starting inside the room, but then you'd need some way of finding a starting point inside the room. This way is simpler, since you always know that (0,0) is outside and the border ensures that it's connected to every other outside tile.

This won't work if your irregular rooms have pillars.

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Filling Irregular Shaped Rooms
« Reply #2 on: September 01, 2012, 08:58:50 AM »
Just a note because I had to do flood filling on a mass scale one time....

If by chance you end up making huge dungeons or having lots of rooms, there is a flood fill algorithm called "scanline" filling that is significantly faster than the general "fill outward" routine that you might write.  Just a little tidbit (and it is not particularly complicated so it's a nice exercise ;) )

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Filling Irregular Shaped Rooms
« Reply #3 on: September 01, 2012, 10:17:18 AM »
If you carve a room in solid wall area starting from zero point you don't have to fill it and you always create a room where everything is connected (when the routine is supporting that feature). If you want to add special walls later in the room it's easy.
« Last Edit: September 01, 2012, 10:19:31 AM by Krice »

penguin_buddha

  • Newcomer
  • Posts: 19
  • Karma: +0/-0
    • View Profile
    • Email
Re: Filling Irregular Shaped Rooms
« Reply #4 on: September 01, 2012, 07:47:10 PM »
Thanks for the help guys. I finished up the process and here are some sample maps:

#OOOOO##OOO##############
OOOOOOO#OOOO##OOO##OOOO##
OOOOOOO#OOOO##OOOOOOOOOOO
#OOOOOOOOOOO##OOOOOOOOOOO
##OOOOO#OOOO#####O#######
##OOOOO#OOOO#####O#######
###OOO##OOOO##OOOO###OO##
####O#O#O#O##OOOOOO#OOOO#
#OOO###OOOO#OOOOOOO#OOOO#
#OOOOOOOOOOO#OOOOOOOOOOO#
#OOOOO#OOO###OOOOOOO#O###
#######O####O##O#OO##OO##
#OOO##O##OOO###OOOO#OOOOO
#OOOO#OOOOOO#OOOOOOOOOOOO
#OOOOOOOOOOO#OOOOOOOOOOO#
#OOOOO#OOOOO#OOOOOOOOOOO#
#OOOOOO#OOOO##OOOOOOOOO##
####OO########OOOO#######
###OO#########OO####OOO##
##OO####OO####OO###OOOOO#
OOOOOOOOOO####OOO##OOOOO#
OOOOO##OOOO###OOO##OOOOO#
OOOOO##OOOO###OOO##OOOOO#
OOOOO##OOO####OOOOOOOO###
##############OOO########

######################OO#
##########O###########OO#
###OO#####OO######O##OOO#
###OO#####OO###OOOO##OOOO
##OOOO####OO###OOOOO#OOOO
##OOOO###OOOO##OOOOO#OOOO
##OOOO###OOOO##OOOOO#OOOO
##OOOO###OOOO##OOOOO#OOOO
##OOOO###OOOO##OOOO###O##
##OOO####OOOO###OOO###O##
##O#OO###OOOO###OO####O##
##O#OO###OOOO###O#####O##
##O#O#O##OOOO###OO###OO##
#O###O#O#OOOO##OOOOOOOO##
#O###O#O#OOO###OOOOOOOO##
#O###O##OOOO###OOOOOOOOO#
#OOOOOO##OO####OOOOOOOOO#
#OOOOOOO#OO####OOOOOOOOO#
#OOOOOOOO#OO###OOOOOOOOO#
#OOOOOOOOOOOO##OOOOOOOOO#
#OOOOOOOOOOOO##OOOOOO####
#OOOOOOOOOOOOO#OOOOOO####
#OOOOOOOOOOOOO###OOOO####
OOOOOOOOOOOOOO###OO#O####
#OOOOOO#OOOOOO##OOOO#####
####OO#OOOOOOOO#OOOO###O#
#######OOOOOOOO#OOOO#O#O#
#######OOOOOOOO#OOOO#O#O#
#######OOOOOO##OOOOO#O#O#
#######OOOOOO##OOOOO#O#O#
#OO####O#OOOOOOOOOOO#OOOO
#OOOO###OOOOOOOOOOOO#OOOO
#OOOO###OOOOOO#OOOOO#OOOO
#OOOOO#OOOOOOOOOOOOOOOOOO
#OOOOO#OOOOOOO#OOOOOOOOOO
#OOOOOOOOOOOOO#OOOOOOOOOO
#OOOOO##OOOOO##OOOO#OOOOO
#OOOOO##OOOOO####OO#OOOOO
#OOOOO###OOOO####O##OOOOO
##OOO####OO######O##OOOOO
##OOO####OO###OOOO##OOOOO
##OOO####OOO##OOOOOOOOOOO
#########OOO##OOOOO#OOOOO
###OOOO##OOOO#OOOOO#O##OO
##OOOOO##OOOO#OOOOO####OO
#OOOOOO##OOOO#OOOOO####OO
OOOOOOOO#OOOO#OOOOO####OO
OOOOOOOOOOOOO##OOO#####OO
#########OOO###########OO
#########O#O###########O#

####OOOOOO####################OOOO################
####OOOOOOO#######OOOOO######OOOOOO##########O####
####OOOOOOOO###OOOOOOOOOO###OOOOOOO##########OO###
###OOOOOOOOO###OOOOOOOOOOO#OOOOOOOOO#########OO###
####OOOOOOOOO###OOOOOOOOOO##OOOOOOOO#########OOO##
#####OOOOOOOOO##OOOOOOOOOO##OOOOOOOOOOO######OOO##
#####OOOOOOOOOO##OOOOOOOOOO#OOOOOOOO#OOO#####OOOO#
#####OOOOOOOOOO##OOOOOOOOOO#OOOOOOOO#OOOO####OOOO#
######OOOOOOOOOO##OOOOOOOOO#OOOOOOO##OOOO####OOOO#
######OOOOOOOOOOOOOOOOOOOO##OOOOOO###OOOOO###OOOO#
#######OOOOO#####OOOOOOOO#########O##OOOOOO##OOOO#
#################OOOOOO##########OO#OOOOOOO##OOOO#
###O###########OOOOOOOO########OOOO#OOOOOOO##OOOO#
##OOO########OO##OOOOOOO#####OOOOOO#OOOOOOO##OOOO#
#OOOOOOO###OO####OOOOOOOO###OOOOOOOOOOOOOOO##OOO##
#OOOOOOOOOOOO####OOOOOOOOO##OOOOOOOOOOOOOOO##OOO##
OOOOOOOOOO###OOOOOOOOOOOOO##OOOOOOOOOOOOOOO##OOO##
OOOOOOOOOO######OOOOOOOOOOO#OOOOOOOO#OOOOOO#OOOO##
OOOOOOOOOO######OOOOOOOOOOO#OOOOOOOO#OOOOOOO#OOO##
#OOOOOOOOO######O#OOOOOOOO###OOOOOOO##OO######OO##
##OOOOOOOO#####O##OOOOOO#####OOOOOOO##########O###
####OOOOO######O###O#########OOOOOOOOOO#######O###
######O#O######O#############OOOOOOO###OOOOO##O###
##############O##############OOOOOO########O######
##########O###O####O########O#############OO######
###OOO###OO##O####OOO######O##############OO######
###OOOOOOOOO#O####OOOOO###O###############OO######
###OOOOOOOOO#O###OOOOOOOOO############O##OOO######
###OOOOOOOOOO####OOOOOOOOOOO########OOO#OOOO######
###OOOOOOOOOO###OOOOOOOOOOOOOOO#####OOOO#OOOO#####
###OOOOOOOOOO###OOOOOOOOOOOOOOOO##OOOOO##OOOO###O#
###OOOOOOOOOOO###OOOOOOO####OOOOOOOOOOO##OOOO#OOO#
###OOOOOOOOOOO#####OOO##O###OOOOO##OOOO##OOOO#OOO#
##OOOOOOOOOOOO####OOOOOOO###OOOOO##OOOOO#OOOO#OOOO
##OOOOOOOOOOOOO###OOOOOOOO##OOOOO##OOOOO#OOOO#OOOO
#OOOOOOOOOOOOOO##OOOOOOOOO##OOOOO##OOOOO#OOOO#OOOO
#OOOOOOOOOOOOOOOOOOOOOOOOOO#OOOOO##OOOOO#OOOO#OOOO
###OOOOOOOOOOOOOO#OOOOOOOOO#OOOOO##OOOOO#OOOO#OOOO
#####OOOOOOOO##OO#OOOOOOOOO#OOOOO###OOOO#OOOO#OOOO
#####OOOO#####OO##OOOOOOOOOOOOOOO###OOOO#OOOO#OOOO
#####OOOOO###OO####OOOOOOOOOOOOOO####OOO#OOOO#OOOO
###OOOOOOOOO#O#####OOOOOOOO#OOOOO####OO##OOOO#OOOO
###OOOOOOOOOO######OOOOOOOO#OOOOO########OOOO#OOOO
####OOOOOOOOO######OOOOOOOO#OOOOO#########OO##OOO#
####OOOOOOOOO######OOOOOOO##OOOOO#########OO##OOO#
####OOOOOOOOO######OOOOOOO##OOOO##########OO##OOO#
####OOOOOOOOOO#####OOOOOOO##OOOO##########OO##OOO#
####OOOOOOOOOO#####OOOOOOO##OOOO##########OO##OO##
####OOOOOOOOOO######OOOOO#################OO#OOO##
####OOOOOOOO########OOOOO#################OOO#####
« Last Edit: September 01, 2012, 07:50:17 PM by penguin_buddha »

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Filling Irregular Shaped Rooms
« Reply #5 on: September 01, 2012, 08:35:48 PM »
I like them - they're quite a nice departure from the typical "rooms and corridors" look that's so ubiquitous.
A few issues - first, they might be a bit more legible if you used '#' and ' ' or '#' and '.'; if you're concerned about character width, you can use [ code ] [ /code ] tags in the message, like this:
Code: [Select]
#####
#...#
Code: [Select]
#####
#   #

Second, diagonal corridors don't always make for good gameplay - if the map is unknown, then while the player can see all the floor tiles from one end of the corridor, the corridor walls could be out of line of sight. I'd recommend either choosing a very permissive field of vision, widening the diagonal corridors, or sticking to orthogonal corridors. Of course if the whole thing is visible from the start there's no problem.

Third, just my personal preference - it looks like the graph of connectivity between the rooms is almost a tree, that is there aren't many looping paths through the dungeon. This means there are lots of dead ends for the player to get trapped in, it takes a lot of backtracking to fully explore, and in general the shortest route between two points in the dungeon could be quite long. Again, there are some cases where this isn't a problem, for instance if the player doesn't need to fully explore the level, has more than one option for where to leave the level, or if teleporting is cheap, etc. etc.

penguin_buddha

  • Newcomer
  • Posts: 19
  • Karma: +0/-0
    • View Profile
    • Email
Re: Filling Irregular Shaped Rooms
« Reply #6 on: September 01, 2012, 09:21:03 PM »
Hmm can't seem to straighten them out, even using the code tags. Ill try to widen the corridors. The goal of the game is simply to escape, so exploring whole levels isn't really important.

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Filling Irregular Shaped Rooms
« Reply #7 on: September 01, 2012, 11:18:50 PM »
Sounds like all you need is wide corridors, then :)
To actually use the code tags you need to remove the spaces that I put in. That was to stop them actually being interpreted as code tags by the forum software...

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Filling Irregular Shaped Rooms
« Reply #8 on: September 02, 2012, 08:52:13 AM »
Sounds like all you need is wide corridors, then :)
To actually use the code tags you need to remove the spaces that I put in. That was to stop them actually being interpreted as code tags by the forum software...

Just fyi, code tags don't work at all for me.  Even the ones you used are messed up!

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Filling Irregular Shaped Rooms
« Reply #9 on: September 02, 2012, 01:18:42 PM »
Sounds like all you need is wide corridors, then :)
To actually use the code tags you need to remove the spaces that I put in. That was to stop them actually being interpreted as code tags by the forum software...

Just fyi, code tags don't work at all for me.  Even the ones you used are messed up!

I'm having no problem. this code in the message

produces this display

and everything is fine.

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Filling Irregular Shaped Rooms
« Reply #10 on: September 02, 2012, 01:36:26 PM »
interesting, it looks correct in that post, but not in your previous one...

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Filling Irregular Shaped Rooms
« Reply #11 on: September 02, 2012, 04:38:20 PM »
It's  an image.

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Filling Irregular Shaped Rooms
« Reply #12 on: September 02, 2012, 05:26:05 PM »

guest509

  • Guest
Re: Filling Irregular Shaped Rooms
« Reply #13 on: September 05, 2012, 01:18:04 AM »
  Never thought of floodfill from the outside. Good to note.