Naming Forests

Some time ago I wrote a number of posts on naming map features.  At the time I didn't get around to naming forests, so I'm going to do that now.  Having named a number of features at this point, I know there are three main questions to answer:  (1) When should I name a feature?  (2) How do I generate a name for this sort of feature?  and (3) How should I display this name on the map?

Some map features always get named -- for example, towns and cities are always named and labeled on the map.  Other features only get named sometimes.  For example, Dragons Abound doesn't give a name to every point or bay on the map.  The rationale for when to name varies based upon the feature.  Sometimes a feature doesn't get named because it's not significant enough to warrant a name -- an example of this being small bays or points.  Sometimes a feature doesn't get named because (I think) it will make the map less interesting.  For example, I'll only label three bays or points in a typical sized map.  Even if there are more suitable candidates, it starts to detract from the interest of the map if they're all labeled.  And finally, sometimes a feature doesn't get labeled because the label won't fit on the map or creates clutter.  In Dragons Abound, this happens fairly often with rivers -- although every river gets a name, only the labels that will fit on the river will actually get displayed.

For forests, the main criteria for naming is the size of the forest.  In most cases, small forests aren't interesting enough to warrant a label.  (On the other hand, one of the key elements of creativity is breaking these sorts of rules; you can imagine a map with one small, isolated forest with a name like “The Druid's Woods" -- that would be quite interesting.)  Another problem with labeling small features is that the label will often not fit within or close to the feature, creating map clutter.  A secondary criteria is the number of named forests on the map.  As with bays and points, it's better to only label a couple of forests to help them feel “special."

Another challenge for forests is deciding what exactly counts as a forest to be labeled.  Here's a map excerpt with the forests outlined in purple:

As this illustrates, forests are often chopped up into pieces (or turned into awkward shapes) by rivers.  That's really just an artifact of illustrating the map.  The rivers actually run through the forest.  The forest is just pulled back from the rivers to make them easier to see.  That's apparent if I use a style that doesn't pull back from the rivers:

For labeling purposes, I probably want to ignore rivers when defining the forest areas.  So the above map would have one big forest rather than seven smaller ones.  But that might be a matter of taste.

Dragons Abound also avoids mountains when drawing forests, and this can also split a forest into pieces.  Unlike rivers, mountains can take up a lot of space on the map:

It seems odd to have one forest stretch over such a big chunk of map with no connection between the parts.  So unlike rivers, I'll allow mountains to separate one forest into two:

With the first question settled, let me jump ahead to the third question -- how I will display the name on the map.  I have a couple of immediate options that reuse existing code.  The first is to treat the name as an area label, similar to what I do for country names or ocean names -- the label floats around inside the area, looking for a good fit.  The second option is to tie the label to an (imaginary) point at the center of the area and let the label try to find a good fit near that point.

Here's an example of the area label option, using a multi-line label:

Right now I just want something that works so I can see the invented names.  I will tweak label criteria and styles to get a better fit later.

I have described previously a number of resources I use to collect possible names for features.  I have some tools that can data mine these resources for words and synonyms in various forms.  It turns out that forest names -- at least in the real world -- are pretty boring.  When I investigate forests, I find that almost all forests in the real world are called “forest" or “woods."  Browsing the historical thesaurus turns up a few other synonyms, but in English “forest" is used far more than any other term.

Looking at the adjectives and other nouns that are used in forest names also turns up nothing too surprising.  Adjectives are dominated by colors and descriptives (like “rough"), and no nouns are used very frequently, although wood types (e.g., “ash") do appear in the list as you might expect.  I'll create a vocabulary starting with the kinds of words I use for naming points and bays, removing all the water-related words, and adding in wood types and wood adjectives.

There will be some editing of the vocabulary and forms of names as I see results that I don't like (or do like).

Now let me return to label placement on the map.  One common style of forest label is to have a slightly arced label, as in this example:

I can reproduce this fairly easily; area labels already have the ability to change their angle and set a curve:

The real challenge is to place angled labels well.  The multi-line horizontal labels work well (almost) anywhere within the label area.  But we expect angled labels to be at an angle for some good reason, usually to fit along the long axis of the label area, or to mirror an important feature of the area.  In the Dragons Abound map above, “Presbyry Farest" (*) looks okay, but “Chi's Woods" doesn't because it is angled perpendicular to the long axis of the forest.  A human labeler would have run “Chi's Woods" along the long axis of those woods.

