Haunted Forests

(After a long break to pursue other interests, I've returned to Dragons Abound with some new material.  I have at least a few months of postings lined up and we'll see where it goes after that.  Special thanks to the folks who reached out to ask if I was okay!  I was fine, just off doing other things, but the care you showed meant a lot to me.)

The forests I implemented for “Knurden" style maps (here) are essentially a background color filled with scattered trees, like this:

Partway through implementing these forests, it occurred to me that I could create a “haunted forest" by replacing the forest background color with a blurry grey and making skeletal tree icons.  I set that thought aside, but I did parameterize the top-level routine so that it could work with any kind of tree style and make something like haunted forests easy to implement.  Famous last words!  Let's see how right or wrong they are.

The first step is to pick a clump of forest to make haunted.  I want a clump that is fairly small, like the forest north of the river on this map:

I use the debugger to get the size of that forest, and then just pick a forest of roughly that size to make the haunted forest.  For the moment I draw it as a fir forest to check the logic.  On this map I got lucky and got that same forest:

Eventually I might want to use some additional criteria to pick the forest (such as picking one away from towns) but for now I'll just take the first forest I find that is the proper size.

The next step is to draw in the gray fog.  I'll start with just filling in the forest shape with gray:

This is supposed to be fog, so I'll make the edges indistinct.  Maybe it should have tendrils or wisps as well, but I can always add that later.  And I'll make it somewhat translucent as well.

I like the edges here, but overall this is too subtle.  This might be a good place for a radial gradient, so that I can make it heavier and darker in the center and fading out to the edges.  SVG only supports circular gradients, so the fade will not be consistent but might still look good.  I also played around with using some different colors.  I ended up with this:

This looks pretty nicely fog-like, although it isn't perhaps as menacing as I might like for a haunted forest.

The next step is to add some trees to the mist.  As you'll find if Google it, there are a lot of ways to procedural generate tree skeletons.  A common one is “Lindenmayer systems" (or L systems) which is a family of grammars that can be used to generate tree skeletons as well as other phenomenon.  The trees I'm going to generate are so small and simple that an L system seems like overkill.  So I'll just roll my own and see how it goes; I can always do something more complex later if this doesn't work out.

We'll start with the trunks as a smoothly tapered line:

Of course, scary trees shouldn't grow straight like that, so let me add some jitter:

