Map Borders (Part 5)

In Part 2 of this series I developed a grammar for the Map Border Description Language (MBDL) and in parts 3 and 4 I implemented routines to execute all the primitives for the language.  Now I'll work on connecting those parts up so that I can describe a border in MBDL and have it drawn around the map.

You may recall from Part 3 that I wrote the MBDL grammar to work with a Javascript parsing tool called Nearley.   The final grammar looked like this:

@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 ")"

By default, when Nearley parses a rule successfully, the rule returns an array containing all of the elements that matched the right side of the rule.  So for example, if the rule

test -> "A" | "B" | "C" 

was matched against the string

A

then Nearley would return

[ "A" ] 

an array with a single value, the string “A" that matched the right-hand side of the rule.

So what does Nearley return when it parses an element using this rule?

number -> WS decimal WS

There are three parts on the right side of this rule, so it will a return an array with three values.  The first value will be whatever the rule for WS returned, the second value will be whatever the rule for decimal returned, and the third value will be whatever the rule for WS returned.  If I parsed “ 57" using the above rule, the result would be this:

[
  [ " " ],
  [ "5", "7" ],
  [ ]
]

The end result of a Nearley parse is a nested series of arrays representing the parse tree.  For some applications, the parse tree is a very useful representation.  For other applications, not so much.  Dragons Abound, for example, doesn't have much use for the parse tree.

Fortunately, Nearley rules can override the default behavior and return whatever they'd like.  In fact, the (built-in) rule for decimal doesn't actually return a list of the digits, it returns the equivalent Javascript number, which in most cases is much more useful, so that the return value of the number rule is actually:

[
  [ " " ],
  57,
  [ ]
]

Nearley rules override the default behavior by attaching a post-processor to the rule that takes the default array and replace it with whatever is desired.  The post-processor is just Javascript within some special brackets at the end of the rule.  For example, in the number rule I will never care about the possible whitespace to either side of the number.  So it would be nice if the rule just returned the number, rather than an array of three elements.  Here's the post-processor that will do that:

number -> WS decimal WS {% default => default[1] %}

This post-processor takes the default result (the three element array shown above) and replaces it with the second element of the array, which is the actual Javascript number from the decimal rule.  So now the number rule returns the actual number.

This capability can be used to process the input language into an intermediate language that is easier to work with.  For example, I can use the Nearley grammar to turn an MBDL string into an array of Javascript structures, each of which represents a primitive identified by an “op" field.  The rule for the line primitive would look something like this:

element -> "L(" number "," color ")" {% data=> {op: "L", width: data[1], color: data[3]} %}

So the result of parsing “L(13,black)" would be a Javascript structure:

{op: "L", width: 13, color: "black"}

By adding appropriate post-processing to all the rules, the return result from the grammar can be the sequence (array) of operations structures for the input string.  So the result of parsing the string:

L( 415, “black")
VS(5)
[B(1, 2, “black", 3, “white") HS(5) E(1, 2, “black", 3, “white")]

would be

[
 {op: "L", width: 415, color: "black"},
 {op: "VS", width: 5},
 {op: "P",
  elements: [{op: "B", width: 1, length: 2,
                       olColor: "black", olWidth: 3,
                       fill: "white"},
             {op: "HS", width: 5}, 
             {op: "E", width: 1, length: 2,
                       olColor: "black", olWidth: 3,
                       fill: "white"}]}
]         

which will be much easier to process to produce a map border.

At this point, you may be wondering -- if the post-processing step of a Nearley rule can contain any Javascript, why not skip the intermediate representation, and just draw the map border directly during the post-processing?  For many problems, this is a perfectly good approach.  I chose not to do that in this case for a couple of practical reasons.

First, there are a couple (*) of features in MBDL that cannot be executed as they are parsed.  For example, you cannot draw a repeating geometric elements (such as a bar or a diamond) as you parse it, because you need to know some information from the other elements within the same pattern.  Specifically, you need to know the total length of the pattern so you know how far to skip between the repeats of each individual element.  So the pattern element would have to build up an intermediate representation of all the geometric elements within it anyway.

(* There are some other features with similar restrictions that I haven't yet discussed.)

Second, the Javascript in Nearley is embedded into the rules, so there is no way to pass additional information into the Javascript except via global variables.  For example, to draw the border, I need to know the size of the map, the four clipping areas to use, etc.  While I certainly could add code to make this information available to the Nearley post-processors, it would be a little messy and potentially hard to maintain.

So for those reasons I've parsed to an intermediate representation which is then executed to produce the actual map border. 

The next step is to develop an interpreter that can take the MBDL intermediate representation and execute it to generate the map borders.  This isn't too difficult.  It's mostly a matter of setting up some initial conditions (such as generating the clipping areas for the four sides of the map) and then iterating through the sequence of intermediate representation structures and executing each one.

There are a couple of tricky bits.

First, I had to switch from drawing the border from outside to inside to inside to outside.  The reason is that I want most borders not to overlap (obscure) the map, so I want to draw the border so that the inside edge lines up with the map.  If I'm drawing outside to inside, I have to figure out the width of the border before I draw it so I know how far to back off so that I won't overlap.  If I'm drawing inside to outside, I just start at the edge and draw outwards.  This also makes it possible for me to overlap the map if I want; I just start the border with a negative vertical space (VS).

Repeating patterns is another tricky bit.  To draw a repeating pattern, I need to look through all the elements of the pattern to determine the widest element, because that will determine the width of the overall pattern.  I also need to look through and keep track of the length of the pattern so that I'll know how far to skip between each repeat.

Here's an example of a fairly elaborate border I used to test the interpreter:

I suppose I could have (should have?) hooked this up to the parser for testing, but instead I hand-crafted the intermediate representation used for that border:

[
 {op:'P', elements: [
     {op:'B', width: 10, length: 37, lineWidth: 2, color: 'black', fill: 'white'},
     {op:'B', width: 10, length: 37, lineWidth: 2, color: 'black', fill: 'black'},
 ]},
 {op:'VS', width: 2},
 {op:'L', width:3, color: 'black'},
 {op:'PUSH'},
 {op:'L', width:10, color: 'rgb(222,183,64)'},
 {op:'POP'},
 {op:'PUSH'},
 {op:'P', elements: [
     {op:'E', width: 5, length: 5, lineWidth: 1, color: 'black', fill: 'red'},
     {op:'HS', length: 10},
 ]},
 {op:'L', width:3, color: 'black'},
 {op:'POP'},
 {op:'VS', width: 2},
 {op:'P', elements: [
     {op:'E', width: 2, length: 2, lineWidth: 0, color: 'black', fill: 'white'},
     {op:'HS', length: 13},
 ]},
]

Creating this was somewhat painful trial & error.  However, at least the interpreter is working!

As a final step then, let me use the parser to create the intermediate representation from the MBDL version.  There isn't much to show about that effort; I had to correct a few field names but otherwise it worked fine.  I used a slightly different version of MBDL for the border:

[B(5,37,"black",2,"white") B(5,37,"black",2,"black")] 
VS(3)
L(3,"black") 
{L(10,"rgb(222,183,64)")} 
[E(5,5,"black",1,"red") HS(-5) E(2,2,"none",0,"white") HS(10)]
L(3,"black")

This draws the same border but in a slightly different way.  I also changed the syntax for overlays to use braces {} rather than parentheses just to distinguish it a little more clearly from the other syntax.

To illustrate why I want to draw from inside to outside and not automatically place the border outside the map, I can add a negative vertical space to the start of this border to float the map scale inside the edge of the map:

So now I have (most) of the infrastructure in place for procedural generation of map borders:  a language for describing borders, a parser for the language, and routines to execute the parsed representation.   Now I just have to tackle the tough part -- figuring out how the procedural generation!