Map Borders (Part 3)

In the last posting, I developed the first iteration of the Map Border Description Language (MBDL) and wrote a context-free grammar for the language that can be used with Nearley, a Javascript parsing toolkit.  Now it's time to implement the actual drawing primitives.  (At this point I don't yet have the parser hooked up to the drawing primitives.  I'll just be calling them manually to test them.)

I'll start with the line primitive.  Recall that this has the form:

L(width, color)

In addition to width and color, there's an implicit parameter that is the distance from the outside edge of the map.  (By convention, I am drawing the borders from the edge of the map outward.  Note this is a change from how I started!)  This doesn't have to be specified in MBDL because the interpreter that executes MBDL to actually draw a border can keep track of this.  However, it does need to be an input to all the drawing primitives, so they know where to draw.  I'll call this parameter the offset.

If I only had to draw the border across the top of the map, the line primitive would be pretty straightforward to implement.  However, I actually have to draw it at the top, bottom, left and right sides.  (At some point I may implement slanted or curved borders, but at the moment I'll stick with the standard rectilinear borders.)  Finally, the length and placement of the line element depends upon the dimensions of the map (combined with the offset).  So I need all those things as parameters as well.

With those parameters defined, it's fairly easy work to create the line primitive and use it to draw a line around the map:

(Note that I'm using the various Dragons Abound features to create a “hand-drawn" line.)  Let me attempt a more challenging border:

L(3, black) L(10, gold) L(3, black)

That looks like this:

Pretty good.  Note that there are spots where the black lines and the gold line do not quite align due to the jitter.  I can tune down the amount of jitter if I want to eliminate those spots.

Implementing the vertical space primitive is pretty easy; it just increments the offset.  That lets me skip some space:

L(3, black) L(10, gold) L(3, black)
VS(5)
L(3, black) L(10, red) L(3, black)

When drawing lines, I can make the corners work by drawing between the offsets and drawing clockwise around the map.  But in general I need to implement clipping on each side of the map border, to create mitered corners.  This will be necessary for making patterned borders fit together smoothly at the corners, and in general will eliminate the need to draw elements with angled ends as would otherwise be required.  (*)

(Note: As will be noted in a later posting, I eventually abandoned using clipping areas to implement corners.  The primary reason is that to do complex corners such as square offsets:

requires increasingly complex clipping areas.  I also eventually figured out a better way to deal with patterns in corner.  Rather than go back and fix this posting, I thought I'd leave it this way to illustrative the “creative" process :-)

The basic idea is to clip each border along the diagonals, creating four clipped areas in which to draw each side of the border:

The clipping will cause anything drawn into the area to be cut off at the proper angle.

Unfortunately, this creates a slight discontinuity along the diagonal line -- probably due to the browser not doing a perfect job of anti-aliasing along the clipping edge.  A test shows this is the background color showing through a gap between the two edges.  A working fix is to extend one of the masks slightly -- about a half pixel seems to do the trick -- although this also seems to fail sometimes.

The next things to implement are the geometric shapes.  Unlike lines, these repeat in a pattern to fill a side of the map border, like this:

A person would draw this left to right, drawing a box, a diamond and then repeating the same way to fill the border.  So intuitively you might implement it like that in a computer program, drawing the pattern repeatedly across the border.  However, it's somewhat simpler if you draw all the boxes first and then all the diamonds.  Each part just becomes a matter of drawing the same geometric shape at intervals across the border.  And conveniently, each element is at the same interval.  Of course a person wouldn't do it this way because it would be too hard to place elements in the right spots, but that's not a problem in a program.

With that insight, the basic geometric shape routine needs parameters for all the shape dimensions and colors (i.e., width, length, line width, line color and fill color) as well as an initial position (which I will treat as the center of the shape for reasons that shall become apparent), an interval of horizontal space to skip between repeats, and the number of repeats.  It's also convenient to specify the direction of repeat as a vector [dx, dy] so that I can run the repeat left to right, right to left, up or down just by changing the vector and the starting point.  Put that together and it creates a row of repeated shapes:

Using this multiple times and drawing in the same offset, I can combine black and white bars to create a map scale:

Before I look at how to use these in an actual map border, let me implement the same functionality for ellipses and diamonds.

Diamonds are just boxes with the vertices rotated around, so that's only a small code change.  It turns out I don't have any ready-made code to draw an ellipse, but it's simple enough to take the parametric form of an ellipse and create a function to give me points on the ellipse:

Here's a (hand-crafted) example using the capabilities so far:

Looks pretty good for just a small amount of code!

Now let's address the tricky part about borders with repeating elements:  the corners.

There are several choices for corners when you have a border with a repeating element.  The first choice is to arrange the repeat so that it flows around the corner without a visible break:

Another option is stop the repeat somewhat short of the corner on both sides.  This is often done when the pattern can't be easily “turned" around a corner:

The final choice is to obscure the pattern behind some sort of corner decoration:

I'll get to corner decorations at some point, but for the moment let me consider the first option.  How can I get a pattern like the bars or circles above to flow seamlessly around the corners of the map?

The basic idea is to put an element of the pattern precisely at the corner, so that (logically speaking) one half is on one edge of the map and the other is on the adjacent edge.  In this example, there's a circle element that sits precisely on the corner and could have been drawn from either direction:
 
In other cases, the element is half drawn in one direction, and half in the other but the edges match up:

In this case the white bar is drawn from both directions but still meets seamlessly in the corner.

There are two things to note about placing an element into the corner.

First, the corner element will be split and mirrored along a diagonal line that passes through the center of the element.  Elements with radial symmetry -- like circles, squares and star shapes -- will not change shape.  Elements without radial symmetry -- like rectangles and diamonds -- will change shape as they are mirrored along the diagonal.

Second, for the corner elements of two sides to meet correctly, there must be an integer number of elements along both sides of the map (*).  There do not need to be the same number of elements along both sides, but there must be a whole number of elements on both sides.  If one side has a fractional number of patterns, at one end the pattern won't match up with the adjoining side.

(* In some cases, as with long bars, a partial repeat can meet with a full repeat and the elements will still line up.  However, the resulting corner element will be asymmetrical and a different length than the same element on the map sides.  An example can be seen here:

The white bar element of the scale meets at different partial repeats and results in an off-center element.  This isn't necessarily wrong for a map scale, which is intended to show absolute distance and not to be symmetric.  But for a decorative pattern this usually looks bad.)

Here's an example showing how a whole number of repeats gets cut off exactly in the corner:

If you do the same thing on all four sides the corners match up and the pattern runs seamlessly around the border:

A close inspection will show that the pattern doesn't meet exactly in the corners.  Half of the circle in each corner comes from each side, and those two halves are each being independently “hand-drawn" so they don't match exactly.  But they are close enough for now.

So I can make the pattern meet seamlessly in the corners by picking a whole number of repeats on each edge.  However, that's not a trivial problem.

First, suppose we know our side is 866 pixels long and we want to repeat our element 43 times.  Then the element should be repeated every 20.14 pixels.  So how should I adjust the length of an element (really a pattern of elements in the general case) to be a certain length?  In the example above, I added extra space between the circles.  But if the circles were originally touching, that changes the pattern.  Perhaps I should have stretched the circles instead to preserve the touching?

Now the elements still touch, but the circles have become ellipses and the corners are odd shapes.  (Remember when I said above that elements without radial symmetry would change shape when reflected around the corner?  This wouldn't be a big problem with bars.)  Or maybe I should shrink all the elements enough so that they'll both touch and fit in the proper length:

But to do this, I've had to make the elements considerably smaller than they were originally.  None of these seems like a perfect choice.

A second problem arises when the sides of the map are not the same size.  Now I must solve the problem of finding a whole number of repeats to fit for both sides.  Ideally I'd like to find one solution that works for both sides.  But I don't want to do that at the cost of changing the pattern too drastically.  It might be better to have a slightly different pattern on the two sides if they were both fairly close to the original pattern.

Finally, a third problem arises when I am using the overlay capability to stack elements:

I don't want to make any changes to the pattern that will break the relationship between the elements.  I think that proper scaling will generally maintain the relationships but I need to test that notion.

A fun problem, eh?  I don't have any particularly good answers.  Maybe I'll have something by next time!

Map Borders (Part 2)

In the last posting, I looked at map borders from my collection of reference maps and identified a number of common elements across the collection.  In this posting I'm going to define an initial version of a Map Border Description Language (MBDL, to be grandiose) to describe map borders.

Why bother creating a description language for map borders?  There are two purposes.  First, it will be the target of my procedural generation.  Later on I'll work on an algorithm for creating new map borders, and the output of that algorithm will be a description of the new border in MBDL.  Second, MBDL will serve as a text representation for map borders.  In particular, I'm going to want to save and re-use borders I like.  To do that, I need some textual notation I can capture and use to re-create a map border.

I'll begin creating MBDL by defining the simplest element: a line.  A line has a width and a color.  So in MBDL I will represent a line as:

L(width, color)

A few examples (pardon my mad Photoshop skillz):

A sequence of elements is rendered from outside to inside (*), so assuming this is the border on the top of the map:

Note the second example -- a line with borders is represented as three separate line elements.

(* Working outside to inside is an arbitrary choice -- it just seemed more natural than working inside to outside to me.  Unfortunately, I discovered later -- much later -- that there was a good reason to work in the other direction.  More on that anon, but I've left these writeups the old way, since it would be a royal pain to redo all the illustrations :-)

Conveniently, spaces can be represented as lines with no color:
But it might be clearer to have a specific vertical space element:

VS(width)

The next simple elements are geometric shapes: bars, diamonds and ellipses.  Lines are assumed to stretch the whole length of the border, so they do not have an explicit length.  But geometric shapes won't fill the whole line, so each one needs to have a length in addition to a width (*), an outline color, an outline width and a fill color:

B(width, length, outline, outline width, fill)
D(width, length, outline, outline width, fill)
E(width, length, outline, outline width, fill)

(* By convention I will treat width as the outside to inside direction, while length will be along the border.)

Here's an example of simple geometric shapes:

To make these elements fill across the length of the border, they will have to repeat.  To indicate a group of elements that will repeat to fill the length of a border, I will use square brackets:

[ element element element ... ]

Here is an example of a box diamond repeating pattern:

Sometimes I will want (horizontal) space between the elements of repeating pattern.  While I could use an element with no colors to create space, it's clearer and more convenient to have a horizontal space element:

HS(length)

The final function I need to capture for this first iteration of MBDL is the capability to overlay elements.  Consider, for example, this border:

The simplest way to express this is with a wide yellow line underneath the top pattern.  There are different ways to implement this (such as with a negative Vertical Space), but I'm going to choose to use curly parentheses to indicate the normal inward sequence of elements should be suspended:

{element element element ...}

Essentially this says to remember where the pattern was at from outside to inside when entering the parentheses, and then return to that spot when exiting the parentheses.  Alternatively, the parentheses can be viewed as saying the elements within take up zero vertical space.  So the above border is:

L(1, black)
{L(20, yellow)}
VS(3)
[B(5, 10, black, 3, none)
D(5, 10, black,3,red)]
VS(3)
L(1, black)

You draw the black line, make note of where you are, draw the yellow line, and then go back to the position you noted earlier, skip down a bit, draw the bar-diamond pattern, skip down a bit, and then draw another black line.

There is more to do on MBDL, but this is sufficient to describe many map borders.  The next step is to translate from an MBDL description of a border to the actual border.  This is similar to getting from the written representation of a computer program (e.g., in Javascript) to actually executing the program.  The first step is to parse the language -- to translate it from the original text directly to an actual map border, or into some intermediate representation that makes it easier to translate into a border.

Parsing is a quite well-studied area of computer science.  Parsing a language isn't always easy, but the good news in this case (*) is that MBDL is a context-free grammar.  Context-free grammars are pretty easy to parse, and there are any number of Javascript parsing tools for context-free grammars.  I settled on using Nearley.js, which seems to be a mature and (more importantly) well-documented tool.

(* This isn't just good luck, I made sure as I created the language it was context-free.)

I'm not going to provide a primer on context-free grammars, but the syntax of Nearley is pretty straightforward and you should be able to get the idea without too much trouble.  A Nearley grammar consists of a number of rules.  Each rule has a symbol on the left side, an arrow, and then right side of the rule, which can be a sequence of symbols or non-symbols, and different options separated by the pipe “|" (or) operator:

border -> element | element border
element -> “L"

Each rule says that the left side can be replaced by any of the options on the right side.  So the first rule here says that a border is either an element, or an element followed by another border.  Which itself can be an element, or an element followed by another border, etc.  The second rule says that an element can only be the string “L."  So together, these rules match borders like this:

L
LLL

and do not match borders like this:

X
L3L

By the way, if  you want to play around with this (or any other) grammar in Nearley there's an online playground for it here.   You can type in a grammar and test cases to see what matches and what doesn't.

Here's a more complete definition of the line primitive:

@builtin “number.ne"
@builtin “string.ne"
border -> element | element border
element -> “L(" decimal “," dqstring “)"

Nearley has a couple of common elements built-in -- “number" being one of them -- so I can use that to recognize the numeric width in the line primitive.  For color, I'm going to use another builtin and allow any double-quoted string.

It's nice to be able to use whitespace between the different symbols, so let me add that.  Nearley supports character classes and the EBNF shorthand for “zero or more" of something using “:*", so I can use that to define “zero or more white spaces" and stick that wherever I want to allow whitespace:

@builtin "number.ne"
@builtin "string.ne"
border -> element | element border
WS -> [\s]:*
number -> WS decimal WS
color -> WS dqstring WS
element -> "L(" number "," color ")"

However, having the WS all over makes the grammar difficult to read, so I'll leave it out, but imagine that it is there :-).  

An element can also be a vertical space:

@builtin "number.ne"
@builtin "string.ne"
border -> element | element " " border
number ->  decimal
color ->  dqstring
element -> "L(" number "," color ")"
element -> "VS(" number ")"

This now matches borders such as

L(3.5,"black") VS(3.5)

Next are the bar, diamond and ellipse primitives.

@builtin "number.ne"
@builtin "string.ne"
border -> element | element " " border
number ->  decimal
color ->  dqstring
element -> "L(" number "," color ")"
element -> "VS(" number ")"
geometric -> "B(" number "," number "," color "," number "," color ")"
geometric -> "E(" number "," number "," color "," number "," color ")"
geometric -> "D(" number "," number "," color "," number "," color ")"

This will match elements such as

B(34, 17, "white", 3, "black")

(Note that the geometric primitives are not “elements" because they cannot stand alone at the top level.  They need to be enclosed in a pattern.)

I also need the horizontal space primitive:

@builtin "number.ne"
@builtin "string.ne"
border -> element | element " " border
number ->  decimal
color ->  dqstring
element -> "L(" number "," color ")"
element -> "VS(" number ")"
geometric -> "B(" number "," number "," color "," number "," color ")"
geometric -> "E(" number "," number "," color "," number "," color ")"
geometric -> "D(" number "," number "," color "," number "," color ")"
geometric -> "HS(" number ")"

Now I will add the pattern (repeat) operation.  That's a sequence of one or more elements inside square brackets.  I'll use the EBNF operator “:+" here that means “one or more."

@builtin "number.ne"
@builtin "string.ne"
border -> element | element " " border
number ->  decimal
color ->  dqstring
element -> "L(" number "," color ")"
element -> "VS(" number ")"
geometric -> "B(" number "," number "," color "," number "," color ")"
geometric -> "E(" number "," number "," color "," number "," color ")"
geometric -> "D(" number "," number "," color "," number "," color ")"
geometric -> "HS(" number ")"
element -> "["  (geometric):+ "]"

Note that a pattern can only be filled with geometric primitives.  You can't, for example, have a line inside a pattern.  The pattern element will now match something like

[B(34,17,"white",3,"black")E(13,21,"white",3,"rgb(27,0,0)")]

The last part of the language is the overlay operator.  This is any number of elements inside of parentheses.

@builtin "number.ne"
@builtin "string.ne"
border -> element | element " " border
number ->  decimal
color ->  dqstring
element -> "L(" number "," color ")"
element -> "VS(" number ")"
geometric -> "B(" number "," number "," color "," number "," color ")"
geometric -> "E(" number "," number "," color "," number "," color ")"
geometric -> "D(" number "," number "," color "," number "," color ")"
geometric -> "HS(" number ")"
element -> "["  (geometric ):+ "]"
element -> "{"  (element ):+ "}" 

which permits:

{L(3.5,"rgb(98,76,15)")VS(3.5)}

(Note that unlike the repeat operator, the overlay operator can be used inside of itself.)

With some clean up and the addition of white space where appropriate, this is the MBDL grammar:

@builtin "number.ne"
@builtin "string.ne"
border -> (element WS):+
WS -> [\s]:*
number -> WS decimal WS
color -> WS dqstring WS
element -> "L(" number "," color ")"
element -> "VS(" number ")"
element -> "(" WS (element WS):+ ")"
element -> "[" WS (geometric WS):+ "]"
geometric -> "B(" number "," number "," color "," number "," color ")"
geometric -> "E(" number "," number "," color "," number "," color ")"
geometric -> "D(" number "," number "," color "," number "," color ")"
geometric -> "HS(" number ")"

So now MBDL is defined and I have created a grammar for the language.  This can be used with Nearley to recognize legal strings in the language.  Before I go any further with MBDL/Nearley, I want to implement the primitives used in MBDL so that I can actually display an MBDL border.  I'll do that next time.

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.