L Jumps for Cave Generation

I Own The Letter O

unread,

May 13, 2008, 8:40:40 AM5/13/08

to

Hi,

I've finally got my new compiler and have started on Atman again (a
short coffee-break roguelike designed to test my i/o library, saving/
loading functions and dungeon generation). My last attempt at Atman
was aborted after my previous compiler fell over and went boom.

I'm writing various dungeon generation functions/methods at the
moment. I've got some good results with cellular automata (I hope
that's right) for cave designs and before I move onto aboveground
natural environments and man-made dungeons I want to make sure I've
got the best possible method for generating cave. I read somewhere
about L-Jump methods for generating caves, but I haven't been able to
find anything here or at Roguebasin.

I presume an L-Jump is drawing an 'L'
*
*
**

Then placing another 'L' along side it, randomising the direction of
the 'L'.
*
*
***
***
etc...

Is this correct, can you point me to any good examples of an L-Jump
cave/dungeon, or to source-code/pseudo-code so I can get a peek at how
somebody else has done it. Do you begin to weight the probabilty
towards closing the 'L's in a dungeon and towards opening the 'L's in
a cave?

I just want to make sure that I'm not missing a good trick by sticking
to the CA caves that I'm getting.

(CA also looks like it'll do a good jungle, by seeding with different
types of trees with a different rarity and growth rate and letting
them live for a set of iterations or include a river/lake and iterate
around it etc etc.)

Any help would be gratefully accepted.

Gerry Quinn

unread,

May 13, 2008, 9:17:34 AM5/13/08

to

In article <686d78f5-59f6-45fc-8f18-cb19080323b2
@m73g2000hsh.googlegroups.com>, lord...@yahoo.co.uk says...

> I'm writing various dungeon generation functions/methods at the
> moment. I've got some good results with cellular automata (I hope
> that's right) for cave designs and before I move onto aboveground
> natural environments and man-made dungeons I want to make sure I've
> got the best possible method for generating cave. I read somewhere
> about L-Jump methods for generating caves, but I haven't been able to
> find anything here or at Roguebasin.

There's no best method! I used a combination of a cellular automaton
with a large-scale template for generating caves in my game Lair, and it
works well. But there are other options.

The straightforward cellular automaton algorithm is fine for smallish
maps but can give samey results when applied to large open areas.

I've never heard of L-jumps.

- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>

Brog

unread,

May 13, 2008, 10:06:15 AM5/13/08

to

On May 13, 1:40 pm, I Own The Letter O <lord_h...@yahoo.co.uk> wrote:
>
> I'm writing various dungeon generation functions/methods at the
> moment. I've got some good results with cellular automata (I hope
> that's right) for cave designs and before I move onto aboveground
> natural environments and man-made dungeons I want to make sure I've
> got the best possible method for generating cave. I read somewhere
> about L-Jump methods for generating caves, but I haven't been able to
> find anything here or at Roguebasin.

I've never heard of L-jumps, but you may be thinking of L-systems
(http://en.wikipedia.org/wiki/L-system). These get mentioned quite a
bit in relation to procedural content generation, and you could
certainly use them to generate levels.

I Own The Letter O

unread,

May 13, 2008, 10:20:36 AM5/13/08

to

I got the phrase 'L-Jumps' from an article on dungeon generation over
at Temple of the Roguelike (http://www.roguetemple.com/forums/
index.php?topic=77.0). I wasn't sure what they meant and guessed with
my rotating 'L' thing above.

I looked at the L-Systems link and... wow... that looks far too
complex for my first Roguelike but thanks for showing me that, I love
fractals and all that. Maybe I'll return to that page when programming
a more complex Roguelike (and after getting a little bit cleverer).

If nobody here has heard of 'L-Jumps' I'll have to have a fiddle
around and present my results when complete.

Jeff Lait

unread,

May 13, 2008, 1:40:55 PM5/13/08

to

On May 13, 8:40 am, I Own The Letter O <lord_h...@yahoo.co.uk> wrote:
> Hi,
>
> I've finally got my new compiler and have started on Atman again (a
> short coffee-break roguelike designed to test my i/o library, saving/
> loading functions and dungeon generation). My last attempt at Atman
> was aborted after my previous compiler fell over and went boom.
>
> I'm writing various dungeon generation functions/methods at the
> moment. I've got some good results with cellular automata (I hope
> that's right) for cave designs and before I move onto aboveground
> natural environments and man-made dungeons I want to make sure I've
> got the best possible method for generating cave. I read somewhere
> about L-Jump methods for generating caves, but I haven't been able to
> find anything here or at Roguebasin.

