Monday, February 11, 2019

Map Borders (Part 1)

A major element of fantasy maps that's been on my list to tackle for some time are borders.  Functional maps typically have a simple neatline to define the map, but fantasy maps and the medieval maps from which they borrow ideas often have fairly elaborate and often artistic borders.  These borders help frame (sic) a map as being intentionally fantastical and instill in the viewer a sense of wonder.

Currently Dragons Abound has a couple of simple ways to draw borders.  It can draw a single or double line around the perimeter of the map, and add some simple corner elements, as in these examples:
Dragons Abound can also add a box at the bottom of the border for the title of the map.  Dragons Abound has several variants for this box, including some fanciful elements like faux screw heads:
There's some variation in these caption boxes, but it's all hand-crafted.   

One of the interesting aspects of fantasy map borders is that they're simultaneously creative and formulaic.  They're often made up of a small number of simple elements combined in a variety of ways to create a unique result.  As always, my first step in tackling a new topic is to look through my collection of reference maps and catalog the kinds of border elements they have and look at how they are used.

The simplest border is just a single line around the edge of the map to indicate its limits.  As I mentioned earlier, this is also called a neatline:

A variant is to place the border within the map extent.  In this version, the map extends to the edge of the image, but the border provides a virtual frame inside the image:
This can be done with any sort of border, but it's typically only used with simple borders like a neatline.

One popular conceit for fantasy maps is to present them as if they are drawn on an old, tattered parchment.  Sometimes this is done by drawing the border as the irregular edge of the paper:

Here's a more sophisticated example:
In my experience, this is less common since digital tools have become the norm.  If you want your map to look like it is on old tattered parchment, it's easier to overlay it on a parchment texture than to hand-draw the same thing.

Repetition is the most powerful tool in map border design.  In the simplest case, the single border line is repeated to create two lines:

Interest can be added by varying the style of the repeated element, in this case by combining a thick single line with a thin single line:

Depending upon the element, there are different style variations possible.  In this example, a line is repeated but the color is changed:

Repeated repetition (sic) can be used to create more complex patterns.  This border has five or so single lines of different widths and spacing:

This border repeats lines but separates them in a way that makes them look like two separate thin borders.  Although I'm not going to talk much about corner treatments in this posting, the different corners for the two lines also help create this distinction.
Is this two lines, four lines, or six lines?  Depends on how you draw it, I suppose!

Another styling element is to fill the space between elements with color, pattern or texture.  In this example, a border is made more interesting by filling between two lines with an accent color:
Here's an example where the border has been filled with a pattern:

Elements can also be styled to look three dimensional.  Here's a map where a border has been shaded to make it look three dimensional:

In this map, the border is shaded to look three dimensional, and this is combined with placing the border inside the map's edge:

Another common border element is a scale in the form of alternating bars:
These bars form an implicit grid (or graticule).  On real maps the scale was intended to help estimate distances, although in fantasy maps they're usually just a decorative element.  

These bars are most often shown as black and white, but sometimes red or another color is incorporated:

Again, this element can be combined with other elements, as in this example with lines and a scale:
This example is a little unusual.  Normally the scale (if present) is the innermost element of the border.

This map has multiple scales at different resolutions (as well as some odd runic markings!):
(Over on Reddit, AbouBenAdhem informed me that the odd runic markings are the numbers 48 and 47 in Babylonian cuneiform. Also, the “scales at different resolutions” have six divisions and ten subdivisions, reflecting the Babylonian sexagesimal number system.  Normally I try to cite my map sources, but for this posting I have so many small clips that I did not make the effort.  But this map is by Thomas Rey for the author S.E. Boleyn, so perhaps there is a Babylonian background in his novels.)

Beyond lines and scales, the most common element is a repeated geometric pattern.  These are often composed of elements such as circles, diamonds and rectangles:

Just as lines can be shaded to look three-dimensional, so can these geometric elements.  Here's a border that combines lines, fill and three-dimensional geometric elements:

Complex borders can be created by combining these elements in different ways.  Here's a border that combines lines, geometric patterns and a scale:

The examples I've shown so far are all digital maps, but of course you can do the same things with hand-drawn maps.  Here's an example of a simple hand-drawn geometric pattern:

Again, these elements can be flexibly combined in different ways.  Here's a geometric pattern combined with the “torn edge":

