Tuesday, January 15, 2019

Voronoi Revisited (Part 3)

In the two previous blog posts, I gave up on trying to generate an interesting fractal coastline without using a very dense Voronoi (Delauney) grid and instead modified Dragons Abound to work with a very dense grid.  Or at least got it to the point where it could generate interesting coastlines.

However, the rest of the program doesn't work well with so many Delauney triangles (256K at my current settings).  One problem is that Dragons Abound draws the land and sea by drawing all the individual triangles, and that many SVG elements crashes the browser.  So I have to turn off land rendering completely.  There's probably a way to work around that issue, but having so many triangles creates other issues.  For example, there are various parts of the program that have to process the entire map.  Each of those becomes sixteen times slower when there are 256K locations rather than 16K locations.  There are also some parts of the code (the new precipitation model being an example) that break in various ways when dealing with so many triangles.  And there's nothing to be gained by having the location grid be so detailed -- after creating the coastline, nothing is improved by the additional complexity.  So while I probably could go through the program and fix the areas where a large number of locations slows down the code unacceptably, or breaks the code, it seems easier to reduce the resolution of the map grid after coastlines have been created.

Azgaar has previously done some work on changing the resolution of the the Voronoi grid underlying the map.  He implemented the capability to change the resolution of the grid on the fly as he was generating, so that he could (for example) increase the density of locations along the coast. However, changing the density locally has some drawbacks -- specifically, it creates some odd shaped triangles along the boundary.  And Azgaar later opined that it was too complicated and not worth the effort.  Azgaar usually knows what he's talking about, so I'll take his word for it and avoid any kind of repacking of the existing grid.

What I'll do instead is created a second grid at the desired (lower) resolution and then copy the heightmap over to the new grid.  (Recall that Dragons Abound now keeps coastlines separate from the grid so that once they're created they're no longer dependent upon matching up precisely with the grid.)  This is a little bit tricky.  Since the original grid is at a much higher resolution than the new grid, there will be many locations in the original grid that map to a single location in the new grid.  Since each of those original locations has a different height in the heightmap, how should I copy that over?  Should I use the average?  Or perhaps the highest (or lowest)?

To start with, I'll just pick one random location to copy over, just to see if the new grid will work with the rest of the program:
It works surprisingly well.  One minor bug where the new locations were not getting properly marked as land, coast or sea but once that was fixed, map generation worked fine.  There are a few minor things to clean up (such as the Palmanor icon out to sea) but overall it looks good.  Even the tiny islands look fine.

In the end, I settled on making each location be the average of the underlying locations when reducing the resolution of the Voronoi grid.  This seems like a reasonable approach, and I can always adjust it later if necessary.  This image shows how the coastlines end up separate from the final grid:
So to recap:  Dragons Abound uses a very high resolution grid of Delauney triangles during the generation of the map heightmap.  When that is complete, Dragons Abound captures the coastlines by tracing where the heightmap transitions from less than zero to greater then zero.  Dragons Abound then copies the high resolution grid into a much lower resolution grid by averaging overlapping locations.  The high resolution grid is then discarded and the rest of the procedural generation and display continues on using the low resolution grid.  An interesting question is whether using a Delauney grid at this point adds any value; perhaps I should just copy into a hex grid or something similar.

Monday, January 7, 2019

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.

Monday, December 31, 2018

Voronoi Revisited (Part 1)

As chronicled in recent blog posts, I've been struggling with modifying Dragons Abound to get the kind of coastline detail I'd like.  My dissatisfaction initially arose when I was implementing barrier islands.  To make the narrowest possible island I could, I made them one location wide -- each location being a Delauney triangle in the underlying representation:
This was pretty unsatisfying -- both because the island was very jagged and because the size of the details was too big.  Greatly increasing the number of Delauney triangles (and hence making each triangle much smaller) would seem to address this problem -- but at the density of triangles I would require the browser crashes.

