One of my goals for this blog is to have almost everything written in such a way that non-programmers can understand it. If I make especially technical posts, I will probably put them under their own category and not have them be essential reading in order to comprehend the project’s components or the project as a whole.
With that said, the basic starting point of procedurally generating a world via a computer program is create the world map, starting with terrain. To do this, it makes sense to use some type of random noise. Noise is not hard to find. The static you hear on the radio is noise. The “snow” you saw on analog TV sets was noise. In computer graphics, noise is very easy to generate. For example, here’s a sample of noise created with one of the filters in GIMP:
By itself, this type of noise is not very useful for creating things like terrains, which have great variations in elevation but nevertheless have structure, instead of appearing completely random. To get something more suitable for terrain, we must turn to fractals. Fractals offer multiple advantages:
* Large-scale structures that give definition to our generated terrain. * Seemingly random variations that allow for easy creation of virtually endless unique terrains. * Based on mathematical formulas, so if you "zoom in" on a fractal terrain, you can find ever finer details in the terrain.
The last point is particularly interesting since it strongly corresponds to how terrain works in real life. For instance, a difficult problem is measuring the exact length of a land mass’ coastline. Putting aside the rise and fall of tides, coastlines demonstrate fractal-like complexity as you measure them in smaller and smaller units. Famed mathematician Benoît B. Mandelbrot wrote a fascinating paper on this very subject.
Fortunately, SagaSim doesn’t need coastlines defined with molecular granularity, so I’m off the hook on that one!
While there are many ways to generate fractal noise, a very common one is the perlin algorithm, named after Ken Perlin, who created the original algorithm for the movie Tron. My algorithm is based on this version by Mr. Perlin. As an aside, in case you’re not familiar with methods for generating terrain, when presented as an image, lightness indicates elevation. Black is the lowest elevation, while white is the highest.
Without going into a lot of mathematical detail, there are a few basic inputs to a perlin algorithm: persistence, octaves, and lacunarity. Persistence indicates the “amplitude” or intensity of the noise. A high persistence means that the basic features of the noise will remain more “static” than they would if you used a lower persistence. Octaves indicate the “frequency” of the noise. Essentially, octaves work by adding the mathematical output of the noise function to itself–the same way that adding two identical sound frequencies together produces a tone that’s one octave higher. Finally, there is lacunarity, which can also be considered a “smoothness” value. This produces large-scale structures in the noise by layering zoomed-in versions of the noise on top of itself. If you didn’t understand any of that, you’re not alone. Let’s illustrate with pictures!
Here is the base case: persistence of 1.0, 1 octave, 1 lacunarity.
Pretty boring, huh? Let’s bring down the persistence a bit, to 0.3:
Notice that it has higher peaks, because the perlin function is less constrained by the persistence of the original fractal. Next, let’s add a few octaves. We can start with 4:
You can now see that there’s a lot more variation, but also that the structures are pretty much evenly distributed. No matter how much you turn up the octave count, it’s just going to make the noise fuzzier while not bringing out any large-scale features. For that, we need to tweak lacunarity! Let’s turn it up to 4:
At this point we really start to see larger structures come out, such as the deep valleys near the upper left and around the bottom, and the high peaks near the lower right. Things get more intense if we turn the lacunarity up to, say, 8:
You can see that now we have one prominent streak of higher elevations cutting from the right side down to the bottom left, and much lower elevations centered to the bottom right.
Finally, let’s go up to a lacunarity of 16. I normally wouldn’t do this because it tends to create one big “land mass,” but for illustration’s sake, here it is:
That didn’t turn out too badly, but you can likely see how there actually seems to be less variation in elevations–the lower elevations are crowded out by the higher ones, due to layering zoomed-in versions of the basic noise on top of itself so many times. In the actual SagaSim code, I find that using a lacunarity of 8 normally produces the best results.
Finally, since SagaSim is meant to be a world simulator, I had to decide how to handle “wrapping.” After all, you can circumnavigate the Earth, so why shouldn’t the intelligent life forms inhabiting a SagaSim world be able to do the same? To that end, I settled on having a “cylindrical” world map. The left and right sides of the map are analyzed, and I essentially “wrap” them onto each other, gradually fading out. This allows the map to look seamless so that land masses on either side don’t just suddenly “end” at the edge of the map. Incidentally, this also gives me maps that can be seamless wrapped around 3D spheres (something you can also do with GIMP):
By “seamless,” of course, I mean “the poles look like pinched crap.” No offense to any Poles in the audience.
Next time, I will talk about how these noise maps are turned into land masses, oceans, and such. You now probably know more about perlin noise than you ever wanted (or you’re more confused than ever.)
* [Perlin Noise](http://freespace.virgin.net/hugo.elias/models/m_perlin.htm)