Hmm... I remember an L based dungeon generator. I don't recall it
working as you describe, however. It seemed instead to just stamp Ls
repeatedly over the map to fill in rooms and detail. No idea how to
search for references, however, as searching for L is obviously not
very fruitful...

I think your CA method is sufficient. The other major cave generator
is the drunkard walk approach, but that can also benefit from some
post-smoothing (which the CA method can be though of an example of)
On that vein, you might consider feeding your CA the results of a
drunken walk to better control over the resulting topography.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

Jeff Lait

unread,

May 13, 2008, 1:46:57 PM5/13/08

to

On May 13, 1:40 pm, Jeff Lait <torespondisfut...@hotmail.com> wrote:
> On May 13, 8:40 am, I Own The Letter O <lord_h...@yahoo.co.uk> wrote:
>
> > Hi,
>
> > I've finally got my new compiler and have started on Atman again (a
> > short coffee-break roguelike designed to test my i/o library, saving/
> > loading functions and dungeon generation). My last attempt at Atman
> > was aborted after my previous compiler fell over and went boom.
>
> > I'm writing various dungeon generation functions/methods at the
> > moment. I've got some good results with cellular automata (I hope
> > that's right) for cave designs and before I move onto aboveground
> > natural environments and man-made dungeons I want to make sure I've
> > got the best possible method for generating cave. I read somewhere
> > about L-Jump methods for generating caves, but I haven't been able to
> > find anything here or at Roguebasin.
>
> Hmm... I remember an L based dungeon generator. I don't recall it
> working as you describe, however. It seemed instead to just stamp Ls
> repeatedly over the map to fill in rooms and detail. No idea how to
> search for references, however, as searching for L is obviously not
> very fruitful...

I underestimate my search skills. The L-Cave method was proposed by
R. Alan Monroe in:
http://groups.google.com/group/rec.games.roguelike.development/msg/781936d8ee463246
titled "Fun with dungeon generation in qbasic"

It was then used in Netwhack: http://roguebasin.roguelikedevelopment.org/index.php?title=Netwhack

Comments from the Netwhack author suggests that the CA method is
considered to produce superior results:
http://groups.google.com/group/rec.games.roguelike.development/msg/c7cdc5215cb9c96d

Message has been deleted

I Own The Letter O

unread,

May 14, 2008, 3:54:22 AM5/14/08

to

On 13 May, 18:46, Jeff Lait <torespondisfut...@hotmail.com> wrote:
> On May 13, 1:40 pm, Jeff Lait <torespondisfut...@hotmail.com> wrote:
>
>
>
>
>
> > On May 13, 8:40 am, I Own The Letter O <lord_h...@yahoo.co.uk> wrote:
>
> > > Hi,
>
> > > I've finally got my new compiler and have started on Atman again (a
> > > short coffee-break roguelike designed to test my i/o library, saving/
> > > loading functions and dungeon generation). My last attempt at Atman
> > > was aborted after my previous compiler fell over and went boom.
>
> > > I'm writing various dungeon generation functions/methods at the
> > > moment. I've got some good results with cellular automata (I hope
> > > that's right) for cave designs and before I move onto aboveground
> > > natural environments and man-made dungeons I want to make sure I've
> > > got the best possible method for generating cave. I read somewhere
> > > about L-Jump methods for generating caves, but I haven't been able to
> > > find anything here or at Roguebasin.
>
> > Hmm... I remember an L based dungeon generator. I don't recall it
> > working as you describe, however. It seemed instead to just stamp Ls
> > repeatedly over the map to fill in rooms and detail. No idea how to
> > search for references, however, as searching for L is obviously not
> > very fruitful...
>
> I underestimate my search skills. The L-Cave method was proposed by

> R. Alan Monroe in:http://groups.google.com/group/rec.games.roguelike.development/msg/78...

> titled "Fun with dungeon generation in qbasic"
>
> It was then used in Netwhack:http://roguebasin.roguelikedevelopment.org/index.php?title=Netwhack
>
> Comments from the Netwhack author suggests that the CA method is

