Note for procedural generation

I was play deep rock galactic and was wondering how procedural generation work, so i'mma read it up and take notes.

Reading list

Generating Random Fractal Terrain

Concept behind fractal: self similarity, meaning it copies itself in a miniture version, and so on and so forth.

This is like human blood vessels, it starts from main arteries, than branch out to small veins.

Midpoint displacemen in one dimension

Start with a single horizontal line segment.
Repeat for a sufficiently large number of times {
 Repeat over each line segment in the scene {
  Find the midpoint of the line segment.
  Displace the midpoint in Y by a random amount.
  Reduce the range for random numbers.
 }
}

From This

img

to This

img to this

img

This is a recursive operation

It is also a simple algorithm that creates complex result.

Roughness constant H determines the roughness of the fractal.

Height maps

The same algorihtm can be used to generated the height of a 3d space, then combining with the x and y coordinates, you get a height map.

img

diamond-square algorithm

The diamond step: Taking a square of four points, generate a random value at the square midpoint, where the two diagonals meet. The midpoint value is calculated by averaging the four corner values, plus a random amount. This gives you diamonds when you have multiple squares arranged in a grid.

The square step: Taking each diamond of four points, generate a random value at the center of the diamond. Calculate the midpoint value by averaging the corner values, plus a random amount generated in the same range as used for the diamond step. This gives you squares again.

img

Implementing this algorithm recursivly will cause generation with insufficient data at some point. Like after the first pass, the square step will not recieve the four cornors of the diamond in this implementation:

Do diamond step.
Do square step.
Reduce random number range.
Call myself four times.

So the iterative implmentation is:

 While the length of the side of the squares 
 is greater than zero {
 Pass through the array and perform the diamond
 step for each square present.
 Pass through the array and perform the square 
 step for each diamond present.
 Reduce the random number range.
 }

This algorithm can also be used to generate clouds by determining the color value instead of the height value.

img