Re: NEW Dungeon Creation Algorithm, Article

The Sheep wrote:
> At 8 Aug 2005 13:07:42 -0700,
> Thomas wrote:
>
> > (slow version, could be optimized!! a lot!)
> > For every square on our grid, we compile a list of the "nearby" balls.
> > We then add the threshhold of every nearby ball to a temporary integer
> > and then subtract the distance to every ball from this integer. If this
> > number is positive then we have a floor tile. if not we have a wall
> > tile. Its that simple. This algorthim could be optimized and the math
> > is probably a little off. There are algorithms you can find through a
> > google search that will probably be better/faster and offer you much
> > more control. My simple example does work and has been tested on
> > QBasic. I will probably implement this for some levels in my upcomming
> > game CHAZM!
>
> What's the difference between this and just carving the balls in the rock?
> You know, emptying all the tiles closer to the ball's center than it's
> radius...

I can't understand Thomas' pseudocode very well. However, I can
perhaps present the metaball technique a bit more clearly.

You can consider your dungeon to be defined by a scalar field. Every
cell has a floating point value representing the intensity of the field
at that point. Start with it all zero.

We then say that any cell with a field value over one is considered an
empty space, below one is considered wall.

If we modify this field with a finite number of smooth operators, we
should expect it to stay smooth.

Each metaball is defined by a point in space, a radius for the fall
off, and the weight for the center of the metaball. A metaball has its
own scalar field which can be mixed with the existing field through any
operator. Usually, one uses addition to get a blending effect.

There are number of different fall off functions possible. However,
one usually wants the metaball field to go to zero at the radius. This
lets you ignore metaballs beyond a certain distance from your cell
point. (In the case of 2d roguelike maps, brute force and ignorance
would likely suffice, however)

If we want to find the metaball's field strength at position (x,y)
given a metaball center (cx, cy), radius r, and weight w, we'd first
define the distance:

d = sqrt((x-cx)^2+(y-cy)^2)

Then we apply the metaball falloff function, F, to get the final value:

result = w * F(d / r)

Ideally, you can write F in terms of d^2 rather than d, saving a square
root. We want a function that has:
F(0) = 0
F'(0) = 0
F(1) = 1
F'(1) = 0
This gives us a quartic (sometimes referred to as the Elendt model):
F(x) = 1 - (1 - x^2)^2

With one metaball, you carve out a circle. However, where multiple
fields meet their effects overlap to give nice smoothed edges.

Note as well that one can replace the distance-from-point with any
other distance function, such as distance-from-line to get a metaline.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

.