In the examples above, the geometric pattern is fairly simple.  But it's certainly possible to create very complex patterns by combining the basic geometric elements in different ways:

Another popular pattern element is a braid or Celtic knot:

Here's a more complex braided border that incorporates color, scales and other elements:

On this map, a braid is combined with a torn edge element:

Beyond geometric patterns and braids, almost any repeating pattern can be part of a map border.  Here's an example which incorporates some arrowhead shapes:

And here's one that has a repeating wave pattern:

Finally, fantasy maps sometimes incorporate runes or other fantasy alphabet elements into the borders: 

The examples I've used so far all come from modern fantasy maps, but here's an example from an historical (1700s) map that has lines and a hand-drawn pattern:

Of course you can find example maps with many other elements in their borders.  Some of the most beautiful are entirely hand illustrated with such elaborate decorations they threaten to overwhelm the map itself (World of Alma, by Francesca Baerald):

It's also worthwhile to talk a bit about symmetry.  Like repetition, symmetry is a powerful pattern feature, and map borders are usually symmetrical or have symmetrical elements.

Many map borders are symmetrical from inside to outside, as in this example:

The border here is made up of a number of filled and unfilled lines, but from outside to inside it repeats perfectly around the center of the border.

In this more complex example, the border is symmetric except for the alternating black and white scale:

Because it doesn't make sense to duplicate the scale, it is often treated as a separate element even if the rest of the border is symmetrical.

Beyond the inside to outside symmetry, borders are often repetitively symmetrical along their length.  Some illustrated borders might have a single design that stretches the whole length of the map's edge, but in most cases the pattern is fairly short and repeats to fill the border from one corner to the next:

Note that in this example that the pattern contains elements that are not (left to right) symmetric, but that the whole pattern is symmetric and repeated:

One notable exception to this rule are borders filled with runes or alphabetic characters.  These are often unique, as if there was some long message in the border:

Of course there are many other examples of map border elements that I haven't included here, but this is a good starting point.  In the next several postings I'll develop some capabilities in Dragons Abound to describe, display and procedurally generate map borders similar to these examples.  I'll start in the next posting by defining a language for describing map borders.

Monday, February 4, 2019

Perlin Noise, Procedural Content Generation, and Interesting Space

Probably the worst thing to ever happen to the field of procedural content generation (assuming that there actually is a field of procedural content generation, which I'm not entirely convinced is true) is Perlin noise.  Perlin noise works incredibly well (at least if you don't look at it too closely) to generate interesting landscapes.  Not a week goes by on /r/proceduralgeneration without someone posting a “procedural generation system" which turns out to be Perlin noise visualized as different colors.  (Two were posted as I was writing this blog!)
I don't mean to entirely disparage Perlin noise.  It's an incredibly useful tool for procedural generation, and it has provided an easy entry into the field for many people --  myself included.  But at the same time it's very misleading, because it suggests that procedural generation is much easier than it really is.  Most of the weekly “procedural generation system" postings on /r/proceduralgeneration disappear without a trace when their authors discover that the next step in procedural generation is much harder.  The truth is that Perlin noise is a kind of happy accident.  It does work very well for generating interesting landscapes, but not for any systematic or repeatable reasons.

Mike Cook recently posted a tutorial contrasting Possibility Space versus Generative Space.  If you're creating a generative system to create X, then the Possibility Space is all the possible Xs while the Generative Space is all the Xs your system can actually generate.  Mike illustrates the idea with this picture, using the example of Minecraft:

In the case of Dragons Abound, the Possibility Space includes every possible map -- including many degenerative cases, such as a map that is all ocean except for one small island.  The Generative Space is the smaller space of all the maps that Dragons Abound can actually generate.  Because of various rules it incorporates, Dragons Abound cannot generate a map that is all ocean except for one small island, so this map is not in the Generative Space for Dragons Abound.  Possibility Space versus Generative Space is an interesting and useful way to think about procedural generation, and I encourage you to go read Mike's posting, which will explain this idea in more detail and -- bonus -- has some neat interactive toys to play with.

