Barrier Islands

The recent news stories about Hurricane Florence often mentioned the Outer Banks, which are a series of barrier islands on the coast of North Carolina:

Barrier islands are flat or lumpy areas of sand that form by wave and tidal action parallel to the mainland coast.  That often occur in long chains that may go on for many tens of miles.  The barrier islands are often separated by small tidal inlets, and may form lagoons between the islands and the mainland.

According to Wikipedia, barrier islands are on as much as 15% of the coastland, so you might expect to see them on most fantasy maps, but they're pretty uncommon.  And due to the nature of noise, you almost never see them on procedurally-generated maps that rely on noise for making landscapes.

To understand why, consider a vanilla island map:

This is essentially a circle that has been perturbed with some low frequency noise added to break up the circle shape.   Now let me try to use noise to break up the coastline and form some coastal islands.  Here's the same island with some low frequency noise added:

This has add some bays and points.  The features are pretty big because I've used a low frequency noise that changes slowly.  However, the noise isn't strong enough to create islands.  Let me raise the strength a bit:

Now I've created some islands, but they're basically circular blobs, and not necessarily hugging the coast.  I can try adding high frequency noise:

This can give me very jagged coastlines and small islands along the coast, but nothing that really looks like a barrier island.

One reason noise doesn't work well for this is that noise is uncorrelated in x and y, so although noise overall isn't random, the shapes it produces are random:

Which is good for some things, but not good for producing a particular shape like an island alongside a coastline.

As with other cases where I've wanted to generate a particular shape or area, the solution is to create a mask in the required shape and then use noise within the mask.  (And I can also use noise to perturb the mask into a more natural shape.)  Barrier islands are essentially long thin areas that are offset from the coastline.  So let me work on creating that shape mask.

To start with, I'll identify a section of the coast where the barrier island will lie.  That's done by picking a random spot on the coastline and then a second spot further down, marked here by the red line in the upper right:

To start creating the barrier island, I could just take the straight line between those two points and project it out a little ways into the water.  That would give me a very straight and unnatural looking island, but I could perturb the shape to hide that.  The real problem is that the island wouldn't follow the coastline.  That would probably look okay along a mostly straight coast, but would look strange on a curving coast.  It will be better to replicate the coast line as the basic shape of the island.

To do that, I need to make a copy of the coastline and then project it out into the ocean, perpendicular to the coastline.  I already have a routine for calculating the perpendiculars (normals) to a polyline from way back when I implemented hand-drawn lines, and my coastlines always run the same direction, so this is fairly straightforward:

Or would seem to be straightforward.  Let's see what happens when I project the coastline a little further out (to create the other side of the island mask) on a less smooth piece of coastline:

Two of the projected line segments intersect each other and create a dreaded figure-8 in the polygon.  This is known as the parallel curve problem.  You can't just offset the coast some distance, you must also take care of problems that arise from acute inside and outside angles.

I looked for some Javascript code to handle this problem, but the only example I found (here) failed rather spectacularly on some easy examples.  So I wrote my own.  The basic approach is to offset each point by the normal, but then to check if the new point creates a line segment that intersects any of the existing line segments.  If it does, you cut off the loop and insert a new segment consisting of the intersecting point and the new point.  At least for the test cases I've tried, this works well enough for my purposes.

So now I'm able to generate simple (loop-free) masks for the islands:

These are a little too regular, so I will perturb the outlines:

It's okay if these outlines touch land at some points, because barrier islands often do that.

The next step is to fill in the land, but before I do that I want to make the islands longer and add some logic to avoid overlapping islands if I create multiple barrier islands on the same coastline.

Now let me try adding the land.  To do this, I raise the height of any land location (which are Delauney triangles) above sea level:

There are a couple of things to note here.  First, in the upper left there's a fairly successful barrier island.  However, it's not like the island neatly fills in the polygon.  Instead, a number of triangles of land have been “turned on" by having their centers within the polygon.  This adds quite a bit of randomness to the island's shape.  Second, you can see that the other two islands were close enough to the coast that they just merged with the coast.  Since I'm actually trying to create islands here, I don't want to that to happen too often, so I'll adjust the generation to use more water gap between the coastline and the island.  (Eventually Ill also added a specific test to prevent this from happening.)

One nice thing about the irregular triangles that comprise the land is that it naturally creates the kind of tidal gaps that are typical in a barrier island.  The bad thing is that it generally creates blobby islands that look like distorted pearls on a string.  They don't look much like barrier islands, and when you have many single triangles, it starts to look very unnatural.

If I increase the width of the islands, both effects go away, and I get more natural looking islands, but without tidal gaps:

But I'd still like to be able to generate really narrow islands.  Another approach is to (greatly) increase the number of world locations to improve the resolution:

This can achieve some impressively thin and detailed islands, but it greatly increases the time and memory to create the map.

With any of these methods, there's a good likelihood that some parts of the island will be very jagged:

This happens because the outline is hitting two sides (or sometimes all three sides) of the underlying Delauney triangles.  This is an inherent problem in using the Delauney triangulation in map generation -- and not one I see often discussed!  This doesn't show up as much on DA's coastlines because there's an intentional smoothing step to reduce this, but that smoothing step tends to eliminate narrow islands.  A potential solution is to make slightly wider islands and use the smoothing as well -- with some tuning this yields thinner islands without lots of triangle artifacts:

However, there's still a limit to how thin islands can be with this approach.  It also means you never get really fractal coastlines.

The smoothing algorithm sometimes causes the long barrier island to break up into smaller islands (as in the lower left islands above) but it's handy to have an option to force that to happen as well:

The only thing that remains is to name and label the islands.  The only slightly tricky aspect is that I don't really want to name every island in the barrier island chain.  In real barrier island chains, the individual islands often do get named, but that makes labeling a mess:

So when I create the barrier island, I make note of the entire arc and attach one label to that, even if the generation actually ends up breaking the arc into multiple islands:

“Banks" and “Bars" are appropriate for barrier islands, so they're options in the naming.

This example shows a potential problem with barrier islands:

Here the barrier island has been created inside a bay.  That doesn't make a lot of sense (and leads to label clashes besides).  To prevent that, I can use my bay-detecting logic to detect and then avoid these stretches of coastline.  This is probably not foolproof, but works well on this map: