Terrain generation in the DMD

Started by Bacteriophage, October 18, 2015, 05:59:03 PM

Previous topic - Next topic

Bacteriophage

I was wondering if anyone knows anything about the terrain generation algorithm used in the DMD.  A few thoughts/questions:

1. I seem to recall hearing the words "Perlin noise" in connection to CW1's chronom maps.  The picture in the Wikipedia article on the topic does seem to match what the DMD shows with persistence and lacunarity off.

2. I think I might sort of know what lacunarity is: from what I've read, high lacunarity indicates large gaps rather than small gaps, and a "non-homogeneous" appearance.  If I apply this to a certain terrain level, this sort of works.  As lacunarity increases, smaller "islands" of a given height are placed with increasing frequency between larger "islands", and the terrain looks more and more "random" over a small area, rather than having sharp, clear edges.  This only seems to work if a low number on the slider refers to a high lacunarity, and vice versa.  Also, I'm not sure how it would be possible to control something like this in the generation algorithm.

3. I don't really know what persistence is, but I have a somewhat-educated guess that it has something to do with the tendency of an upward slope to continue being an upward slope, rather than suddenly going downward?  Again, this only makes sense if low "persistence" refers to a slope that keeps going in the same direction, while high "persistence" refers to a slope that jumps randomly between up and down.

4. If you look at a map, turn the persistence up, and increase the lacunarity from 0, the terrain irregularities seem to converge toward the top left corner.  I'm not sure why.

5. I'm not sure I can really tell the difference between "alternative noise" and the normal algorithm, except that "alternative noise" has a significantly higher apparent amplitude and "seamless" is only an option for "alternative noise".

If anyone knows or suspects anything about these or other topics (or has questions of their own), I would appreciate a reply.

Builder17

I think next crazy button in DMD is nice. What you think about it?

warren

The wikipedia article on perlin noise is clear as mud. In terrain generation, use of the diamond square algorithm is usually used to make random terrain. This is reinterperable as multiple layered octaves of value noise more or less. Perlin noise is an example of gradient noise, and can be seen as horizontal displacement of pixels before assigning a height, much as the diamond square uses vertical displacement after assigning a height. The two look almost identical when configured similarly.

Using the diamond square as the example, there are two main alterable parameters:
1) Initial amplitude: If set low, the terrain will not hit the ceiling and floor values. This is a pure algorithm. If set high, sometimes calculated values will hit the ceiling or floor. These values will then be clamped back into range. This has a shrinking effect. The higher the initial amplitude relative to the distance between ceiling and floor, the more mountains and valleys end up in the terrain.
2) Amplitude falloff: as the algorithm moves from defining large features to small features, by how much is the displacements reduced. A 1:1 ratio of amplitude to scale produces a pure algorithm. Faster falloffs reduce the fractalness of the terrain by making the smaller features fade into perfectly smooth slopes. Slower falloff produces sharp cliffs and spikes all over the map.

These noise algorithms are all usually much faster than any other random terrain algorithms.

Bacteriophage

Thank you warren; that was very interesting.  It led me to some other ideas and thoughts, which I write below.

I don't think the "base" Perlin noise (no persistence, no lacunarity) incorporates features at multiple scales.  Looking at the DMD maps, hills and valleys seem to be of roughly uniform size, and lines of constant height seem to be ordinary curves, not fractals.  The Wikipedia article, impenetrable as it is, displays two pictures: one of "a two-dimensional slice through 3D Perlin noise", which I am going to assume looks something like 2D Perlin noise, and one of "Perlin noise rescaled and added into itself to create fractal noise".  DMD maps look far more like the first than the second.

I think persistence and lacunarity work as follows:  lacunarity defines a scale, with larger lacunarity meaning a smaller scale.  Perlin noise is generated, fit appropriately to the scale, and added to the original noise, with an amplitude given by persistence.  This explains many of my observations neatly.  Leaving lacunarity high and turning persistence down leads to a gradual smoothing out of terrain irregularities, as the amplitude of the second Perlin noise function is decreased.  Leaving persistence high and turning lacunarity down leaves the second Perlin noise the same in all cases, but changes its scale, thus leading to the "growing" appearance of irregularities from the top left corner.

So that leaves my alternate noise question, and the question of why there are only features of one or two scales.  I assume this has to do with the computational time needed to be able to hit the "next crazy" button about 10 times per second and not see a noticeable delay, but this may also affect playability in some way.  I wonder if alternate systems were tested during development.

warren

#4
Okay: First of all, the definitions I gave above are not entirely correct.

With that said: persistence=high amplitude falloff. Fractal randomness!=fractal.

The only part of the definition of fractal that fractal randomness maintains is self similarity at smaller scales.

I likely made errors in defining the difference between perlin and diamond square. In fact, I think I probably confused perlin noise for a third, entirely different algorithm very similar to what wikipedia described. The main difference is mostly perlin noise involves interpolation, diamond square involves recursion.

Luckily, programmers invented the internet. When it comes to computer stuff, accurate information is only ever a google search away. Wikipedia is really a secondary source of information for coders.