(* The “Farest" problem happens because of linguistic drift.  There's a list of words that are protected from drift, but I hadn't yet added the forest synonyms to the list when I created that example.)

Zooming out a bit on the example map above (Silverdale by Thomas Rey) shows three or four labels of this sort:

Here you can see that “Hartwood Forest," “Moon Woods," and “Northstar Glacier" all run along the long axis of their areas.  (Hartwood Forest should probably be more vertical, but the Painted Stones icon prevented that placement.)  “Cold Woods" follows an axis as well, but is also placed to run across the top of the river tributaries.  The curves of these labels generally follow the area shapes, except for “Moon Woods," which has the opposite curve.  That looks a little awkward upon reflection; the curve makes the label crowd the edge of the area and be visually a little cluttered with the river label.  Perhaps Thomas did it this way because the opposite curve on a label at that direction would be a little difficult to read.

Good label placement for these sorts of curved and angled labels is very difficult.  First, the size and shape of the label area is not just a geometrical measurement but depends on the map context.  In the Silverdale map, the “Moon Woods" placement is problematic partially because the river label is close to one side of the woods area.  Second, figuring out the axes or straight skeleton of an irregular polygon and applying them to label placement is not trivial.  I suspect that duplicating a good cartographer's label placement in this case would involve many heuristics and special cases.

As what I hope will be an acceptable shortcut for all of that, I've added a placement criteria that tries to maximize the closest distance between the label and the polygon defining the label area.  Although this isn't foolproof, in many cases it will effectively force the label to lie along the major axis of the region.  Here's an example that shows how this heuristic changes the placement of “Chi's Woods:"

In this case, it does a pretty good job of reasonable placement.

However, there are other criteria for label placement, such as not clashing with other labels, so in many cases the eventual placement will not follow only this criteria.  In the image above “Presbyry Farest" is a particular hard placement.  The forest area has numerous other labels which must be avoided, and is criss-crossed with rivers which also must be avoided.  In the end, there's no placement that doesn't break some of these criteria.  “Chi's Woods," on the other hand, can be placed easily into a spot that is far away from the edges of the area at only the cost of obscuring part of a river.

Another style often applied to these sorts of labels is to stretch them out so that they better span the labeled area.  Dragons Abound already does this for ocean labels, so I can easily add this style to forest labels as well:

It might be worthwhile to check the size of the forest area versus the length of the label to determine whether (or how much) extra letter spacing to apply.  Here's an example where a forest name (“Bishop Tanpik's Forest") has been compressed to make it fit better while another name with more room (“Forest of Horses") remains stretched out:

This is less than perfect; it relies on noticing ahead of time that there might be a problem and preemptively shrinking the label.  And it only works in cases where labels have added letter spacing.  A more robust algorithm might notice in the middle of label placement that a label has consistently been hard to place and then look for ways to make the label smaller.  Something to think about for the future.

Here's the full map with labeled features.  With all the heuristics turned on, label placement finds a spot to squeeze in “Bishop Tanpick's Forest" where it barely remains inside the forest and only obscures part of one river:

Various Miscellany (Part 4)

As I was working on the world generation code, I happened to profile the program and notice that the single most costly function was “getPointAtLength".  This is a browser built-in function, and it takes an SVG path that has already been drawn on the screen and a length, and returns the point on the path that length from the start of the path.  This is handy way to find particular points on complicated SVG curves once they've already been drawn on the screen.

In this case, I was using this as a way to interpolate a line as I was rendering it to the screen.  For example, if I want a path to look “hand-drawn", I break it down into additional segments by interpolating between existing points and then perturb those new points.  I was using the browser's “getPointAtLength" because I was drawing curves using SVG's built-in Bezier curves and other features.  But getPointAtLength is not very fast.  Initially that wasn't a big problem, because I didn't use it that often.  However, as the map has grown more complex it was getting called more and more often.

But as the map has grown more complex, I've also been switching over to drawing Bezier curves myself, rather than relying on SVG's built-in Bezier curves.  This makes it easier for me to do things like cut a curve off at a particular point, or combine it with another curve.  When I draw a Bezier curve myself, it's just a sequence of short line segments.  So everything I draw is actually just a polyline and rather than use getPointAtLength, I can write a much simpler function that works on polylines.  So I switched over to doing that, and saved about 25% overall on the code execution time (!).

