## Monday, March 20, 2017

### One of the (Forest) Masses

In the previous posting I discussed how to draw a shape like a fluffy cloud.
I want to apply this to draw a forest on a map as a mass of trees, like a simple version of this:
Basically a green blob with a cloud edge.

The first step is to get the basic shape of the forest on the map.  This is surprisingly complex.  First of all, I have to generate biomes on the map.  I talked about that in this posting.  Here's my usual mountain map with biomes colored in:

This part of the map has only two biomes -- the light green represents grasslands, and the dark green represents forest.  (You can see, by the way, that mountains are not a biome.  There are forests in the mountains.  This is problematic -- most fantasy-style maps don't try to depict any biomes in the mountains.)  When I eventually draw in the forests I won't have this biome coloring turned on, but I'll leave it in for the purposes of this post.

The next step is to get paths representing the edges of the forest.  The basic idea is to look at every location on the map.  If a location is a forest, and a neighboring location is not, then the edge between those two locations should be part of the forest edge.  Identifying those edges is not too difficult, but chaining all the edges together to create continuous paths is a bit more challenging -- particularly because you cannot count on finding the edges in any particular order.  This general problem -- finding the edges in the world where some condition changes -- comes up fairly frequently.  For example, the coast is just where the height of the land changes from positive to negative.  So it's useful to have a generalized function that takes a condition and returns all the edges where that condition changes.  So I can use that function to identify the forest edges.

At any rate, once I have all those edges I can draw them on the map.
To understand some of the challenges of creating these paths -- look at the little bowtie in the lower middle of the map.  There are a bunch of different ways to connect those line segments together into paths -- getting that right is not trivial.

Once I have the paths for the forest edges, I can draw them in using the cloud effect for the edges instead of straight lines.  Here's the first attempt:
At first glance, that's not too bad, although there are clearly some problems.  In various places (e.g., on the left side of the middle-bottom), you can see that the woods outline has "loops" in it.  In the middle upper-left, there's a spot where the bumps are going the "wrong way" -- the bumps are pointing into the forest rather than out of it.  And in the upper-right you can see that the size of the bumps varies pretty radically from tiny to much bigger.

Some of these problems can likely be fixed by simplifying the forest edges.  The edges you get when you subdivide the map on a condition tend to be pretty complex, so I already have a couple of functions to simplify paths that I've used on things like the coasts and rivers.  One smooths out the path, eliminating most small sharp deviations.  This will probably fix most of the loops in the edges.
And indeed, you can see that most of the loops are gone.

The sections of the map where the bumps point the wrong way are probably where the path for the edge of the forest goes clockwise instead of counter-clockwise.  (Or vice versa.)  To fix that, all I need to do is detect when the path is going the wrong way and reverse it.  But how can you tell if a path is going clockwise versus counter-clockwise?  I don't entirely understand the method myself, but you can find it discussed in this Stack Overflow question.  Applying a version of that and reversing the counter-clockwise paths gives me this:

If you look at the "hole" in the forest you'll see that the bumps now point in the right direction.  (There's still a broken forest in the upper-left that I didn't notice until later; that was a bug that I eventually worked out.)

In this run I accidentally wrote the forest outline on the wrong layer, so you can see some of the forest edges where they normally would not be displayed, such as along the coast.  Because the forest comes all the way to the coast, the bumpy edge of the forest mostly is drawn out in the water, where it is normally masked away and not seen.  Most fantasy maps back the edge of the forest off a bit so that it ends before the coastline, so let me address that.

To pull the edge of the forest back from the coastline, I treat forest locations near the coast as a different biome, which effectively draws the edge of the forest in some distance from the coastline.
Overlapping forest symbols and mountain symbols makes a mess, so most fantasy maps also avoid drawing forests in the mountain areas.  This is a bit more difficult.  The obvious approach is to avoid all the locations that are above the minimum mountain height, much the same as I did with the coast.
That works okay, but there's still some overlap and it tends to produce little holes and clumps of forests.  The overlaps occur because the mountain symbols are (much) bigger than the locations they represent.  (And to a lesser extent because of the line smoothing and small edge removal in drawing the forest.)  I could tweak this by forcing the forest to an even lower elevation, but that's likely going to work poorly on some maps.  A more robust approach is to check against the mountain symbols themselves and drop any forest locations that intersect with one of the mountain symbols.  Here's the map showing all the bounding boxes (with a good deal of margin added):
That's quite busy, but you can see that it has mostly pushed the forest back away from the mountains.  Here it is with the bounding boxes removed and the spacing a little tweaked:
So that's the basics.  This came together much more quickly than I expected, thanks in part to being able to reuse a lot of the path code I'd already developed.  Next time some tweaks and improvements.