> considered to produce superior results:http://groups.google.com/group/rec.games.roguelike.development/msg/c7...
> --
> Jeff Lait
> (POWDER:http://www.zincland.com/powder)- Hide quoted text -
>
> - Show quoted text -

Wow, don't underestimate those searching skills. I looked in both
Roguebasin and rgrd believing the method to be called L-Jump's and
didn't find a thing. Having looked at the examples I agree the CA is a
better method for producing large and smooth caves. I'm having to much
fun with CA to investigate anything else at the moment (planning to
set up a smaller CA within my main Cave CA for making cave lakes based
on Shallow Water becoming Deep Water and Deep Water feeding into empty
floor spaces to make Shallow Water, then reiterating and seeing how
the Cave CA works when it iterates again around the water, it's going
to be fun).

I did like the scraggly dead-ends that L-Cave produces though, I like
a cave to have little nooks and crannies, something that maybe a
smaller race can exploit but a medium/larger one cannot (be it imps
hiding in cracks zapping you, or your halfling squeezing in a crack to
avoid a Cave Troll then struggling to load his bow to shot fire arrows
at it).

It might be good if I experimented with making a CA Cave, adding a few
scraggly L-Cave bits around the edges and then iterating a few cycles
of lake.

I may return to my wrong idea of L-Jumps at a later date when I'm
bored of CA. I expect my crazy version will create a 'mine' style cave
that looks like it's been worked a bit by man/dwarf/generic stone
cutting race.

Jakub Debski

unread,

May 14, 2008, 8:54:40 AM5/14/08

to

Jeff Lait was thinking very hard :

> I think your CA method is sufficient. The other major cave generator
> is the drunkard walk approach, but that can also benefit from some
> post-smoothing (which the CA method can be though of an example of)
> On that vein, you might consider feeding your CA the results of a
> drunken walk to better control over the resulting topography.

The problem with CA is that it doesn't guarantee global traversality
and you have to connect disconnected areas other way.

In 10 minutes I made a new cave generation algorithm where all the
cells are accessible.

0. Place first digger in the central cell
1. Choose random digger from the list of diggers.
2. Remove this digger from the list.
3. If cell, where digger was, has less than 5 or 6 walls around, then
goto 1.
4. Place two new diggers in walls around cell, where digger was.
5. Goto 1.

That's all. Simple and effective.
Source code:

#include <stdio.h>
#include <time.h>
#include <vector>

using namespace std;

#define CAVE_SIZE_X 70
#define CAVE_SIZE_Y 45

char map[CAVE_SIZE_X][CAVE_SIZE_Y];

struct digger {
int x;
int y;
digger(int a_x,int a_y):x(a_x),y(a_y)
{
map[a_x][a_y]=1;
};
};

vector < digger > diggers;

int main(void)
{
srand(time(0));

memset(map,0,CAVE_SIZE_X*CAVE_SIZE_Y); // fill with walls

// Place first digger
diggers.push_back(digger(CAVE_SIZE_X/2,CAVE_SIZE_Y/2));

while (!diggers.empty())
{
int random = rand()%diggers.size();
digger pos=diggers[ random ];
diggers.erase(diggers.begin()+random);

if (pos.x==0||pos.x==CAVE_SIZE_X-1||pos.y==0||pos.y==CAVE_SIZE_Y-1)
continue;

int walls_around=0;
for (int a=-1;a<=1;++a)
{
for (int b=-1;b<=1;++b)
{
if (a==0 && b==0)
continue;
if (map[pos.x+a][pos.y+b]==0)
walls_around++;
}
}
if (walls_around<5+rand()%2)
continue;

int count=0;
while(count<2)
{
int dx=pos.x+rand()%3-1;
int dy=pos.y+rand()%3-1;
if (map[dx][dy]==0)
{
diggers.push_back(digger(dx,dy));
count++;
}
}
}
// print map
for (int y=0;y<CAVE_SIZE_Y;++y)
{
for (int x=0;x<CAVE_SIZE_X;++x)
{
if (map[x][y])
printf(".");
else
printf("#");
}
printf("\n");
}
return 0;
}

A few caves generated by this algorithm:

###########################.##.#.#####################################
###########################...#.######################################
##########################.#...#######################################
#########################..##..#######################################
#########################...#..#######################################
#########################.....########################################
#####################..##.....########################################
#####################.....#.#..########.##############################
#####################..#.#.#...#######...#############################
#####################.###.#.....#######....###########################
###################.....##.####.########...###########################
##################...#..#..####..########..####..#####################
###################.###..#..#..#..########.##....#####################
####################.......#..#...#######........#####################
###################....#....#.....######..#..###..####################
##################...##.#..##..#..#######..#...#......###....#########
############.###....##....##.....########.#....##.#...........########
###########...#.......#.....#...########...#....#..#......###..#######
####....#...#....##..##.........####...#.#..##...#....######.#.#######
####........#..####.##........#####.........##....#...####.....##.####
#####....#.#..####.....#.....#####.....#....#...#..#..###...#.##...###
#####...###....###.....##....######.###..#...#.##......#.#.....#..####
#####....##...#####.#.##..#..#####..########......#..#.....#.#....####
#####........#.####.....#.##..##.....#######...#.#...##....##.#.#.####
#####.....###.#.###..#....#..##...#.########...#....###....#.#.....#..
####......####...#..####.##..#..##...##########....#.....##.#.#.##....
#####.#.#######.....####..#....####..#.########..#...#......##..###...
######..########..######...#...##.......######.....#######.........###
#####.....#...##########..###..#.#....#..######.....########.#.....###
######...#....##############..#.........##########...########..#.#####
######..#....################....#.#.....#########...#######...#######
#######...###############.....#....##.#..##########...#######...######
########..##############........#.#.##.#############....######...#####
#######################...#####.........#############......##.....####
######################...####......#...###############...#....#.#.....
#######################.....#.........#################.###..#..#..#..
####################.##....#...####.#...######################.#######
###################.....#####..#.#.......####################...######
#################.......#######....#..#..####################...######
#################......#########..####################################
##################..############..####################################
#################################..###################################
##################################..##################################
##################################..##################################
###################################.##################################

################################################.##.##.##.############
################################################............##########
###############################################..#....#...#..#########
##############################################....#...##.###..########
#..#####################.######################.#..##..........#######
#...###############..##....###..############...##..#...#....#..#######
#....#############....#.#..##...######..###.......#.#..##.#....#...###
#...#.###########.............#...####.......#.#.....#.####........###
#......##########..##..#...#..##..####...#.......#.#..########..#.#...
.##..#..#########.######..##.#..######..#..#..#...#..#.#.#####..#....#
##..#..#..#.####..####...#...#...###......##..##..##......##........#.
##...........##..#......#.......####.....####..##.###.....##..#.####..
###....#.#..##.#.....#.......#...####...#..###...#######....#.#..##.##
###.##...........######..#######...#..##...###..#.#######..###..##..##
.#.#.....#.....#..#####..######......#.########...##########.#.#...###
#...#.###.#.#.#....#.####.######.###....#######...#########...#..##.##
#........#.#..##.#....###..####...###...######..#....#######...#......
#..#...#........###....##..........###########...##..############..#.#
..#.##....#...#.........##.....#.#..#.#######...##...#################
##.#.....#....##...##..#...#.#.....#...######...#....#################
###.....#...#.......#..#...#..#.#...#.#..###.#.#.#..##################
####....#....#.....#.#######...#...#.....##...###..###################
###..#..#######.#..#.######.#.#......#.............###################
###..#.#######..#.#...#####..##.....##..##.#..#...####################
##...#..#######.#.....####..##.########..#..#..#######################
........####..........##.......#####...#....#..#######################
#.....#####.......#...........######....#..#...#######################
##..#...###.#####...##...##..###.###..######...#######################
####.#......#####.....#####.............####...#######################
###..##....#######.....###....#..#.......####..#######################
###..##############..#.###.#.....##.#.....#.#..#######################
.##...#############.....###.#.######...##.....#########..#############
......##############....#.....######.#.##..#..####...#....############
###...#################..#....######.........#####........############
######################..#..##..######.#.#.###.#####..##...############
######################.#...##..###########....########...#############
#####################...#...#...####.#####.....#######..##############
####################..#..#..##..###...###.......####....##############
####################............####.####..#..........#.##############
#####################.###.........##..###.###.##.#..###.##############
###########################..#....#...###.##....##.###..##############
##############################.#.#...###..........####..##############
###############################.#..######..#.##...####################
###############################...#######...##########################
##############################..#.##########.#########################

#################################..###.#.#######################..##.#
##################################..#..#..######################.....#
##################################...#...#...#..#################....#
###################################..#.##.........###############..##.
#####################...###########..#..#...#.......#############..###
#####################....########..##....##.....#....###..########...#
####################....########....#...#....#.##.#.##....#######.#...
#############..#..#.....##..###.....#..#.#...#####........######.....#
#############..........##....#..#....#...#...######..##...####....#...
############.####..#.............##.......#.........#..#..###....#..##
############..###..#..##...##...#####..#...#.........#...##...#....#..
#############..##...........##.#####...##...#.#.#...##..##.....#.....#
#############...###.......##...#####..####...#...#..##..##....#..####.
##############...###....##.....###.....####.##.##.##...#..##..#...####
##############...#.......#..##........####.......#...#....#.....#.####
#############.##...#.###....###.......####.#.......#.#...##...##..####
#########.##.........###.#.##.##..########...#..##.......#....##...###
########.......#..#.#....###...#..#########.##..#...###....#.......###
#########....##..####.....###.....########...#....##.....##........###
#########...#...#####.#...#..#....#########.#.##.##....#...##.#.#..###
#########.......######.#......#...##....##.#....#.#...###.#..#...#####
..#######....#...#.##.........##..#.........#..#...#######.......#####
...#######.#.##.....#..#....#..####...####..##...#..######...#..######
....###.#...###....##...##...#..###..#####.###...##.#.#.##..##########
##..##.....##.....##..#...#.......#...#.##.###..#........#..#####..###
##..##.....##.....##...#....#.......#....#..###...##.#...#.........###
###.###....#...######.#.#.#..####..##.#.....####.#..#.....#......#####
###..##...#...########......####..##..#..###.#####..#.....#.....######
####..#......##########..#..###...##..###.....###............#########
###......#...#########.........#..###.........##.......###############
####....##..###########..#.#......####.....#..###.####################
###########.############.....#####.##..#.....#########################
##########..############....######..#....#..##########################
##########..#############..######..#.....#############################
##########...#############.....##..#...###############################
###########..##############........#..################################
#############################.......##################################
#############################......###################################
##############################.##..###################################
################################...###################################
###############################.....##################################
################################.#...#################################
#################################.#..#################################
##################################..##################################
##################################..##################################

###########################################################.##.#######
############################################################.##.######
###########################################################.....######
##########################################################......######
###########################################################..##..#####
#############################################################.....####
#############################################################..#..####
##########################################################..##...####.
##################################################..######..###...#..#
##################################################...#.##...####.....#
####################################################....##.####.#...##
#####################################################.......##...#####
###################################################...###...#...######
################################################...#..####......######
################################..##########..#...#...#.##...#..######
#############################..#...#.#######...#.##..#......###.######
#############################....#....#......#...#..#.....#.#..#######
##############################.....#.#......#......#...####.....######
########################.########....###.....##........####....#..####
######################....##....#.........#.#..##.##.#.####....#...###
#####################.....#...#......#.....##..#.#....####.........###
#########..#########..#..#...#.....##..##.##....#.....####..#......###
#########...#####.#..#...#..#...#...#.##.##...##.###...####..##.####..
##########..####......#........#...#.##.#.##..........####......##...#
##########..####...#..#.#.###.....##.......##...#....####.......##...#
#########....##..#.....#..####.##...#..........#.###.##...####...#....
##########.#..##....#..#...####..#..#.#..#......###......#####...#..##
##..#..###..#...#.#.....#..####......#....###..#..#.#..#########..#.##
#...........#...####.......##...#..#..#..####..##..##############...##
##.......#......#######..#.......#.#....######......##############..##
##..#..####....#######.........#....#..########..#..##############..##
#####.......#########.#..###.#...#..#..############..#############....
####.......##########....####.....#..#..##########...##############.##
###........##########...######.##....#..###########.##################
##..###.....##########.##############..###############################
##.#######.###########################################################
....##################################################################
#..###################################################################
######################################################################
######################################################################
######################################################################
######################################################################
######################################################################
######################################################################
######################################################################

Brog

unread,

May 14, 2008, 9:22:35 AM5/14/08

to

On May 14, 1:54 pm, Jakub Debski <debski.ja...@wp.pl> wrote:
> Jeff Lait was thinking very hard :
>
> > I think your CA method is sufficient. The other major cave generator
> > is the drunkard walk approach, but that can also benefit from some
> > post-smoothing (which the CA method can be though of an example of)
> > On that vein, you might consider feeding your CA the results of a
> > drunken walk to better control over the resulting topography.
>
> The problem with CA is that it doesn't guarantee global traversality
> and you have to connect disconnected areas other way.
>
> In 10 minutes I made a new cave generation algorithm where all the
> cells are accessible.
>
> 0. Place first digger in the central cell
> 1. Choose random digger from the list of diggers.
> 2. Remove this digger from the list.
> 3. If cell, where digger was, has less than 5 or 6 walls around, then
> goto 1.
> 4. Place two new diggers in walls around cell, where digger was.
> 5. Goto 1.
>
> That's all. Simple and effective.

That's.. exactly what Jeff just said, the "drunken walk" approach.
And as he said, the results are a bit rough and you might want to do a
pass over them with the CA to smooth them.

I Own The Letter O

unread,

May 14, 2008, 9:46:41 AM5/14/08

to

> pass over them with the CA to smooth them.- Hide quoted text -

>
> - Show quoted text -

I now know what Drunken Walk is, so I'm learning alot from this post
so far. I think they both have their merits. From the CA experiments
I've done it creates nice open and smooth spaces but leaves some areas
disconnected. 'Drunken Walks' seem to create long rambling and
twisting passageways with a lot of diagonal movement required. As I
intend to use water in the caves as well (a lot of caves that I've
visited or seen on telly have flooded sections) it is easy to imagine
that CA caves are softer rock that has eroded smoothly and 'Drunken
Walk' caves are harder rocks that are slowly giving themselves up to
the erosion. A 'Drunken Walk' cave could require a high caving skill
to negotiate and certain sized creatures could be barred from certains
areas entirely.

In short I think I like both ideas, once I've finished fiddling with
CA for caves I'll experiment with 'Drunken Walk' generators as well as
'L' stamping for roughing the edges of a CA cave and my crazy messed
up L-Jumps for mined/worked caves.

(I also messed up the inputs to my CA at one point and generated a
near perfect maze, that might warrant some investigation after I'm
done with caves.)

Gerry Quinn

unread,

May 14, 2008, 11:42:59 AM5/14/08

to

In article <mn.737e7d858...@wp.pl>, debski...@wp.pl says...

> Jeff Lait was thinking very hard :
> > I think your CA method is sufficient. The other major cave generator
> > is the drunkard walk approach, but that can also benefit from some
> > post-smoothing (which the CA method can be though of an example of)
> > On that vein, you might consider feeding your CA the results of a
> > drunken walk to better control over the resulting topography.
>
> The problem with CA is that it doesn't guarantee global traversality
> and you have to connect disconnected areas other way.

Or just fill up small disconnected areas. In my CA-based system I find
the largest connected region, check that it is large enough and that all
essential locations are in it, and remove all other regions.

This is a bit easier because my method is modified from the original CA
so that certain paths are guaranteed empty, and certain walls are
guaranteed to exist. The main reason for this is that the CA algorithm
gives uninteresting results in very large areas. Lair has cave systems
up to 80x80, and a CA left to run in a square that size will give samey
results.

Here's what happens when CA is allowed run with a region of forced
walls:

<http://indigo.ie/~gerryq/lair/map-base.gif>
<http://indigo.ie/~gerryq/lair/map-full.gif>

I have control of the overall shape of the cave system (in this system
the player will start near the centre and the exit will be in a dead-end
in the north west), but every map based on the same template will be
different. I also use the templates to generate rooms, which admittedly
are a bit too recognisable when you've played a few games.

> In 10 minutes I made a new cave generation algorithm where all the
> cells are accessible.
>
> 0. Place first digger in the central cell
> 1. Choose random digger from the list of diggers.
> 2. Remove this digger from the list.
> 3. If cell, where digger was, has less than 5 or 6 walls around, then
> goto 1.
> 4. Place two new diggers in walls around cell, where digger was.
> 5. Goto 1.
>
> That's all. Simple and effective.

But your digger caves are very nice and seem like an exceppent
contribution to roguelike cave generation. I may consider modifying it
for use with my templates :-)

