Monday, October 8, 2018

Lord of the Rings Map Style

This posting by John Nelson has been viral for the last few days -- well, viral in my Twitter feed of cartography nerds, anyway.  It describes how the author re-created the classic Tolkien Lord of the Rings map style in ArcGIS Pro.  (Seems to be a bit of a cottage industry to knock off Tolkien's style.)  It's a fun break from the regular development plan to see if Dragons Abound can replicate a style, so I decided to see how well Dragons Abound could mimic the classic Tolkien map style.

I can't imagine someone reading this blog has never read Tolkien or seen his maps, but if not, here's an excerpt that will give you a sense of the style:
This map was drawn by Christopher Tolkien (J.R.R.'s son) for the original publication of Lord of the Rings.  It's an interesting style, with very heavy mountains, woods and coastlines, red labels and little else.  (In particular, there are virtually no cities marked on the map.)

To start with, I replicated the color scheme of the map, with black borders, red labels and a cream colored background.  The original map is really black & white with red labels, but it was printed on a cream colored paper that in most cases has further yellowed over time.  I like the color combination, so I'll keep the cream colored background for now.
I've also used black rivers as Tolkien used.  However, the coastlines aren't quite right.  Tolkien used a fairly heavy hand throughout the map, and this includes the coastlines.  He also decorated the ocean with two black wave lines.  This is easy enough to replicate in Dragons Abound -- it has a very flexible system for drawing coastal embellishments.
Now let me use a more appropriate font.  The lettering on the original map is hand-drawn, and there's no version of that available.  Nelson used the Aniron font by Pete Klassen, which is based on the font in the end credits of the Lord of the Rings movie, so I'll try the same.
Unfortunately, my program has some problems with this font.  It doesn't seem to be able to accurately measure the size of the font, which results in mis-sized labels and labels that get cut off.  It's a bit of a mess, obviously.  I'll try using Kelt, which is another LotR-inspired font:
This is sized much better, but has another problem, in which some of the letters don't get completely filled.  This turns out to be a 3 year old bug in Chrome.  Frustrating.  Well, I can always use Firefox, which renders the font correctly.

Leaving the broken font rendering aside, there are some invisible rivers that need to be fixed.  That problem is pretty straightforward -- just an error in minimum river width.  The map above also has a faux 3D shading that needs to be removed -- the Tolkien map style is very 2D and flat.

The next thing to tackle is mountains.  The mountains on the LotR map are very bold -- sharp  peaks, thick outlines and mostly solid black shadows.  They are also arranged in long narrow lines.
It's fairly easy to generate mountains with all black shadows that look similar to Tolkien's:
It's more difficult to get anything like the straight narrow lines of Tolkien's mountains.  That's largely because they're pretty unrealistic, as has been pointed out numerous times.  Dragons Abound actually has a way to generate mountains along fault lines, but it doesn't often produce such well-defined narrow mountains ranges.  At best it's an approximate match:
But I won't worry too much about that aspect of the map, since I'm really copying the style and not the geography.

Another unusual feature of Tolkien's mountains is that most of the hills are unshaded:
I haven't done this before, but it isn't too hard to insert an option to turn off shading on hills.
The mountains in this style are so heavy that it is nice to have unshaded hills to lighten the map up a little.

That leaves forests as the last major map feature.  Tolkien illustrates forests as dense maps of egg-shaped trees, bordered by a row of trees with visible trunks:
Tolkien's fill technique is pretty unsophisticated; he basically draws in rows of trees from left to right, top to bottom.  It ends up looking pretty artificial; I probably won't try to replicate that.

John Nelson seems to have replicated this style in ArgGIS by drawing a row of trees along the border of the forest and then filling the remainder with a seamless forest pattern:
Here you can see the obvious edge row, and although the fill pattern is pretty good, if you look closely the repeat is obvious.

I've considered at various times writing code to draw a symbol or icon repeatedly along a path as Nelson does here for the edge of the forest, but I haven't really come up with many problems where I would use that capability.  Nelson needs it because he fills the forest with a static pattern, so the edges would have obvious problems if they were not covered.  But of course, I'll use procedural generation to fill the forest, so that won't be an issue for me.

As long-time readers of the blog are probably aware, I already have the capability to draw forests as individual trees:
These trees are more complicated than Tolkien's trees, but my first thought was to see if I could adapt these trees to produce something like the Tolkien map. Here's an initial attempt:
This is not entirely bad, but there are a couple of problems.

First, the trees are all perfect circles.  That's because Dragons Abound makes clumpy tree shapes by overlapping several circles with scalloped edges.  I can turn off the edges, and only use one circle, but it's not possible with my current code to generate more egg-shaped trees.  Second, the packing of the trees is not entirely satisfactory.  To fill an area, Dragons Abound works from the underlying world locations, which are various sized triangles based upon a Voronoi mesh.  This mesh is not regular, so some areas have many triangles while other areas have few.  The tightest packing Dragons Abound can do is to put a tree symbol in every triangle (as the map above) and this will leave some gaps and some crowded areas.  (There are also some all-black trees generated.  That's just a bug.)  Particularly along the edges it is important to have a tight packing or the forest loses the sense that it's a solid mass of trees.

To start with, let's see if I can generate more egg-shaped trees.  Here's the trees I'm currently using:
Drawing an egg shape doesn't seem to be the most straightforward thing in the world, but according to this page, it's a matter of smoothly lengthening one of the axes as you go around the circle.  (Let's not even contemplate an egg shape that is not axis-aligned!)  In my case, since I want the upper part of the circle to be the longer end, I have to lengthen the y axis when y is less than zero.  (Remember that in SVG, the Y axis is reversed, and negative numbers go upward.)  Here's what that looks like with a modest amount of distortion:
And with a larger amount:
Let me see how a range of these look on the map:
That's a surprisingly big improvement, and probably sufficient.

To address the packing problem, I'm going to try to create polygons for the clumps of forest, and then fill those polygons with trees.  That way I won't be relying on the underlying Voronoi mesh and I'll have more control over placement.

First I need to create polygons for all the forests on the map.  I'm actually already doing this to illustrate forests as masses, so I'm able to easily re-use that now for forests as individual trees.  The Tolkien map also only illustrates the biggest forests, so I took this opportunity to add a forest size cutoff, so that I can create maps with only the larger forests.
Here I've drawn in the two remaining forest areas. You can see quite clearly the varying density of tree symbols when using the underlying Voronoi mesh.  Now I need to work on filling the forest polygons with trees.

If you think of the forest polygons as being filled with an infinite number of points, then the problem is to select some finite number of those points that are randomly but regularly distributed.  This is a sampling problem," so called because we're trying to select a good sample of points.  Mike Bostock has a nice web page explaining why this is useful.  I've had several situations where I would have liked to sample an area in this way, so it seems like a good capability to develop -- I'm sure I'll find many uses for it.

So how can you generate a “random but regular" sampling of points?  The Mike Bostock page also talks about a good distribution that meets this criteria called Poisson-disc sampling, and discusses an efficient algorithm for creating a Poisson-disc sample called Bridson's algorithm.  (More on this and related subjects from Amit and Azgaar.)

One challenge is that Bridson's algorithm provides a sampling for a rectangle, and I want a sampling for an arbitrary polygon.  One way to adapt the algorithm to a polygon is to run the algorithm on the bounding box for the polygon and ignore samples that fall outside the polygon.  This will be somewhat inefficient (in the ratio of the area of the polygon to the area of the bounding box) but should work.

To start with, I'll grab an implementation of Bridson's algorithm from here and use it to sample a rectangle:
To use this with a polygon, I will find the bounding box of the polygon and then generate a distribution within that bounding box, but I will only use the samples that also fall within the polygon:
This works, although as you can see it isn't very efficient -- a lot of samples are generated outside the polygon and will never be used.  To make this more efficient, I can embed a test within the algorithm so that it doesn't explore any point outside the polygon.  As long as I then start the sampling within the polygon (which I can do by picking one of the vertices as the starting sample) and the polygon is reasonably shaped, then the algorithm will only explore points within the polygon or one sample outside the polygon, and will only return the points within the polygon:
Now I can use this routine to generate points for placing individual trees within the forest polygons.  A little tweaking is required to find a spacing that provides a similar visual feeling to the Tolkien map:
Since each tree is individually generated, this doesn't have the outline or pattern fill artifacts seen in John Nelson's ArcGIS map style, or the straight lines of trees from the original map.

Unfortunately, it turns out this has a different problem.  When I went through and eliminated the smaller forest areas, I didn't realize that some of them were actually holes in the bigger forest areas, as shown here:
(Polygon shown in blue and holes in red for consistency.)  This sort of thing is why I hate working with polygons.  In the general case, they're a big mess.  (At least I don't have any figure 8 shaped polygons!)  In this case, I can probably get away with implementing one level of holes.  I hope.

Back to the drawing board.  Here's a polygon with a hole (shown in red):
I need my Poisson disc sampling function to take a list of holes in the polygon and treat those areas the same as the outside of the polygon.  This is essentially just a one-line change:
Seems to work.  So now I need to do the same thing with the forest polygons.  To identify the holes of a polygon, I have to run through all the other polygons and check each one to see if it is inside the original polygon.  (In this case, if any point on a candidate polygon is inside the original polygon, then the whole candidate polygon is inside as well, so I can just check one point.)  Then I pass the list of holes into the Poisson function:
And now the holes are properly empty.

The LoTR map also has a tiny bit of grassland (or maybe swamps) noted -- The Gladden Fields."
The symbols are small, blobby three blade versions of the typical grass symbol.  Let me see how close I can tweak my grass symbols:
It's not quite the same but close enough. I've also dialed back the display of the grass symbols so that there won't be many on the map.

There are a number of features on the original map that I cannot reproduce -- paths and markers of historical events in particular.  But as a last touch, at least one edition of the Christopher Tolkien map had a stylized square compass rose in the upper corner of the map:
I've turned that into a compass rose for Dragons Abound:
I've left in Christopher Tolkien's initials as a tribute.

To finish up I'll add a frame and captions in a book style, and a paper texture background.  The cream map color is a little overwhelming on that background, but the background itself is a pretty good yellowed paper. 

Here's the final result (click through for larger version):
The “Ocean of Ogres" sounds like a dangerous place to sail!


  1. Looks glorious, a very good approximation and it stands out on its own as well.

  2. Amazing piece of art!!

    J.R.R Tolkien has left the chatroom