In addition to the Possibility Space and the Generative Space, another useful space to think about is “Interesting Space."  If we're creating X, then this is the space of all interesting Xs.  So in the case of Dragons Abound, this is the space of all interesting fantasy maps.  Interesting Space is a subset of Possibility Space and hopefully intersects with Generative Space -- for example, I hope that Dragons Abound generates at least some maps that are interesting.

Before I go any further, I'm happy to concede that “interestingness" is vague and subjective.  What I find interesting and what you find interesting are likely not identical.  I don't even always know what I find interesting -- I often see something new and find it interesting, even though I wouldn't have thought so before I saw it.  Even worse, exposure to something interesting tends to make it not interesting.  Once you see an interesting map feature on twenty consecutive maps, it's not as interesting any more.  So “interestingness" is not easy to pin down.  I'll have more to say about what makes something interesting in the future (and in the past I've had something to say about the related idea of Creativity Space), but for now that's not really important.  All we need to agree upon is that some things are more interesting than other things, and that the more interesting things are in the “Interesting Space" and the less interesting things are not.

So how would we illustrate Interesting Space the way Mike illustrated Possibility Space and Generative Space?  As I suggested above, Interesting Space is a subset of Possibility Space that (hopefully) intersects with our Generative Space:

A good generator has a lot of overlap with Interesting Space; a bad generator has little overlap.

These diagrams are only a metaphor, but within the limits of the metaphor, I want to ask this question:  Do I have the shapes of the different spaces right?  The shape of Possibility Space doesn't really matter; it just needs to contain the other two.  The shapes of the Generative Space and the Interesting Space are more interesting (sic) questions.  I've drawn them both as single, compact shapes within the Possibility Space.  Is that reasonable?

I think drawing the Generative Space as a compact ellipse is a good choice for many procedural generators, and particularly for something like Perlin noise.  This shape implies that the generator creates all the solutions within a single well-defined and compact space.  If the generator can create X then it can usually create all of X's neighbors.  There aren't usually any big “holes" or weird distortions in the Generative Space.

There are a couple of reasons that Generative Spaces tend to look like this.  First, on a practical level, the generator is some small amount of code relative to the Possibility Space.  At this moment, Dragons Abound is about 28K source lines of code.  That's a lot by comparison to many other procedural map generators -- maybe it's the biggest ever -- but it's still very, very tiny in comparison to the Possibility Space of all fantasy maps.  So no matter how clever the Dragons Abound code is, it's Generative Space is only going to take up a small part of the Possibility Space, and because computer code by definition is algorithmic and deterministic, that space is going to be relatively compact -- that is, if Dragons Abound can produce one sort of map, it can almost certainly produce a lot of other similar maps.

The second reason Generative Spaces are compact and consistent is strategic.  My purpose in creating Dragons Abound is to generate interesting maps -- to overlap as much as possible with the Interesting Space.  And the Interesting Space is a tough target -- it's very small in comparison to the Possibility Space.  In fact, it's really, really small.  All of these spaces have a huge number of dimensions, and the size of the space essentially grows as the power of the number of dimensions.  The real relationship between Interesting Space and Possibility Space is something like:

Except the Interesting Space is much, much smaller.  This forces procedural generation into certain strategies.  For example, why doesn't Dragons Abound create entirely random maps?  Well, in that case the Generative Space would look like this:

Except with the green dots much much smaller.  The odds of actually hitting the tiny Interesting Space with one of the random maps is effectively zero.  To improve the chances of hitting the Interesting Space, the creator of the procedural generation uses knowledge about the Possibility Space and the Interesting Space to guide generation -- the creator steers the Generative Space to be mostly in the neighborhood of Interesting Space, not just spread out randomly.

So for those reasons, I think it makes sense to think about the Generative Space as a connected, compact region.

But I think drawing the Interesting Space the same way is probably exactly wrong.  It should be drawn as a scattered, disjoint set of weirdly-shaped areas.  Why?  Because (1) things can be interesting for different, orthogonal reasons, and (2) interestingness is a discontinuous function.

Consider, for example, these two map excerpts:

The first excerpt is interesting because the coastline is baroquely detailed and has many small islands.  The second excerpt has an uninteresting, smooth shoreline, but the shore has interesting features -- it is uninhabited and has the ominous “Bleak Shore" name.  To the extent that these excerpts are interesting, it's for entirely different reasons.   So we wouldn't expect these two parts of the Interesting Space to be neighbors.

