Map Borders (Part 8)

I still have some features I want to implement for map borders (Celtic knots!) but it's probably time I make some attempt at procedural generation of borders.  I've been dragging my feet for a couple of reasons.  Primarily I don't have any really great ideas about how to generate interesting borders -- and the notions I do have, have problems.

My intention has been to generate map borders using a generative grammar, similar to the approach I have taken for generating map names.  Part of the reason I developed MBDL was because the tools for generative grammars (like RiTa, which is what I use) are developed to generate text, so it's easier to use a tool to generate MBDL than to (say) generate the actual graphics.

However, there are some limitations to this approach.  Most of the generative tools (including RiTa) implement context-free grammars.  The context-free part of this means that the grammar rules always have a single symbol on the left-hand side, like these examples from Lost Coast names:

<coast> => coast | shore | banks
<lost> => lost | forgotten | accursed
<monster> => Zombie | Kobold | Orc
<adj> => <lost> | <monster>
<name> => The <adj> <coast>

Context-free grammars are pretty versatile, but there are some things they just cannot generate because of the limitation on the left-hand side.  One of those limitations pops up when you want to generate matching (or symmetrical) output.  Suppose you wanted to write a grammar that created a border with matching lines around an interior pattern.  You could write something like this:

<output> => <lines1> | <lines2> | <lines3>
<lines1> => 'L' <other> 'L'
<lines2> => 'LL' <other> 'LL'
<lines3> => 'LLL' <other> 'LLL'
<other> => ...(etc)...

This would generate one, two or three matching lines around <other>.  Now suppose I want to extend this to be any number of lines.  The obvious way to do this is to write a rule to generate a random number of lines:

<output> => <lines> <other> <lines>
<lines> => 'L' | 'L' <lines>
<other> => ...(etc)...

Here the <lines> rule generates a single line, or a single line followed by a <lines>.  This will generate some random number of lines.  But the two uses of <lines> in the <output> rule won't necessarily produce the same random number of lines!  To do that, the second use of the <lines> rule would have to know about something that happened in another place in the grammar -- it needs “context" which it cannot have in a context-free grammar.

Because of this limitation, you can only implement symmetrical output within a single rule.  This is a pretty crippling limitation for generating map borders, because as we have seen in many examples, symmetry is an important part of almost every map border.

This sort of limitation pops up more frequently than you might imagine, so most generative grammar tools have built in at least some additional capabilities to get around these limitations.  RiTA, for example, includes the capability to execute arbitrary Javascript within the grammar.  However, at some point the workarounds become so complex and kludgy that it becomes hard to maintain and eliminates most of the advantage of using a context-free grammar in the first place.  The more I thought about what I wanted to do for map borders the less I liked the idea of kludging a fix using embedded Javascript, etc.

Eventually I realized that in this case I had another option because I'm also defining MBDL.  While it might be impossible to implement symmetry in a context-free grammar, I could implement symmetry within MBDL itself.  It sounds counter-intuitive, but I can add symmetry to MBDL and still be able to parse it using a context-free grammar, and also be able to generate it using a context-free grammar!

To add symmetry to MBDL I need two features.  First I need to be able to mark a sequence of map elements, and then I need another marker to show where to (symmetrically) re-create the marked elements.  I need a pair of symbols for this, and I'm starting to run out of handy symbols in MBDL, so I'm going to (re-)use parentheses for marking a sequence of elements.  I'll use the dollar sign to show where to recall the original sequence.  So for example:

(L(1,"black") VS(3) L(1, "red") VS(3) L(1, "blue") VS(2)) L(3,"gold") $

This says to draw black, red, and blue lines, then a gold line, then repeat the same black, red and blue lines.

A couple of notes about symmetry.  First, I don't really want to reproduce the saved sequence, I want to reverse it and then reproduce it.  I want it to be symmetrical around the middle of the pattern.  In the above example, the black lines should be on the outside of the border, so I need to flip the saved sequence before generating it again.  Second, I will allow saving multiple sequences.  In this case, the last sequence saved will be the first one reproduced.  Again, this will maintain the mirror symmetry for the border.

Here is an example, using this border:

(L(1,"black") VS(3) L(1, "red") VS(3) L(1, "blue") VS(2)) L(3,"gold") $

Note that I can generate the same border with this MBDL:

(L(1,"black") VS(3)) (L(1, "red") VS(3)) (L(1, "blue") VS(2)) L(3,"gold") $ $ $

which uses three save/recall sequences.  The first recall brings back the last saved sequence, so this is the equivalent of doing it all in one save/recall.

With that implemented, I can start writing a generative grammar for MBDL.  I can certainly use this to generate a variety of borders similar to my example borders, but I'm not sure it will be able to create new and interesting borders.  At any rate, I don't have any better ideas at the moment, so I'll press on with this and see where it goes.

To start off with, I'll implement some rules to generate simple line borders:

<Color> => "black"
<Width> => `Utils.rand(1, 3)`
<Line> => L(<Width> <Color>)
<VS> => VS(`Utils.rand(2, 5)`)
<Border> => <Line> |
              <Line> <VS> <Line> |
              (<Line> <VS>) <Line> $ 

(Anything within backticks is executed as Javascript; in this case to generate random numbers.)  If you examine the rules, you'll see that a Line is black and has a width of 1-3.  A vertical space is width 2-5.  Finally, a Border is either a Line, two Lines separated by a vertical space, or three Lines with the outer two symmetrical.

I'm not sure I want to have offset corners decided as part of the border creation, but at least for the moment I can add that in as an option:

<LineBorder> => <Line> |
                <Line> <VS> <Line> |
                (<Line> <VS>) <Line> $
<Border> => <LineBorder> [3] | O(CLIP, SQOFFSET) <LineBorder> [1]

The numbers in brackets are weights.  In this case, it means that square corners will show up three times as often as offset corners.

In the reference maps there's a border version with a thin inner line and a thick outer line.

<Thick> => `Utils.rand(8, 12)`
<ThickLine> => L(<Thick> <Color>)
<Border> => <Line> |
            <Line> <VS> <Line> |
            (<Line> <VS>) <Line> $ |
            <Line> <VS> <ThickLine>

There's also a version with what look like narrow white lines one either side of a thick central line.

<Border> => <Line> |
            <Line> <VS> <Line> |
            (<Line> <VS>) <Line> $ |
            <Line> <VS> <ThickLine>
            ((<Line>) <VS> $ <VS>) <ThickLine> $

The next kind of border has overlapping lines like this:

Creating this is tricky -- it involves moving outward to draw the square offset lines and then back in to draw the regular lines.

<hothachar> => {O(SQOFFSET, 40)
                O(CLIP, SQOFFSET, 18, 40) VS(18)
                (<LineFilled>)}
               O(SQOFFSET, 0) $',

(“Hothachar" being the name of the map the inspired this border.)  It would be preferable to not hard-code the various offset distances, but that would require some fussing around with embedded Javascript.  I have a notion how to do this more cleanly, but it will require me to implement a new RiTa language feature.  (See below)

The last of the simple line borders from my reference maps is a colored border.  For now I'll just implement a few simple color choices.

<FillColor> => "gold" | "darkgreen" | "darkred"
<ThickFilled> => <Line> <VS> (<Line>) L(<Thick>, <FillColor>) $

Which generates this:

If I need to generate two completely identical lines, I can use the “save" and “recall" feature of MBDL to do that.  But suppose that I want to generate two lines that have the same width, but different colors:

That turns out to be difficult to do.  When I draw the first line, I can randomly select a width for the line, but in a context-free grammar there's no way to remember that choice and reuse it later.  This is the same problem I had in implementing the “Hothachar" border above -- I didn't have any way to pick a random offset and then remember it for reuse later.

This is a pretty handy feature to have, so many tools implement some way to do this.  However, the tool I'm using, RiTa, doesn't happen to provide this feature, so I'm going to add it.  The implementation is pretty simple.  If the left side of a rule starts with a dollar sign, I'll treat it as a one-time rule:

$width => 18 | 19 | 20
<Line> => L($width, <Color>)

The first time a one-time rule is encountered, the rule fires as normal to create a value.  Any time after that, the one-time rule just reuses whatever value was generated the first time it was fired.  This is also the capability I need to avoid hard-coding values in the “Hothachar" rules above.

I can use this feature to pick a size for the boxes in a scale and keep all the boxes the same length:

With this feature implemented I have the flexibility to implement a number of additional border forms.  I'm not going to bother showing all the rules from this point; I'm sure you get the idea.

Up to this point I've done lines.  Now let me generate borders with patterns.  Patterns are sequences of repeating geometric shapes, and they provide much more complexity (and interest) than lines.

A simple pattern from one of my example maps has alternating bars and diamonds.  I can generalize that a bit and create patterns with different elements:

One variant is to use colored pattern elements

I used random color choices to generate these examples, but that's clearly not good.  For the moment, I'm going to use a black background for borders and I'll use the land and sea colors from the maps for accent colors.  There's probably more creative ways to handle color, but this will at least tie any color in the map border back to the map.

The example maps also have some borders where the elements are filled with gradients to create a faux 3D effect.  That can be added by using gradients to fill instead of colors:

At the moment I'm limited to some pre-defined gray-scale gradients, but in theory I could create and use color gradients as well.

A problem pops up here with offset corners:

When there's not enough room for even a single repeat of the pattern, things break.  I was fixing this by not drawing the pattern at all, but that leaves an empty corner that looks odd.  I think a better fix is to draw as much of the pattern as possible and then break off.  This puts a partial repeat into each of the legs of the offset corner, which is not ideal but usually looks better than leaving a blank area:

Maybe replacing the pattern with something like small dots would look better?  Something to think about.

Patterns can also have lines on either side to frame the pattern:

These edges can be dashed.

Dashed lines are actually made using a smaller pattern of boxes alternating with spaces.

Dashed lines can also be used to make fancy neatlines:

And various combinations:

Another pattern variant is alternating small and large pattern elements, to get a separator effect.

A skinny bar also makes a good separator:

Another pattern variant is stacked pattern elements:

Currently I'm only stacking similar elements in a fairly simple way: the same shapes, with the “top" element being outlined in black and either white or a pattern color.

Another pattern feature is the “lace edge."  This is made by putting another pattern of touching circles under the main pattern:

If the border has an edge, the lace ends up between the pattern and the edge:

Here are some other lace variants:

 

There's a surprisingly good variety from intermixing a few different shapes with about ten rules.  I can also generate the lace on both sides of the central pattern.  I haven't decided if I like this or not, but implementing it drove out a two serious bugs in my MBDL interpreter, so I guess that was good:

The lace edges also work pretty well as the main patterns in a border:

As sometimes happens, I didn't have any good ideas when I started this phase of implementing map borders, but just plunging ahead and trying different things has produced some decent results.  More to come on borders, but let me end this post with an example map and border:

I really like the “lush tapestry" feel of some of these complex borders.  As always, you should be able to click through for a bigger image.