Gerry Quinn

unread,

May 14, 2008, 11:46:40 AM5/14/08

to

In article <05d25d00-ef7f-458f-9464-d39dd5169332
@x41g2000hsb.googlegroups.com>, lord...@yahoo.co.uk says...

> I now know what Drunken Walk is, so I'm learning alot from this post
> so far. I think they both have their merits. From the CA experiments
> I've done it creates nice open and smooth spaces but leaves some areas
> disconnected. 'Drunken Walks' seem to create long rambling and
> twisting passageways with a lot of diagonal movement required. As I
> intend to use water in the caves as well (a lot of caves that I've
> visited or seen on telly have flooded sections) it is easy to imagine
> that CA caves are softer rock that has eroded smoothly and 'Drunken
> Walk' caves are harder rocks that are slowly giving themselves up to
> the erosion. A 'Drunken Walk' cave could require a high caving skill
> to negotiate and certain sized creatures could be barred from certains
> areas entirely.

Another fix would be to make the digger larger, or otherwise expand the
passageways. Though the algorithm would not be quite so simple, you'd
probably have to make it move in larger steps too. On the other hand,
you'd also have an extra parameter to play with.

- Gerry Quinn

jot...@hotmail.com

unread,

May 14, 2008, 4:39:11 PM5/14/08