I addressed this by divorcing the land outlines from the underlying location representation.  This allowed me to draw islands any shape or size I wanted, regardless of the underlying grid of locations:
So, problem solved!  This allows me to draw barrier islands, and since the coastline no longer has to follow the underlying grid, if I want a more detailed coastline I can create a coastline as normal and then add detail to it.

Except...  How do you add detail to a coastline?  That isn't as easy as you might think.  Since I want a fractal coastline, I looked at using actual fractals to add detail to the coastline:
And with some tuning, this can add a lot of detail and interest to coastlines.  However, it cannot produce something like this map:
with a broken shoreline, a variety of different shaped islands, etc.

Perlin noise can produce this sort of terrain with a sufficiently detailed underlying grid, but can it be done *without* storing the terrain height values in an underlying grid with the required resolution  (since I know that breaks my code)? So far, I haven't figured out how to do that.  The coastline is essentially the path through all the points where the Perlin noise function has a value of zero.  Although you can find out directly from the Perlin noise function a value at a particular (X,Y) location, you cannot find (say) “all the locations where the function has a value of zero."  So it's difficult to see how you can trace out the height contour without an underlying grid.  

Even worse, I asked Amit how to do this, and he didn't have an answer either.  It's one thing when I can't figure it out, but when the smart guy can't figure it out I begin to think it can't be done.  Frustrating.  I have the capability to shape the coastline however I want, but I can't get the shapes I want without a very detailed underlying grid.

So how can I get a high-resolution grid without breaking my code?

One approach I've thought about is something Azgaar did in his map generator -- variable size Voronoi cells.  The basic idea is to increase the density (and reduce the size) of the underlying grid along the coastlines, and make it less dense in the oceans and other areas that do not need the detail.  With this option, you will have many grid cells only in the areas where you need the detail.  This would be a pretty challenging change to implement in Dragons Abound, but it's something I want to think about.  On the other hand, Azgaar himself wasn't too happy with this approach, so that's also something to keep in mind.

In the meantime, I want to investigate exactly what is causing the browser to crash when I had lots and lots of triangles.  The Chrome developer tools can provide a lot of insight into performance.  I'm by no means an expert in how to use the tools, but many of the features are simple enough for anyone to figure out.  Case in point, if you want to know the overall memory use in a program, the Memory tab shows the current usage:
In this case, I'm displaying Azgaar's web page and it is using a modest 20 MB of memory.  I can use this to give me some basic insight into the memory usage of Dragons Abound and determine the point at which I crash the tab.

The basic parameter that controls the resolution of the underlying grid in Dragons Abound is cleverly called “npts" for Number of Points.  For every unit area of the map (the regional maps I normally use as examples are 1 unit in area), Dragons Abound creates this many locations in the underlying grid.  Typically I use a value of 16K (16384) for npts, which roughly means that each location in the grid corresponds to about a 70 square pixels on the screen at the default magnification.
Exact memory usage will obviously vary from map to map, but for the above map with 16K points, the memory usage was about 92 MB:

Which was lower than I expected and overall seems pretty modest.

If I double the number of points in the underlying grid, the memory usage goes up to 138 MB:
The memory usage doesn't double because some of that memory is overhead and other data structures that didn't change in size.  The 16K additional points amount to about 50 MB of memory, so each point ends up using about 3K bytes of memory.  That's more than I expected, but the overall usage is still very modest.  On a computer with 64GB of memory, 150 MB is hardly noticeable.

Skipping ahead a few doublings, I find that the tab that Dragons Abound is running in usually crashes around 128K points.  If I catch it before it crashes and check the memory:
which is ... not much.  Certainly not enough to crash the tab.

I've been operating under the assumption that memory usage was crashing the tab, but apparently memory is not the problem.  So why is the tab crashing on me?  The only other clue I have is that the tab doesn't crash until the map is complete, so perhaps that's an indication that it is crashing during rendering.  

The obvious guess is that the SVG I'm producing is overwhelming the browser renderer, either because it is too big or too complex.  As a first step, I can investigate how many SVG elements I'm creating.  In D3, I can get the total number of SVG elements I've created with svg.selectAll('*').size().