If there's a moral to this story, it's in favor of delayed optimization.  When you first code something, use the easiest available solution.  If it later turns out to be a bottleneck of some sort, you can always go back and fix it.  (Not always true, but mostly true.)

---

Back when I did the original rules for city names, one of the ways to name a city was to combine a base name with a suffix like “-ville" or "-ton":

Woodford
Hollyville
Potterington
Garmanridge
Greenford
Kileley
Meadowtown
Edgeson
Ridgetown
Stanson

This produces very good names, but one drawback is that some of the suffixes are related to terrain.  For example, towns with “-bridge" or “-ford" suffixes are typically on rivers, so we'd expect to see those suffixes mostly on river towns.  But Dragons Abound has all the possible suffixes in one general list, so you could get a town like “Greenford" far from any river.

To address this, I created new suffix lists for rivers, shores, woods, plains and hills with only the suffixes specific to those terrain.  (I drew heavily on this Wikipedia article.)   Then I modified the naming rules to use both the base list of generic suffixes and the appropriate terrain suffixes when naming a town.  (And in fact, I left some terrain-specific suffixes in the general list as well, because I think it's okay to occasionally get a “Greenford" in the middle of the plains -- maybe there used to be a river there that has since dried up, or it ended up with a -ford in its name for some other reason.  This is fairly common in real-world town names.)  Finally, I need to be able to turn on the terrain specific rules when appropriate, which required adding a new feature to RiTa, the tool I use for name generation.

Here's a map with the new name rules:

If you look at the coastal cities, you'll see that a number of them have suffixes for either being on the shore (-pool, -bank) or for being on the plains (-more).  (The terrain-specific suffixes are only one way to name cities, so they don't show up on every city.)  I'm not sure anyone will look specifically at the names on the map to see if the suffixes make sense, but I think the attention to detail does add to the map's “believability."

---

As long as I'm working on city names, I also want to add an option to name a city that is on a river to something like “Newcastle on Tyne".  This requires a couple of tricks.  First I have to figure out if a city is on a river, and then I have to identify the river's name.  This is a little more difficult than it might seem, because up until now, locations have not really cared whether a river runs through them or not.  Rivers are just paths overlaid on the terrain.  So the first step is to go back to when rivers are created and preserve the connection between the river and the locations it runs through.

That done, I have to modify the name generation process to turn on a new rule for cities on rivers, and in that new rule insert the name of the river.  This requires some more modifications to RiTa, but in the end:

I don't want this to be too common, so for now the rule is only in play for large (“capitol") cities.  These do tend to be located on rivers, so I think I'll see a reasonable number of these names.

Another city name tweak I want to add is the possibility for a capitol city to be named after its territory.  This works much like “upon a river" -- for a capitol city I save the territory name and then turn on a rule to use the territory name for the city:

One problem with this scheme is that the rules that implement linguistic drift can fire on the city name, which could (for example) turn “Tuntun City" into “Tantun City".  That might be okay once in a while, but if it happens consistently I'll have to figure out some way to suppress that drift.

---

Some time ago I switched to a new way of drawing lines where I manually draw a line as a polygon, rather than use an SVG line, which traces a path a circle.  When I implemented that, I gave the lines flat ends -- I just draw a straight line across the width of the line at both ends.  One nice thing about this is that if a line starts at (x, y) then the end of the line is exactly on that point.  One not nice thing about this is that if two lines come to the same point from different directions, they don't match up.  This is apparent when I draw a fat line around a square:

There's a gap where the start of the line meets the end of the line.  They both go exactly to the midpoint of the line and no further.

In most cases this is invisible on my maps, and where it's not I can sometimes work around it.  (For example, in the square above, rather than end at the starting point, I could continue around to the first corner and the overlap would take care of the problem.)  However, it would be nice if the line drawing routine did a better job of this.

This problem isn't unique to Dragons Abound.  SVG/CSS offers three styles of line ends:  butt, round and square.  The way Dragons Abound currently does things is “butt."  “Square" works well for 90 degree angles as above, but “round" is more versatile so I think I'll implement that.

I'll start with a simple flat line:

Now I'll add an additional point at each end of the line that sticks out the width of the line.

