Sunday, May 27, 2018

Browser Performance & Web Server & ES6

Since very early in the development of Dragons Abound I have done all my work in Chrome.  This was not through any particular devotion to Google's product, but simply because it was impossible to run Dragons Abound in Firefox.  A run that takes about 90 seconds in Chrome would take 900 seconds or more in Firefox, if it would complete at all.  Most times, Firefox's memory size would grow very large and the browser would crash.

At the time Firefox was my daily browser, so it was pretty inconvenient to have to run Chrome in parallel just for development.  But I soured on Firefox for other reasons (primarily the decision to cripple extensions) and ended up switching to Chrome for all my browsing needs.  When Firefox Quantum came out to much fanfare, I checked performance and while I found it somewhat improved it was still unusable for development.

Earlier today I loaded up Firefox for other reasons and decided to check again to see if any progress had been made.  The first thing I discovered was that Firefox objected to a number of practices in my code.  Chrome is fairly forgiving of minor syntax problems within SVG, but Firefox apparently much less so.  After correcting those errors I made a side-by-side run and was shocked to find Firefox is now considerably faster than Chrome.  On the test run, Chrome took 192 seconds and Firefox took 110 -- that's almost 75% faster.

The two browsers don't report performance in identical ways so it is hard to identify exactly where the majority of the speedup occurs, but it appears that Firefox might do a better job executing certain in-browser SVG functionality, such as getTotalLength.

When I repeated this test on a more powerful machine, I got different results.  In this case, Chrome took about 47 seconds and Firefox about 66 seconds.  It might be that with a more powerful graphics card, the browsers offload the work of rendering the page differently.

Interestingly, on this machine, Firefox registered a large number of errors about fonts and font attributes.  I spent a fair amount of time correcting as many of these problems as I could.  Many of the problems were caused by using empty values for different style attributes.  This didn't bother Chrome, but caused Firefox to throw an error.  Firefox also seemed to have a problem with font names that start with numbers; this was fixed by renaming the fonts.

More serious than these problems was that Firefox on this machine had many problems with the fonts I am using, throwing up many messages along these lines:
downloadable font: GSUB: too large substitute: 1650 
I'm not sure whether these errors were at fault but fonts had problems in this Firefox.  Even Google Webfonts were displaying poorly or incorrectly.

In general, I don't have the time/energy to make Dragons Abound run well in more than one browser, and since Chrome appears to be more tolerant and working fine for now I'll stick with it.  Might be worth looking in on Firefox from time to time to see if these problems get resolved and performance continues to improve.

The above portion of the post was written about six months ago; I decided to look in again on Firefox to see how it has progressed.  I see that I didn't actually note what version of Firefox I was using above.  The current version is 60.0.1 (32-bit).  On the Chrome side, I'm running 65.0.3325.181 (Official Build) (64-bit).  I tested by running each browser once, generating the same map in a fresh tab.  Not very scientific, but enough to give me a notion of the speed of each browser.

Chrome took 157 seconds to generate and render the map; Firefox took 82 seconds.  Firefox still complains about a lot of the fonts I'm using, and it seemed to take a long time to load the page initially.  But to my eye the Firefox map looks identical to the Chrome map.  This is a rather astonishing time difference, so let's see how it breaks down.

These are the top ten time users in the Firefox profile:

14,407.47 ms17.54%Graphics
8,211.89 ms10%GC
7,897.69 ms9.62%pickNextTerritoryLoc
5,739.89 ms6.99%Gecko
4,374.89 ms5.33%windModel
3,043.17 ms3.71%distance
3,026.53 ms3.68%bezierCurveTo
2,742.50 ms3.34%addVectors
2,623.89 ms3.19%JIT
2,518.81 ms3.07%get
2,424.13 ms2.95%valueLocDynamic

