Random Terrain Generation

Terrain has the property of being self similar. If you pick up a rock and look at at its texture, you will notice that it has roughly the same overall pattern as its parent rock formation when viewed closely. This is where the use of fractals comes in. Fractals are part of a relatively new branch of math known as chaos which seeks to describe complicated systems found in nature such as weather patterns that are not easily explained by traditional theories. Although the topic of fractals and chaos theory are beyond the scope of this project, many of the methods used to generate terrain employ simple fractal methods to produce such natural patterns.

So far, two algorithms for random terrain generation have been implemented in the project: the midpoint displacement method and the Perlin noise function.

Midpoint displacment

The midpoint displacement algorithm uses an iterative approach to produce random terrain by displacing the midpoint between two boundaries by a random amount and repeating the process for the left and right subdivisions recursively. The mathematics behind it is called Brownian motion. This concept is easily visualized in two dimensions as shown in the following pictures and can be easily extended into three dimensions.

In midpoint displacement algorithm in three dimensions is called the Diamond Square algorithm.

Perlin noise

Perlin noise is a continus random variable function developed by Ken Perlin in the 1980s. The basic idea behind it is to implement a function that returns a value that varies continuously as a function of its parameter. This is done by taking a discrete random number function such as C's rand(), who's parameter is a seed, and interpolating the values of the function evalulated at two points to get a continuous function. Depending on the method of interpolation, very complicated natural patterns can be produced.

Perlin noise can be implemented in N dimensions. A one dimensional function can be used to produce a random waveform which can be used as "noise" in sound effects. A 2D Perlin noise function can be used to generate heightmaps, which can look like clouds, by producing a height as a function of xy pairs.