Let's try it on an angled line, just to make sure I'm calculating the extension correctly:

Hmm.  Apparently not.  I'm actually calculating from the normal to the line, and I've forgotten (as I often do) to convert properly between the normal and the perpendicular.  Fixing that:

That's better.  I already have a routine that takes arbitrary points and makes a quadratic arc between them.  It isn't really a semi-circle but at the typical line scale it's probably close enough.

Here's how it looks on the box:

The right-angle corner is the worst case but still looks better than using a butt end on the line.

---

I wrote recently about improving the look of rivers, and one of the issues I left for later back then was improving the transition between coastlines and river outlines.  This image illustrates one of the problems:

Here the river has a thin black outline while the coast has a thicker black outline.  This creates a bit of a discontinuity where they meet.  (Upon review: maybe this doesn't strike you as that big a problem, but it bugs me!)  To address this, I'd like to start the river outline off at a width closer to that of the coastline.

The river is drawn first as a solid black line and then as a narrower solid blue line on top.  This creates the black borders (outline) on either side of the river.  To make these wider at the river mouth, I need to increase the width of the black line and taper it off as it goes up-river.  This is non-trivial for a couple of reasons.  The first is that I don't actually keep track of which rivers make it to the ocean and which end at other rivers.  So let me add that info:

Here I've drawn in red the rivers that make it to the ocean.  That looks good.

The second trickiness is in the code that creates the river borders.  It doesn't actually work.  This is my face reading the code:

Not sure what I was thinking with this code, and I'm even more confused why it seems to work.  Regardless, I fix up the problems and implement consistent river borders.  Now it's a matter of increasing the width of the borders near the ocean.  This is not entirely straightforward because the river actually extends into the ocean and then gets clipped to the land.  (This is done to avoid having to figure out exactly where the land ends.)  But I can fudge the end a little bit to account for that:

On these two rivers this works very well on one side of the river and pretty well on the other.  One challenge is that the thickness of the coast line can vary, and I don't know it's actual value where the river crosses it.  So I use the average thickness instead.  Still it matches up pretty well in most situations (and at any rate is certainly better than it was).

You might notice that (particularly when zoomed in) the land peeks out from behind the coastline and there is an artifact where the river joins the ocean:

As far as I can tell, these problems are caused by Chrome's poor handling of clipping.  There's not much I can do about it.  Fortunately at the usual zoom levels this is not really noticeable.

Another problem is evident when the color of the river's border doesn't match the color of the coast line:

This results in a rather abrupt change that creates an ugly discontinuity.  I'm not sure I'll ever use this option but I feel like trying to fix it anyway :-).

What I need here is an option to smoothly change color from the coastline color to the river outline color.  Unfortunately, SVG does not support gradients along a path.  The workaround, as described/demonstrated by Mike Bostock here, is to chop up the path into a bunch of small segments and then color each of those segments with colors from along the gradient.  If you chop up the path into sufficiently small segments, you get a smooth gradient.

I've written previously about how Dragons Abound now draws lines.  In a nutshell, it draws a line as a polygon which essentially traces around the outside of the line.  To make this a gradient, I have to chop the polygon up into segments and then color each segment, like this:

Here I've purposely used only a few segments so that the gradient is obvious.  With five times as many segments, it looks smooth except under close examination:

There are probably some proper ways to do gradients between two colors based upon human perception, but I'm just interpolating evenly in RGB space.

Here's what a gradient looks like when drawing the square I was using to test round line ends above:

When I first drew this, it looked like this:

which was pretty annoying.  The problem is that the browser doesn't try very hard to make sure that paths are drawn exactly, so you sometimes end up with visible edges between two perfectly matched paths.  This is similar to the problem with the clipping at the end of the river.  Eventually I remembered that Martin O'Leary had clued me in to an obscure CSS setting that had fixed a similar problem.  Setting this to “crispEdges" solved this problem as well.

My happiness at this fix was short-lived, though.  I tried drawing a curve:

The jaggedy edges on the gradients curve are caused by the crispEdges setting.  Back to the drawing board.

An alternative fix is to draw a thin line around each segment as it is drawn.  This has some drawbacks but will work to eliminate the gaps between segments.

Unfortunately, I now discovered other problems when trying to draw gradients on lines with sharp angles:

