Thursday, February 23, 2017

The Sunny Side of the Mountain

The other day I was admiring the mountains in Kacey's amazing Ehren map:
I really like his shading approach.  (But go admire the whole map, it's well worth your time.)  One element of the shading is contour hatching with trailing lines behind the ridges.  That's not too different from the scribbled hatching I've been using, so I thought it would be a fun experiment to implement that sort of shading.

The basic approach is pretty straightforward -- rather than drawing back and forth as I do with scribbles, I just draw in one direction.  On top of that, I make each line trail off as it is drawn, so that it starts thick and gets thinner.  Finally, I have to do some tweaking on the lit side of the mountains, since the shadows there should be lighter there than on the other side of the mountain.
I think this looks pretty good.  Here's what it looks like on the map:

Here I have the shadows darkest right at the ridge lines.  That might seem backward; you might think the shadows should be darkest where they are farthest away from the ridge lines:
Orienting the shadows that way makes the mountains look more rounded.  I think I prefer the first version, but the program can easily generated it either way.  It's also easy to generate solid lines:
This gives a more two-dimensional / graphics arts sort of feel, but looks very flat on a map.

In Kacey's Ehren map, he also puts a gradient underneath the contour shading to add more depth.  SVG does linear gradients, so let's see how those look as mountain shading.  There's a lot of possible complexity here, but I'm going to start with a simple right to left gradient from 70% transparent to fully transparent:
And here it is combined with contour hatching:
And with reversed ("rounded") shading:
Here's what gradients + contours looks like on the map:
Overall, I like this a lot, and it's now the default shading for the mountains.

Saturday, February 18, 2017

A Mountain By Any Other Name Is Still a Hogsback

In its current incarnation, Dragons Abound doesn't name its mountains.  Originally, all of the terrain was generated with noise functions, and the mountains just showed up wherever the noise function produced a large value, so the program didn't understand that one area was mountains and another was not.  But as I've discussed in previous posts, the program now intentionally creates mountain areas, so it's more feasible to name the mountains.  So how do mountains get named?

Many mountains (and terrain features in general) are given proper names -- these are unique names that don't have any other meaning, like the "Appalachian Mountains."  These are often derived or shared with other features.  For example, the Appalachian Mountains are derived from the Apalachee tribe of Native Americans; in turn that name seems to derive from the name of the village where Spanish explorers first encountered the tribe.  Similarly, the Allegheny Mountains are named after the Allegheny River, which derives from the Lenape tribe's words for "fine river".  But these days "Allegheny" is just a name that doesn't have any other meaning.

Other times mountains are given descriptive names, like the "Rocky Mountains" or the "White Mountains" of New Hampshire (and other places).  One imagines an explorer saying to the mapmaker, "And across this area was a long range of white mountains..." and that description becoming the accepted name.

Finally, there's the "Mountains" part of the name.  This takes on many forms, such as "Hills", "Cliffs", "Buttes" and so on.  These are all synonyms for mountains, or for related mountain-ish features.

Putting that together, I can generate the name for a mountain range by generating a proper name + a mountain word (e.g., "The Numping Mountains") , or a descriptive phrase + a mountain word (e.g., "The Gravel Mountains").

It turns out that generating proper names is fairly easy for me, because Martin O'Leary already wrote some code to invent names in recognizably distinct languages that I'm using to name other map features like cities and rivers.  It even has the capability to generate a series of names that share some linguistic features as if they all come from the same class of names, e.g.,
so I'm not going to spend a lot of time on that aspect of naming mountains.  At some point I may want to generate names that are more recognizably English, but that's a problem for another day.

Generating descriptive phrases is a bit more challenging.  A simple approach would be to pick a random English adjective or noun, and this works better than you might expect, because the human brain is so adept at rationalizing names.  To pick a random example, "The Wagonwheel Mountains" seems perfectly fine.  "The Loud Mountains" is a bit more jarring, but you can understand how that name might have been invented.  However, a lot of choices strain rationalization: "The Chlorophyll Mountains", "The Adaptable Mountains" and so on.  To work well, the descriptive phrase needs to have a semantic connection to the physical reality of the mountains.  "The White Mountains" is natural-sounding because mountains can be white colored; "The Adaptable Mountains" sounds strange because it's hard to imagine how mountains can be adaptable.  Unfortunately, understanding the semantic validity of a phrase with respect to a mountain is not an easy task -- this is the sort of thing that natural language processing and artificial intelligence struggles to solve.  If only someone had already compiled a list of words that could be used to describe mountains!

Of course, such a list does exist -- or at least in theory:  A list of all the real-world mountain names.  If I had that, I could pull out the adjectives and nouns that people have used to describe mountains.

As it happens, such a list does exist, at least for the United States.  (And, oddly, the Antarctic.)  The US Board on Geographic Names is a federal agency founded in 1890 to keep track of the official names of geographic features within the United States.  And thanks to the federal laws that require agencies to make this sort of information publicly available, you can download all the geographic names in the United States here.  What you get are huge data files that list the names of geographic features, the type of feature (e.g., Stream, Forest, etc.) and other information such as location.  For example, the first part of the file for Wyoming looks like this:
169560|Gibson Blair Ditch|Canal|CO|...
169563|Roosevelt National Forest|Forest|CO|...
169581|Crow Creek|Stream|CO|...
There's a lot of information about each feature, but for my purposes I can pull out the name and the feature type and filter down to just the mountains to make a list of all the mountain names in the US.  Here are the matches for Wyoming:
169920|Sierra Madre|Range|WY|...
170032|Medicine Bow Mountains|Range|WY|...
170426|Front Range|Range|CO|...
378928|Caribou Range|Range|ID|...
382164|Gannett Hills|Range|WY|...
768433|Badger Hills|Range|MT|...
The USGS feature type for a mountain range is "Range" (and for an individual mountain, "Summit", although "Cliff," "Ridge," and "Slope" are all used for other mountain-like features).  You can see that some of these ranges start in other states and cross into Wyoming.

Once I have a list of mountain names, I want to pull out all the descriptive nouns and adjectives.  If I assume that the last word in the name is the equivalent of "Mountains" then I'm left with a list like this to parse:
Medicine Bow
You can see already that this isn't going to be perfect, but it will hopefully get down to a list that I can curate by hand.

The next step is to label the words in this list as either adjectives or nouns.  I'll pass this job off to the Natural Language Toolkit.  This is a Python library that provides a number of handy natural-language processing functions, including classification by part of speech.  Classification works best when you have a full sentence (consider "He was a major" versus "It was a major problem") but for my purposes I can use the most common part of speech for a word (e.g., "major" is more often an adjective than a noun).  Conveniently, this can also tell when a word is a proper noun (or at least isn't recognized as any other word type) so that lets me filter words like "Sierra" and "Gannett" out.

I'll use this to go through the list and count the occurrences of each word.  So for example, the five most common nouns used to describe mountain ranges in the US are:
  1. pine: 767
  2. creek: 724
  3. rock: 523
  4. horse: 437
  5. buck: 426
There are 2600 nouns in the full list, including almost a thousand that only appear once, such as "bagpipes", "magicians", "library" and "clamshell."

I can do a similar analysis to get a list of adjectives:
  1. bald: 1037
  2. black: 971
  3. red: 955
  4. big: 871
  5. round: 717
This list is much shorter:  430 in total, including 161 that only appear once (alien, suburban, biological...).

The final step is to do the same analysis for the last word in the name of the mountain range.  This gives me a list of synonyms for "mountains":
  1. Hills: 1617
  2. Mountains: 1239
  3. Range: 479
  4. Buttes: 432
  5. Peaks: 319
It's interesting that "hills" are more common than "mountains" in the US.   This list is much shorter, with only 58 entries and no odd words except perhaps "Hogsback" and "Nubbles" (which appears 22 times and apparently means "a small nub"). 

With these lists generated, I can now name mountain ranges by the noun + a mountain synonym (e.g., "The Pine Hills"), the adjective + a mountain synonym (e.g., "The Bald Mountains") or a combination (e.g., "The Bald Pine Range").  The count of occurrences for the words can be used to determine the frequency of generation, so that I get "The Red Horse Peaks" much more frequently than "The Alien Bagpipe Nubbles".

