Various Miscellany (Part 3)

Some current statistics (8/23/18):

    Source lines of code:  23,776

    Dead/removed lines of code: 7,202

    Sources lines of code in libraries: 20,774
   

I realized my previous code counts were misleading, as I was including packages I didn't write myself (such as d3.js).  This motivated me to move all the various libraries I use into a separate directory, although the SLOC count of the libraries is not entirely accurate, since there are multiple versions of some of the libraries (e.g., both the full and the minimized Javascript).

---

Much of my development work on Dragons Abound focuses on some theme or another:  forests, city icons, etc.  But I intersperse that development with shorter efforts where I do things like refactor code, fix bugs or implement small features.  Every few weeks I try to spend some time generating “random" maps and seeing what problems are revealed.  Developing new features often breaks old features or they interact in unexpected ways.

To aid with this, I recently made an effort to go through the default parameters and set them to values that can generate a wide range of random maps.  (As opposed to particular map styles, where I lock the parameters down to specific values to get a specific look.)  As I was doing this recently, I realized that I really had three different kinds of parameters.

First, I have parameters which are essentially constants.  Typically I created these because I didn't know what value would work, but then I discovered that there's one “best" value.  An example is a parameter called “mtnToplineSegments" which controls the number of segments in the topline of a mountain icon.  This parameter needs to be high enough to provide a reasonable amount of detail in the icon.  For example, a mountain icon with just 2 topline segments would be a triangle -- kind of boring.  On the other hand, I don't want this number to be too high, because it increases the complexity and time it takes to generate and render the mountain icons.  In the end, it turned out that 7 was a pretty good value for this parameter, and there's really no need to change it.  So it's basically a constant.

Second, I have parameters which provide some variation in the individual elements as they are generated.  For example, “mtnRatioRange" defines the range allowed for the ratio (of height to width) of the individual mountain icons.  I don't want all the icons to be the same ratio, so this provides some variation.  By default, this is “[1.25, 1.50]" which means that all the mountains are 25% to 50% wider than they are tall.  During the generation of each icon, a random number is picked in this range and that becomes the ratio for that icon.  I call these “variation" parameters.

Third, I have parameters which provide some variation from map to map but which need to be the same for all the elements on one map.  An example of this kind of parameter is “mtnShadeType".  This parameter controls how shaded areas on a mountain icon are going to be drawn, and it can have a variety of values:  scribble, gradient, contour, flat, gradient+contour, or flat+contour.  But whatever value is used, it needs to be the same value across all the icons on the map.  It doesn't make sense to have some mountains illustrated one way and some another.  So for these kinds of parameters, I really need to make a decision about the value before I start generation.  I call these “choice" parameters.

Confusingly, the parameter types can overlap.  For example, suppose I want to have some maps where the mountains are tall and narrow and others where they are short and wide.  I can control the ratio of the mountains through the “mtnRatioRange" parameter, to get either kind of mountain.  But to get consistently tall and narrow across a particular map I'll have to treat mtnRatioRange first as a choice parameter to get a range, and then as a variation parameter.  Combine this with parameter styles as I discussed recently, and it can quickly become quite confusing to track parameters!

---

One of the first random maps I ran used custom city icons, i.e., the kind drawn by a person and read into Dragons Abound from a file.  But all of the icons were clustered in the middle of the map:

I've seen similar problems before.  The way Dragons Abound places something like an icon is to draw it (or import it, in this case) in the middle of the map and then move it to where it belongs.  When stuff ends up clumped in the middle of the map it's because that update never happened.  This was a little puzzling because I know this style of icons had been working previously.

I figured out that the icons worked if they were allowed to move around the map (like the larger icons are allowed to do to keep them from clashing with something else on the map) but were not working otherwise.  Apparently, these style icons were not being moved to the city's location at the beginning of the simulated annealing labeling routine.  If the simulated annealing labeling routine was allowed to move the icons it would move them to the correct spot.  Otherwise they just sat where they were placed.  The solution was to (duh) start them in the correct spot:

And that takes care of that.

---

Here's a problem with the mountains on that same map:

You can see where I've circled in red that some clefts have been added to the mountains.  But instead of being mostly vertical, these clefts are slanted too much to one side.  I'm fairly certainly the problem is in a routine that adds “lateral breaks" to the mountain's topline, but this sort of thing can be hellish to debug because it's really hard to look at the numbers and figure out if they're right or wrong.  So I revive some of my testing code that draws a single mountain with lots of debugging outputs.

Fairly quickly I find at least one problem.  I have a routine “findPointAtX" that walks along a polyline (like the topline of a mountain) and finds the first line segment that contains a particular X coordinate.  It looks like I rewrote that routine at some point and made a subtle change in the return values, and that has broken the routine that adds vertical breaks to mountains.  Taking account of the new return values fixes vertical breaks:

The vertical breaks are where the descending lines are drawn.  So that's fixed, but I use findPointAtX in a number of places; I need to check all of them.

The next problem that pops up is this:

The ridge line from the dip to the corner of the mountain is supposed to go mostly down and some to the right, but it's being drawn to the furthest right point of the baseline.  It's fairly easy to find the point where the ridge line is created and spot the problem.  When I went through the default parameters to set up a good variety for random mountains, I fixed the name of this parameter -- but missed correcting it in this routine.

This doesn't give me much confidence in my changes, though!

---

One map run produced bright pink city icons:

It turns out I had that color in the list of possible icon colors; I'm not exactly sure why.  Anyway, it's not in there any more!

Speaking of city icons:

I like the look of these icons, with the grey buildings, colored roofs and a heavy outline.  But the icons for Omke and Peban have a problem.  It may not be entirely obvious, but the city wall does not extend far enough to the right to cover all the city buildings.

The reason is (I think) fairly straightforward.  I'm finding the leftmost and rightmost points for the wall by looking at the first and last building generated.  However, in some cases the last building generated might not be the furthest to the right.  Buildings can also have secondary buildings, so I need to check all of those as well.  That should fix the problem (although I forgot to save the random seed for the above map, so I can't regenerate it to check).

---

During my testing I generated this map:

The first thing to notice is that the ocean illustration in the center of the map is not getting masked properly; the underlying ocean lines are showing through.  For various reasons there's a complicated hierarchy of layers in the ocean; it looks like the problem here is that the correct layers are not getting masked.

That fixes the illustration problem.  However, I don't much like the look of the ocean lines in this map.  They really dominate the map when they should be more subtle.  This is an intentional style, modeled after this example map:

I've never really loved this effect, especially when (as in the example above) it is so obvious that it takes over the whole map.  It occurred to me that it might be better if the lines faded away as they got farther from shore, so I added that as an option:

That actually turns out to be a cool effect, giving the sense of ocean depth.

---

Here's an excerpt of mountains from a map:

There's something odd going on with a few of these mountains.  They're very narrow and tall.  Mostly they're also short, but there's one (which starts behind the “I" in the city name) that's also quite tall.  This doesn't happen very often, and not on every map, so it's probably a problem with the random parameters for the mountains creating some undesirable combination.

However, after some debugging I realize it's not a problem with the mountain parameters, but instead a case where the union of two mountains fails.  The mountain generator merges two mountains in various places.  One example is where it adds a little “rubble pile" to the base of the mountain.  It does this by creating a very small simple mountain (the rubble) that partly overlaps with the real mountain, and then takes the union of the two mountains.  In this case that union was failing and returning the small spiky remains.

I've chronicled my problems with polygon union on this blog before.  It's hard to find a polygon union in Javascript that is (1) correct, (2) fast, and (3) easy to use.  And to be fair, I've made matters worse for myself by assuming that a union of two polygons should return a single polygon.  I only use union in cases where that *should* be true, but occasionally it isn't true either because the union algorithm is wrong or I've used it incorrectly.  At any rate, my general approach when a union returns multiple polygons is to keep the biggest and throw away the rest.  In this case, that logic was broken as a result of some other changes, so I had to go back in and reinstate the correct logic.

---

Another long-term struggle for me has been getting Dragons Abound to reliably generate the same map over again.  The major problem, of course, is that Dragons Abound makes a lot of random choices when generating a map, so it's unlikely to make the same choices twice in a row.  But of course, computers don't actually use random numbers, they use pseudorandom numbers -- numbers that look random but are actually generated in a specific sequence.  So if you want to get the same sequence of random numbers a second time, you just have to take care to start in the same spot.

Javascript doesn't actually provide this capability, but it's easy to find a replacement random number generator that does.  With this kind of random number generator, you can feed in a starting point (called a “seed") and get back the same sequence every time.  So swapping this in for the usual Javascript random number went most of the way to being able to recreate a map.  Just feed in the same seed and get the same map.

Except it didn't quite work that way.  There would always be a few small differences.  I finally got tired enough of this that I spent a few days tracking down the problem(s).

One thing I discovered fairly quickly was that in a number of spots I was using d3.randomNormal instead of the usual random number generator.  The usual random number generator provides uniformly distributed numbers, usually from 0 to 1.  This means you're just as likely to get any number between 0 and 1 as any other number.  But in many cases, you don't really want a uniform distribution.  If you're randomly generating the heights of men from (say) 4 feet tall to 7 feet tall, you don't want as many 4 foot tall as 6 foot tall men.  You want a bell shape curve centered over the median height, so that you get a lot of 5' 8" tall men and very few 7' tall men.  This is a “normal" distribution, and that's the sort of distribution that d3.randomNormal provides.  But the way I was using it, d3.randomNormal was still using the default Javascript random number generator, and so its output wasn't repeatable.

There are a couple of ways to fix that problem.  A simple random normal generator isn't hard to write, but as it turns out d3 provides a way to specify the source random number generator used by d3.randomNormal.  By telling d3.randomNormal to use the seeded random number generator, it becomes repeatable.

However, there still remained some areas where the map was diverging the second time I generated it.  After much debugging, I figured out that there were some changes in the parameters that were carrying over from the first run into the next run.  The reasons why are complex and not particularly interesting, but essentially, the first time through Dragons Abound was making some choices -- say, to fill region labels with white -- and that choice was being remembered in the second run.  That by itself was okay -- I wanted the program to make the same choices! -- but it also meant that the program used one less random number the second time around, because it didn't need one to make that choice.  And now the sequence was off by one random number.  The solution in that case was to be a little more careful not to carry over any parameters from the first run to the next run.

However, that still didn't fix everything -- specifically, I was still getting different place names on different runs.  The problem in this case was that the tool I am using to generate place names -- RiTa -- was somehow still using the default random number generator.  Logically, it should have been using the new seeded random number generator, but debugging confirmed that it was still using the default generator.  I'm not exactly sure why -- probably some kind of subtle scoping or optimization problem.  The solution was to modify the RiTa code to allow me to provide the random number generator to use.  Then I could pass in the seeded random number generator and force RiTa to use that.

Now I could run the program twice in a row and get the exact same output.  But when I reloaded the page and ran it again, I still get slightly different output.  (But repeatable!)

Several *days* of debugging later I finally trace the difference to part of the mountain creation code that is adding ridge lines.  Eventually I realized (duh!) that the noise generator being used by this code is being initialized as a global.  In Javascript (as in most languages) there is no guarantee about the order of initialization, so apparently the noise generator was getting initialized (which uses some random numbers) *before* the seeded random number generator replaced the default random number generator.

The fix is just to initialize it as part of the regular code flow.  And that -- finally -- is the last non-repeatable element of the code.  Now I get exactly the same output from any particular seed no matter when I load or run the code.

Although at this point I don't recall exactly why this was so important to me :-)

---

One improvement I've been meaning to get to for some time is to add the ocean illustrations to the label placement routine, so that they can “float" to a better position if the original placement has a problem.  The original placement routine is pretty good, so it's hard to find really serious problems, but here's a mild example;

Here's the label for “Latun's Village" ends up sticking out towards the ocean illustration.  A better placement would move the illustration away from the label to create better separation.

To do this, I need to turn the image into a label and let the label placement routine try to find a better location.  This isn't too difficult; I just turn the image into a label and make sure it has the criteria to maximize the distance to the nearest other label:

Here the black box shows the original location of the label and the purple box the final location.  The Illustration has moved away from the city label.  Unfortunately, this has placed it pretty close to “Ta Island".  This can be improved by tweaking the criteria for this label, but the real solution is to make the ocean illustration also want to stay away from features (like the island) as much as other labels.  That's not a criteria I currently use but it isn't too hard to add.

And now the illustration has pushed up and away from the island to the lower right.  It isn't precisely centered because it has some other criteria to fulfill, but this placement is better than the original placement.

---

Floating the ocean illustration immediately causes another problem:

The ocean illustration has floated under the compass rose.

In this image I've added green boxes for all the features that the ocean illustration should be trying to avoid.  You can see there's no green box around the compass rose.  There's actually supposed to be, but the code for it is broken.  That error was never apparent before because there's not been anything in the ocean to clash with the compass rose.  But now that the ocean illustration can float around it can happen.  

The solution is to fix the compass rose code to mark it correctly as a map feature to avoid:

Now the illustration has avoided the compass rose.  By the way, the compass rose box looks “too big" because the rose is actually a square image that is slightly rotated.  The slight rotation keeps the rose from looking too rigid and artificial, but it also causes the bounding box to be bigger.  (If the bounding box itself was rotated it would be smaller, but the bounding boxes are aligned to the axes.)