Temple of The Roguelike Forums
Development => Programming => Topic started by: penguin_buddha 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/Basic_BSP_Dungeon_generation)
http://roguebasin.roguelikedevelopment.org/index.php/Irregular_Shaped_Rooms (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?
-
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.
-
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 ;) )
-
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.
-
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#####
-
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:
#####
#...######
# #
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.
-
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.
-
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...
-
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!
-
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
(http://i.imgur.com/Axuy5.png)
produces this display
(http://i.imgur.com/6BKzo.png)
and everything is fine.
-
interesting, it looks correct in that post, but not in your previous one...
-
It's an image.
-
It's an image.
oh haha ;)
-
Never thought of floodfill from the outside. Good to note.