Running with 16K points and checking the number of SVG elements shows me this:

In turn, 32K points has 65457 elements and 128K points has 258823.  Each point added to the underlying grid adds two elements to the map.  I think I've found my culprit.

Each point in the underlying grid adds SVG elements because of the way Dragons Abound renders the land (and the sea).  The land is rendered by drawing each underlying location as a filled polygon and then blurring them all together.  This enables Dragons Abound to mottle the land in pleasing ways, or use the height of the land to render the land in 3D shading, as you can see in the land here:
I can investigate by turning off the land and ocean visualizations and checking to see how many SVG elements are created.  With 256K points:
Wow, that's a huge reduction in the number of SVG elements. And as hoped, the map now renders without crashing!  So as long as I avoid using the grid to render the land and sea, I can use a much denser grid than I've ever been able to before.

Now that I can use a much denser Voronoi grid, I want to check to see whether that enables generation of the sort of land features I want, such as coastal islands.  The dense Voronoi grid creates other problems (especially with rivers) so I'll turn off everything except the coastlines to speed up testing and focus on that.  Here's an initial render of some coastline using 256K points and some default noise:
The good news is that this renders fine, and in fact already produces a much better coastline.
Even without tuning it's a big improvement.  The noise is producing the kinds of fractal coastlines and coastal islands that I noted above in the reference map.

Here's a 300% zoom on the islands:
At this magnification, you can see some of the triangle artifacts from the underlying grid, but even so the islands are able to form some interesting shapes.  I can use smoothing (as I do on the current maps) to remove some of the more obvious triangle artifacts.  At the default magnification this provides a less jagged coastline, but also removes some fine detail:
I'll probably have to tune that to find a good middle ground.  More on that next time!

Wednesday, December 26, 2018

Barrier Islands Revisited

One of my motivations for rewriting Dragons Abound so that land masses don't have to conform to the underlying Delauney triangulation of the world was the problems I encountered in implementing barrier islands.  Now that the rewrite is done, I want to revisit barrier islands and take advantage of the new capabilities.

Recall that 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.  North Carolina's Outer Banks are a typical example:

When I implemented barrier islands for Dragons Abound, I was forced to make the islands at least a couple of locations thick.  If I tried to make islands that were just one location thick, the underlying triangles become very obvious in the outline of the island:
Now that I can draw a land mass without regard to the underlying locations, I can make a thin, smooth barrier island.

My original implementation of barrier islands worked by creating an outline where I wanted the island to be, and then turned any of the underlying Delauney triangles within the outline to land.  Now that I can define land as polygons, I don't need the second step of turning on the underlying triangles.  I can just use that outline directly as the barrier island:
But as you can see, the outline I create isn't quite perfect -- it folds back on itself near the bottom end.  When you project a line in a direction as I do here to create the polygon, it can create some weird shapes.  When I was just using this as a way to locate land locations, this was irrelevant.  But now that I'm using this directly, I'm going to have to clean it up and make it look more like an island.

I do a couple of things to improve the island outline.  First of all, instead of projecting from the actual coast, I project from a smooth version of the coast that removes most of the small folds and bumps.  Second, I scan through the outline and clip away any self-intersections where the island coastline crosses itself.  Finally, I cap the ends of the islands with arcs rather than just a straight line connecting the inside to the outside.

Here is a (zoomed in) example of a cleaned up, narrow barrier island:
If you look at natural barrier islands you'll see that the outward facing sides of the islands tend to be smooth while the insides are more irregular.  Presumably these islands are mostly sand, and the wave action on the outside tends to smooth them out, while the protected insides can be more irregular.  I can simulate that by adding some noise to the inside of the barrier island profile:

Here's an example of a possible problem:
Because it was created in a narrow inlet, the barrier island is overlapping the coast.  When land is tied to the underlying locations, it isn't possible for two land masses to overlap.  (They just end up merged.)  But now that the shape of the island isn't tied to the underlying locations, I need to add some smarts to keep from getting implausible results.