to

On 14 Maio, 16:46, Gerry Quinn <ger...@indigo.ie> wrote:
>
> Another fix would be to make the digger larger, or otherwise expand the
> passageways. Though the algorithm would not be quite so simple, you'd
> probably have to make it move in larger steps too. On the other hand,
> you'd also have an extra parameter to play with.
>
> - Gerry Quinn

Yet another way to make the digger method better would be to change
the probability of moving away from the center of the map (relative to
choosing other directions), so that it is proportional to the inverse
of the distance to the center. The probability to move away would be
higher at the center, but as the digger moves to the edges of the map
it would be lower and lower. The cave would be much more compact.

Jotaf

I Own The Letter O

unread,

May 15, 2008, 4:00:09 AM5/15/08

to

On 14 May, 16:42, Gerry Quinn <ger...@indigo.ie> wrote:
> In article <mn.737e7d85845f9384.68...@wp.pl>, debski.ja...@wp.pl says...

I just started to force some results as well. I want my cave-style
dungeons to spread N/E/S/W as well as down and I would like the
entrance to match the exit from the previous level. I am also
considering have features flow down as well as across, i.e. a
waterfall on vertical level 1 breaks through to vertical level 2 and
vertical level 3 before forming a lake on vertical level 4 (it may run
through an inaccessible part of vl2 and vl3 and become the only way to
reach vl4 making for quite a tricky puzzle).

