Friday, October 28, 2016

More Islands

In a previous post I talked about an approach for creating a large central island on a map by creating a circular island and then perturbing the outline of the island using noise to create more interesting shapes:

This works well for large central islands, but it's not a very good approach for creating smaller islands.  In this post I'll discuss some other approaches for creating islands that are better suited to creating incidental islands.

A straightforward and simple approach for creating smaller islands is to pick an initial sea location for the island, make that land, and then add randomly land on the coast of the island until the island is the desired size:

Because you're adding bits of land to the island randomly, there's a chance that you'll get an oddly-shaped island.  The more locations you add to your island, the more likely it will be a blob shape.  If you create an island of 5 locations this way, getting all five in a long row is not that unlikely.  If you create an island of 500 locations it would be very unlikely to get them all in a row.  But you still get some random-looking variations:
If the shapes this produces seem too random, an easy way to get a blobbier shape is to weight the random selection by how many neighboring locations are already island locations.  This will tend to create a more convex island shape.
I don't like this method for producing large islands because they almost always end up as featureless blobs, but it works well to create small islands as accents around a larger island or off a coast:
Another type of island we might like on our map is a cluster of small islands.  This is easy enough to do once we have blob islands working; it's just generating a spray of small blobs around a point:
You could also generate islands along a line to get something that looks like an island chain, but I haven't implemented that yet.

Assuming we're scattering our islands randomly and close enough together, some of them will overlap and form larger islands and create a natural size distribution as well.  Combining blob islands, cluster islands and larger landforms starts to give us some interesting and realistic-looking terrain:
And here's an example with a mountainous central island and some outlying islands:
So far I've talked about how to generate islands, but placing them is also important.  Outlying islands generally look better if they're relatively close to the main land masses.  This connects them visually and looks more natural to our eyes:
And here:
Compare to this example, where the islands in the lower half of the map look unnaturally far away:
You can address this by weighting the placement of these incidental islands so that they're more likely to be near land, or using some more intelligent algorithm.  But that may not be necessary.  Maps tend to be mostly land anyway (since there's not a lot of interest in empty sea), and if there isn't a lot of room in the seas for islands, they'll be forced to be placed near land.  (Indeed, I had to generate quite a number of maps to get the "bad" example above.) 

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);
     // Mask this value
     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.

Sunday, October 16, 2016

Is it Windy in Here?

One of the things I'd like to add to the map generation is realistic biomes -- where grass, forest, desert, etc. naturally occurs on the map.  The biome in a location is largely a function of the amount of water available and the temperature.  This is often illustrated with a Whittaker diagram.


