# Using fractals for dungeon generation

G

#### Guest

##### Guest

I wonder if you know any fractals and fractal algorithms that might come
in handy when genereating terrain or caves?

Also, some time ago tehre was a question about a fractal that'd look
like some seemingly-random rivers.

--
Radomir @**@_ Bee! .**._ .**._ .**._ .**._ zZ
`The Sheep' ('') 3 (..) 3 (..) 3 (..) 3 (--) 3
Dopieralski .vvVvVVVVVvVVVvVVVvVvVVvVvvVvVVVVVVvvVVvvVvvvvVVvVVvv.v.

G

#### Guest

##### Guest

Hansjoerg Malthaner wrote:
> I once experiemented with parametrized curves (x,y) = f(p), p in
0..1
> to produce rivers. I didn't get anything that looked enough like a
> river, but I think a better mathmatician than me could get something
> together that is enough riverlike for a game.

Making the river go to some general direction and then adding
random sideway movement seems to work well. That's how I got

G

#### Guest

##### Guest

Dnia Wed, 20 Apr 2005 09:47:03 +0000 (UTC), The Sheep napisa³(a):
> I wonder if you know any fractals and fractal algorithms that might come
> in handy when genereating terrain or caves?
>
> Also, some time ago tehre was a question about a fractal that'd look
> like some seemingly-random rivers.

You can use fractals to generate heightmaps.
Then adding rivers/lakes is very simle.

regards,
Jakub
--
"We're just toys in the hands of Xom"
xenocide.e-plan.pl - SF roguelike in development
www.graveyard.uni.cc - visit Roguelike Graveyard
www.alamak0ta.republika.pl - my other projects

G

#### Guest

##### Guest

The Sheep wrote::

> I wonder if you know any fractals and fractal algorithms that might come
> in handy when genereating terrain or caves?

I used to use 'perlin noise' to generate terrain (might work for caves,
also). I don't know if it truly is a fractal.

I also used the fractal area subdivision method. (But you know that as
well, your 'divide rooms by corridors' uses that ideas ).

> Also, some time ago tehre was a question about a fractal that'd look
> like some seemingly-random rivers.

IMO it's easier to create a landscape by area subdivision and then set a
well in the landcape and let the water find a way downhill. This will
also generate lakes.

--
c.u. Hajo

G

#### Guest

##### Guest

Dnia Wed, 20 Apr 2005 14:40:19 +0200,
Hansjoerg Malthaner napisal(a):

> The Sheep wrote::

>> I wonder if you know any fractals and fractal algorithms that might come
>> in handy when genereating terrain or caves?

> I used to use 'perlin noise' to generate terrain (might work for caves,
> also). I don't know if it truly is a fractal.

> I also used the fractal area subdivision method. (But you know that as
> well, your 'divide rooms by corridors' uses that ideas ).

Yes, and this topic was discussed here a lot.
I thought there might be some fresh ideas.

>> Also, some time ago tehre was a question about a fractal that'd look
>> like some seemingly-random rivers.

> IMO it's easier to create a landscape by area subdivision and then set a
> well in the landcape and let the water find a way downhill. This will
> also generate lakes.

Yes, but then you can't just generate any part of map you want, not
looking at other parts. Remember?

--
Radomir @**@_ Bee! .**._ .**._ .**._ .**._ zZ
`The Sheep' ('') 3 (..) 3 (..) 3 (..) 3 (--) 3
Dopieralski .vvVvVVVVVvVVVvVVVvVvVVvVvvVvVVVVVVvvVVvvVvvvvVVvVVvv.v.

G

#### Guest

##### Guest

The Sheep wrote::

> Dnia Wed, 20 Apr 2005 14:40:19 +0200,
> Hansjoerg Malthaner napisal(a):
>
>
>>The Sheep wrote::

>>>Also, some time ago tehre was a question about a fractal that'd look
>>>like some seemingly-random rivers.
>
>>IMO it's easier to create a landscape by area subdivision and then set a
>>well in the landcape and let the water find a way downhill. This will
>>also generate lakes.
>
> Yes, but then you can't just generate any part of map you want, not
> looking at other parts. Remember?

I remember very well
That's the reason why H-World never got rivers.

I once experiemented with parametrized curves (x,y) = f(p), p in 0..1
to produce rivers. I didn't get anything that looked enough like a
river, but I think a better mathmatician than me could get something
together that is enough riverlike for a game.

--
c.u. Hajo

G

#### Guest

##### Guest

Hansjoerg Malthaner wrote:
> The Sheep wrote::
>
>> Dnia Wed, 20 Apr 2005 14:40:19 +0200,
>> Hansjoerg Malthaner napisal(a):
>>
>>> The Sheep wrote::
>
>>>> Also, some time ago tehre was a question about a fractal that'd look
>>>> like some seemingly-random rivers.
>>
>>> IMO it's easier to create a landscape by area subdivision and then
>>> set a well in the landcape and let the water find a way downhill.
>>> This will also generate lakes.
>>
>> Yes, but then you can't just generate any part of map you want, not
>> looking at other parts. Remember?
>
> I remember very well
> That's the reason why H-World never got rivers.
>
> I once experiemented with parametrized curves (x,y) = f(p), p in 0..1
> to produce rivers. I didn't get anything that looked enough like a
> river, but I think a better mathmatician than me could get something
> together that is enough riverlike for a game.

Try passing a random walk through a low-pass filter (to remove the
high-frequency noise).

--
Palladium? Trusted Computing? DRM? Microsoft? Sauron.
"One ring to rule them all, one ring to find them
One ring to bring them all, and in the darkness bind them."

G

