It has been a while since my last post. During that time I was trying to understand terrain generation techniques which I  will describe in this blogpost. It is the most interesting part that I've learned during the game development.

Main objective
The main goal is to advance from Transport Tycoon style map on first picture to map style which  you can see on the second picture.

transport tycoon style	new style

The big question is: "How to achieve it?" Well there are several options how to do that. However, I didn't want to do a lot of handwork. So instead tile based map as I was trying to use this in the first Map Editor I was looking for something more cool.

I have found two options based on TRN (triangular regular network) or TIN (triangulated irregular network) I've chosen TRN that is using height map as data structure. However there are some limitation by definition (heightmap is function ) that means only one value for each map coordinate pair which is a problem for some objects in nature such as caves.

Generation techniques
The first issue I had facing was heightmap generation. There are several ways to do that. The first and easier one is to generate it in 3rd party application e.g a well known Gimp application should be used for that or you can use Terragen or similar program. This could solve the problem well, however this wasn't enough for me and because I am very interested in this topic I've decided to generate the terrain dynamically in the game with hope that I would be able to generate random map in multiplayer game.

I will show you how to generate a heightmap using Gimp or another graphic program at first. Then I will describe how I did it algorithmically.

The heightmap could be represented as two dimensional array of values that specifies the height of a field. Let's say that you have 256x256 game map then you have to store 65536 height values. The easiest way is the to use grayscaled bitmap that allows you to use 0-255 values for each field (pixel). This should be enough for most purposes, anyway you can use RGB or RGBA for storing another information. The code for loading the bitmap into heightmap array is very easy using SDL library.

So how to generate a heigtmap in Gimp?

The first step is to create a new grayscale image.

Then you can experiment using paintbrush or generate a random heightmap using filters. You can generate quite good heightmap using solid noise filter (Filters->Render->Clouds->Solid noise).

The rendered terrain mesh could look like this one:

You can see example of manually created height map on image bellow (created using paintbrush and blur filter).

As I wrote before the code for loading heightmap using SDL is very easy:

[codesyntax lang="cpp"]

bool Map::loadFromFile(const char* path) {
	SDL_Surface * sf = SDL_LoadBMP(path);
	if (sf) {
		_height = sf->h;
		_width = sf->w;

		if (_heightMap != nullptr) {
			delete [] _heightMap;
			_heightMap = new unsigned char[_width * _height];
		}

		// grayscale check
		if (sf->format->BitsPerPixel == 8) {
			unsigned char * data = (unsigned char *) sf->pixels;
			memset(_heightMap, data, _width * _height);
			SDL_FreeSurface(sf);
			return true;
		}
	}
	return false;
}

[/codesyntax]

It is possible to do static maps for whole game but as I wrote I am interested in dynamic terrain generation in the game. I believe that I will save some time and resources.

Requirements
It is a good practice to define expectations about output. I am expecting some flat area for buildings in player base, there should be hills on map that make access to enemy base more difficult and also it would be weird to have a mine in a flat area. However, units must be able to access to the enemy base (There should be always one path at least).

Generation
I've studied this topic for last few months and I will try to summarize my understanding here.

They are several methods to generate terrain. Most of methods that I mention are based on generating noise. Terrain likes noise with spectral density or .

This topic is also related with fractals and procedural content generation. I would recommend you to read Texturing and modeling procedural approach, Realtime Procedural Terrain Generation paper by Jacob Olsen which were the best sources for me.

If you are not a mathematician then a knowledge of fractal geometry is not necessary to generate terrain. So if you don't want to confuse yourself as I did don't start with this theory :-). The important thing which and how the input variables of different algorithms change the output terrain.  The first thing is to generate base terrain then you usualy do post processing such as erosion simulation, etc and for best result it is good to experiment and combine multiple approaches.

Base terrain algorithms
I have tried Fault formation, Diamond square, Value noise, Fast Fourier Transformation terrain and Voronoi diagrams.

Fault formation was the first algorithm that I used. It is really simply but it needs post processing because the terrain don't look real. You can find quite good description on Lighthouse 3D webpages.

Diamond square algorithm looks like one of the most popular algorithm for generating terrain over the internet. I have been fighting with him a lot of my time. I've tried few implementations found over the internet or books. I realized that for purpose of my game the algorithm can't be use separately.

You can seen two images of terrain generated by diamond square bellow.

Fast Fourier Transformation terrain generation is an algorithm where you generate (pseudo)random height map (white noise). Then you use Fast Fourier Transformation algorithm to transform the noise into frequency domain and using appropriate filter you remove the "ugly" frequencies. Then you transform it back and yes you have a nice terrain. It looks quite good and eroded. You can read more about it in this article.

Value noise algorithm generates the 'right' noise for terrain and it is well described in one great source of information that is fractal terrain generation project (there are also described other methods to generate terrain that I don't mention)

Voronoi diagrams is an interesting approach described in J.Olsen's paper. It is used for breaking regularity. If you follow the instructions described in the paper the rendered terrain may look like that on the image bellow. As you can see it needs some post processing.

Post processing
One of the post processing algorithm could be erosion simulation. I've used algorithms described in Jacob Olsen's paper. The erosion simulation is suitable for terrain that is too much sharp or unrealistic. For example Fault formation.

Another "post-processing" is to set ground level, that means all height values bellow your specified value is rendered as flat. There might be a question which base level to chose, well I've tried base level computed as median of whole height map and it seemed to work well.

Measuring requirements
One of the problem in dynamic terrain generation is that you have to confirm that the generated terrain meets your requirements. I have read about  two ways:

1) You have proof for that the generation process will meet it.
2) You have indicator variables and you are generating until you the correct values of variables are computed.

There is some work needed in this area but I suppose that I will try to use combination of faith for 1) and  some indicators just for sure.

Usability
For the purpose of my game I will probably use a combination of mentioned algorithms and some little hand work to meet requirements especially in single player missions. Maybe I can use some predefined seeds for random generator to achieve results that looks well :).

As you can see on the following two images combining techniques described in this blogpost you can achieve these terrains that can be used in my game..

Conclusion
Well for me it was better practice and experiment rather then trying to understand all theory behind. I found out that if you are not sure if you implemented an algorithm well try first some camera tricks or scale your height map. I will show you on the next images how can the same data look using different camera settings. The other thing is that you could significantly change look of a terrain by modifying random generator used for their generation.

There is one funny story behind that. I was frustrated that I am doing something wrong in terrain generation, however when I was in plane and we were landing to Zurich, Switzerland I looked from the window and I saw fractals and then I got the idea to play with camera..

The last thing is little motivation if the problem seems too huge or complicated on the first look don't give up and try it several times. It is like a puzzle but you have to find the right pieces :)) If you are uncertain if it would work just try it and you will see.

Finally, a height map is generated and mesh is rendered however, it is time to get a real look, so my next work would be focused on terrain texturing.