I'm still having to much fun with CA (and no time yesterday to code)
and haven't tried 'Drunken Walk' or my crazy 'L-Jump' ideas yet so I
can't really guess about the results I'll get.

Perdurabo

unread,

May 15, 2008, 5:09:52 AM5/15/08

to

On May 14, 1:54 pm, Jakub Debski <debski.ja...@wp.pl> wrote:

<snip>

mmmm...do you mind if I use this code as a base for a dungeon-
generation algorithm in Kharne? I've been have-heartedly looking for
something to do cave levels and this seems to fit the bill, though
I'll have to convert it to Object Pascal.

Best,
P.

I Own The Letter O

unread,

May 16, 2008, 3:39:07 AM5/16/08

to

I tried making my own 'Drunken Walk' algorithm rather than stealing
the one supplied by Jakub (not out of any morals but because I've
never used the vector library as I'm quite new and want to thoroughly
explore what I've learnt so far, and because I'm scared of new
things :)).

Anyway I was a bit drunk last night and made the most unintelligble,
overly-complex and buggy code I've ever written in my short career.
After a few hours I got a rather hacked version to work. I need to
fiddle with a few of the parameters to get good results (and go
through the code and condense it, even on the bus to work this morning
without it in front of me I was coming up with ways to reduce 12 odd
lines of code that appears twice with a class method that would only
have three lines and that I could obviously call again later if
needed).

At the moment the little digger dudes seem to like to huddle in the
middle rather than reach the edges of the maps like the good examples
given by Jakub above. I did however run a single iteration of CA over
the top of a 'Drunken Walk' (which I think was suggested above) and
got some very interesting results. I still need to experiment with 'L-
Caves' and my crazy 'L-Jump' thing. I only have internet at work and
at various relatives houses but should be able to start a development
blog thing over the weekend where I'll put up some screenshots of each
method if anybody cares (and some hybrids ones, I think a 'Drunken
Walk' smoothed over by CA but with a few 'L-Cave' straggly bits to
represent nooks and crannies might be good).