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.