Voronoi Revisited (Part 2)

In my last posting I hunted down the code that was causing the browser to crash when I created a map that used a large number of Voronoi polygons (really Delauney triangles) for determining the height map and land contours.  With that fixed, I found I could use a grid with a large number of locations to create the kind of interesting, fractal coastlines I desired.  This was an early attempt:

Not perfect, but definitely showing promise.  Let me see if I can tune the program to improve on this initial result.

Most procedural land generators use Perlin noise to create a heightmap.  You find some good parameters for the noise, pick a seed, and then use the noise value at every (x, y) location to define the land mass.  One of the nice things about creating land this way is that if you want more detail on the coastlines, you can just tweak the noise parameters.

However, Dragons Abound doesn't create land this way.  (Or at least not only this way.)  Dragons Abound has a number of different ways to create land.  While all of these use noise in some manner, very few of them create land directly from noise.  For example, Dragons Abound has a routine to create an island which creates a mask for the island (typically an ellipse), uses noise to distort the ellipse into a more natural shape, and then uses different noise to roughly fill in the mask.  Any particular map is usually created by a combination of several different routines.  So adding more detail by tweaking the noise parameters doesn't work very well for Dragons Abound.

For my purposes, it's better to think of the problem in a slightly different way.  Given a particular heightmap representing land masses, how can I add detail to the edges of the land masses?  That might lead you to start thinking about how to detect the edges of land masses and mask out the rest of the map, etc.  But a second insight is that I don't really mind if I add additional detail on the rest of the map as well.  If the land is a little bumpier or the ocean floor a little more gnarled, that's fine.

So what does it mean to add detail to the coastline?  The coastline is just the contour line where the heightmap has a value of zero.  (This is arbitrary, but it's what every procedural land generator uses.)  To make that line more detailed, I need to push the land around that contour line up and down a bit, so that simple coastlines become elaborate, bits of land pop up out of the ocean to become islands and so on.  But not in a completely random way -- I want to the changes to seem natural.  Add that all up, and it starts to sound like adding a small amount of noise to the entire map.  And in fact that's what I did in the initial example up above.

Of course, I have to do this carefully so that I don't wipe out the created landmasses or create other problems.  There are essentially three parameters I need to tune.

The first parameter is the scale of the noise.  The scale is just the range of values for the noise.  In this case, I want to push some areas down and build some areas up so I want a range of values from negative to positive.  However, I don't want to introduce new mountains or create ocean far away from the existing coastline, so I'll keep the maximum (absolute) value of the noise to be a small fraction of the typical land height.

The second parameter is the base frequency of the noise.  The frequency is how fast over location that the noise changes.  A low frequency noise changes very slowly, so a positive area in low frequency noise might (say) cover the entire map.  A high frequency noise changes quickly, so a positive area in high frequency noise might be (say) the size of a small island.  In this case, the base frequency of the noise determines the *biggest* features I'll see in the noise.  So if I want the noise to be able to add (say) small islands to the map -- but nothing bigger than that -- I have to pick the base frequency to be the same size as a small island. 

You might think that would be straightforward (just measure a small island and set the base frequency to that size).  However, frequency is measured in the noise function's coordinates, not the map coordinates!  A typical noise function might have a range of 0 to 255 in each coordinate, while a map might have a range of -1 to 1 in each coordinate.  To make matters worse, the noise coordinates wrap, and many users of noise don't even realize that.  It's confusing to translate from one to the other and determine the appropriate frequencies, so it's usually easiest to just try out a range of frequencies and select the one that is producing the right sized map features.

The third parameter is the number of octaves of the noise.  Octaves are additional layers of noise.  Each layer typically doubles the frequency and halves the scale of the noise.  So each new layer adds features that are half the size of the previous layer, but only half as strong as well.  So you want to pick the number of octaves that will give you the smallest features you want -- and this may require tweaking the scale of the noise so that it is still strong enough at the highest octave to show up on the map.  Since I'm purposely doing this to make coastlines very intricate, I'll be using quite a few octaves of noise.

Now let me get on with the tuning.  To start, I'll generate a sample map without any additional noise:

This is obviously a bland coastline, with smooth coastlines and only a couple of large islands.  Here's the same coastline with an initial sample of noise added:

The noise has significantly changed the shape of the map, turning big chunks of land into ocean and vice versa.  There are also many new islands, including some far out to sea.  All of this indicates that the scale of the noise is too large.  The biggest individual features added by the noise look to be about the size of the smaller island in the original map.  That's probably a reasonable maximum new feature size, indicating that the base frequency is about correct.  Finally, there is a lot of small detail -- down to the limits of the display size -- indicating that the number of octaves is sufficient.  (However, the number of octaves might be larger than necessary.  That doesn't affect how the map looks, but is inefficient.)   It looks like the main tuning required is to the scale of the noise.

Tuning the scale is a little challenging because what I want from this noise is to mostly affect the land and sea around the height = 0 contour line.   So I need to use a relatively small scale, but how to pick the right number is not so clear, because from map to map the distribution of height varies.  The solution is to figure out the proper scale on the fly.  I can take all the absolute heights on the map, sort them, and find the cutoff that selects (say) 10% of the locations near zero.  If all these locations fall in the range of (say) [-0.05, 0.05] then I can use 0.05 to determine the scale for the added noise.

(I say “determine" because for several reasons you can't just use 0.05 directly.  First, I want to turn land into sea and vice versa.  Adding (say) 0.002 to -0.05 doesn't create any visible change in the map.  So the range needs to be considerable greater than 0.05 if I want to change a significant fraction of the -0.05 locations from sea to land.  Second, noise functions are not uniformly distributed, so in fact with a scale of 0.05 a noise function will never actually return a value of 0.05!  Again the practical implication is that the scale needs to be much larger than the largest values you want to see reasonably often.)

With some experimentation, I find a value that creates some complexity in the coastlines without changing them drastically, and a smaller number of islands:

As always, these parameters can take on a range of values in Dragons Abound so that I get a variety of maps from those with fairly smooth coasts to ones with very jagged complex coasts.  Letting the program pick values, here's the result:

The coastlines are on the smoother side, but there's still a lot of added medium-scale complexity and a fair number of new islands.

One capability I implemented when I did fractal coastlines was to control the level of fractalization with a noise function, so that some areas of the map would have smooth coasts while others would have complex coasts.  I thought this was a great addition to add interest and make the map look less “generated," so I'm going to add that here as well.  The idea is pretty straightforward -- before I add the coastline noise to the map, I multiply it by the output of a second noise function which varies from zero to 1.  Where this noise function is small there will be little additional detail added to the coastlines.  Where it is close to 1 the full additional detail will be added.  By picking a scale for the second noise function that varies slowly over the map extent, I will get some areas where the coastlines are complex, some where they are simple, and reasonable transitions between:

Here I've set the coastal parameters high to make the differences more obvious.    You can see wild, rugged coast in the Northeast and smoother, more gentle beaches to the West.

So the coastline generation is much improved, but I still can't fully generate a map with this many Delauney triangles.  I've been showing outline maps in this posting because many of the other map features are broken.  I'll tackle that next time.