Game Development Reference

In-Depth Information

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.