Monday, October 24, 2016

Making Mountains Out of Molehills, I Mean Out of Noise

The base terrain in my map generator is created with low-frequency noise.  This gives a rolling landscape which looks natural (if a bit uninteresting):

To make the map more dramatic and (hopefully) more interesting, I'd like to add some more distinctive terrain features, such as mountains.

A common way to model mountains is to use higher-frequency (more "peaky") noise.  Overlaying several multiples of higher frequency noise (i.e., octaves)  produces something that looks like this:
I don't know how this compares to real mountains, but it looks pretty realistic to my eye.   The psuedo-code for this looks something like this:

// Combine 6 octaves of noise with a 50% fall off
height[x,y] = Noise.octave(x*4,y*4,6,0.5);


Note that I'm multiplying the (x,y) coordinates by 4 when passing them into the noise function.  This is a handy trick for starting your octaves at a higher frequency.  Each doubling of the coordinates effectively shifts the noise up one octave.  So in this case, I'm skipping the lowest two frequencies of noise.  The frequency is related to the scale of your coordinate system, so you'll have to experiment with the starting frequency, number of octaves, and fall off to find a combination that looks good to you.

Some people prefer mountains with sharper peaks.  This can be generated by replacing the vanilla noise function with "ridged multi-fractal" noise:
You can see this produces mountains with sharper peaks.

There isn't a lot of good description of ridged multifractal noise on the Internet, but it turns out to be a fairly simple concept.  Recall that Perlin noise produces numbers that from -1 to 1.  Noise is specifically designed to be smooth -- if you plot out the noise you'll find that there are no abrupt changes of values in any direction.  Since sharp peaks are an abrupt change of value (the mountain goes steeply upward on one side of the peak, and then steeply downward on the other side), it's difficult to get sharp peaks out of noise.  Musgrave [citation required] suggested applying the absolute() function to Perlin noise to get a noise that changes directions sharply at zero.  Since we want our peaks to be at 1 rather than zero, we have to also flip the noise over.  In pseudo-code that looks like this:

// Ridged noise
height[x,y] = 1 - Math.abs(Noise.noise(x*4,y*4));


(Note that I'm again applying the trick to get higher-frequency noise.)  Ridged multifractal noise is just doing this same thing with noise octaves.  I'm not sure whether Musgrave applied the absolute value transformation to the individual noise being summed into the octave, or to the entire octave.  I chose the latter, and I think it looks fine.  The pseudo-code looks like this:

// Combine 6 octaves of ridged noise with a 50% fall off
height[x,y] = 1 - Math.abs(Noise.octave(x*4,y*4,6,0.5));


Another way to create "peakier" mountains is to use the square root of the noise:
To my eye, these are very peaky; maybe too much so.  Martin O'Leary's original map generator made use of this approach.

Once you've decided on an approach that generates mountains you like, how do you add them to the map?  Making it the base terrain over the whole map is not a great idea:
As I suggested earlier, I really want an "interesting" map that isn't dominated by any one characteristic but presents a mix of terrains.  Ideally,
1. Mountains should cover a reasonable percentage of the map.
2. Mountains should merge realistically into the neighboring terrains.
3. The distribution of the mountains should be a reasonable pattern.
The first criteria is fairly simple to achieve:  Select what percentage of the map should be mountains and generate that many mountains.  The second criteria is also not difficult:  The edges of mountain areas should get progressively lower until they match the surrounding terrain.  We can do this by multiplying the mountain height by a steadily diminishing value (a gradient mask).  The third criteria is a little more difficult.

For example, we can't simply throw mountains randomly on the map until we've met our percentage of mountain terrain.  The mountains will be scattered around the map and make no sense.

We can use noise to get a more natural clumping of the mountains.  The basic idea is to use the noise as a mask.  Generate noise from 0 to 1 at every location on the map.  Find a threshold number T such that the locations with noise > T comprise the mountain percentage of the map (to meet criteria #1).  This will give us natural-looking clumps of mountains.  To meet criteria #2, we can extend the mountains to a second threshold T', but between T and T' we'll fade out the mountains.  In psuedo-code:

// Create the mountain mask.  Changing the frequency of the
// noise here can create different kinds of clumps
for each location "loc" on the map:
noise[loc] = Noise.noise(x,y);
// Find the two thresholds
T = findThreshold(noise, mountainPercentage);
T2 = findThreshold(noise, hillPercentage);
// Put down the mountains/hills
for each location "loc" on the map:
if noise[loc] > T2 then
// Use whichever mountain algorithm you like here
rawHeight = Noise.noise(x*4,y*4);
actualHeight = rawHeight * Math.min(1, (noise[loc]-T2)/(T-T2));
// And add it to the terrain
height[loc] += actualHeight;

The examples used in this posting have all used this algorithm.  You can look back at them and examine the clumping and the way they fade into the terrain.  This is generally a pretty good approach, but since it locates the mountains without any regard to the existing terrain, it can create odd placements, such as mountains in the lowest parts of the terrain:

If you don't like the semi-random placement from using a noise mask, and already have a base terrain, an approach that yields reasonable (if somewhat boring) placement is to locate the mountains on the highest parts of the existing terrain.  And again, you can use thresholding to fade the mountains into the surrounding terrain:
On the other hand, if you're producing top-down maps as I am, all this may be overkill.  Maybe you just need to decide where mountains go and mark that on the map.  For example, here's a mountain placement that looks pretty realistic:

But when you turn that into a top-down, 2D map it is difficult to even see where the mountains are:
Partly this is "just" a display problem -- the map needs a better visualization of the mountains.  But it's also true that for this sort of map, you don't need a detailed, hyper-realistic heightmap of the mountain areas.