The first step in improving the placement is to identify all the bays on the coastline and keep barrier islands out of the bays.  Detecting the bays uses the method I described in this post; the basic idea is to measure the sinuosity of the coastline where I'm going to place the island and avoid any spots where the sinuosity is high.  This will cause the barrier islands to largely end up on flat spots on the coastline.  There are a few other rules that help with placement.  I avoid any coastlines that are too short -- this avoids creating barrier islands off of small islands.  I also avoid overlapping any existing barrier islands.  Finally, I check to see if the barrier island overlaps with any of the existing coastlines.  If it does, I reject it.  (Alternatively, I could try merging it with the coastline.)

The one improvement I'd still like to make is to add some small breaks into the islands, similar to what happens at the south end of the North Carolina Outer Banks.  That's on the TODO list for now.

Monday, December 17, 2018

A (Not So) Minor Rewrite

I've written recently about shortcomings in my map generation caused by using Voronoi cells/Delauney triangles to define land masses.  One problem I noted when implementing barrier islands -- because land must be at least one Delauney triangle in size, barrier islands could only be made so thin.  And even with a high density of triangles, the resulting islands would be very jagged because the coastline followed the triangle edges:
Another problem was that I couldn't generate a coastline with the kind of fractal detail that you often see in maps drawn by people.  And if I did add a lot of jagged detail to the coastline, it no longer followed the land exactly, resulting in the land or the sea showing through where it shouldn't:
Here you can see spots where the land sticks out a bit past the border.

The solution to this problem is to define land (at least when drawing the map) by the space enclosed by the coastline.  This is a pretty significant change -- I rely quite heavily on the underlying grid of Delauney triangles to draw the map.  For example, I consult locations to determine the biomes, colors, and other features that should be displayed there on the map.  But using actual polygons to define land masses (even if I continue to use the underlying grid for other purposes) would bring significant benefits, so I decided to at least explore the feasibility.

(Much of the initial work for this I did on an Amtrak train ride to New Jersey, and I wasn't able to capture screenshots, so this first part will be somewhat dry.)

To begin with, I kept world generation unchanged, but as a final step I captured all the coastlines as polygons and saved them.  Initially, some of these coastlines did not form closed loops since I have avoided creating coastlines around the very edge of the map.  In the past, coastlines at the very edge of the map caused some difficulties, so I simply did not generate coastlines in those areas.  However, my work setting DA up to generate continent-sized maps removed those issues, so I was now able to modify the generation of coastlines to only create closed loops.  So now the map generates all land masses as closed-loop polygons without any holes.

Here's an example of my current approach.  The coastline follows the edges of the triangles, so each triangle falls either completely in the land or completely in the sea.  A red dot marks the center of every location that has a height greater than zero, and blue dots mark locations less than zero:
Since the coastline runs along the edges between greater than zero and less than zero, every red dot is inside the land polygon and every blue dot is outside.

When I perturb the coastline it no longer runs on the edges of the triangles.  This may result in a red dot being outside the coastline, or a blue dot inside the coastline:
Many parts of DA rely on knowing where the land and sea are, and they start to break down when the coast doesn't correspond to that split:
Here you can see how the river ends awkwardly on a non-existent coastline.

To rectify this, I want to switch over to identifying a location as “land" if it falls inside one of the land polygons.  Since the coast no longer necessarily follows the edges of the Delauney triangle, a triangle might only be partially in the land.  Rather than rely on the height in a location to decide if it is “land" or “sea" I'm now going to determine that by checking whether any part of a triangle is inside any land polygon.  In combination with this, I will mask all the land to the actual land polygons.  So even though I will paint some land locations that are outside of the actual land mass, they'll be clipped and won't show.  The trick is to include every location that has any part inside the polygon so that I get complete coverage inside.  In the following illustration, every red dot indicates a location that is at least partially within the land polygon, and every blue dot a location that is entirely outside the polygon:
Here you can see how the centers of some land locations are actually outside of the land polygon.  But crucially, none of the sea locations are inside the polygon.

However, this doesn't fix the river problem in all cases.  The river needs to be drawn past the edge of the land, so that it is clipped to the land polygon and the mouth of the river aligns with the coast.  To force the river to be drawn past the coast, I identify all the sea locations that are immediate neighbors to land locations -- I call these “coastal" locations -- and then I make sure the river extends out to a coastal region.  The result is that the river crosses the coastline and is clipped properly.  In this illustration, I've marked the coastal locations with green:
You can see the river is now clipped correctly.

With that in place, I can now experiment with making the coastline more interesting.  Here's how the coastline changes if I add a sizable amount of jitter:
This doesn't do much beyond change the shape of the coastline a little.  That's because I'm using the same line segments and just moving the endpoints around a bit.  That doesn't add any detail.  If I break the original line segments up into pieces and jitter the pieces:
The jitter adds some complexity to the coastline and oddly enough also softens it.  This is because breaking the line segments down into smaller pieces and jittering the pieces effectively creates curves.  This is a somewhat more interesting coastline, but doesn't produce the kind of fractal look I'm seeking.

Jitter moves each point randomly and independently.  It might be better to use noise to move the points around, so that nearby points move roughly together.  Octaves of noise might also help create fractal detail, as it does when creating a fractal landscape.
This certainly has a greater level of detail, but it reminds me more of a Dr. Seuss illustration than a real coastline.  There are also numerous artifacts where perturbing the coast has caused it to cross itself.

If I want a fractal coastline, perhaps I should try using a fractal generator.  There are a few articles on using fractals to generate coastlines, but nothing I can really use out of the box, so I'll have to implement it myself.

One of the simplest fractals is the Koch curve, which you've probably seen before.  The basic idea is to divide a line segment into three parts and then add a triangle to the center part.  Doing this repeatedly creates an increasingly complex shape:
Of course, this produces a perfectly regular structure, which is not what I want for a coastline, but that can probably be fixed.  So let me implement a Koch curve and apply it to a simple line segment like a bit of flat coastline:
Let's see how this looks if I vary how the line segment is split into three pieces, so that the pieces can be different sizes:
Varying the height of the bumps changes the character of the line.  With low values, the triangle becomes lower and more smooth:
Which starts to look like a coastline.  With high values a problem becomes apparent:
The line starts to overlap on itself and self-intersect.  It makes an interesting pattern but would be a problem in a coastline.

Using a negative value for the height inverts the line:
Which viewed this way looks like the silhouette of a cartoon cloud.

For my purposes, one of the most useful settings is to mix negative and positive height values, so that the fractal sometimes goes one direction and sometimes the other:
And with a lower height value:
Even this relatively unsophisticated approach looks pretty good.

Before going on, let me fix the problems that arise when the coastline self-intersects.  Trying to prevent this from happening is pretty difficult, but fixing it afterwards is straightforward.  Beginning at one end of the line, I scan ahead a segment at a time.  If the current segment intersects with a later segment in the line, I keep the intersection point and clip out everything else.

Even large height values are now okay:
Although you can see there are many spots where the line comes very close to touching itself.

At the high values, the triangle nature of the fractal is fairly evident but that can be eliminated by going deeper into the fractal (and using a thinner line to show the detail):
Before I go any further, let me try this on the coastline and see how it looks:
Well, that's disappointing.  Why did that happen?  The problem is that I'm fractalizing each segment of the coast line.  But those segments are not very long -- basically just long enough to get one triangle stuck into them -- which turns the coastline into a series of spikes/anti-spikes.  As a quick first attempt to improve this, I can use line simplification to create longer line segments on the coast:
Still rough and not quite where I want it to be, but showing enough promise to continue experimenting.

To return to the original problem of fractalizing a line, so far I've been using the Koch curve, where a part of the line is recursively replaced with a triangle (or 2/3 of a triangle).  I can change that to be a three-sided figure pretty easily:
Not unsurprisingly, this gives a more rounded fractal.  It doesn't look too bad on the map:
Increasing the number of sides quickly breaks down, because the resulting segments are too small for the next level of recursion.  The Koch triangle produces four segments of length/4.  The three-sided figure produces five segments of length/5, and so on.  With higher numbers of sides the segments quickly too small to be fractalized themselves.

Choosing a random number of sides from 2 to 4 so that each fractal varies makes the character of the curve less predictable:
So far, every recursive level of fractalization uses the same ratios of sizes.  To change that, I can borrow the notion of persistence from noise generation. With persistence, as the scale of the noise grows finer and finer, the amplitude of the noise is reduced.  If I apply that same idea here, I get a fractal line that gets smoother as the scale gets smaller:
If you compare this line to the previous one, you can see that there is similar large scale changes, but at the finer scale the line is smoother.

I can also reverse the persistence, so that at a large scale the line doesn't change as much, but there is added detail at a lower level:
Here the line is closer to the original straight line, but with strong fine detail.  This seems like it might be useful for coastlines, so that the fractalization doesn't wander too far from the original line, but still adds detail.

A limiting factor in my implementation so far is that the fractalization part only works on line segments, so when I apply it to the coastline I have to essentially throw out the existing detail and just treat that section of coastline as a straight line.  If I set the fractalization low, it's obvious that the coastline is being reduced to low resolution segments:
I call this the Picasso map.

So how can I avoid turning everything into straight lines?  In the Koch curve, the fractalization is caused by adding (two sides of) a triangle to a straight line.  I need a way to add a triangle to an arbitrary polyline.

You can think of adding the triangle to the straight line as offsetting a point in the middle of the line perpendicular to the line:
So if I want to do this to an arbitrary polyline, I need to offset perpendicular to the polyline.  In the case of a polyline, I don't have just a single line for the whole offset area, so I need to be able to offset by the perpendicular all along the polyline -- the perpendicular will keep changing.  I also need to know how far to offset along the perpendicular at any point:
So this triangle offset can be looked at as a pattern of offsets to the perpendicular by different amounts.  I'll turn the triangle offset into a pattern for the fractalization that tells me how far to offset given how far along the line I'm at -- then when I want to offset a point that is (say) 37% along the length of an arbitrary polyline I can look at a point that is 37% along the length of my fractalization pattern, find the Y value at that point, and then use that to control how far I offset the point in my polyline.

So what does it look like to apply this to a polyline rather than a line segment?  Here's a curved polyline:
And here's the same polyline after adding a triangle to it:
As you might expect, it is taller and more pointed.  That's perhaps not too interesting, but here's what it looks like if the fractalization is recursively applied (and allowed to randomly switch between negative and positive):
Since I didn't have to turn the line into a straight line, it has retained much of it's original shape.  So now I can apply fractalization to an arbitrary polyline.  Here's an example of this applied to a coastline:
The red line shows the original coastline before fractalization was applied.  You can see that unlike the Picasso Map, the original coastline did not need to be reduced to long straight lines before fractalization.   You can also see that the fractalization has made significant changes in the coastline -- eliminating big sections of land in some areas and adding some in other areas.

Now that fractalization of arbitrary coastlines is working, I want to add the capability to vary the roughness of the fractalization across the map, so that I can have smooth coastlines in some places and rough coastlines in other places.  This is evident in many real world places.  A good example is Ireland, which has a rough Western coast and a smooth Eastern coast:
Ireland's Western coast is probably rougher because it faces into the North Atlantic.  I could link this effect to ocean currents or something similar on my maps, but for a first approximation I'll just use a noise function to smoothly control the roughness of the coastline.  This view shows the original coastline in red and then the “fractalized" coastline in black underneath:
In this example, you can see that the fractalized shore follows the original coastline closely around 9 o'clock on the island, but up around 1 o'clock the shore is much rougher and deviates from the original shore quite a bit.
Here's what the fractalized coasts look like on a map:
This isn't quite the look I'm aiming for, so I'm probably going to revisit this with a different approach, but it's not entirely bad.  I like very much that the coast is smooth in some places and rough in others; that's a feature I will try to maintain.