Upload new Attachment "textured.jpg"

While working on a project recently, I found myself needing a nice hilly island terrain to use as a playing field. It needed to be fairly smooth, but with some tall interesting hills and fairly broad valleys. I looked up some algorithms, but most of what I found looked too sharp and craggy. Playing around with variations of another method, I came up with the algorithm I explain below. I think it produces some very nice terrain with smooth slopes and interesting features, as well as being very easy to modify to automatically generate islands. It also has the nice feature of using no square roots or trig functions, so it is fairly fast.

This tutorial explains how generate terriains using heightmaps and the hills algorithm I came up with to create these heightmaps. It does not explain how to draw a terrain in 3d; there are other far better tutorials out there for that. At the end of the tutorial, I have included a complete C++ class that will generate terrains of any given size using this algorithm. Feel free to use it, modify it, or whatever, but if you do use the algorithm, please let me know.

Let's begin by establishing some basics. The standard way of creating 3d terrains is through the use of heightmaps. A heightmap is simply a 2d array of values. Each value in the array represents the height of the terrain at that value's position. For example, if the cell at (2, 3) has a value of 5, then the terrain contains the point (2, 3, 5 ). To render a heightmap in three dimensions you create a mesh by iterating through the two indices of the array and set the height at each vertex to the value of the heightmap at that point. Typically, I use the X and Y axes for the two indices, and the Z axis for the height of the terrain, but any orientation will work.

Upload new Attachment "heightmap.gif" The table on the left shows the cells of the height map and the values at each cell. On the right is shown a wireframe view of the terrain generated by that map.

Another way to picture a heightmap is to think of it as a grayscale image, where the brightness of each pixel corresponds to the height of the terrain at that point. In this manner, dark regions on the image represent valleys and lighter regions represent peaks. For example:

Upload new Attachment "map.jpg" The heightmap on the left generates the terrain on the right. As you can see, the black on the image becomes the low area of the terrain while the brighter letters stand out as mountains.

Now that we understand how to generate terrains from heightmaps, the next step is coming up with an algorithm to generate this heightmap. There are a bunch out there already, each with it's own appearance and characteristics. For some examples (including some similar to this one) check out this and this. The algorithm shown next is a little different.

The hill algorithm is a simple iterated algorithm with a few parameters that can be varied to change the characteristics of the terrain. The basic idea is simple:

1. Start with a flat terrain (initialize all height values to zero).
2. Pick a random point on or near the terrain, and a random radius between some predetermined minimum and maximum. Carefully choosing this min and max will make a terrain rough and rocky or smooth and rolling.
3. Raise a hill on the terrain centered at the point, having the given radius.
4. Go back to step 2, and repeat as many times as necessary. The number of iterations chosen will affect the appearance of the terrain.
5. Normalize the terrain.
6. Flatten out the valleys.
   
   

Steps 1, 2, and 4 are obvious, and 5 and 6 will be covered on the next two pages. Now let's take care of step 3. What do I mean by "raise a hill"? Simple. A hill is kind of a rounded hump shape. The bigger the radius is, the taller the hill gets. Mathematically, it is a parabola revolved around the centerpoint, which reaches zero at the radius. To be even more specific, given a centerpoint (x1, y1) and a radius r, the height of the hill at the point (x2, y2) is equivalent to:

Upload new Attachment "equation.gif"

This is convenient because it avoids using any costly square roots or trig functions, but what does it look like? The next illustration shows what one hill looks like in isolation.

Upload new Attachment "1-norm.jpg"

A terrain with just one hill, right it in the middle. The radius can be seen as the circle where the hill meets the ground.

To generate a complete terrain, then, we need to repeatedly add a number of hills. Two things must be kept in mind when we're doing this. First, we ignore negative height values. The equation shown above will yield a negative result if the point being calculated is farther from the centerpoint than the radius. When this happens, we ignore it. Second, two hills overlap, we add their heights to each other. This gives nice amorphous lumps instead of obvious perfectly round bumps. The following images show a terrain being gradually built up as more and more hills are added.

Upload new Attachment "iterations.jpg"

Now that we have our raw terrain generated, let's see what we can do with it to make it more usable.

One facet of the terrain algorithm we are using is that it does not automatically clamp height values into some numeric range. This means that after generating, our lowest valley could be above zero, and the highest mountain could be anywhere. This makes things a bit difficult. Ideally, the height values would range from zero to one, so that we can scale the entire terrain to make it as tall as we want without affecting anything else. To do this, we need to normalize the terrain.

Normalizing is a simple mathematical process of getting values in some range, and mapping them to another range. Graphically, it looks some like this:

Upload new Attachment "normalize.gif"

The graph on the left shows a curve which has not been normalized. Its values fit the range (1.0, 4.0). After normalization, you can see that the curve has been smoothly scaled to fit the range (0.0, 1.0).

To do this to our terrain, we simply scan through all of our height values, keeping track of the lowest and highest ones found. Once we know this minimum and maximum, we scan through the heightmap again, this time normalizing each height from the range (minimum, maximum) to the range (0, 1). The equation to do that looks like this:

Upload new Attachment "normal_equation.gif"

Now, we know that the lowest point in our terrain will always be zero, and the highest peak will always be one. This will come in handy later.

The terrain we just created looks pretty nice, but there is not much in the way of flat valleys on it. If this is what you are looking for, then you can be done now. However, it might be nice to have some more lowlands. What we need is a way to flatten out the terrain some without flatten out the mountains. Since we have already normalized our heightmap to the range (0, 1), a simple way to broaden the low areas is to square each height value. This will effectively lower the midrange height values without affecting the maxima too much. Graphically, it maps something like this:

Upload new Attachment "flatten.gif"

The next image shows how flattening affects a generated terrain.

Upload new Attachment "flatten_terrains.jpg"

The terrain on the left has not been flattened. The terrain on the right has been flattened by a power of two.

If even more flattening is needed, you can raise the height values to even higher powers. On the next page, we'll learn a simple modification to the algorithm to generate islands.

The algorithm as it has been presented so far works well for generating terrains that run all the way to the edge of the height map. In many cases, this may be what we want. However, if you find yourself needing islands, where the heightmap tends towards zero at the edges, there is a simple modification we can make to the algorithm.

As we saw, step 2 involves choosing a random centerpoint for a hill. Normally, this is chosen to be anywhere on the heightmap, evenly distributed. What we want now is to have our hills clustered towards the middle of the heightmap. To do this, we need two random values, call them distance and theta. The distance will be how far from the center of the heightmap our hill will be placed. It can range from zero (right in the middle) to half the size of the heightmap minus the radius of the hill. This will prevent hills from reaching the edge of the heightmap. Theta determines in which direction from the center the hill be placed. It ranges from 0 to two pi. From these two values, we can then calculate the x and y coordinates for the centerpoint of the hill and proceed as usual with the algorithm. So, to generate centerpoints for hills using the island modification, we use the following equations:

Upload new Attachment "island_equation.gif"

Note that the maximum radius for a hill should be less than half of the size of the heightmap.

Using this, we can add as many hills as we want, and still be sure that the outer edge of the heightmap will reach zero. It looks something like this:

Upload new Attachment "island_dry.jpg"

Note that when we run the flattening step on the island, it ends up shrinking the coastline pretty significantly. If using islands, you might want to avoid flattening.

By adding a water plane at a height slightly above zero, we get something like this:

Upload new Attachment "island_wet.jpg"

Here you can clearly see the coastline. For a more irregular coastline, try decreasing the maximum hill size and/or lowering the number of hills.

That's about it. I hope this has been interesting and useful to you. As you can see, the algorithm is pretty straightforward. Finally, on to the code itself.

I've written a complete C++ class you can use to generate terrains using the described algorithm. The class takes care of managing the heightmap memory for you as well. It does not perform any rendering; it only creates and generates the heightmaps. It has parameters to allow you to set the size of the heightmap, the range of hill sizes, the number of hills, whether or not to generate and island, the amount of flattening, and the random seed used. To use it, all you need to do is this:

#include "rfHillTerrain.h"

using namespace RobotFrog; // the class is in this namespace

int main( void )
{
    HillTerrain terrain(); // you can also specify terrain params here
    terrain.Generate();
        
    for( int x = 0; x < terrain.GetSize(); ++x )
    {
        for( int y = 0; y < terrain.GetSize(); ++y )
        {
            float z = terrain.GetCell( x, y );
            // do whatever with the z values here to draw your terrain
        }
    }
}

The constructor has parameters for all of the variables affecting the algorithm. In addition, you can also change the parameters on an existing terrain and regenerate it. The terrain also stores the random seed it uses to generate itself so that you can create the same terrain when you need to.

The code has been tested and it runs fine on MacOS and Windows. It should theoretically run without problems on any platform that has <math.h> for sin() and cos(), <stdlib.h> for rand() and srand(), <assert.h> for assert(), and <new.h> for std::bad_alloc. The class is put inside the namespace RobotFrog, so you will need to either specify the namespace when using it, or just import it. The constructor also throws an exception if it can't allocate enough memory, so you will need to enable exception handling.

The class was not designed to be inherited, but if you felt like implementing other algorithms using it as a base, it should be fairly easy to modify. Basically, you would need to make Generate() virtual, and then override it.

The two links below download the class in either .sit or .zip format. This includes only the class files, you'll have to write your own main().

Upload new Attachment "HillTerrain.zip"

이 코드는 MIT 라이센스 하에 있다. 이것은 기본적으로 나에게 책임을 지우는 것을 제외하고 무엇이든지 해도 좋다는 의미가 된다. 여러분이 여러분의 개인 혹은 상업용 게임에 이것을 사용하는 것을 원한다면, 무료라고 생각하기 바란다. 사용하고 싶은데로 사용하기 바란다. 내 개인적인 만족을 위해서 이것의 사용여부를 내게 알려준다면 나는 매우 기쁘게 생각할 것이다.

번역중