What's more, the two parts of Interesting Space probably aren't connected, either.  There's no way to slowly change the first interesting map into the second interesting map without creating some uninteresting maps along the way.  So these two parts of Interesting Space are disjoint.

So Interesting Space isn't a single region, but a bunch of disjoint regions.  Do each of these separate Interesting Spaces have smooth, compact shapes?

Again, I don't claim to be able to define “interestingness" completely.  But we can agree on some aspects.  One of those is that just because X is interesting, it doesn't mean that 2X is twice as interesting.  To take the Bleak Shore example above, one stretch of mysterious shore on a map is interesting, but ten would (counterintuitively) be very uninteresting.  You can probably think of other examples where “interestingness" behaves in odd and counterintuitive ways.  So interestingness has some elements of discontinuity -- it's not a smooth function that varies in a rational and predictable manner as we move through the Possibility Space.

These things together suggest that we ought to draw the Interesting Space as a bunch of disjoint, oddly shaped regions.
You start to see why creating a good procedural content generator is so hard.  Because of the way algorithms work and the limits of our effort, the Generative Space is going to be small and compact.  At the same time, we're trying to hit as many possible weirdly shaped and scattered Interesting Space regions.  It's amazing that we can hit anything at all!

Now let me return to the topic of Perlin noise.  What would this graph look like for the Generative Space of Perlin noise in the Possibility Space of landscapes?  I think it would look something like this:
The Perlin noise generator has a large amount of overlap with a particular Interesting Space within the universe of all possible landscapes.  That's great -- almost everything you can do with Perlin noise falls within that region and looks pretty interesting.

But that easy success is deceptive.  If you're new to procedural generation, you'll see how well Perlin noise works and you're likely to think that Perlin noise is a magic tool for generating all kinds of interesting landscapes, not to mention other sorts of procedural generation.  But as the diagram illustrates, the Generative Space of Perlin noise is actually far away from many other parts of the landscape Interesting Space.  A typical second step in procedural generation of landscapes is to add rivers.  But when you try to implement rivers using Perlin noise you find that it is impossible!  There's no way to push out the borders of the Perlin noise Generative Space to reach the distant Interesting Space that contains realistic rivers.

Perlin noise is deceptive in another way as well.  I said above that Interesting Space is so small that if you want to hit it, you have to use some knowledge about the Possibility Space and the Interesting Space to guide the procedural generation.  But the Perlin noise algorithm doesn't know anything about landscapes or geologic processes or what people find interesting and yet somehow works very well without any of that knowledge!  Perlin noise happens to be the exception that proves the rule (*).  But if you're new to procedural generation, you probably don't know the rule.  In fact, you'll deduce the wrong rule -- that procedural generation in general should work like Perlin noise.

(* It doesn't just “happen" to be the exception.  Perlin noise is a popular starting point precisely because it is the exception.  It's easy to get started with Perlin noise without having to understand a lot about landscapes.)

Consider another common starting point in procedural content generation: dungeon layout.  Unlike landscape generation, dungeon layout doesn't have an algorithm similar to Perlin noise that magically creates solutions in Interesting Space.  Given what we know about Generative Space and Interesting Space, we might guess that dungeon generators will have to either (1) incorporate specific knowledge about dungeons and interestingness, or (2) produce mostly uninteresting dungeons.  And in fact, if you were to go survey the last year of dungeon generators posted to /r/proceduralgeneration you would find that most of them don't incorporate any knowledge about dungeons beyond making sure all the rooms are connected, and as a result, the output of these projects look more random than interesting.
So -- presuming you more-or-less accept what I've written -- what lessons should we take away from this notion of Interesting Space?
  • Procedural generation is fundamentally hard because Interesting Space is a really small and difficult target.
  • Despite the occasional exception like Perlin noise, we should not expect simple, naive algorithms to do a good job generating interesting content.  Instead, good procedural generation needs to incorporate and leverage extensive, deep knowledge of the domain and what makes content interesting.
  • But even with the best generation algorithms, Generative space is compact and Interesting Space is not, so we should expect our procedural generation to have a lot of misses, and engineer our systems accordingly.
  • For complex domains, Interesting Space is disjoint and weirdly shaped.  We shouldn't expect that an algorithm or approach that works well in one part of Interesting Space to necessarily work well in another part.  Therefore we can expect procedural generation to incorporate many different algorithms to exploit different parts of Interesting Space.