Temperature is pretty straightforward (warmer near the equator and colder near the poles), but the amount of precipitation is more complex.  Martin O'Leary's map generator just has a fixed amount of precipitation at every location.  (It's only used to generate rivers.)  My notion of an interesting map has a variety of biomes, so I wanted something more complex.  I could use noise to create the precipitation pattern, but I also want the map to be plausible.  Using noise could lead to some odd maps: jungle next to deserts, an isolated pocket of heavy rainfall deep in a mountain range, etc.  The human mind is pretty good at rationalizing patterns, but I wanted something a bit more realistic.  I decide to simulate a very simplified rainfall model:  moisture enters the atmosphere by evaporating from the oceans, is blown onto land by the trade winds, and precipitates out where conditions are favorable.

The first step in creating this rainfall model is wind.  Real wind models are of course very complex, but my concern is primarily with how the surface winds are affected by the land geography.  At a very simple level, this is just how the rise and fall of the land changes the direction and speed of the wind.  I experimented with a variety of different approaches, but in the end settled on two simple rules:
  1.  Wind slows down when going uphill and speeds up when going downhill.
  2.  Wind turns away from obstructions.
The simulation of the wind is a flow model.  The wind in a location is represented a vector of the wind force and direction.  At every time step of the model, the wind in every location is propagated forward based upon its direction.  If the new location for the wind is higher, then some of the wind is turned aside while some of the wind continues upward but at less force.  How the wind splits depends upon the steepness and direction of the slope.  Conversely, wind going downward increases in force and turns towards the downward slope.  All the wind entering a location is then summed to get the new wind force and direction for that location.  This repeats until all the wind has propagated across the map and disappears out the edges.

Here is an example of wind interacting with the surface geography:


The red arrows represent the wind vectors at each location.  In this example, the island rises up out of the sea and presents an obstacle to the incoming wind.  The wind splits around the island and the wind that goes over the island is slowed.  The result is a "wind shadow" on the leeward side of the island.  The peninsula has a similar effect and the two features funnel the wind between them.  (Note that there's actually wind everywhere; for display purposes I'm not showing arrows where the wind is very weak.)


Here's a more zoomed out view, showing the wind patterns up a mountainous coast.  The high hills along the sea make it difficult for the wind to reach the interior.  Along the southern part of the coast the fairly steep shore turns the wind northward. It flows up the coast until it enters an inlet, where the land to the north turns it inward. It flows up the inlet until it is forced up the slopes and onto the land. In the upper left you can see how the wind tends to flow up the rills and valleys where the path is easiest. Once upon onto the generally flat land above, the wind starts to spread out.

Tweaking the rules on how slopes affect the wind can lead to stronger and/or more chaotic patterns.


This picture illustrates how the wind can form very distinct and complex patterns.  This map has gentle slopes and a number of large rounded hills. Wind hits the land almost directly, where it gets filtered by the coast into a number of strong streams. These flow inland, generally following the topography, turning, splitting, and rejoining. In places the prevailing wind blows at 90 degrees or more to the original trade wind. Weaker winds (not depicted here) can be quite chaotic, flowing every which way.

I'm generally pleased with the wind model -- it generates complex and plausible results.  The real drawback is that it is fairly slow to run.  Because the wind vectors can split into neighboring locations and because a map based on Voronoi partitions is irregular, it can take thousands of time steps for wind to blow completely across a map with rough terrain.  At the moment, the wind model is the slowest step in the map generation.

Sunday, October 9, 2016

Making Islands

Many of the procedural map generators you'll find on the Internet generate maps of islands, like this example from Red Blob Games:


Islands are nice because they're self-contained, and having all the edges of the map as water avoids problems with land running off the map.  Island maps are also handy for something like a role-playing campaign because they set a natural boundary to the story.  But Martin O'Leary's fantasy map generator creates maps that look like a portion of the coastline of a bigger country, like this early example from my map generator:

These maps look pretty authentic.  But although I like the look of these maps, I also wanted to be able to generate island maps.  But Martin's generator doesn't do islands. So how do you generate an island, anyway?

To start with, you can simply plop a blob down in the middle of the map.


That's certainly an island, but it's a pretty unsatisfying sort of island.  A more interesting island should have a more irregular (but natural-looking) shape, possibly with some outlying pieces.  I don't really care about perfectly simulating the natural processes that lead to islands.  I just want an island shape that is interesting and plausible.  So how can we generate an interesting island?

Let's back up a step.  Before we worry about generating an interesting island, let's consider how we can generate an interesting landscape -- without worrying about whether it is an island.  One common approach is to use noise.  A common technique in procedural generation is to create a heightmap based on a noise function, usually overlayed at several frequencies.  The result is not always entirely plausible, but our brains interpret it as "natural looking":


(That view, by the way, uses the 3-D viewer from this page.   You can play around on that page generating noise-based landscapes.)

Unfortunately, the landscapes generated that way aren't often islands:


A simple way to turn these landscapes into islands is to apply a circular mask to the landscape.  Anything outside the mask is pushed down into the sea. Voila!  An island:



That's a little better -- it's definitely an island, and has some interest within the boundaries of the island -- but the circular outline is too apparent.  A circle just isn't a very interesting island mask, largely because it's so obviously unnatural.  We know how to create an interesting landscape using noise, so our problem is really how to create an interesting island mask.

An initial idea is to make the mask more interesting by pushing the circle inward in some places, and outward in other places, in some sort of natural-looking way:

That's an improvement -- still a blob, but at least more interesting than a perfect circle.  So how can we do this pushing in and out effect?

The approach I took was to create a circular island and then perturb it.  The idea is to randomly move all the pieces of the island around -- to perturb their locations.  In pseudo-code it might look something like this:
for (x = 0; x < mapWidth; x++) {
       for (y = 0; y < mapHeight; y++) {
           if (circularMask(x,y,radius) == true) {
                 // Circular mask says to put some land at
                 // (x,y).  Instead, let's perturb that
                 // location and put land in the perturbed
                 // location instead.
                 x = x + randomOffset();
                 y = y + randomOffset();
                 world[x, y] = land;
           }
       }
    }

Let's try it:


Well, that doesn't look quite right.  The problem is that we're just randomly throwing every bit of the island around the map.  Some of it ends up in the center of the map, but the rest goes every which way.  We want neighboring parts of the island to move together -- so that if one piece of the shore gets pushed out, so do its neighbors.  Instead of moving each piece of the island independently, we want to move pieces that are near each other approximately the same way.

Luckily for us, that's exactly what noise does.  The value of the noise function depends upon the parameters you give it and the value varies smoothly as those parameters change.  If we use our x,y coordinates as the parameters, then nearby points will be similarly perturbed.  So let's revise our code to use noise to perturb the island locations:
    for (x = 0; x < mapWidth; x++) {
       for (y = 0; y < mapHeight; y++) {
           if (circularMask(x,y,radius) == true) {
                 x = x + noise(x,y);
                 y = y + noise(x,y);
                 world[x, y] = land;
           }
       }
    }

Let's try it:
Although this looks much better, there's a (possibly non-obvious) problem.  In the algorithm above, I'm adding the same noise to both the x and the y coordinates.  So points will only be perturbed along a diagonal -- the same distance and direction in both x and y.  To address this, we need to modify the algorithm so that we have separate noise sources for the two dimensions:

    noiseX = new NoiseGenerator();
    noiseY = new NoiseGenerator();
    for (x = 0; x < mapWidth; x++) {
       for (y = 0; y < mapHeight; y++) {
           if (circularMask(x,y,radius) == true) {
                 x = x + noiseX(x,y);
                 y = y + noiseY(x,y);
                 world[x, y] = land;
           }
       }
    }


The cool thing about generating islands this way is that we can create quite a bit of interesting diversity just by tweaking the noise we use to perturb the island.  For example, if we use a low-frequency noise, the perturbations are smooth:
 If we use a high-frequency noise, the perturbations are jagged:
We can also vary the magnitude of the perturbations.  A low frequency perturbation with a stronger magnitude gives us a stretched out blob:
A high frequency perturbation with a stronger magnitude gives us a wildly chaotic coastline:
These two adjustments alone can produce a nice variety of plausible island shapes, but you can imagine other variants.  Adding octaves of noise can create some interesting shapes:
Or you could try adding more noise in one direction than the other:
In these examples so far, the land I've been perturbing has been a flat circle.  More complexity and interest is added when the land being perturbed is more interesting -- when it has been filled in with noise, mountains, etc.

Friday, October 7, 2016

Is It Noisy In Here?

I'm not going to write a detailed explanation of noise and its use in procedural generation.  There's plenty of material on that topic for the interested.  I'll summarize by saying that for procedural generation, truly random numbers don't always work well.  Often it works better to use a random number generator that varies smoothly according to some input parameters, aka "noise".  This idea was famously popularized in 1985 by Ken Perlin when he invented "Perlin noise".  (He won an Academy Award for this work, so don't tell me that computer science isn't glamorous.)  Noise is often illustrated with this sort of "cloud" picture:

Here the dimensions (x, y) are the input parameters, and the noise output is a number from 0 to 1 shown as a shade from black to white.  You can see that the noise (shade) varies smoothly in interesting ways as you move across the photo.

What I will talk about here are a couple of pitfalls, issues and technical details about noise generation (specifically Perlin and Simplex noise) that I have not seen much mention of elsewhere.

The first pitfall is that some implementations of Perlin noise or Simplex noise on the Web are not correct.  For example, the first result in a Google search for "perlin noise javascript" is this page.  If you read through the code on that page you'll notice a curious thing:  there are no initialization parameters and no use of random numbers.  If you use that code, you'll generate exactly the same Perlin noise every time you use it!  That's not exactly an error, but it's probably not how you expect it to work.

The second result in the Google search has a more serious problem.  Take a look at the first twenty lines of the code and see if you see spot the problem:

// Ported from Stefan Gustavson's java implementation
// http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
// Read Stefan's excellent paper for details on how this code works.
//
// Sean McCullough banksean@gmail.com

/**
 * You can pass in a random number generator object if you like.
 * It is assumed to have a random() method.
 */
var ClassicalNoise = function(r) { // Classic Perlin noise in 3D, for comparison 
   if (r == undefined) r = Math;
   this.grad3 = [[1,1,0],[-1,1,0],[1,-1,0],[-1,-1,0], 
                                 [1,0,1],[-1,0,1],[1,0,-1],[-1,0,-1], 
                                 [0,1,1],[0,-1,1],[0,1,-1],[0,-1,-1]]; 
   this.p = [];
   for (var i=0; i<256; i++) {
   this.p[i] = Math.floor(r.random()*256);
   }
   // To remove the need for index wrapping, double the permutation table length 
   this.perm = []; 
   for(var i=0; i<512; i++) {
  this.perm[i]=this.p[i & 255];
  }
};
The good news is that this code is using a random number generator to initialize the noise generator, so you won't get the same results every time you run it.  The bad news is that this code is filling a permutation table with random numbers.  This table is supposed to be shuffled numbers from 0 to 255.  Instead it's some random selection of numbers from 0 to 255.  Most of the time that will work pretty well.  Just hope you aren't the unlucky user who ends up with the table of 255 ones!

Assuming you find a correct implementation, there are also issues with the return value of Perlin and Simplex noise functions.  To start with, some implementations -- like the first one above -- return values from 0 to 1, while others -- like the second one above -- return values from -1 to 1.  So you need to be check that before using.  But a more serious issue with the return value is that it doesn't really range from -1 to 1.  Ken Perlin stated that his original implementation returned values from -1 to 1, but it actually returned values (for the two-dimensional case) from about -.70 to +.70.  This was (mostly) fixed in the design of Simplex noise, and some implementations of Perlin noise correct the range as well.  But if you're not certain, you should check the range of your noise function.

For advanced students, a further complication with return values arises when we consider using octaves.  The basic idea of octaves is to layer noise at different frequencies and different scales.  This can create a more natural result, and is how noise is most often used in procedural generation.  However, you need to be aware that this changes the range of the noise output.  The random noise tends to cancel out, so the range of the output narrows.  For example, if we have a noise source that has a range of -1 to 1 and we combine 6 layers with a persistence of 0.5, the resulting noise has a range of about -0.82 to 0.82.

(Even more advanced students will realize that I actually lied in that previous paragraph.  I'll get back to that in a moment.)

Unfortunately, range isn't the only issue with the return values of the noise functions.  It turns out that the output of these noise functions is not uniformly distributed.  If you make a histogram of the output of a Perlin noise function, it looks something like this (copied from here):


This shows that numbers near zero are much more likely than numbers near the edges of the range.  If you use a noise function to (say) create mountains, and your rule is that you have a mountain wherever the noise is greater than 0.5, you may be surprised to see that your mountains cover only about 5% of the map instead of the expected 25%!

(Now that we've seen the distribution of noise, let me return now to my earlier lie.  It's not exactly true that when you layer noise in octaves the output range is reduced.  Summing noise functions makes the output distribution taller and steeper.  On a practical level, this means that the range of the output numbers will narrow.  But it's still possible -- just very unlikely -- to get larger numbers.  Layering 6 octaves with a persistence of 0.5, the expected range is about -0.82 to 0.82, but theoretically you could get a number from approximately -2 to 2.  If a number outside of the expected range will break your code, you should check for that and clip anything outside that range.)

I've recommended testing your noise function to understand it's range, so let's talk now about how to do that.  Here's some Javascript code to generate a hundred million values of a one-dimensional noise function and check the output range by finding the highest and lowest returned values.  Can you see the problem with this code?

    var pn = new Noise();
    var minVal = 9999;
    var maxVal = -9999;
    for(var i=0; i < 100000000;i++) {
       var val = pn.noise(i);
       minVal = Math.min(minVal, val);
       maxVal = Math.max(maxVal, val);
    };
    console.log('Noise range was '+minVal+' to '+maxVal);


Don't feel bad if you don't.  There's no real error in this code -- the problem is in the noise generation code.  That starts off like this:

    Noise.prototype.noise = function(x) {
       var bx0 = Math.floor(x) % 255;

       [...]

As you can see, the whole number portion of the input "x" is taken modulo 255.  As a result, this noise function has a periodicity of 256 -- it starts repeating after 256 units in the "x" direction.   We think we're testing 100 million values, but we're actually only testing 256!  This periodicity is related to the 256 value permutation table we saw earlier.  In theory, a noise function can use a longer permutation table for a longer periodicity, but in practice you'll rarely see that implemented.

The consequence of this periodicity is that you need to scale your input parameters to the range [0, 255].  If you want to use noise to generate a landscape that is 10,000 units on a side, you need to divide your x and y coordinates by 40 before feeding them into the noise function.  (There's no periodicity with the fractional portion of the input parameters, so you can simply divide by the appropriate number.)

A less well-understood consequence concerns the octave function.  The typical implementation of octaves multiplies the input parameters by 2 every octave, so the noise being layered starts to repeat after the 8th octave (2^8 == 256).  In practice this is inconsequential because that many octaves of noise are rarely used.  But if for some reason you really need that many octaves, consider extending your noise generator to a greater periodicity.

In a future post I'll talk about ridged noise and at some point I'll get around to cleaning up the Javascript implementation I'm using and post it somewhere.

Thursday, October 6, 2016

Welcome!

In the late summer of 2016, Martin O'Leary made a posting on his web blog of a fantasy map generator written in Javascript.

An example map from Martin O'Leary's fantasy map generator

I was quite intrigued by Martin's map generator.  (So was a lot of the Internet.  And even National Geographic.)   But unlike most folks, I accepted Martin's invitation to grab the code and start playing with it.

An example map from my modified map generator

For the past month or so, I've continued to modify and extend Martin's map generator.  His maps reminded me of something you might see inside the front cover of an old fantasy paperback, so I made them look more like an old book page.  I added color, and different ways to display the maps. 

Along the way I've run into some interesting problems and insights.  I've posted some of these to the procedural generation Reddit, but I don't want to overstay my welcome there with constant posting, so I decided to start this blog up to capture some of my work in creating this map generator.  If that's the sort of thing you find interesting, I welcome your attention!  My posting here will no doubt be erratic and meandering, so I encourage you to subscribe through RSS, email or some other method to be notified of new material.