Cavern-type dungeon generation
Mike_aka_MD
caverns in my roguelike. I have created an algorithm for this; sample
results follow. The problem with my algorithm is that there is no way
to ensure that all dungeon areas are accessable. If anyone has any
ideas how i can connect the separate dungeon segments and still
maintain the cavern-like appearance of the dungeon id appreciate it.
also if you have any questions about my algorithm id be glad to answer
them.
###############################################################################
##############.........######....##...........#######..################.....###
#############...........######.................##..................###......###
#############............######....................................###.....####
#############............#######...................................###....#####
############..............######...................................##.....#####
###########.......................................................###.....#####
###########......................................................###.......####
###########.....................................................###.........###
###########..................#.................................####..........##
############................###...............................#####..........##
############................###..............................#######.........##
############...............###......#...........##..........#########........##
###########...............###......##.........#####........###########.......##
##########...............###.................#######....##############.......##
####..####...............###................##########################.......##
####...##.......####.....###...............##########################........##
####...........######....####.............###########################........##
#####.........########..######............###########################.......###
######.......##################..........#############################.....####
########....######################.......######################################
####################################....#######################################
###############################################################################
###############################################################################
#####..#######....###############################....##........#########....###
####...............########..######.......######...................####......##
####...............#######....####........#####....................####......##
###................######.....####........#####...................####.......##
###............##########......##.........#####..................#####........#
###...........###########................######.............#...######........#
####..........############...............#####.............###..#####.........#
#####.........############..............####...............##########.........#
#####.........############..............####...............###########........#
#####.........############..............####..............############.......##
#####.........############..............#####............############.......###
#####.........############..............#####............###########........###
#####..........############..............###..............##########........###
####...........#############.......................####...##########.......####
####...........#############......................######..#########......######
####..........##############............##.......#######..#########.....#######
####.........###############........#######.....###################....########
#####.....##################........#######...#####################...#########
############################........#######..#####################....#########
#############################.......#######..####################....##########
##################################################################..###########
###############################################################################
Dave Slutzkin
> I personally favor organic caverns to roomed dungeons, and plan to use
> caverns in my roguelike. I have created an algorithm for this; sample
> results follow. The problem with my algorithm is that there is no way
> to ensure that all dungeon areas are accessable.
<snip dungeons>
(They look good.)
It looks like they're always connected vertically, and it's just
horizontally that you've got the problem. So maybe do some sort of
horizontal flooding? Start at the leftmost square, then keep moving
right until you can move no more. Do the same from the right. If they
haven't reached each other then one can drill through a wall to make a
passage.
Or, for gameplay, you could just make sure that the two sets of stairs are
connected? Or you could avoid the whole issue by allowing the player to
tunnel a lot? ;-)
later,
Dave Slutzkin.
Ville Heikkilä
Mike_aka_MD wrote:
> I personally favor organic caverns to roomed dungeons, and plan to use
> caverns in my roguelike. I have created an algorithm for this; sample
> results follow. The problem with my algorithm is that there is no way
> to ensure that all dungeon areas are accessable. If anyone has any
> ideas how i can connect the separate dungeon segments and still
> maintain the cavern-like appearance of the dungeon id appreciate it.
> also if you have any questions about my algorithm id be glad to answer
> them.
I got very similar results playing around with an algorith wich used
game-of-life style rules repeatedly to semi-randomly created starting
position.
If your algorithm is anything like that, you could check for
accessibility at some very early stage of generation. If the algorithm
then finds enough large areas that are seperated from each other it can
find the shortest possible tunnel to connect these two areas and create
the tunnel. The rest steps of the algorithm probably take care of making
the tunneled area look like rest of the level.
--
VTT
Jesse Welton
MDS...@hotmail.com (Mike_aka_MD) wrote:
> I personally favor organic caverns to roomed dungeons, and plan to use
> caverns in my roguelike. I have created an algorithm for this; sample
> results follow. The problem with my algorithm is that there is no way
> to ensure that all dungeon areas are accessable. If anyone has any
> ideas how i can connect the separate dungeon segments and still
> maintain the cavern-like appearance of the dungeon id appreciate it.
Use a flood-fill to identify each separate region. Use A* to find
the shortest connecting paths between them, then cut tunnels of an
appropriate width along those paths. I'll give some possible results
for your example maps, using a digging pattern like this:
:
:!:
:
(That is, the shortest path is marked as '!', and I'm also digging out
the nearest neightbors, marking them as ':'.)
###############################################################################
##############.........######....##...........#######..################.....###
#############...........######.................##..................###......###
#############............######....................................###.....####
#############............#######...................................::#....#####
############..............######...................................!!.....#####
###########.......................................................#::.....#####
###########......................................................###.......####
###########.....................................................###.........###
###########..................#.................................####..........##
############................###...............................#####..........##
############................###..............................#######.........##
############...............###......#...........##..........#########........##
###########...............###......##.........#####........###########.......##
##########...............###.................#######....##############.......##
####..####...............###................##########################.......##
####...##.......####.....###...............##########################........##
####...........######....####.............###########################........##
#####.........########..######............###########################.......###
######.......##################..........#############################.....####
########....######################.......######################################
####################################....#######################################
###############################################################################
###############################################################################
#####..#######....###############################....##........#########....###
####...............########..######.......######...................:::#......##
####...............::::::#....####........#####....................!!!:......##
###................!!!!!!.....####........#####...................#:::.......##
###............####::::::......##.........#####..................#####........#
###...........###########................######.............#...######........#
####..........############...............#####.............###..#####.........#
#####.........############..............####...............##########.........#
#####.........############..............####...............###########........#
#####.........############..............####..............############.......##
#####.........############..............#####............############.......###
#####.........############..............#####............###########........###
#####..........############..............###..............##########........###
####...........#############.......................####...##########.......####
####...........#############......................######..#########......######
####..........##############............##.......#######..#########.....#######
####.........###############........#######.....###################....########
#####.....##################........#######...#####################...#########
############################........#######..#####################....#########
#############################.......#######..####################....##########
##################################################################..###########
###############################################################################
It might not produce very satisfying results (too straight) if the cavern
sections are ever much farther apart than this, though.
Does that help?
-Jesse
Jesse Welton
Slutzkin <da...@labyrinth.net.au> wrote:
>
> It looks like they're always connected vertically, and it's just
> horizontally that you've got the problem.
I suspect that this is entirely due to the fact that the map is almost
4 times as wide as it is tall, so that this property is likely, but not
guaranteed. I would avoid any solution that depended on it.
-Jesse
Mystran the Dark-Elf
"Mike_aka_MD" <MDS...@hotmail.com> wrote in message
news:9d3a89d7.02041...@posting.google.com...
> I personally favor organic caverns to roomed dungeons, and plan to use
> caverns in my roguelike. I have created an algorithm for this; sample
> results follow. The problem with my algorithm is that there is no way
> to ensure that all dungeon areas are accessable. If anyone has any
> ideas how i can connect the separate dungeon segments and still
> maintain the cavern-like appearance of the dungeon id appreciate it.
> also if you have any questions about my algorithm id be glad to answer
> them.
I did some caverns with a system as follows:
1. set i = 0 and fill the map with wall
2. clear random spot
3. move to a random direction from that spot (N, E, W, S)
4. clear that spot
5. substract 1 from i
6. jump to 3 if i < imax
imax value depends on how much you want to clear but try something
like 1/4 of the blocks on the map first..
improved version check whether a spot is already cleared, and if it is
doesn't decrement i. This gives you better control of the size of the
cave and a bit better games..
Yes, these caves are much more random than yours, but.. well.. I like
them more fun also... try.. for you might be surprised on the results.
You want a good LOS system that highlights the visible are with this though
as otherwise it is quite hard to figure out what's really happening around.
- Mystran
Mike_aka_MD
> I got very similar results playing around with an algorith wich used
> game-of-life style rules repeatedly to semi-randomly created starting
> position.
>
> If your algorithm is anything like that, you could check for
> accessibility at some very early stage of generation. If the algorithm
> then finds enough large areas that are seperated from each other it can
> find the shortest possible tunnel to connect these two areas and create
> the tunnel. The rest steps of the algorithm probably take care of making
> the tunneled area look like rest of the level.
sounds good, make sure the cavern is continuous first and then smooth
it over to make it look right. Now how would i go about checking for
continuousness and correcting a lack of it?
Thanks~ Mike
Ville Heikkilä
Mike_aka_MD wrote:
> Ville Heikkilä <keb...@hotmail.com> wrote in message news:<3CB9A40E...@hotmail.com>...
[clipped algorithm description]
> sounds good, make sure the cavern is continuous first and then smooth
> it over to make it look right. Now how would i go about checking for
> continuousness and correcting a lack of it?
There are good articles writen on that topic and newsgroup search with
google will probably give you some answers too.
--
VTT
Bru, Pierre
I used a Diffusion-Limited Aggregation [search DLA, fractal, or go
directly to http://www.oche.de/~ecotopia/dla/index.html] to generate
caves looking like the attached screenshot. I did not posted the
programm yet as it is desperately slow (I do all my testings on my old
i486-DX12: if the speed is fair on that machine, it will burst on
every other)
Pierre.
---
###.###.....#############...#..##..######....########..#........##............
#######..#..##############....###.###.####..#####.###.....###.################
#.#.####...#####..###########.#...##..###..######.##..#######...##############
#...######..##..#.#########...#..###.####.#######..#..#.###.#.################
##..######.####...###########.....##.####.########.#........##################
...#######..####..###############....####.#####.##...###.##.##################
##....#####...#.#.##################......#####.##.#..#####.##################
##.##....##.#.........###############.#########....##.#####....###############
########....###.#.###....#.##########..#######..##.###########################
#####.##.#.###..########.........#####.#####.#..##.###########################
##.......#.####.########.#####.#.#####..##.#.#....############################
##.##.#########.##############.#.####...........##############################
#..############.##########.###.#...........###....######.#..##################
....###########.#########...######.#.###.#..##.#...#####...###################
##.########################........#.#########.##..##......#..######.....#####
###########################..###..#..########...##.#..####.#..##..#..#########
######################.#####.###.##.#######.....##...#####...###.#...#########
###################....#########.##.#########.#.###....###.#.........###.####.
.##################.....#######..#...########.#.####.#.#######.#.###...#.#.#..
#######################..####....###..#######...####.#..#####..#..####.....#..
########################.......####...#####.....##...#########.##..#######....
#####################....#.#.#.####.#.#######.######.#########.##......###.###
################.......###.###.####.#.#######.######..########..#.##..##...###
#####################..###..#..######...##########...########..##..#######...#
MDS...@hotmail.com (Mike_aka_MD) wrote in message news:<9d3a89d7.02041...@posting.google.com>...
> I personally favor organic caverns to roomed dungeons, and plan to use
> caverns in my roguelike. I have created an algorithm for this; sample
> results follow. The problem with my algorithm is that there is no way
> to ensure that all dungeon areas are accessable. If anyone has any
> ideas how i can connect the separate dungeon segments and still
> maintain the cavern-like appearance of the dungeon id appreciate it.
> also if you have any questions about my algorithm id be glad to answer
> them.
[--sniped screenshot--]
oli g
"Bru, Pierre" schrieb:
IMHO your generated caves are not really caves (they are more like tunnels), but if you would combine your
algorithm with that one of Mike_aka_MD (from the original post) you would have big caves, connected by
not-so-straight tunnels.
Oli
Ville Heikkilä
"Mike_aka_MD" <MDs...@hotmail.com> kirjoitti viestissä
news:b27649f7.02041...@posting.google.com...
> sounds good, make sure the cavern is continuous first and then smooth
> it over to make it look right. Now how would i go about checking for
> continuousness and correcting a lack of it?
Hi, a gave my algorithm some more toughts and came up with this:
First you create the "seed" of the dungeon and save it. Then you create the
dungeon from the "seed" as usual ignoring contiousness. Then you check if
the dungeon is continuous and if it is not, you calculate the shortest
possible paths to make the dungeon continuous. After that you carve out the
shortest possible paths to the "seed" of the dungeon and then use this seed
to create the final dungeon. You probably need to use wider than 1 char
paths so the newly created tunnels survive to the final dungeon, you could
use the
#
#!#
#
pattern someone suggested before.
--
VTT
stank-monkey
> In article <9d3a89d7.02041...@posting.google.com>,
> MDS...@hotmail.com (Mike_aka_MD) wrote:
>
> > I personally favor organic caverns to roomed dungeons, and plan to use
> Use a flood-fill to identify each separate region. Use A* to find....<snip>
Better yet, use the floodfill to identify these regions, and make them
equivalent to dungeon levels 5-10 levels more difficult than actual.
The bravest could venture then in and be rewarded... maybe ;^)
Stanky
R Dan Henry
thr33d...@hotmail.com (stank-monkey) transmitted thus:
Of course, if your game includes monsters who can walk through walls
or (worse) dig through walls, the player may have little choice but to
face the out-of-depth foes.
R. Dan Henry, Grand Pashah of Small Miscellaneous Objects
rdan...@earthlink.net
"Lately, the only thing keeping me from being a serial
killer is my distaste for manual labor." -- Dilbert
arak...@gmail.com
> ideas how i can connect the separate dungeon segments and still
> maintain the cavern-like appearance of the dungeon id appreciate it.
Similar to what Mike_aka_MD has already said, consider filling a horizontal line across the map.
Except, my methodology is to do it when filling your map array with random blocks, before your first iteration or through the cellular-automata function, to achieve something like this:
########################################
##....#.#.#...#..##..##......###..#....#
#...##....###.#..#..#......#...#.#..#..#
#..#.#..#.........###...#...###....##..#
#....##.#.##....###.#.#...##.#.......#.#
#.#.##.##.#.#.....###..####.##..#.#.#..#
###...#....#..#.##.###.#...#.#######...#
##..##.#.......##..#........#..#.####..#
###....#.###....##.#...#...#.......#..##
#....####...##.##..#....##..##..#.#.#..#
#......................................#
#......................................#
###....#.##...##...#..#.#..###....#.#.##
#...#..#.#...#.##.#.#.#..###.#..#....#.#
#..#.#........#....#.##.##..####..#..###
#..#..#..###.####.##.#......#...#.#....#
#.#.#..##..#..#...##.....#..###...#..#.#
##.#..#.#.#..###.....#.#.........#.###.#
###...#.#......#..#...###.#....##.#....#
##....#..##..#.#..##.#..#.####....###.##
##...#.#.###.#.###.#.......#.##.#...##.#
###....#.#.#...##......##.#.....##.#...#
########################################
This will greatly improve the odds of the caverns being connected along the horizontal axis, from the first iteration, and thus will look the most natural after X iterations. I only use 2 iterations with my alogarithm, because of transformations done on the random seeded map.
//
// public void InitMap()
//
// This will clear the middle row of the random map
//
for(int Row = 0; Row < MapHeight; Row++) {
for(int Column = 0; Column < MapWidth; Column++) {
int MapMiddle = (MapHeight / 2);
if(Row == MapMiddle)
{
Map[Column,Row] = OpenSpace; // As opposed to wall
[...]
Joshua Skelton
http://joshuaskelton.com/post/48733271827
If the entrance/exit is placed within a rectangle and the line width is at least two, I've found it always generates connected maps.
Gerry Quinn
joshua....@gmail.com says...
> http://joshuaskelton.com/post/48733271827
>
> If the entrance/exit is placed within a rectangle and the line width is at least two, I've found it always generates connected maps.
Grey'.
It starts like yours with the rooms and connections in white. I place
black where I want to be sure there will be a wall. Everything else is
grey.
Then set the grey cells randomly to 50% wall or floor (whatever). I
apply a standard multistep CA method, but after every round of
calculation all black cells are set to wall and all white cells are set
to floor.
It's kind of like what you are doing but more forced, and with forced
walls as well as forced floors. Probably the results come out the same,
but I don't have to worry about paths getting blocked because white
floor always stays floor. Likewise, divisions I mean to enforce are
black and cannot be eroded by the cellular automaton algorithm.
- Gerry Quinn
