Overview

From noise emerges,
The pattern of hills and plain,
Thus we can create

Yannakakis and Togelius start by saying [1] "one class of algorithms that are frequently used to generate heightmaps and textures are noise algorithms, many of which are fractal algorithms meaning that they exhibit scale-invariant properties. Noise algorithms are usually fast and easy to use but lack in controllability."

After this, the writers go on to say [1] "Both textures and many aspects of terrain can be fruitfully be represented as two-dimensional matrices of real numbers. The width and height of the matrix map to the x and y dimensions of a rectangular surface." In addition, it is said that in this case a texture is called an intensity map and that [1] "the value of cells correspond directly to the brightness of the associated pixels."

Terrain is said to be called a Heightmap, it is explained as [1] "the value of each cell corresponds to the height of the terrain (over some baseline) at that point." this continues by saying [1] "If the resolution with which the terrain is rendered is greater than the resolution of the Heightmap, intermediate points on the ground can simply be interpolated between points that do have specified height values." It is said that using this common representation on any technique to generate noise could be used to generate terrains and vice versa though these may not be equally suitable.

Yannakakis and Togelius say [1] "It should be noted that in the case of terrains, other representations are possible and occasionally suitable or even necessary. For example, one could represent the terrain in three dimensions, by dividing the space up into voxels (cubes) and computing the three-dimensional voxel grid." An example of this would be Minecraft which uses unusually large voxels, it is explained that Voxel grids allow structures that cannot be represented with heightmaps such as caves and overhanging cliffs, but using this requires a larger amount of storage.

Fractals such as midpoint displacement algorithms are in common use for real-time map generation. Midpoint displacement is explained as a simple algorithm for generating two-dimensional landscapes by repeatedly sub-dividing a line. The procedure is as follows:

1. Start with a horizontal line.
2. Find the midpoint of the line and move the line up or down by a random amount.

This results in breaking the line in two, this can be repeated for both new lines and so on until the resolution is reached. Below is the midpoint algorithm visualized.

In this reference, [2] a fractal-based algorithm is presented called the Morphologically Constrained Midpoint Displacement (MCMD). It is based on improvements of the classical midpoint displacement methods and MDI algorithm.

An easy way of extending the midpoint displacement to two dimensions would be to create two-dimensional Heightmaps that can be interpreted as three-dimensional landscapes this is the Diamond-Square algorithm [1](also known as “the cloud fractal” or “the plasma fractal” because of its frequent use for creating such effects).

Yannakakis and Togelius say [1] "This algorithm uses a square 2D matrix with width and height 2n +1. To run the algorithm you normally initialize the matrix by setting the values of all cells to 0, except the four corner values which are set to random values in some chosen range (e.g., [−1,1])." Continuing on from this is says to follow these two steps[1]:

1. Diamond step: Find the midpoint of the four corners, i.e., the most central cell in the matrix. Set the value of that cell to the average value of the corners. Add a random value to the middle cell.

2. Square step: Find the four cells in between the corners. Set each of those to the average value of the two corners surrounding it. Add a random value to each of these cells.

After following these steps this method can be called recursively for each of the four subsquares of the matrix until you reach the resolution limit of the matrix (3*3 sub-squares), Everytime this method is called reduce the range of the random values somewhat. this is shown in the following figure.

There are many more advanced methods for generating fractal noise such as Perlin noise which has some benefits over the Diamond-square algorithm.

References

[1] G. Yannakakis and J. Togelius, "Artificial intelligence and games.", Springer International Publishing, 2018.

[2]F. Belhadj, “Terrain modeling,” Proceedings of the 5th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa - AFRIGRAPH 07, 2007.