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.