There has been an emphasis lately on the use of procedural generation in games. As such I spent some time researching this area of games development and the algorithms used to achieve this. From this I have produced a simple application which procedurally generates terrain. The terrain in this application is generated using Perlin noise, this is achieved using the C++ Perlin noise classes provided by Ken Perlin on his personal website (Perlin, 2015). Perlin noise is a procedural noise generation technique used in a variety of applications, most commonly computer generated imagery. It was first used in Disney’s Tron (1982) and has since been used in many games and movies. This algorithm is commonly implemented in two, three or four dimensions and involves three main stages; grid definition, computation of the dot product between the distance-gradient vectors and interpolation between these values.
Grid definition is used to assign a gradient vector of unit length in every dimension. For two or more dimensions Perlin noise applies a random vector to a unit circle. This process is continued until all gradients are obtained and re-normalized. The second stage of the algorithm is used to determine which pixel a given point falls. For each coordinate in the texture a distance vector between a particular point and the coordinate is determined. The dot product between the gradient vector from the first stage and the distance vector is calculated. This process is repeated for every pixel in the texture. The final stage of the Perlin noise algorithm involves interpolating between the dot product values for each pixel. Interpolation is performed using a zero first derivative function at both endpoints. A scaling factor is also applied in order for the resultant value to fall within the range -1.0 to 1.0.
This application was based on an Direct3D 11 application previously developed, this application originally loaded in a single height map texture which was then used to build a 3D terrain model. I have adapted the application to no longer load a height map. Instead the applications Terrain class creates a square plane 512x512 units in size.
Perlin noise is then used to take every mesh point on this plane and applies a random gradient. The Perlin noise function then picks a random pixel on the plane and retrieves the distances between the four closest points and the pixel. The dot product of these values are then calculated and then linearly interpolated which results in a seemingly random terrain. This is performed using the noise3 function inside of the PerlinNoise class provided by Ken Perlin. The noise3 function acts only on the Y value of the terrain plane, adjusting only the height of the plane at given points, the results of which can be seen in the video below.
The terrain is lit using ambient lighting which is handled by the TerrainShader class. The terrains mesh is given shared normals for every vertex so that lighting can be accurately calculated over the entire terrain. The terrain is also textured inside of this class using a series of textures which are tiled across the terrain mesh. Each of these textures is procedurally blended together depending on the height of the terrain at any given point. This allows the terrain to have muddy rock based slops and grassy hill tops. This is achieved by determining the slope of the terrain at each pixel using a pixel shader.
Due to the scale of the terrain the application may experience a drop in frame rate. To help alleviate this, the terrain is partitioned using a quad tree. This technique separates the terrain into a series of quads and each of these quads is separated into a number of smaller quads. This process is repeated until each quad contains less than 100000 triangles. The use of quad trees is also used to help determine the height of the camera as it moves across the terrain. This helps to prevent the camera being able to move through the terrain.
Height based movement is determined by first checking if the camera is located on or above the terrain. If it is then the QuadTree class performs a check to determine which node of the quad tree the camera is currently in. A line-triangle intersection test is performed to find which triangle in the current node the camera is currently above. The height of the triangle below the camera is then returned from this test and the camera’s height is then placed four units above this triangle.
Perlin, 2015