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:
- Start with a flat terrain (initialize all height values to zero).
- 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.
- Raise a hill on the terrain centered at the point, having the given
- Go back to step 2, and repeat as many times as necessary. The number
of iterations chosen will affect the appearance of the terrain.
- Normalize the terrain.
- 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:
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.
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
Copyright © 1999-2002 Bob Nystrom.