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.