###############################################################################
##############.........######....##...........#######..################.....###
#############...........######.................##..................###......###
#############............######....................................###.....####
#############............#######...................................###....#####
############..............######...................................##.....#####
###########.......................................................###.....#####
###########......................................................###.......####
###########.....................................................###.........###
###########..................#.................................####..........##
############................###...............................#####..........##
############................###..............................#######.........##
############...............###......#...........##..........#########........##
###########...............###......##.........#####........###########.......##
##########...............###.................#######....##############.......##
####..####...............###................##########################.......##
####...##.......####.....###...............##########################........##
####...........######....####.............###########################........##
#####.........########..######............###########################.......###
######.......##################..........#############################.....####
########....######################.......######################################
####################################....#######################################
###############################################################################
###############################################################################
#####..#######....###############################....##........#########....###
####...............########..######.......######...................####......##
####...............#######....####........#####....................####......##
###................######.....####........#####...................####.......##
###............##########......##.........#####..................#####........#
###...........###########................######.............#...######........#
####..........############...............#####.............###..#####.........#
#####.........############..............####...............##########.........#
#####.........############..............####...............###########........#
#####.........############..............####..............############.......##
#####.........############..............#####............############.......###
#####.........############..............#####............###########........###
#####..........############..............###..............##########........###
####...........#############.......................####...##########.......####
####...........#############......................######..#########......######
####..........##############............##.......#######..#########.....#######
####.........###############........#######.....###################....########
#####.....##################........#######...#####################...#########
############################........#######..#####################....#########
#############################.......#######..####################....##########
##################################################################..###########
###############################################################################
> 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.
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
> 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
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
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
> 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
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
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--]
"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
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
> 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
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