If you're starting out with procedural generation, my advice would be to think about interestingness.  What would make an output interesting?  What does my algorithm need to understand to produce outputs that are more often interesting than not?  What's a different way an output could be interesting?  What's the new algorithm I need to generate that sort of interest?  How do I combine / balance this with the first algorithm?

So if I were to create a dungeon generator, I might think about dungeons for a while and decide that I think dungeons are interesting if they:
  1. Look like they were created to be the storerooms, jail cells and other subterranean infrastructure of a large castle, and 
  2. Were later invaded by monsters and modified by the monsters to suit their needs for shelter, food, water, defense against attack, etc.
Now you can think about what a subterranean storage level looks like and what an algorithm to procedurally generate variations on that theme might look like, and how monsters might then modify that layout.  I believe that tackling these sorts of questions will teach you more about procedural generation than implementing Yet Another Perlin noise landscape generator, or a random rooms and corridor dungeon generator.

Monday, January 28, 2019

Naming Forests

Some time ago I wrote a number of posts on naming map features.  At the time I didn't get around to naming forests, so I'm going to do that now.  Having named a number of features at this point, I know there are three main questions to answer:  (1) When should I name a feature?  (2) How do I generate a name for this sort of feature?  and (3) How should I display this name on the map?

Some map features always get named -- for example, towns and cities are always named and labeled on the map.  Other features only get named sometimes.  For example, Dragons Abound doesn't give a name to every point or bay on the map.  The rationale for when to name varies based upon the feature.  Sometimes a feature doesn't get named because it's not significant enough to warrant a name -- an example of this being small bays or points.  Sometimes a feature doesn't get named because (I think) it will make the map less interesting.  For example, I'll only label three bays or points in a typical sized map.  Even if there are more suitable candidates, it starts to detract from the interest of the map if they're all labeled.  And finally, sometimes a feature doesn't get labeled because the label won't fit on the map or creates clutter.  In Dragons Abound, this happens fairly often with rivers -- although every river gets a name, only the labels that will fit on the river will actually get displayed.

For forests, the main criteria for naming is the size of the forest.  In most cases, small forests aren't interesting enough to warrant a label.  (On the other hand, one of the key elements of creativity is breaking these sorts of rules; you can imagine a map with one small, isolated forest with a name like “The Druid's Woods" -- that would be quite interesting.)  Another problem with labeling small features is that the label will often not fit within or close to the feature, creating map clutter.  A secondary criteria is the number of named forests on the map.  As with bays and points, it's better to only label a couple of forests to help them feel “special."

Another challenge for forests is deciding what exactly counts as a forest to be labeled.  Here's a map excerpt with the forests outlined in purple:
As this illustrates, forests are often chopped up into pieces (or turned into awkward shapes) by rivers.  That's really just an artifact of illustrating the map.  The rivers actually run through the forest.  The forest is just pulled back from the rivers to make them easier to see.  That's apparent if I use a style that doesn't pull back from the rivers:
For labeling purposes, I probably want to ignore rivers when defining the forest areas.  So the above map would have one big forest rather than seven smaller ones.  But that might be a matter of taste.

Dragons Abound also avoids mountains when drawing forests, and this can also split a forest into pieces.  Unlike rivers, mountains can take up a lot of space on the map:
It seems odd to have one forest stretch over such a big chunk of map with no connection between the parts.  So unlike rivers, I'll allow mountains to separate one forest into two:
With the first question settled, let me jump ahead to the third question -- how I will display the name on the map.  I have a couple of immediate options that reuse existing code.  The first is to treat the name as an area label, similar to what I do for country names or ocean names -- the label floats around inside the area, looking for a good fit.  The second option is to tie the label to an (imaginary) point at the center of the area and let the label try to find a good fit near that point.

Here's an example of the area label option, using a multi-line label:
Right now I just want something that works so I can see the invented names.  I will tweak label criteria and styles to get a better fit later.

I have described previously a number of resources I use to collect possible names for features.  I have some tools that can data mine these resources for words and synonyms in various forms.  It turns out that forest names -- at least in the real world -- are pretty boring.  When I investigate forests, I find that almost all forests in the real world are called “forest" or “woods."  Browsing the historical thesaurus turns up a few other synonyms, but in English “forest" is used far more than any other term.

