Hey everyone. I recently made my own cave generator based on Brian's
Cellular Automata at
http://www.herassmygod.org/bcr19374/programming/cellular/ and it works
beautifully.

What I don't understand is how it works. When I looked at the source
code, it says that "if at least X amount of tiles are within 1 radius
of a tile, and at most Y amount of tiles are within 2 radius of a tile,
then the tile changes".

I can't see the logic behind the "at most Y amount of tiles are within
2 radius" part. I don't really HAVE to, because it works fine with a
30% fill with a 4 0 2 generation and that's all I really need. But I'm
curious...

Can anyone explain this to me? Thanks!

Usually, a cellular automaton uses the number of adjacent squares;  if
5 or more squares are squares in radius 1, the cell is a wall,
otherwise, a floor. The problem with this is that it tends to generate
large open spaces, which are uninteresting as far as roguelikes go. the
soulution is to take any uninteresting tiles, those that are all alone,
and make that area more interesting, by adding walls to it.  I just
makes the map more interesting is all. I find that I haven't needed to
do that, that I get interesting enough maps with 1 generation and 42%
fill. There are lots of interesting things you can do with cellular
automata.

The page you referenced is unreachable (invalid domain name), but that
rule sounds like what I described in this article:
  http://www.jimrandomh.org/misc/caves.html
(second draft with nice HTML formatting of article first published as
http://www.jimrandomh.org/misc/caves.txt), which explains the reasoning
behind the radius-2 rule. It fills in big empty spaces without breaking
connections, so that you can seed with a lower fill and usually get a
uniform looking, connected dungeon.

--
CalcRogue: TI-89, TI-92+, PalmOS, Windows and Linux.
http://calcrogue.jimrandomh.org/

At Mon, 25 Jul 2005 20:52:08 GMT,

Would you agree to put it on roguebasin?

--
 Radomir `The Sheep' Dopieralski    @**@_
                                    (`') 3  Grrr!
                     .   .  . ..v.vVvVVvVvv.v.. .

Ah yes, sorry bout the link. The real ones are those you posted...

"It fills in big empty spaces without breaking connections, so that you
can seed with a lower fill and usually get a uniform looking, connected
dungeon."

What does "seed with a lower fill" mean?

Oh, another question I've been meaning to ask: when I tried the "4-5"
thing on your site (Fill: 45%, R1Cutoff: 4, R2Cutoff: 5 Repeats: 5) all
I got was a huge map, all walls, with one piece of floor. What's going
on?

Thank you very much for your time. I really appreciate it!

You initialize (seed) the map by making some percentage of tiles
walls (fill). So by this I meant, make fewer of the tiles walls
initially.

Ah, I think I see where the confusion comes from. The "4-5" rule is
this:
 Tile T will be filled if either
  - T is already filled *and* at least 4 of its neighbors are filled
  - T is not yet filled *and* at least 5 of its neighbors are filled

This is the same thing as saying
  Tile T will be filled if the number of tiles within one step of T,
  including T itself, is at least 5.

But this is not the function which my sample program uses. The
function I use is
  Tile T will be filled if the number of tiles within one step of T,
  including T itself, is at least R1Cutoff OR the number of tiles
  within TWO steps of T, including T itself, is at MOST R2Cutoff.

So, if R1Cutoff=4 and R2Cutoff=5, that will happen almost all of the
time.

Anyways, the function I eventually chose as the 'best' answer was
  Fill: 40%
  Repeat 4 times:
    R1 cutoff: 5
    R2 cutoff: 2
  Repeat 3 times:
    R1 cutoff: 5
    R2 cutoff: -1

So the parameters would be
  xsize ysize 40  5 2 4  5 -1 3

--
CalcRogue: TI-89, TI-92+, PalmOS, Windows and Linux.
http://calcrogue.jimrandomh.org/

The Sheep <thesheep@ sheep.prv.pl> wrote:

Of course.

--
CalcRogue: TI-89, TI-92+, PalmOS, Windows and Linux.
http://calcrogue.jimrandomh.org/

Your algo is great!!! have been playing with it this week-end and found
some other parameters wich could be interesting:

Wormholes 1 or 2 tiles wide:
   xsize ysize 45  5 2 10  5 -1 10 5 2 1

Wormholes 2 tiles wide (sometimes with rooms):
   xsize ysize 45  5 2 10  5 -1 10 5 2 1

Some others:
   xsize ysize 45  5 0 5 5 1 1
   xsize ysize 45  5 -1 5 5 1 1

It can be interesting to include the pseudo-random seed as a parameter,
so you can see R1 and R2 effects on the same pattern.

Do you mind if I use it in my roguelike ?

-----------
Severian
Plasma Roguelike

At Tue, 26 Jul 2005 02:20:07 GMT,

Great! I'll add it asap, but...

It seems to be down at the moment?

--
 Radomir `The Sheep' Dopieralski    @**@_
                                    (Qq) 3  Sob?
                     .   .  . ..v.vVvVVvVvv.v.. .

You still have the problem of getting rid of disjoint regions. How do
you plan on tackling that?

I've implemented this nifty generator in my roguelike (I liked the
looks of the samples and I didn't want to emulate NetHack with rooms
and tunnels.. what kind of a _dungon_ has those?) and my current plan
is to have the upstairs and downstairs be in the biggest region, and
allow the smaller disjoint regions to exist.. maybe give the player a
pickaxe and put some treasure in them. Heh. Any other ideas?

Giving a pickaxe was my idea too :) and choosing entrance and exit in
the same region (by pathfinding them), at least at the first levels.

Another idea: you could create a living dungeon, just by generating -
let us say, every 50 rounds - a new cycle for the map, and coming
backward then, like if it was 'pulsating'. Don't know if I am clear...

In article <1122311243.766395.306...@g49g2000cwa.googlegroups.com>,
Verda...@gmail.com says...

It fills up the middle of any big empty space, but not the edge.  So
the maze stays connected even though a lot more of it is getting filled
up.

- Gerry Quinn

In my map, I have three variables per tile: Char, Color, and
Attributes. Attributes are used later, for walkable and stuff, but
thats after the map generation. So I thought, why not use them now?
Here's what I do:

Use this Attributes variable to store the "region" variable that the
tile is in. That tile and the ones connected to it, and the ones
connected to those, etc. will all be in the same region. You would have
a few different regions across the map.

Start out with a Region variable as zero. Cycle through every tile on
the map, and when you hit a floor that is un-regioned (has no region),
set that to your Region variable. Then, start a "spreading" thing (kind
of like what A* uses) and take over all the adjacent un-regioned floor
tiles, and take over the ones next to those, etc. until theres no more
connected tiles to spread to. Increment the Region variable. Then
continue cycling through the map, looking for more un-regioned tiles
and do the same process. Soon, every floor tile on the map will have a
region.

If there's only one region, youre done. If not, keep reading. Find a
tile of one region, and a tile of another. Then, make a path of floor
tiles from one to the other. When they meet, make all their region
variables the same, so they're combined. Keep making paths until it's
all connected.

I'm not that good at explaining code, but you probably get the general
idea. This method worked great for me, and with a little tweaks, the
connections between regions could look like caves themselves.

At 26 Jul 2005 03:55:13 -0700,
 Shawn  Moore wrote:

Just an untested idea, but how about this:

The cellular automaton preserves connectivity, so any disjoint regions
must come from the initial noise used to fill the map. The idea is to
use something different than just noise, to assure the connectivity before
applying the automaton filters.

For example, you could fill the map with solid rock and carve some empty
spaces using several random walks (you can ensure they are all connected
by starting all of them but the first one on an empty cell), until you get
the desired percentage of empty cells.

--
 Radomir `The Sheep' Dopieralski    @**@_
                                    (Xx) 3  ...
                     .   .  . ..v.vVvVVvVvv.v.. .

Where do you get that ? The first rule says that if a floor has five
walls as neigbours, a wall will be created, so I guess it can close
areas.

At 27 Jul 2005 06:21:23 -0700,

Right, no idea where it came from :( Sorry.

--
 Radomir `The Sheep' Dopieralski    @**@_
                                    (Xx) 3  ...
                     .   .  . ..v.vVvVVvVvv.v.. .

Actually I tried your idea wich look very promising, then realised that
closed areas could appear from open ones.

Nevertheless your idea was good indead: if we find an algorithm that
preserves connectivity, then an open area map will always be
transformed into another open area. It looks like a mathematical
function :)

We are sure some transformations preserve connectivity:
- when it only removes walls
- when it adds a wall where there are neighbour walls only on one side
- or, said in another way, when it does not connect on side with
another- ; for instance:

#..  ###  ..#  ...  ##.      ##.      ###      ###      ###      ###
#X.  .X.  .X#  .X.  #X. (x4) #X. (x4) #X. (x4) #X. (x4) #X. (x4) #X#
#..  ...  ..#  ###  #..      ##.      #..      ##.      ###      ###

(actually the last one should not appear)
(x4 means you can repeat the pattern in the 4 directions)

Another idea, perhaps we can look into Mandelbrot fractal and Julia
graphs: for each complex point of Mandelbrot there is a Julia graph
associated, and if the point is INSIDE mandelbrot figure, then the
julia graph associated will be in only one piece.

Wait, what's this about mandelbrot?

Is it better than cellular automata?

Julia sets are too regular for carving caves I guess.

Have a look there if you want to have more information about Julia
connectivity:

http://www.geocities.com/CapeCanaveral/2854/

Let's try not to reinvent the wheel :)

I found this Angband patch creating fractal caves from midplacement
algorithm; it seems to have a way to connect areas together:
http://public.www.planetmirror.com/pub/angband/Patch/sfpatch4.tar.gz