For tree trunks, I want the jitter to go back and forth (I don't want trees shaped like a big C for example) and I want the perturbations to be pretty sharp, not smoothed out as when I create a “hand-drawn" line.  So I had to create a new perturbation function that alternated the direction to perturb the line.

While I'm at it, I also want to apply a mask that fades out the tree towards the bottom, as if it is disappearing in the fog.  I can do this by applying a mask filled with a linear gradient from white to black.

Note that I've adjusted the mask so that the tree doesn't completely fade away.

Now I need to add some branches to the tree.  I'll alternate sides on the tree and make the branches shorter as they get near the top.  Maybe I'll need branches on the branches, but we'll see.  These icons are pretty small.  To make branches, I'll pick a point on the tree, draw a line straight up, and then rotate it either left or right.  After playing around a bit:

(This is at 150% size.)  This looks sort of okay -- good enough to move forward with putting these on the map to see how they really look.

To sprinkle the trees throughout the fog area, I use Poisson sampling, which I've talked about previously.  It takes a few tries to get a good sampling distance, but that gives me this:

I'm not sure whether I like this or not.  At this scale it is hard to be artistic, but these look (to my eye anyway) to blotchy and clumsy.  I made some adjustments to try to keep white space between the branches and to generally thin down the lines.

The “trees" look a bit like scraggly Christmas trees, but there's a limit to what can be done at this scale.  The trees are also too regular in the fill, but that I can address; I tried a couple of different approaches and settled on this:

Now that I'm more-or-less happy with the look of the haunted forest,  I want to put an appropriate label onto the forest.  And this is where I run into a problem.

As it turns out, the haunted forest above isn't really a separate forest.  It's actually part of the larger forest south of the river.  But maps are often drawn with the forests pulled back from the rivers to show how they run, and so this forest gets split by the Flotilla River and displays as if it is two separate forests.  This becomes apparent if I turn off the option to draw the forest back from the river:

*Poof* no more haunted forest.  (The river should be under the forest, but that's a different problem.)

This matters because naming occurs earlier in the map generation process and works on the intact forests.  So there isn't any way to give the haunted forest segment its own name.  The haunted forest really needs to be its own separate forest.  The best way to accomplish this is to split off the haunted forest earlier in the generation process, and modify map so that it is separated from other forests even if the forests aren't pulled back from the rivers.  That's not so easy to do (and my approach is not particularly efficient) but eventually I have this:

The haunted forest is now on a different part of the map,  As you can see I fixed the error so that the forests are now obscuring the rivers, but I've still pushed the forest back away from the haunted forest even though that's not on for display purposes.  So now I can go back to trying to label the haunted forest.

First I'll just put a placeholder name on the forest.  I'm just reusing the existing forest label code, so this is straightforward.

Next I need to generate a good name for a haunted forest.  I haven't done place names in a while, so I have to go back and re-familiarize myself with the code.  I use a library called RiTa.js which I've modified somewhat to meet my needs.  Names are generated using a (mostly) context-free grammar, which I explained in detail here.  But I don't need to create an entirely new grammar; it should be sufficient to borrow the grammar for naming forests, use a lexicon suited for scary haunted places and throw out any name forms that aren't appropriate.  I can borrow some of the lexicon from the similar Lost Coast names.  With some editing, here's a list of ten random haunted forest names:

• Milky Forest
• Wailing Forest
• Wasted Woods
• Bloodstained Woods
• The Calamity Forest
• The Apparition Forest
• Cruel Woods
• Unearthly Aberration Forest
• Sepulchral Talons Forest
• Foggy Toll

And for my example map:

The “Sunless Forest".  This label style is a little difficult to read on the gray of the haunted forest, so that might need to be tweaked.

The last thing I've added is some code to place the haunted forest as far away from the nearest city as possible.  Although I could see some interest in having a haunted forest right outside of a town, I think on balance it probably makes more sense to have it far away.

And that's about it for the haunted forest, at least for now.  One thing I'm trying to do is stop development of a feature at a reasonable point and let it sit for a while.  Later new ideas might occur to me, or, after having seen it on maps a few times, I might have an idea on how to improve it.  So I'll let this age and possibly revisit it later.  (And if anyone has any good ideas on drawing a skeletal tree better at this scale let me know!)

Next time I'll return to the topic of pencil effects in SVG.

Knurden Style: Completed Maps (Part 7)

As promised last time, some completed maps.  These are 3250x3250 so you will have to click through or download to view full size.  (You may use the maps for non-commercial purposes, if you'd like.)

This was my primary test map.  The city names that lie across islands are difficult to read; I will probably tweak the city label style some to try to address that.

I tried a map using the Mediterranean template that creates a central sea:

With this configuration the central rhumblines become a pretty striking feature.  It's not the sort of thing you'd want to see on every map, but it look pretty good here.  There are a couple of other nice features on this map.  I like the big enclosed bay at the lower right (although “Obvioussland" is not a great name -- I'm not even sure how the name generator came up with that).  The snaky river in the upper left looks very good, although for some reason it got two names.

 

Here's a final map, this time a “coast" map showing one coast of a larger continent:

This one happened to generate a Lost Coast and I've modified the label style for that to fit in with the general style of these maps.  There's also a weird coincidence on this map where one of the rhumblines comes out of the mouth of river which looks strange.

Here's a side-by-side comparison:

You can certainly see differences in the scale and color palette, but overall, I think the finished maps capture a lot of the style of the original map.  

So that's it for Knurden-style maps.  Next time ... haunted forests.

Knurden Style: Labels & Etc (Part 6)

In previous postings, I implemented the major portions of Daniel Hasenbro's Knurden map style, the mountains and the forests.  I also previously handled the shoreline and the basic colors.  There remain a few more elements to implement.

One important element is the labeling.  The excerpt above shows examples of the important label types.

The font used for the labels is one of the IM Fell fonts (DW pica).  The city labels are filled in a light reddish brown, and stroked in a dark red brown.  There are two other potential elements to labels.  The first is a mask that blocks out the background around the letters; these labels do not appear to have any masking.  The second is a halo.  This is usually a white blur that surrounds the letters and also helps separate them from the background.  The Knurden city labels have a narrow, somewhat transparent white blur.  Matching the style is then a matter of trying different colors, sizes, blurs and so on until I get something that looks approximately the same.

The colors are still a little bit off because fonts are treated somewhat different in SVG than in Photoshop, but it's a fairly close match.

The labels for woods use an italic version of the IM Fell font.  The letters are outlined in the same dark brown but filled with white, and there does not seem to be a mask or halo.  The forest labels are also fairly small, about 60% or so the size of the town labels.  But here I run into a problem.

The italic version of the IM Fell font has characters that are a little too skinny at the size I need for the forest labels.  In theory, that's not a problem, because you can change the thickness of fonts by using the CSS “font-weight" style.  By setting the font-weight appropriately, I can get a thickness that is readable and roughly matches the Knurden map.  However, I discovered that setting font-weight breaks the font stroke (outline).  You can make the font fatter, or you can have an outline, but you can't have both.

This is probably because font outlining is done using the generic SVG shape stroking capability.  The text is just treated as an SVG shape and then the perimeter of the shape is stroked to create an outline.  Font weight, on the other hand, is a CSS style feature that presumably happens later in the display pipeline.  If the shape is already stroked, it can't then be made fatter.

As it turns out, there is a CSS style to stroke a font as well, called “-webkit-text-stroke"  So you might guess that it would be possible to use this in combination with font-weight to get weighted, stroked text.  Unfortunately you'd be wrong, as -webkit-text-stroke doesn't seem to work on SVG text.

Another possibility for creating an outline effect is to put two copies of the same text on top of each other, and make the back copy thicker using font-weight so that it shows around the edges of the top copy.  Then make the top copy the fill color and the bottom copy the stroke color, and it will appear that you have stroked the outside of the text in a different color.  And while this does work, it turns out that the difference in thickness between the heaviest and the lightest font weights is still pretty minimal, so that the stroke is very thin.  

Just a hair of black peeking out.  So on a practical level, this doesn't work.

Yet another possibility is to make the bottom copy bigger by changing it's size.  The problem with this idea is that when the font changes size, the individual characters don't stay centered on each other.  The space between characters also gets bigger, and this throws everything off.

In theory I suppose you could handle every character separately and line them up correctly, but ... not going to go down that rabbit hole!

After much experimentation, I found yet another way to get the desired effect.  There's a little-known attribute for SVG text called “paint-order" which can be used to modify the order in which the fill, stroke and markers get drawn.  It turns out that when the stroke is drawn first (instead of the fill), “font-weight" starts working!  

I'm not entirely sure of the reasoning here, but I'll take it!

(I later thought of another way to achieve this effect.  Draw the text first with a thick outline, and then draw the text with no outline over the top.   That might work.  It seems there are many ways to skin this particular cat -- I'm glad at least one of them works!)

With this fix in place it's straightforward to get a reasonably close match:

There are only two river labels on the Knurden map, but they use an interesting technique that is used on other labels on the map as well:

For these labels, Daniel gets a kind of “negative" effect by using a transparent light color for the font and surrounding it with a dark halo.  This is fairly straightforward in Dragons Abound, although it takes a lot of tuning to get the colors close (if not exactly the same):

One problem with this style of label is that it can be hard to read on a busy background:

So I may tweak it a bit to address that at some point.

Ocean labels are much as river labels, adjusted for the ocean colors, so I won't go into any big detail on them.  Region labels are like forest labels, but not italic and in all-caps.

With labels done, I want to go back to forests and pick up an interesting little trick from the Knurden map.  Although forests are done as large masses, Daniel also scatters some solitary trees around the map:

As in this example, the trees are normally scattered around the edges of forests and also along rivers.  The solitary trees sometimes appear as clumps of two, or less frequently, three.

Implementing this was a bit more challenging than I expected.  Finding the border around a shape is not very easy or efficient, and in this case often creates a torus shape (a polygon with a hole in it) which is tricky to work with.  Eventually I settled on iterating over all the underlying Voronoi polygons in the land and deciding for each one whether or not it was in the border area, and then whether or not it should contain a tree clump.  At any rate, after that I have isolated trees around the edges of the forest masses:

Now I can do something similar for rivers.  I'll look for locations near rivers that also have above average precipitation.  (As an aside: I don't actually keep the precipitation values by the time I'm generating these trees, but I do have the biomes for each location, so I can use the biomes as a proxy for the level of precipitation.)  That adds a scattering of trees alongside fertile rivers that get a lot of rainfall:

The last thing I want to replicate from Daniel's map are his rhumblines.  Normally rhumblines radiate from spots in the ocean, or from a compass.  Daniel has done something interesting by making them come from the middle of the land.  This makes them useless as navigational aids, but it looks pretty cool.  It looks a little odd to have these radiate from the exact center of my (square) maps, so I'll offset the lines upward a bit.

The last thing I want to replicate is something Daniel does on the larger islands:

He puts a white circle around the island, and fills the circle with transparent white to lighten the background.  I don't think this means anything; it appears to be just a decoration.  Still, it looks neat and I'd like to be able to duplicate it.

Picking the islands to decorate is an interesting problem.  Daniel doesn't decorate all of the islands, generally avoiding those that are in clusters with other large islands or too close to the mainland.  He also doesn't do this decoration on two islands close to each other.  Here's my first attempt to pick out islands:

I have a test to make sure an island is not too close to the mainland, but I've got the polarity of the test reversed, so I'm picking islands that are close instead of far.  Here's a second attempt:

This is better, but the upper island is too close to another big island.  I want these to be somewhat isolated islands (at least from other big islands).  Filtering for that gets me this:

Now I just need to adjust the circle and fill:

That's a pretty reasonable approximation.

There are a few other features of Daniels' map that I won't be reproducing.  His city icons are little works of art:

And while Dragons Abound's city icons are not terrible, they're not nearly as nice as this.  (But that's something I hope to revisit!)

Daniel also does something nice with his country borders by adding a halo effect:

I rather like that, and stylistically it fits in well with his labels.  Dragons Abound does do country borders and I could add this effect fairly easily, but I'm not happy with how Dragons Abound places borders so I don't use that at the moment.

Finally, there's a coast decoration Daniel does with a looping line on the inside of the coast:

That's very nice but I don't have any good ideas on how to easily recreate it, so I'm going to pass on that as well.

Next time, some complete maps!

Knurden Style: Forests (Part 5)

 In the last posting, I created individual trees:

Now I'll work on drawing forests.

In the Knurden map, forests are blobs with individual trees around the edges (and other decorations):

At a simplified level, these forests are a solid color surrounded by a ring of trees.  But drawing this isn't so easy, because the solid color in the center of the forest obscures the trees on the back edge of the forest and is in turn obscured by the trees on the front edge of the forest.  We can't even draw the back trees and then draw the solid color on top of them, because that would cut a straight edge across the back trees!  So how can we draw this effect?

My breakthrough realization was that the trees on the back edges of the forest are a lot like the partial trees in the middle of the forest.  I could draw in the solid color, and then draw “half trees" along the back edges, and then full trees along the front edges.

To start, I have to figure out how to draw a half tree.  To a first approximation, these half trees are like shortened full trees without the bottom part of the outline.  I'll tweak the shape and remove the outline:

But here the dark shadow on the right side of the tree goes across the bottom, which makes these look like complete short trees.  So I'll adjust the shadow so that it doesn't go across the bottom, so the bottom part of the tree looks more cut off.  And I'll draw the top half of the outline.

That looks pretty good (and this is somewhat larger than the trees will be on the map).

Before I can try these half trees out I need to fill in the solid color blob in the middle of the forest.  These really aren't a solid color on the Knurden map but I'll get to that eventually.  For now I'll just get the solid blob down.  This isn't too hard, because I have another forest style that also starts with a blob of color.  But even if I didn't, this is straightforward: identify the area where the forest will be and fill it with color.

Here I'm using a darker version of the land color; I'll probably tweak that eventually.

Now I need to draw the half trees on the “back" edge of this polygon.  But how do I tell which edges are on the back of the polygon?  That turns out to be surprisingly easy.  Imagine that you're walking around the polygon clockwise:

You'll realize after a moment's thought that whenever you're walking to the right, you're on the back edge of the polygon.  (This is one reason it is useful to have your polygons consistently clockwise or counter-clockwise ordered.)  So I can walk around the polygon clockwise, dropping half trees whenever I find myself going to the right:

One thing to note is that this will drop the trees in the wrong drawing order.  The trees need to be drawn from back to front, and this will often drop trees from front to back.  So after creating the trees you have to reorder them from back to front before drawing them.

The other half of this is to draw full trees on the rest of the polygon.  One subtlety to note before we do that.  Because the back trees are only drawn from the midpoint up, and they're drawn on the polygon, the midpoints of those trees are on the polygon.  So I need to do the same thing with the full trees. I don't want to draw them on the polygon, but shift them down some so that their midpoints are on the polygon as well.  Otherwise the front trees will look taller than the back trees.

Overall, this looks pretty good, but there are a few gaps.  After some debugging work, it turns out these are due to a coding error in my routine to interpolate a polygon.

To place the trees regularly around the edge of the polygon, I'm taking the original polygon and interpolating it to create a new polygon which has a point at every place where I'm going to place a tree.  Interpolating a polygon is a little tricky.  Imagine that you have a polygon and you're going to interpolate it so that you have points at some fixed interval instead of the original points:

Here I have a simple two segment polyline in black, and then I've marked out along it in red new points at a fixed interval.  But what happens when I create a new line based on those points?

Whoops!  I've cut off the original corner.  Less obvious but also problematic is that the last segment is much shorter than the other segments.  We really want an interpolation routine that (1) maintains all the original polygon points, and (2) equalizes the intervals between the new points.  It isn't possible to do both perfectly, but a reasonable compromise is to interpolate each line segment individually, selecting the number of pieces for the segment to get as close to the desired interval as possible.  That gives you something like this:

Now I've retained all the original points, and although the points on the second segment are further apart, I've avoided a very short interval right at the end of the line.

So how do you subdivide the segment?  The basic idea is to divide the length of the segment by the desired interval, and then round that number to the nearest integer.  That gives you the number of divisions, and you use that to calculate the actual interval.  (In the worst case, the actual interval will be +/- 50% of the desired interval, but it will usually much closer.)  Since this is a simple line segment, you can create the intervening points using the slope of the line.  Here's what that looks like in Javascript:

// Divides a line segment into step-sized chunks

function divideLineSegment(p1, p2, step) {

    // How many steps in this line?

    const n = Math.round(Utils.distance(p1, p2)/step);

    const dx = (p2[0]-p1[0])/n;

    const dy = (p2[1]-p1[1])/n;

    const npl = [p1];

    // We do this n-1 times so that we can use p2 as

    // the last point just to be sure it doesn't move

    // because of a rounding error.

    for(let i=1;i<n;i++) {

npl.push([p1[0]+dx*i, p1[1]+dy*i]);

    };

    npl.push(p2);

    return npl;

};

Note the trick here that uses the last point rather than calculate it from the slope.  This makes sure the point doesn't move due to a rounding error.  That's important when we're trying to get things to match up precisely on the screen.

Fixing that routine fixes most of the gaps:

Some gaps still arise where line segments are an awkward length, but happily the effect is actually better with occasional small gaps.

There are a couple of other elements needed to complete the forests.  To give the solid interior of the forest some variety, Daniel does a couple of things.  First, he scatters some treetops throughout the forest.  These are basically the same as the half-trees used to line the back edge of the forest, but to my eye a little bit shorter.  To create a good scatter of trees, I can use a Poisson sampling, as I've done before in similar cases.

That gets me to this:

The second thing Daniel adds are some patches of lighter and darker color, as if you're seeing the highlights and shadows of trees without the outlines.  However, the colors are not paired light + dark as they are in a tree, just scattered about.  I can add these by reusing the Poisson sampling to place light and dark patches.  He just draws these as short vertical lines, so I'll do the same.  The contrast on these is not as obvious as on the tree shadows and highlights, so I'll dial that back as well.

This looks okay, but this sort of thing -- a small, irregular dash of color -- is where SVG is weakest.  These spots lack any sort of character.  I've tried adding a blur, but that is not an improvement.  They're not terrible (especially when less zoomed), so I'll certainly keep them in, but I wish I could do something a little better.

Moving on, the last thing Daniel does is to give the solid color in the interior of the forest a slight light to dark gradient in the direction of the lighting.  This is somewhat harder to do in SVG because gradients are based on the rectangular bounding box of the polygon, meaning that they don't follow the contours of the polygon.  So instead of having the left edge of the polygon be lighter in color, you have the left area of the polygon lighter in color.  Which is not the same thing at all, but if the gradient isn't too obvious it still looks okay in many cases:

A side-by-side comparison of the original forests to the DA version:

Obviously it's not a precise match but I think it's pretty close and the overall “feel" is not bad.

In the course of implementing these forests I realized I already had a couple of other tree styles that could be used to draw forests this way instead of the Knurden-style trees, if I just implemented the half-tree and tree highlights.  This turned out to be more difficult than I expected (largely because of a pernicious bug that took a long time to find) but the results are fairly good:

Here I'm using the “fluffy" tree style, and I've implemented a (fairly rudimentary) half-tree as well as the highlight patches for inside the forest.  You can see some problems (primarily the half-trees along the left edge of the forest) but overall I think it looks pretty good.  The colors are more muted in this style, so it isn't as “graphic" as the Knurden style.

Here's the same forest style using fir trees:

This works better (or at least I like it better), partly because the geometry of the fir tree is closer to the Knurden oval tree shape.  

Next time I'll do labels (*) and clean up some last details.

(*) I came back to this to do the last two hybrid forest styles, so you can see the labels are actually implemented in those screenshots.