Terrain Generation Tutorial: Hill Algorithm

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.

One Hill

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:

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.

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.

Multiple Hills

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.

The terrain as the number of hills increases. By 200 iterations, individual
hills cannot be made out, and the terrain looks organic.

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

Copyright © 1999-2002 Bob Nystrom.