On the lowest line you can see that the angle segments are messed up for the first couple of angles.  This happens because I'm interpolating the line into many segments to make a smooth gradient, and the size of the resulting segments is less than the width of the line, creating problems where the outer part of the line is much longer than the inner part.  I can't think of any easy fix to this problem at the moment.  However, I shouldn't have any sharp angles along the short section of river where I need to use a gradient, so maybe this will be sufficient for this case?  Let's try it on the map:

Angles aren't a problem, but in this view (at 200%) you can see a different problem; the gradient portion of the river looks very sharp and angular.  This happens because it is rendered piecewise, so there's not smoothing of the curves.  I can work around this by interpolating the gradient region at a higher resolution.

And with that I think I'll declare victory and move on.  This is a ridiculous amount of overkill for what is a minor map feature that I might not use much, but if I have an option available I like it to look as good as possible!

---

The work fixing rivers did something that broke lakes.  I've never been entirely happy with how lakes look on the Dragons Abound maps anyway, so I took a little time to fix a few problems. Most of these were slight technical glitches, like having a clipping path on the wrong SVG element, creating a slight bleed from a blur onto adjacent elements (well, I said it was technical :-) so I'm not going to bother writing them up.

A more substantial change was to allow rivers to continue to flow through lakes.  Previously I wasn't allowing this.  If a river crossed a lake it was adjusted to either start in the lake or end in the lake.  The problem with allowing a river to continue across a lake is that it can leave the lake and cross back into the lake, which in some cases looks strange.  However, with the improvements I've made since initially implementing lakes, it now looks better:

On this map, a lake was created on top of a confluence of a number of rivers.  The rivers on the right side of the lake flow across/through the lake.  If you look at these as continuous rivers, it looks odd -- the rivers flow into the lake and then out again.  If you look at the area as all being part of the lake, it looks fine -- there are just a couple of islands on that edge of the lake.  Here I think it looks okay, but in general it doesn't look good.  Often a river just clips the edge of a lake and that makes no sense.

I'm sure I've complained before about lakes.  They're one of the hardest map elements to get right.  Modeling the actual formation of lakes -- filling up depressions in the world, etc. frustrated me greatly the last time I attempted it.  So my lakes are really just “stickers" overlaid on the map.  The rivers just flow as they normally would underneath the sticker.  To make all the rivers coming into a lake flow out of a single exit means resculpting the ground under the sticker.

The basic notion is to find the lowest point in the terrain that surrounds the lake and then modify the height of all the ground in the lake so that it all flows to that low point.  That's not quite as easy as it sounds, but starting at the exit and working your way back across the lake adding small increments to the height works out:

This map happens to have two lakes that flow into each other.  This looks a bit awkward to my eye for some reason that I can't pinpoint.  I find that lakes are under-represented on fantasy maps in general, but this doesn't look too different from the treatments I see.  It will certainly do for now.

---

On the same map with the lakes and rivers, there's a problem with the mountains:

Well, to be honest there are several problems, but I'm concerned at the moment with the mountain that sticks out into the ocean.  Dragons Abound prevents this from happening by making sure that the location of both the left foot and right foot of the mountain are on land.  But when I switched to treating land as polygons,  this test was broken.  The right foot of the mountain thinks it's on land, because at that point the coast outline is cutting across a location in the underlying grid that is partially land and partially sea, and locations like that are treated as land.  The fix is to check instead whether the left foot and right foot are within the coastline polygon.  I also have to take some care in what I use for the left and right feet of the mountain.  I was using the bounding box, but because the baseline of the mountain is an arc, the corners of the bounding box are lower than the ends of the line that defines the top of the mountain.  So I had to quit using the bounding box and instead use the end points of the topline.

With the new test in place, the above mountain is rejected and a different mountain drawn:

Interestingly enough, the replacement mountain's left foot is just barely within the coastline.

Another potential problem can be seen in this example:

Both feet of the left-most hill are on land, but the left foot is on an island while the right foot is on the mainland.  To fix this, I needed to tweak the check to require both feet to be in the same land mass.

---

I'll finish up with the current code counts:

    Source lines of code:  27,789 (23,776)

    Dead/removed lines of code: 8,071 (7,202)

    Sources lines of code in libraries: 21,375 (20,774)

Numbers in parentheses indicate the counts on 8/18.

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.

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.