There are actually many more named individual mountains in the US than named mountain ranges.  I can do a similar analysis on those names.  The main difference is more variety in the "mountain" synonym.  The five most popular are:
  1. Mountain: 22221
  2. Hill: 17126
  3. Ridge: 12842
  4. Peak: 7089
  5. Butte: 3937
And further down the list you get some interesting variants like Whaleback, Airy, Comb and so on.  I hadn't considered naming individual mountains, but it might make sense for (say) the tallest mountain in an area.

Monday, February 13, 2017

Mountain Placement

With the mountain drawing finished (for now, anyway) I want to turn my attention (at least briefly) to the problem of placing the mountain symbols on the map.  This is a challenge because the mountain symbols don't correspond one-to-one for mountain locations on the map -- that is, they symbolize the mountains, but there isn't a mountain symbol on the map for every mountain.  So I have to choose what symbols, how many, and where to place them to symbolize the mountains on the map.

Figuring out where the mountains are on the map is straightforward.  Like most procedural map generation, I have a height map for the world.  I decide what percentage of the map should be mountains (this can vary, so that map might have lots of mountains or few mountains) and declare that percentage of the highest land locations "mountains".

My initial approach for placing the mountain symbols was to go through the map from North to South (essentially from back to front) and when I hit a mountain location, I check to see if there's already a mountain symbol on the map within some distance (based on the size of the symbol I would put down for this location) from this location.  If there is, I skip putting down a mountain symbol.  If there isn't then I put down a mountain symbol for this location and continue on.

That approach was used (for example) to generate this map:
This works okay, but one drawback is that it essentially picks the locations to illustrate with symbols at random.  On the theory that the big mountains are more important, I rewrote the algorithm to walk through the mountains from biggest to smallest, so that the tallest mountains get drawn preferentially.  
I'm not sure this noticeably improves this particular map, but I think it will produce more consistent results.

By varying the distance to exclude other mountains, I can control whether the mountains are sparse or dense on the map.  Dense layouts have a certain appeal -- the mountains almost form a texture:
On the other hand, a sparse layout isn't terrible, and might look better on a map that was already busy with other features.

Right now, I'm calculating the exclusion distance as a circular radius around a location.  A more sophisticated approach would be to create a bounding box around the mountain, or even intersect the actual symbols.  But I'm not sure that would add much value.  I'm not trying to make the mountains never overlap with each other.  A certain amount of overlap is good, and the semi-random occurrence helps create some interest as well.

You may recall from a previous posting that Dragons Abound can generate mountain ranges that extend along a fault line.   How does my current mountain placement do with that?

This isn't perfect -- it would be nice to have a unified set of similar mountains running down the spine of the mountain range -- but it isn't terrible.  You can see mountain passes and some high valleys in places.  And it's a lot simpler than trying to figure out the "spine" of a mountain range and how to place symbols along there :-).

Monday, February 6, 2017

Adding the Details

In the previous posting, I developed a new family of mountain outlines.  Now I'm going to add back in some of the features from my previous mountain work.  This is mostly a matter of re-using the existing code, so I'm not going to go through it all again in detail.  First up is to add the scribbled shading.
In keeping with my new philosophy about a seamless sequence from tallest mountain to shortest hills, when I added in the shading, I modified the existing code so that as the mountain gets smaller, more curve is added to the ridge line that defines the shading, so that the low hills look more rounded and soft than the high mountains.
Now I'll add some back-and-forth perturbation of the ridge line with the same philosophy: the magnitude of the perturbation will diminish as the mountain gets smaller.  Here it is outlined in red to make it obvious:
The tall mountains get lots of back-and-forth in the ridge line, and the low hills virtually none.  Here's what that looks like on the map, with the ridge line drawn in to make it more obvious:
Next, let me add in a tapered foot.  Low mountains get a long smoothly tapered foot while the tall mountains get little or none.
Now I will add perturbations to the mountain outline.  This adds noise in the Y axis (up and down) along the contour as well as a smaller amount of noise perpendicular to the contour.
Combining two mountains into a single mountain:
Lastly, I want to add back in "clefts" which I've generalized (largely due to admiring this map) to be on either side of the mountain:
On a previous posting, someone on Reddit (account since deleted, so I can't credit him) suggested making the base of the mountains rounded downward to indicate depth.  I've implemented that:
And then added some jagged perturbations to that, decreasing with the size of the mountain:

There are a few other features from my original mountains that I'm not going to re-implement, mostly because at map scale they turned out to be (largely) irrelevant.  So here's what the new mountains look like on a map, side-by-side with the old version:
Obviously there are some superficial differences here in line size, placement, etc., but overall I'm happier that the feel of the mountains is more consistent and organic.  There's also obviously some work to be done on placement of the mountain symbols.
And just for fun, here's the same map rendered in the "D&D" style:

Wednesday, February 1, 2017

Or Maybe Not, Let's Try Again

In my last posting I developed the routine that generated a smooth sequence from high peaky mountains down to low curvy hills:
I'm going to try to avoid the mistake I made last time around of not looking at these on the map until too late, so I need to add some basic capabilities to put these on a map: masking out the background, scaling and translating, and perhaps simple shading.

Masking is fairly straightforward -- I just need to take the outline of the mountain, connect it across the bottom and fill that with the background color.  It's also good to add a little buffer at the bottom of the mountain so that another mountain "behind" the front mountain doesn't peek out.  To test this I need to fill with a color different than the background.
That seems to be working.  The funny little bulge at the bottom right of each mountain is where the outline turns a corner.  I'm using a line-drawing routine that tries to draw smooth curves, so that right angle turn becomes that little bulge.

So far I've just been drawing the mountain outlines at their final size.  Instead, I need to draw them all at a fixed size and then use a scaling transform to make them their final sizes:
Here I've run into one of the problems with scaling this way:  The line width also gets scaled.  If all the mountains are close to the same size it isn't as obvious.
But it's still something I need to address.  The solution is to make the lines thicker as the mountains get smaller, although it turns out that a strict scaling looks "wrong":
At the smaller sizes, the line looks too fat.  So you have to scale the scaling :-).  I find an additional scaling of 1.5 to 2 looks okay:
YMMV -- this is largely a matter of taste.  Another problem I notice here is that the ratio of height to width is okay at the beginning, but too tall at the end.  So I'll adjust the width to get bigger as the mountains get smaller.
Okay, that looks like a pretty decent progression to my eye.  Time to try it on a map.
Too many small hills and no tall mountains (looks like frothy bubbles!), but not bad for a first attempt.  Some tweaking:
That's better, but generating maps with these settings it quickly becomes clear that the transition from tall, peaky concave mountains to broad convex mountains never looks very good.  The convex mountains tend to look much bigger than their concave counterparts.
Since the whole point of this approach is to have a seamless transition from high mountains to low hills, this is not good.  Not only is the perceived size wrong, stylistically there's an abrupt change in the character of the mountains.

Not good.

So back to the (literal) drawing board.  I spent some time doodling examples, and I decided that the (one?) problem is that all the mountain elements change over the sequence from mountain to low hill.  I need to keep at least some elements the same over the course of the sequence so that there's a visual consistency.  I like the curved feet of the low hills, so I decided to try a sequence that maintains that element.  This is the result:

This sequence does seem to have more end-to-end consistency.   Let's see how it looks on a map:
This still needs some tweaking, but that looks visually more consistent than the original sequence.

Another possibility is to go from straight to curved on both ends of the mountain contour, like this:
This is sort of a "melting" sequence from high to low, which is nice.  Here's how it looks on the map:
That also seems pretty good to me.

This project has been a lot of "two steps forward, one step backwards."  I often leave out big chunks of failed development (because I think it would be largely boring) but in this case I hope you're enjoying the journey as much as the destination.  I think the added challenge of making the result artistic adds some interest to the usual challenge of figuring out the implementation.