“Graphics" is presumably the rendering of the SVG onto the screen.  The SVG that Dragons Abound generates at this point is large and complex, so it's no surprise this is a big job.  Garbage Collection, Gecko and the Just In Time compiler (JIT) are also in the Top Ten -- these are all browser functions that execute the Javascript.  “pickNextTerritoryLoc" is a function that builds the different countries on the map.  Figuring out which location to add next to a territory is laborious and probably unnecessarily inefficient.  I've talked about the “windModel" before.  It just takes a lot of computation to propagate winds across the map.  “distance" is the usual function for calculating distance between two points.  As you might imagine, it's used extensively all over the code.  Two more interesting functions are “bezierCurveTo" and “get".  The former is part of d3.js and is used when I draw anything with a Bezier curve.  The latter is part of the parameter management I wrote about previously.  For every parameter the program uses, it has to check several structures and that apparently adds up (at least in Firefox).

Here's the Top Ten for Chrome:
17790.2 ms11.4%getTotalLength
16300.7 ms10.4%windModel
10744.6 ms6.9%pickNextTerritoryLoc
9744.7 ms6.2%createTerritories
5415.5 ms3.5%Recalculate Style
4383.1 ms2.8%point
3984.8 ms2.6%createBiomes
3808.5 ms2.4%Minor GC
3754.4 ms2.4%distFromOtherLabelsFn
3173.4 ms2.0%polyclip
3074.5 ms2.0%removeChild

Amazingly, it's largely a different list.  Only “windModel", “pickNextTerritoryLoc," “Graphics/Recalculate Style," and “GC" are in both lists.  Looking at those, it appears that Chrome is much faster at displaying the SVG and managing memory to avoid garbage collections.  “getTotalLength" is a browser function that measures the length of an SVG path; it looks like Chrome's implementation of that may be inefficient.  On the other hand, Chrome calculates distance about 12x as fast as Firefox (!).

I did these tests on a moderately powerful desktop.  My development desktop has more memory and a better graphic card.  It's running Chrome 66.0.3359.181 (Official Build) (64-bit) and Firefox 60.0.1 (64-bit).  On this machine, Chrome took 63 seconds and Firefox took about 53 seconds.  The top ten functions were roughly the same, with some swapping around of places.  So whatever makes Firefox much faster on the slower machine appears to be less relevant on the more powerful machine.

On another topic, I currently run Dragons Abound as a standalone Javascript application directly from the file system.  (It loads in the browser as a FILE url.)   There are some problems with working this way, which I've noted before.  Specifically, there's something in modern browsers called the same-origin policy.   The same-origin policy is intended to keep Javascript from one web page executing Javascript from another web page, since this could be used to do things like steal your PIN number out of your banking web page.  However, same-origin policy is only well-defined for protocols like HTTP and HTTPS.  And in particular, it has never been defined for file URLs.  This leads to all sorts of problems when you try to access anything on the local file system from your browser.

