Game Development Reference
7.3.2 Procedural Terrain
Procedural terrain is that generated by a computer algorithm. Most of the
methods are based on fractals. A program is written that defines the vertices
of a mesh and recursively raises and lowers the points to create altitude. One
simple terrain producing method is the midpoint displacement algorithm.
This algorithm works starting with a flat surface. It divides it in half and then
raises or lowers the middle point. Then each half is halved and the midpoint
of these is raised or lowered. A 2D representation of this progression is
illustrated in Figure 7.17 .
Another popular procedural terrain generation algorithm is the Diamond
Square method illustrated in Figure 7.18 . Starting with a square mesh with
a power of 2 + 1 number of vertices in width and height, 1 for example, 257,
FIG 7.17 Midpoint displacement
on a 2D line.
FIG 7.18 The Diamond-Square algorithm.
1 We need to add an extra vertex along the sides so that there is an odd number of vertices,
allowing for an exact middle one to be located.