Looking at the adjectives and other nouns that are used in forest names also turns up nothing too surprising.  Adjectives are dominated by colors and descriptives (like “rough"), and no nouns are used very frequently, although wood types (e.g., “ash") do appear in the list as you might expect.  I'll create a vocabulary starting with the kinds of words I use for naming points and bays, removing all the water-related words, and adding in wood types and wood adjectives.
There will be some editing of the vocabulary and forms of names as I see results that I don't like (or do like).

Now let me return to label placement on the map.  One common style of forest label is to have a slightly arced label, as in this example:
I can reproduce this fairly easily; area labels already have the ability to change their angle and set a curve:
The real challenge is to place angled labels well.  The multi-line horizontal labels work well (almost) anywhere within the label area.  But we expect angled labels to be at an angle for some good reason, usually to fit along the long axis of the label area, or to mirror an important feature of the area.  In the Dragons Abound map above, “Presbyry Farest" (*) looks okay, but “Chi's Woods" doesn't because it is angled perpendicular to the long axis of the forest.  A human labeler would have run “Chi's Woods" along the long axis of those woods.

(* The “Farest" problem happens because of linguistic drift.  There's a list of words that are protected from drift, but I hadn't yet added the forest synonyms to the list when I created that example.)

Zooming out a bit on the example map above (Silverdale by Thomas Rey) shows three or four labels of this sort:
Here you can see that “Hartwood Forest," “Moon Woods," and “Northstar Glacier" all run along the long axis of their areas.  (Hartwood Forest should probably be more vertical, but the Painted Stones icon prevented that placement.)  “Cold Woods" follows an axis as well, but is also placed to run across the top of the river tributaries.  The curves of these labels generally follow the area shapes, except for “Moon Woods," which has the opposite curve.  That looks a little awkward upon reflection; the curve makes the label crowd the edge of the area and be visually a little cluttered with the river label.  Perhaps Thomas did it this way because the opposite curve on a label at that direction would be a little difficult to read.

Good label placement for these sorts of curved and angled labels is very difficult.  First, the size and shape of the label area is not just a geometrical measurement but depends on the map context.  In the Silverdale map, the “Moon Woods" placement is problematic partially because the river label is close to one side of the woods area.  Second, figuring out the axes or straight skeleton of an irregular polygon and applying them to label placement is not trivial.  I suspect that duplicating a good cartographer's label placement in this case would involve many heuristics and special cases.

As what I hope will be an acceptable shortcut for all of that, I've added a placement criteria that tries to maximize the closest distance between the label and the polygon defining the label area.  Although this isn't foolproof, in many cases it will effectively force the label to lie along the major axis of the region.  Here's an example that shows how this heuristic changes the placement of “Chi's Woods:"
In this case, it does a pretty good job of reasonable placement.

However, there are other criteria for label placement, such as not clashing with other labels, so in many cases the eventual placement will not follow only this criteria.  In the image above “Presbyry Farest" is a particular hard placement.  The forest area has numerous other labels which must be avoided, and is criss-crossed with rivers which also must be avoided.  In the end, there's no placement that doesn't break some of these criteria.  “Chi's Woods," on the other hand, can be placed easily into a spot that is far away from the edges of the area at only the cost of obscuring part of a river.

Another style often applied to these sorts of labels is to stretch them out so that they better span the labeled area.  Dragons Abound already does this for ocean labels, so I can easily add this style to forest labels as well:
It might be worthwhile to check the size of the forest area versus the length of the label to determine whether (or how much) extra letter spacing to apply.  Here's an example where a forest name (“Bishop Tanpik's Forest") has been compressed to make it fit better while another name with more room (“Forest of Horses") remains stretched out:
This is less than perfect; it relies on noticing ahead of time that there might be a problem and preemptively shrinking the label.  And it only works in cases where labels have added letter spacing.  A more robust algorithm might notice in the middle of label placement that a label has consistently been hard to place and then look for ways to make the label smaller.  Something to think about for the future.

Here's the full map with labeled features.  With all the heuristics turned on, label placement finds a spot to squeeze in “Bishop Tanpick's Forest" where it barely remains inside the forest and only obscures part of one river: