Mountains from Pixels, Rain from Math

With terrain generation done, along with the segregation of land and water, we can move on to more complex matters. Here’s where things become more subjective and creative. What terrain types are necessary? How do we handle climate?

I decided to start with basic terrain types contingent on elevation. At the lowest level is water, which isn’t really a “terrain,” but it’s there for the sake of making the terrain map look sensible. Who wants to look at a black ocean, seriously? Yes, it really is that simple a decision.

The various terrain types are based strictly on elevation. Further nuances are defined later by climate and biomes. The elevation scale is in shades of gray, from 0 to 255, with 0 as water. The rest are:

  • Wetlands (shades 1-5)
  • Floodplains (6-25)
  • Plains (26-75)
  • Foothills (76-125)
  • Highlands (126-170)
  • Mountains (171-255)

I’ll admit those numbers are rather arbitrary, but they result in a reasonable terrain distribution. Here’s an example:

terrain map

Example of a colored terrain map.

terrain color legend

Terrain Types

As you can see, the whole gamut of terrains is covered.

The terrain definitions, like many features of SagaSim, are parameterized and customizable. It will therefore be possible for people to tweak the terrain definitions and do fairly wacky things, if they’re so inclined.

Next up is climate! In SagaSim, climate is a function of two things: elevation and latitude. Rather than completely reinvent the wheel here, I decided to make use of the Köppen climate classification system. SagaSim’s version is rather simplified, though I’ve left the door open to make it more realistic in the future. For now, the idea is to just have SagaSim generate climate zones for the world map so the later generation steps can be carried out.

The climate system is also parameterized. I’ve currently defined 14 different climates, as based on the Köppen system:

  • Af
  • Am
  • Aw
  • BWh
  • BSh
  • Csa
  • Cfa
  • Cfb
  • Cfc
  • Dfa
  • Dfb
  • Dfc
  • Dfd
  • EF

Each climate has four parameters: its minimum base latitude, its maximum base latitude, whether it’s considered a rainy climate (a simple true/false value), and the color to use for it on the map (same colors as those in the Wikipedia article.) I say the latitudes are “base” latitudes because the climate generation algorithm doesn’t have to precisely respect them. Instead, there is a fair amount of variation allowed.

Climate generation is done by making multiple passes over the map. On the first pass, there is no existing climate information, so the algorithm starts from scratch. On each land pixel, it looks at the 8 surrounding pixels to see what climate times are immediately adjacent. It also determines which climates are possible at the current pixel, based on latitude. Then, a probability is calculated to determine whether to choose an adjacent climate type or a new one. It is heavily weighted toward picking an adjacent type. The formula is:

