nGENE Tech is a one-man-project. Thus I have permanent problem with lack of visual assets (or their poor quality at best) when creating demos or even simple samples/tutorials. Procedural approach to their creation is a one way to go. Recently I implemented terrain generation tools for nGENE Tech Toolset and here goes some thoughts and details about it. More often than not, terrain in games is created from height-maps. Height-maps are gray scale textures where 1 stands for highest points and 0 for the lowest ones (or 255, 0 if you prefer this format). The rest of the values is interpolated linearly between. That is obvious I think.
Manual creation of height-maps is a real pain. It's really tough to achieve desired effect (with erosion and stuff like that) using Photoshop for instance. Probably some talented artists are able to do that but still it would be a waste of time in the majority of cases. Height-maps can be fortunately pretty easily created procedurally. There are several methods to achieve that eg.:
- fault formations
- mid-points
- particle deposition
Today I'll describe particle deposition algorithm because I think it's pretty cool, easy to implement and after some changes to the Schankel's algorithm the results are quite convincing.
The idea is straightforward. We drop a particle somewhere on the 2D plane and move it down until its position is stable. "Stable" means that particle cannot slip down anymore. It can if any of the neighbours is lower. The position from which the particle should be dropped can be chosen either randomly or according to some model (I'll talk about it later). Avoiding pure randomness gives us more control of the terrain characteristics and appearance.
Also Schankel proposed to search only adjacent positions when testing particle stability whereas Hayes suggested that search radius should be expanded. Thus having radius uniformly distributed from 1 to n we can easily achieve erosion. If we set it to 2 for instance if the adjacent positions are the same we still have to check ones being 2 units away. Using constant (eg. always 1, 2 or 3) search radius results in that the greater this value is, the more gentle are the hills. Another parameter of the algorithm which should be made controllable is elevation threshold, i.e. condition telling when the particle is in stable position. Normally it is set to 1 meaning that whenever there is lower position (difference in heights is 1 unit) available amongst closest neigbours, we have to move our particle down. But there is no limit in setting it to 2, 3, 4, ... or some random value. If we set this parameter to 2, the particle will go down only if the neighbour is 2 units lower. However, by randomizing it during algorithm execution we can have steep slopes and gentle hills - all at the same time!
Hayes suggests using noise function (2- or 3-dimensional) for obtaining these parameters. However, in my opinion even standard rand() will do its job for most of the uses.
By using clever way of choosing places at which to drop particles we can now achieve different landscapes forms ranging from volcanoes (with caldera and such), mountain ridges, dunes, trenches and others. Schankel proposed random distribution of particle-placers around the map. This way, however, only volcanic formations are possible to achieve (Fiji and such).
Underneath there are descriptions of some of the methods.
Volcano
First we have to choose the location of main volcano vent. Then we specify the number of lava streams, their length and direction. This is because in nature lava doesn't go in all directions, it forms something similar to river streams which flow from the crater downwards. Of course as rivers they change their flow from time to time and that problem also has to be addressed - we'll do that by randomizing streams directions a bit.
For each of the streams
Start at the volcano vent
While current length < stream length
Go along the stream direction and randomly modify this direction a bit.
Drop a particle
Move particle down till it's stabilized
Change height value at the final position
Repeat this process several times to achieve volcano of specified height.
Creating crater is very simple. If the height at a given point is greater than height at which crater begins flip it in regard to this height.
Mountain ridges
Mountains in nature have strong peaks. But there are also valleys and cliffs. Creating mountains requires additional step to be performed in the preprocess stage i.e. brownian tree creation. 2D brownian tree in short is a fractal generated following these steps:
Fill whole array to 0
Randomly choose a point from this array and set its value to 1 (it'll be our seed)
Let i = 0
While i < number of iterations
Randomly choose a point from this array
found = false
while found = false
Randomly move a point into one of the adjacent positions
if current point position is adjacent to the point being 1
found = true
Change value at current position to 1
A sample small brownian tree is presented here (I inversed the colours though):
The result can be then used in the mountains generation. For all of the array positions which are equal 1, we simply drop a particle on the corresponding point of the height-map. We repeat it several times and have beautiful and realistic mountains!
Trenches, canyons, cliffs
We do everything as for the mountains. Only in the last step we inverse the colours. For example if the resulting height was 1 (i.e. the greatest possible value) the result would be 0. For 0 - 1. For 0.25 - 0.75 and so on.