I've mostly worked around those problems, but I'm getting ready to switch my codebase over to ES6 modules, and there's another problem with file urls and ES6 modules.  One of the security features of ES6 modules is that they're supposed to only load Javascript -- which they determine by looking at the file's MIME type.  When you try to load an ES6 module into Chrome from the local file system, it complains that the file doesn't have the right MIME type.  (Firefox doesn't complain -- as I said, browser are free to treat FILE urls pretty much as they like!)  It isn't clear whether Windows doesn't report a MIME type or Chrome ignores it -- there are a couple of relevant Chromium bugs open -- but at any rate it creates a problem.

The best solution to all these problems is to run Dragons Abound through a standalone local web server.  Then everything is referenced through HTTP urls and all of the problems with FILE urls go away.  I've resisted this in the past primarily because of inertia, and just the added headache of setting up a local web server and running it whenever I want to work on the program.  So I spent a little time today seeing if I could find a very simple turnkey web server that would make it easy to run a local web server.

I found something called Mongoose.  Mongoose is marketed as a web server for embedded devices -- small electronic computers used in parts of a larger system, like a computer in your toaster.  Obviously I don't care about the embedded device part, but what's relevant to me is that Mongoose is very small and simple, and is available as a one-click Windows application.  I just have to drop it into the folder with the Dragons Abound source code, double-click, and it pops up in my web browser.

Switching over does require a little re-arrangement of my fonts and images (because Mongoose can only see files in the folder it starts in, or subfolders) but that's not a huge problem.

So far Mongoose is working flawlessly. Recommended.

Next up on “Things I've Been Meaning to Do" is to switch over to ES6 modules.  Modules are a way of splitting up code into units that don't interfere with each other.  You can do whatever you want inside a module, and then you just make visible only the important parts.  This makes it much easier to write libraries and generally keep code concerns separate.

Unfortunately, Javascript was originally designed as a kind of quick and dirty scripting language for within web pages, and no one realized that it would grow into the monster it is today.  Consequently, no thought was given to things like modules.  People eventually added in the functionality of modules through various packages like RequireJSSystemJS and so on.  Of course, all these different approaches were only somewhat compatible.  Eventually the Guardians of Javascript decided to build a real module system into the language, and that was ES6 modules.  They've only recently become available across all browsers, so code remains a confusing mix of many different module systems.

Dragons Abound has generally used RequireJS, although for some packages it relies upon I've had to make accommodations for other systems.  But I've wanted for some time to switch over to ES6 modules, if only because the syntax is simpler and cleaner.  So I decided to bite the bullet this weekend and see if I can make the switch.

The first hurdle was just translating all of my source code files from RequireJS to ES6 modules.  This was made a little easier by amdtoes6, a “transpiler" that does the required translation.  I was able to turn it loose on the directory of source files and it did the bulk of the work.  

I say “bulk" because there were a few things I had to fix by hand.  The key part of using ES6 modules is to import into your code the modules you are using.  This is typically shown like this:
import Utils from 'utils';
However, this syntax didn't work for me; I got complaints about relative paths and other problems.  Eventually I settled on:
import Utils from './utils.js';
Which works for me.  The remaining problems revolve around software packages that I use.  A couple (primarily d3js) load as normal scripts fine.  Others (like seedrandom) I can get to work by tweaking the code slightly.  The biggest stumbling block is one of the libraries I use for computing intersections of polygons -- martinez.   This loads without any errors but is not exporting correctly.  All of these libraries have code that tries to work with a variety of module schemes (ReasonJS, CommonJS, etc.) and my best guess is that martinez thinks it is in a different environment than it really is.  When I load it up the export is a function rather than the expected structure.

The solution (or at least a solution) is to add some code that puts the proper structure onto the global where I expect to find that:
if (typeof window === 'object')
window.Martinez = boolean;
In this case, “Martinez" is my name for this module, and “boolean" is the name of the proper structure within the martinez code.  (An odd name, but that's what the author called it.)  The result of this is to make the exported code available as Martinez.intersection(), etc.

With that, everything is working again, now in ES6:

Wednesday, May 16, 2018

Back in the Woods (Part 7): Conifers

In my effort to draw forests as individual trees, I have so far drawn generic deciduous trees -- fluffy round trees like a kindergartner might draw, in other words:
These are the most commonly used tree icons on maps, so they're instantly recognizable.  But some maps use icons that look like pine trees:
These are shaped like tall narrow triangles, and usually colored more blue-green than green.

Since conifers typically grow at higher altitudes and in colder climates than deciduous trees, some maps distinguish trees, using the round deciduous trees on the plains and conifers in the mountains, as in this example:
Dragons Abound doesn't currently distinguish these two types of forest, but since it depends primarily on altitude (height) and temperature, that will be easy to add.

So how do I draw a conifer?  The simple sort of pine tree a kid might draw is made by drawing curved branches in a triangle shape:
How to draw a Pine tree - Step 4
Each branch is essentially three points connected by two arcs:  The two points at the wide interior part of the branch connected by curves to the point of the branch.  The interior points lie along a small narrow triangle and the points are farther out.

I'll start with a triangle:
I'm using a little bit of variance in the width of the triangle.  The interior points for the branches are going to lie along the sides of this triangle.  To find those, I'll break each side of the triangle up into a series of line segments.  Each segment will be the base of a branch.
Which looks exactly the same, because of course you can't see the segments making up the sides.  Let me mark those.
Now you can see (at least on the larger tree) that the sides have been broken up into a number of segments.  It's not immediately obvious, but these vary somewhat in size.  I'll add some variation left and right as well.
That might be too much, but I can adjust the amount later.

To add branches, I'll start again with a simple triangle.  It looks to me like the branches are something like 2-3 times as long as they are wide, so I'll project a point out from the two base points about that distance and insert it between the two base points.
Hmm.  That has a couple of problems.  The branches ought to get narrower (and consequently shorter) near the top of the tree.  So I can't just break the sides up into random pieces, I need to use smaller pieces near the top.  Let me take a step back and see if I can break the sides up into increasingly larger pieces from top to bottom:

Okay, that looks a little better.  Let me turn on the "branches" again and see how they look.
My estimate of branch length looks wrong, but otherwise this looks better.  Let me reduce the branch length:
This looks better, but the branches aren't really visible at map scale.  One problem is that the conifers are at a smaller scale than the deciduous trees, as is apparent if I draw a mix:
So first let me adjust the conifer tree size to make them at least as tall as the same deciduous tree.
The “big" tree is a little overwhelming at this scale, but the map scale trees are now closer in height to the deciduous trees and the branches are visible.  Let me make the conifers broader as well, and throw in the tree trunk and shadow so it's easier to compare.  (These are just copied from the other tree type.)
Okay, the size looks good enough.  The tree still looks a little blocky.  Let me try adding some curve to the branches and adjust the proportions:

The top of the tree looks a little weird, but overall I like this shape.  The bottom is also a little strange, because instead of having a semi-circular skirt, I've got the last branch coming back up to join a straight bottom.  Let me fix those things:
That's getting better.  But in retrospect, I don't really want a semi-circular bottom to the tree, I want a scalloped edge like a row of branches.  That's going to be ... challenging.  Especially to get a whole number of branches across the bottom, and to make the switch from pointing left to pointing right across the bottom.

Fortunately, we had a big wind storm here in Virginia that took out our power for 3 days.  Between my laptop battery and daily trips to the coffee shop, I had lots of time to work on it.  Scalloped bottom:
That's a big improvement.  I was going to make the scallops along the bottom curve like the side branches, but they already look pretty good like this, and I'm not sure any curve would be visible at map scale anyway.  Also, it may not be obvious in this example, but I added some random offsets to the tree, so it sometimes “leans" left or right.

The scallop routine just connects two points with the appropriate scallops, so I can also use it to draw scallops between the other pairs of branches on the tree.  This will add some texture to the tree, the way I added bumps to the deciduous trees to add texture.
The bottom of the tree is pretty wide, so the scalloping always works okay there.  The upper branches get closer and closer together, and eventually there isn't even room for a whole scallop, and I get a little chevron on the upper most branches that looks a little odd.  But at map scale it's not really visible as a problem, and overall this gives the trees a nice graphic arts feel.

Before I go on, let me fix the problem with the top of the tree, where the two lines don't touch.  This happens because the outline of the tree starts and stops there.  It actually starts and stops at the same point, but the width of the line gets drawn to the left on the left side of the tree and to the right on the right side, so the lines only touch at the inside corner.  When you draw a closed polygon, you want the inside of the line to meet and the outside of the line to meet.  In this case, the insides meet but the outsides do not -- to make them meet the outside edges would have to extend far past the actual end of the line.  There's probably some clever point about line drawing I'm missing here, but for my purposes it is easier to fix by moving the start and end of the outline to a different point on the the tree where the lines aren't parallel:
Yes, that's better.

Moving on, another option I added with deciduous trees was a gradient to give a 3D look to the tree.  I can do the same with conifers, although as with peaked roofs, SVG doesn't offer the correct gradient for shading a cone.  I have to make due with a tilted linear gradient:
That adds a little “pop" to the trees.

Another texture option I used for deciduous trees was a noise texture.  I can do the same thing for conifers:
This doesn't look terrible but it doesn't look quite right, either, because conifers have needles, not leaves.  I need a more needle-shaped noise.  I can get that by changing the frequency in just the X dimension to stretch out the noise up and down:
This looks odd on the big tree, but at map scale looks more like needles than leaves.  I'd like to change this texture so that it runs at a slant rather than straight up and down, but SVG doesn't seem to have a way to rotate a filter.  So far StackOverflow doesn't know how to do it either.  Seems like a curious oversight.

A few last things to fix up before I'm done with conifers.  First, let me give them their own color range on the blue end of the green spectrum.
Now let me tweak the forest generation algorithm so that trees in the mountains or in cold areas of the map will be conifers.
Here's an example of a map that shows quite clearly where the average temperature drops and the forests switch from deciduous to conifers.  Also note the conifers around the mountains in the lower right, where they are high enough to thrive.

However, it's a little artificial to have such a clean separation of the tree types like that.  There should be a transition zone with some mix of trees.

Another problem in the above map can be seen right near the center of the map where a mountain is overlapping a conifer.  It's hard to get the overlap correct in all cases, but generally speaking when an element (like the conifer) is further down on the map, it should be on top of elements that are higher up on the map.  But since generation of mountains is separate than generation of the trees, it's hard to get this ordering correct -- I generally have all the trees on top of all the mountains or vice versa.  To fix this, I have to make a list of all the trees and mountains together, sort them by the position of the lowest point on the element, and then go through the list in that order “popping" each element to the top.

This is what it looks like after those fixes:
You can see here that there's a mix of conifers and deciduous trees in the transition zone.  Also, trees are now correctly overlapping mountains.

And that's it for trees, at least for the moment.  I always like the latest thing I've implemented just because it seems fresh, but even beyond that I like the way these trees turned out.

Friday, May 11, 2018

Back In the Woods (Part 6): Shading

Last posting I tackled adding some texture to individual tree icons.  Now I'll look at shading:
In this example, the sun is to the left, so the trees are shaded on the right, by making that side of the tree darker and (in this case) adding a thicker black line on that side for some trees.

This map has a different style of shading:
In this case, the shading is provided by hatching, much as I did for mountains.

The easiest way for me to add shading is to add it in the same way I did to simple buildings when creating city icons, using a gradient.  In this case, I'll use a radial gradient that is light in the center and dark at the edge, but I'll offset it upwards and to the right so that it looks like the sun is coming from that direction:
A couple of things to notice.  First, I'm applying this gradient individually to each of the clumps that make up the tree, so trees with two or three clumps start to show that structure.  It doesn't look very good on the large tree, but at map scale it is a nice effect.  Secondly, you'll notice that the gradient gets dark about halfway across the clump and then stays the same shade the rest of the way.  Why is that?  By default, the SVG radial gradient has the same radius as the size of the object it is applied to.  (How that size is calculated is something of a mystery!)  Since I've shifted the center of the gradient up and to the left, I need to stretch out the radius so it can still reach the far edge of the clump.
How does this combine with the tree textures?  Here it is with the bump texture:
The bumps in the shadow areas get a little bit lost because they're close in value to the shadow but overall it's fine.  And here it is with noise texture:
Suddenly much darker, although I think it looks good at map scale, and very similar to the shading on the “Forest of Reveries" example at the top of this post. 
Of course, I can adjust the noise filter and colors to make this lighter if that's what I want.

I'm not planning at this time to implement the hatch line shading as in the second example above.  I don't think my tree icons are big enough to show the hatching, and there are some challenges in figuring out the area to hatch.

Some maps have a second kind of tree shading, as in this map, The Midlands by M. Plasse over at the Cartographer's Guild:
These trees have a small amount of shading underneath the tree to represent a cast shadow. 

Here's another example from Vellrath by Tommaso Di Giovanni:
In this case, the shadows are drawn quite stretched out, as if the sun is low on the horizon.

In general, for a round tree the shadow is an ellipse cast opposite the direction of the sun.  Since the sun is up high and to the right on Dragons Abound maps, that means the shadow will be below and to the left of the tree.  So to start, I'll create an ellipse with the right end near the trunk:
Here I'm allowing a range of starting points for the ellipse as well as the length of the ellipse.  During map generation, I'll pick one set of values and use them consistently for all the trees.  You can also see that I'm using a pretty crude approximation for an ellipse, but at map scale this isn't visible.

The next step is to fill the ellipse.  To start with, I'll just use a grey color.
It isn't obvious in this illustration, but this is actually partially-transparent black.  By using a translucent shadow, the ground color will show through.  Next I want to add a small amount of blur to the shadow.
Let's try it on a map:
To make the shadows visible on the map, I had to make them almost completely opaque.  As a result, not much of the land color shows through.  So it might be better to use a dark version of the land color for the shadow instead.
Maybe a small improvement?  Hard to say.

And that's about it for shading for now.

Friday, May 4, 2018

Back In the Woods (Part 5): Texture

Most of the maps that use tree icons for forests make the trees looks somewhat three-dimensional by using shading and texture:
In this example, the sun is to the left, so the trees are shaded on the right, and the body of the tree also has a texture that suggests balls of leaves.

Even on maps that are basically flat, there's usually at least a suggestion of shading and texture:
Here the sun is to the right so the trees are shaded to the left.

So far I haven't done any explicit shading or texture in the trees, but when I draw trees as multiple overlapping clumps, I left in the clump outlines, and at map scale it provides some tree-like texture:
I can try to add onto this effect by adding a few single “leaf” bumps similar to the texture in the “Evergrowth” example above.

Of course, if I draw five bumps inside a tree shape I don't want them all clumped up in one corner.  But it turns out that evenly but randomly distributing shapes within a polygon is quite difficult, and computationally expensive.  Simulated annealing is a feasible approach, but I'm not going to implement simulated annealing just to draw tree bumps!  Instead, I'll try for a “good enough" approach.  I'll randomly select the start and end points for a bump within the tree polygon until I find points whose bounding box corners lie within the polygon.  Then I'll check to see if the corners of the bounding box are within some minimum distance of another bump.  If they are, I'll throw out the new bump and try again.

With all that in place and filling with 5-10 bumps inside a tree shape I have this:
It's obviously not perfect.  In the big tree shape, you can see that the algorithm only managed to place 4 bumps, two of them are close together, and one of them goes outside the boundaries of the tree.  On the other hand, the small trees look pretty good.  A few are a little odd but overall it's surprising effective at giving a “tree” texture.  Here's what it looks like on the map:
Which is not too bad.

Another possible method for creating texture is to use an SVG filter.  SVG filters are far too complex to explain here (and my own understanding of them is by no means complete!) but they include a Perlin noise generator, and that can be combined with other functions to create a variety of procedural textures.  In this case, I'm going to modify the “film grain" texture from Inkscape to create a texture that hopefully looks something like leaves:
SVG filters are size-invariant, so the texture doesn't look right on the big example.  But on the smaller icons you can see this is pretty convincing.  Because the texture is based on noise rather than random, the eye sees little clusters and texture in the trees.  Here's what it looks like on the map:
Pretty convincing to my eye, even at such a small scale.

I tried adding the same texture to forest masses:
That's not entirely terrible.  Worth keeping as an option, anyway.  This also looks pretty good when combined with “mottling" where the forest mass is given a patchwork of noise-based colors:
Next time I'll look at adding shading to trees.