1 - (1 / (height * width * 0.25)

This will normally generate a very small number, roughly 1% on most maps. Then a random decimal is chosen. If it falls below the probability threshold, then we will pick a new climate from the available types, rather than an adjacent one.

This is done for every land pixel on the map, starting at the top left and working our way toward the bottom right. Next, we do a few more passes, doing a very similar calculation: for a given pixel, look at the surrounding pixels and choose one at random to assign to this pixel if we meet the probability threshold (about 5% in subsequent passes.)

At the end of the process, we have something like this:

climate map

Example climate map.

The “banding” effect is a consequence of the latitude restrictions and the probability checks. This allows for substantial climate variation without having climate zones go too far out of their assigned latitudinal ranges.

One shortcoming of the current climate generator is that, unlike the perlin noise generator, it does not produce a seamless map. If you were to wrap the above image around a sphere, it would be discontinuous at the left and right edges of the map–the climate zones wouldn’t line up. I intend to fix that, though I’ve not yet gotten around to it.

It might seem like we haven’t done much so far, but it’s all a means to an end. Next time, I’ll get into how rivers and biomes are generated. They’re more complicated than (and dependent on) terrain and climate, so they may get split into two articles.

Water & Earth

Thus far, I’ve explained the basic premise of SagaSim and described how to generate a basic landscape through fractal noise. Now, it’s time to put that noise to work and create land masses!

One of the input parameters to the world generator is “water percentage.” Maybe you want a world that’s like Earth, where roughly 70% of the surface is covered by water. Maybe you want much more land, so you go down to 50%. Maybe you want no ocean at all, so you put in 0%. There is no point in putting in 100%, though, since it means no biomes or climate data would be generated (sorry.) Anyway, let’s start with 70%. I’m generating a larger map this time, so you can really see the features of the landscape.

basic noise map

Perlin noise before any additional processing.

Where does the land end and the water begin? You can’t tell from this map. Instead, I have an algorithm that “normalizes” the map. What it does is go through each pixel, put it in an array (a list), and then it slices the array at whatever point you entered as your water percentage. So, if you chose 70% and had an image that’s 10,000 pixels in total (100×100), the value of the pixel at index 7000 would represent our new “base” color. All pixels below that will be turned to black, then all the pixels above index 7000 get adjusted. Since the sea level value will likely be some shade of gray, and we’re turning it into black, we therefore need to tweak all the lighter-colored pixels so that they now start just one shade above black. In computer graphics parlance, this is known as “stretching the histogram.” Let’s see what the map looks like after this processing has been done:

normalized noise map

Map after normalizing the sea level.

Now, the locations of land masses are much clearer. But the world generator takes one more step to make clear the distinction between ocean and land: it creates a “mask” where all land is white, and all water is black. That way, it’s never ambiguous as to whether a given pixel is meant to be land or ocean. (Rivers are another story, and will be covered in a future post.)

water mask

Map converted to water mask. White is land, black is water.

Much clearer, isn’t it? You can also see that there are five distinct continents, as well as some smaller islands. Here are a few more water masks to illustrate the variety of landforms you can get just by tweaking some of the world generation parameters:

water mask example

Water mask generated from 0.2 persistence, 4 octaves, lacunarity of 8, 70% water coverage.

water mask example

Water mask generated from 0.8 persistence, 8 octaves, lacunarity of 2, 30% water coverage.

water mask example

Water mask generated from 0.2 persistence, 4 octaves, lacunarity of 16, 50% water coverage.

As you can see, there’s plenty of variety to be had by messing with the world generation parameters.

So, now we’ve got our land and oceans set up. Next time, we move on to terrain and climate!

Make Some Noise

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:

sample noise

A sample of noise generated from within 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.

basic noise

Basic noise: persistence of 1.0, 1 octave, 1 lacunarity.

Pretty boring, huh? Let’s bring down the persistence a bit, to 0.3:

noise with 0.3 persistence

Less persistent noise: 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:

noise with 4 octaves

Noise with multiple octaves: 0.3 persistence, 4 octaves, 1 lacunarity.

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:

noise with lacunarity 4

Noise with lacunarity: persistence 0.3, 4 octaves, lacunarity of 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:

noise with lacunarity of 8

Noise with more lacunarity: persistence 0.3, 4 octaves, lacunarity of 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:

noise with lacunarity of 16

Even higher lacunarity: 0.3 persistence, 4 octaves, lacunarity of 16.

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):

noise mapped to a sphere

Noise mapped to a 3D sphere.

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.)

Further reading:

Welcome to the SagaSim development blog!

I’m bad at introductions, so I’ll just get to the point. This is a blog about the development of SagaSim, which might best be described as a “world simulator.” It is currently under active development, and all the features aren’t even planned yet. I’m just working my way through it, one step at a time. Maybe it will be successful, maybe it won’t, but it’s already been quite a learning experience.

So far, the following major features are planned:

  • Procedural generation of world, including terrain, rivers, climate zones, and biomes.
  • Dynamic generation of plant and animal species with unique DNA (over 16 million possible combinations.)
  • Dynamic generation of intelligent, civilized life forms.
  • Simulation of resources, civilizations, important individuals, economies, politics, historical events, disasters, technological development, sociology, etc.
  • Virtually all features can be controlled by the user.

Given that description, it would be better to categorize SagaSim as a sandbox than as a game. There is no way to “win,” the point is to explore the options and watch your world develop and evolve. Everything is displayed using simple 2D graphics, though I don’t discount the possibility of a 3D view at some point.

As of this posting, I have the world generation (mostly) done, and I’m about 1/3 of the way through defining the DNA system. Future posts will delve into detail about exactly how all of this works, so stick around!

For those who are interested in the basic technical details of SagaSim, my platform is Python 2.6 with Pygame, psyco, and NumPy. It is only limited to Python 2.6 because of psyco, though if PyPy ends up fully supporting Pygame and NumPy I will probably transition to that.

I’m still on the fence about what to do with the source code, and whether I should try to raise money to help fund development. I’ll certainly entertain suggestions, though.

Feel free to post any questions, comments, or encouragement!