#### Guest

##### Guest

Dnia 20 Apr 2005 11:43:49 -0700,
Krice napisal(a):

> Hansjoerg Malthaner wrote:
>> I once experiemented with parametrized curves (x,y) = f(p), p in
> 0..1
>> to produce rivers. I didn't get anything that looked enough like a
>> river, but I think a better mathmatician than me could get something
>> together that is enough riverlike for a game.

> Making the river go to some general direction and then adding
> random sideway movement seems to work well. That's how I got

It's still local. You can't just pick an arbittrary area of the map and
generate it.

You could do it if the rivers would be a fractal, or somehow based on
local properties of a fractal.

--
Radomir @**@_ Bee! .**._ .**._ .**._ .**._ zZ
`The Sheep' ('') 3 (..) 3 (..) 3 (..) 3 (--) 3
Dopieralski .vvVvVVVVVvVVVvVVVvVvVVvVvvVvVVVVVVvvVVvvVvvvvVVvVVvv.v.

G

#### Guest

##### Guest

The Sheep <sheep@atos.wmid.amu.edu.pl>
wrote on Wed, 20 Apr 2005 18:51:29 +0000 (UTC):
> Dnia 20 Apr 2005 11:43:49 -0700,
> Krice napisal(a):
>> Hansjoerg Malthaner wrote:
>>> I once experiemented with parametrized curves (x,y) = f(p), p in
>> 0..1
>>> to produce rivers. I didn't get anything that looked enough like a
>>> river, but I think a better mathmatician than me could get something
>>> together that is enough riverlike for a game.
>> Making the river go to some general direction and then adding
>> random sideway movement seems to work well. That's how I got
> It's still local. You can't just pick an arbittrary area of the map and
> generate it.
> You could do it if the rivers would be a fractal, or somehow based on
> local properties of a fractal.

You certainly can do it purely randomly as the player explores. When
you go to generate a new region, check each existing bordering region
that has rivers and put a river "seed" in your new region at the
appropriate border square. Bordering regions that haven't been
generated yet, you can randomly decide if the edge should have a river
seed. Then you generate your rivers from those seeds.

You now just have to make sure all of your river seeds flow into each
other (or not--multiple unconnected rivers could pass through one map).
This works nicely for trails, too.

More generally, you should always fade the terrain of existing maps
into your newly-generated maps to make the edges less sharp.

--
<a href="http://kuoi.asui.uidaho.edu/~kamikaze/"> Mark Hughes </a>
"Gibson and I dueled among blazing stacks of books for a while. [...] The
streets were crowded with his black-suited minions and I had to turn into a
swarm of locusts and fly back to Seattle." -Neal Stephenson, /. interview

G

#### Guest

##### Guest

Hey The Sheep, as it happens, I have also been looking into fractal
algorithms for roguelikes. Let me share what I have so far.

Perhaps the simplest fractal-like generation function is
midpoint-displacement, which you've probably heard of already. You can
see a real implementation in the ToME game; it's used to generate
themed caves and outdoor terrain.

There are limitations to midpoint displacement, especially for terrain
that needs to look natural. A more sophisticated way is to use a
process called Fractal Brownian Motion, or Fractional Brownian Motion
(FBM). I can't get into the details here, but there are two excellent
resources available,

o Perlin's notes at http://www.noisemachine.com/
o Gamasutra article:
http://www.gamasutra.com/features/20010302/oneil_02.htm

Implementation is a bit tricky until you get to understand the basics.
Since I believe that code is the best teacher, we are fortunate that
I've already created an implementation for my upcoming roguelike,
Quenta, which will be released GPL or perhaps LGPL. Here's a screenshot
of a custom app I used to tweak fractal roguelike text-mode terrain:

o http://log4r.sf.net/images/fbm.png

If you wish, I can give you the code. It uses SDL, SDL_ttf, and was
developed on Linux. If there's general interest, I can start a
bare-bones project for this tool. But I'm kind of busy.

Cheers,
Leon Torres

The Sheep wrote:
> I wonder if you know any fractals and fractal algorithms that might
come
> in handy when genereating terrain or caves?
>
> Also, some time ago tehre was a question about a fractal that'd look
> like some seemingly-random rivers.
>
> --
> Radomir @**@_ Bee! .**._ .**._ .**._ .**._ zZ
> `The Sheep' ('') 3 (..) 3 (..) 3 (..) 3 (--) 3
> Dopieralski
..vvVvVVVVVvVVVvVVVvVvVVvVvvVvVVVVVVvvVVvvVvvvvVVvVVvv.v.

G

G

#### Guest

##### Guest

The Sheep wrote:
> It's still local. You can't just pick an arbittrary area of the map
and
> generate it.

Of course I can. Maps in Kaduria are entirely in memory for each level
and rivers can be created anywhere. But it's another issue if the river
is going to cause problems.. it could flow to a long corridor which is
also the only way to another area of the map. To prevent having
river as "impossible" barrier I have made swimming quite easy, you
can swim quite long time without drowning. Another option is cut walls
along the river. I like the idea where the player has to fight against
environmental troubles.

G

#### Guest

##### Guest

Leon Torres wrote:
> I got off my lazy butt and posted the code for that fractal exploring
> tool. It's very quick and dirty, so beware. You'll need SDL and SDL_ttf
> and probably wchar.h.
>
> http://www.ugcs.caltech.edu/~leon/drop/fbmexp.tgz
>
> - Leon

Thanks. Nice resume too - I like the open source section.

--
ABCGi - What is the Matrix/Neo/Twisted?
http://web.archive.org/web/20040930171537/http://members.rogers.com/derbyshire2/#me