Map Borders (Part 14)

(Author's Note: I have an unusually busy summer this year, with much personal travel, house projects, and other tasks to compete with Dragon's Abound, so posting will be sporadic.  I hope to get back to a more regular schedule in the fall.)

Now that I've spent over a month implementing Celtic knotwork, it's time to integrate it into the drawing of map borders.  In my inspirational maps, knotwork usually shows up as a long element that stretches across an entire border edge (and occasionally around the corners):

I have not attempted to run a knot around a corner (TODO!) but I do have the capability to run a knot along an edge, so let me add that as a possible map border.

The first thing I need to do is add a new element to the Map Border Description Language (MBDL) for a Celtic knot.  This looks a lot like a line element, since it's meant to stretch from corner to corner.

   K(width, cord width, color)

   K(14,5,"red")

Here “width" is the total width of the knot, “cord width" is the width of the cords within the knot and “color" is the color of the cord.  So when Dragons Abound hits this in an MBDL, it will draw a knot of that width to fill the border from corner to corner.  Here's an (ugly) first (actually fifth) attempt:

Note that the pattern goes into both corners.  That's because I've based this on the line drawing routine.  Lines go all the way into the corners but end with a miter so that they meet up correctly.  That won't work for knots, so I'm going to have to do something else.

You might also notice that the knot doesn't actually go all the way into the right corner.  That's because the knot has to have an odd number of elements in both dimensions.  It needs one more element to fill out the space completely, but that would be an even element so it is dropped.

I could start the knot in one corner and have it stop short of the next corner, like this:

However, that's going to look a little odd once the right and left sides get drawn in.  A better solution might be to stay out of the corners entirely with knots:

That seems reasonable, at least until (if) I figure out how to make knots join up in the corners.

Now let me address the second part of the problem.  The example above stops somewhat short of the corner, for the reasons mentioned above.  It's also possible for the knot to run slightly long for similar reasons:

The fundamental problem here is that I can't easily stretch or compress a knot except by lengthening it or shortening it by two elements.  The square aspect of the individual elements is pretty much built into the knot layout.  What I can do is tweak the length of the knot by changing the width of the knot, since that will also change the length. The Celtic knot map border element specifies a width (e.g., 25 pixels) but I vary that slightly to make the length work out better.  One subtlety is that I can only make the pattern narrower; if I make it wider it might unintentionally end up overlapping some other part of the border.

Here the code has made the width of the knot slightly smaller and added an element to make the knot stretch exactly from corner to corner.

That fixes square maps, but what happens when I have a map that isn't square?  A pattern that fits the long side will be too long for the short side, and a length tweak like the one above won't be sufficient to cope.

My solution is to use a shortened version of the knot on the short side.  To create the shortened version, I'll cut off the ends of the long version symmetrically.  So I'll essentially show as much of the middle part of the long knot as will fit.  This is a little bit tricky because of how the knot is represented in the array; basically I have to be careful not to turn even columns into odd columns (or vice versa) when shortening the array.

It's a little hard to see variations in the knot with the flat red color, so before I jump into shortening, let me fix the knot display.  The code for displaying a knot takes a display representation that is a list (array) of widths and colors, and by building these up properly I can create cords with borders and highlights, etc.  But the MBDL I showed above for a knot only takes a single color.   Let me change the MBDL specification so that it takes an array of widths and colors:

   K(width, displaySpecification)

   K(14,[[4.4, "black"] [2.4, "powderblue"]])

This requires writing a grammar for an array of arrays in order to parse the display representation, but in Nearley it's not that difficult.

So with that working, here's an example of an asymmetrical border:

If you compare the end of the left border with the top border, you can see how the top border was shortened to fit in the shorter left border.  (It's kind of fun to try to find the exact spot, so I won't spoil it for you :-)

Now that I've displayed a random border, you may notice that the knot wiggles back and forth where straight segments meet up in a row:

This looks okay, but I thought I'd like to have the option to have the line run straight.  This is a two step process.  I have to change the code slightly so that cords drawn on the top and bottom of a wall are at the same offset, and then I need a special case to extend those cords to meet adjacent cords when they are both horizontal.  It turns out that if I do this for the normal style shown above, it essentially makes that style look like the squared knot style, so that's not very useful.  However, the same fix for the squared knot style makes it look more consistent and better in my opinion:

The circle style also has the wiggle, so now I have two styles with the wiggle and one without.

That covers square borders, but Dragons Abound also has borders with offset corners. There are three kinds of corner offsets (square, diagonal and round) but making knots run around these corners seems pointless; they normally won't be big enough to accommodate a knot, so I'll just make the knot stop at the beginning of the offset:

I also need to experiment to see how small I can make the knot and have it look okay at map size.  This is about as small as works well:

This is 22.5 pixels across, which is perhaps a little thicker than I'd like but not unreasonable.  The normal and round styles need a little more room to look good, about 28 pixels:

It might be that I can make these tighter if they're on a black background.

So far every knot I've shown has had four cords.  Using two cords doesn't really produce what we think of as a Celtic knot, but it looks kind of interesting:

That could be interesting as an occasional change of pace.

I'll also add the possibility of a knot with no random breaks in it.  This produces a regular weave:

That also looks nice.

Having looked at four cords and two cords, I should try six cords.  This is impressively complex:

but probably too “overkill" for regular use.

Here's an example of the knot in use in a map border:

There's probably some work to be done here with colors and tweaking the various sizes, but for now I'm going to move on to another way to use Celtic knots in a map border.

Recall that Dragons Abound has a border style I call patterns, which consists of repeating elements along the border:

In this border I have stars, flowers and diamond shapes repeating.  What I want to do now is add a short Celtic knot as a possible element in a repeating pattern.  This is (relatively) straightforward -- adding the Celtic knot as another type of thing that can be in the pattern:

The knot in the example above is a braid.  Using a random knot is a little tricky:

In this border I created a random knot every time I drew a knot in the pattern.  This looks a little odd.  What I want is to draw the same random knot every time.  Unfortunately, the structure of this code makes that difficult to do cleanly, so I have to resort to using a global variable to hold the knot between the times when it is drawn:

There are a few bugs to clean up (primarily with shading) but this post is already overdue, so I will end here.  Next time, corner boxes and that will be the last of map borders for now!

Map Borders (Part 13)

When I left off last time, I'd gotten the basic display capability working:

One problem that you can see above is that there are some artifacts where the individual segments of the pattern join up.  This occurs because the browser introduces some anti-aliasing artifacts where two SVG elements meet exactly.  One way to address this is to overlap the elements slightly to try to eliminate the seams.  There's a bit of black magic and experimentation to figuring out how much you have to overlap and in what order (and worse, this varies depending upon the magnification of the SVG), but after some tweaking I have removed most artifacts:

I've got a growing list of things to do with Celtic knots, but before I tackle anything else I want to add shading to accentuate the crossings.  The basic idea can be seen on this tutorial page:

The idea is to add some shading to either side where a cord passes under another cord.  There are various ways to do this in SVG, but the simplest for me is to draw another line on top of the cord and fill it with a transparent gradient:

I've left it pretty subtle here, but if this lacks impact I can go back and tweak it as necessary.

While I was adding that code I also parameterized various other constants -- a couple of which control whether I use “hand-drawn" lines.  There are some challenges with using hand-drawn lines where something is pieced up of different parts and where lines are laid atop one another.  The code takes care of making sure that end points don't move around, but it's possible that angles can change so that segments no longer meet smoothly.  So if I use it, I will have to use a fairly small amount of jitter.  Here's an example with about the maximum decent perturbations:

I could also vary the width of lines, but that would be even more problematic so I don't think I'll allow that as an option.

Next I'm going to implement a more rounded style of knot.  This works the same as the existing style, except the cords that meet horizontal and vertical walls are replaced by quarter circles.  I already have a routine to generate circular arcs, so this change is mostly a matter of figuring out the right arcs and then tweaking them so that they don't reveal any anti-aliasing artifacts where they overlap.

Another common style squares off the turns in cords, as in this example:

This is a little trickier to implement, because how a cord that meets a wall is drawn depends upon whether it's neighbor in that direction is also meeting a wall.  For example, cords that meet horizontal walls work normally (as they do in the first style) except if they have a vertical wall to the right or left, in which case they go straight into the corner:

Here I'm showing just crossings and one half of the pattern for a horizontal wall.  Along the middle bottom of the pattern it looks the same as in the first style.  But in the corners, where there's a wall next to it, it goes straight into the corner.

(In the middle of implementing this style, I decided to refactor the code so far to simplify some of the special cases that have built up.)

After implementing all the other cases:

The appeal of this style is that it more clearly defines the boundaries of the knot.  Unfortunately, the anti-aliasing problem in the mitered corners here is very hard to get rid of completely.  Close inspection of the knot above will show some problems.  I tried a number of different approaches with no real luck.  I'm going to declare myself defeated on this issue for the moment.

There's one more style capability I want to implement before I move on, and that's the capability to blur the cords.  (The purpose of this will become evident below.)   This is a little tricky because of the way SVG implements blur.  If you apply blur to an SVG element, the blur can spread anywhere within the object's bounding box.  So if I just apply a blur to cord, it smears into the adjacent areas:

You can see how the cord no longer has sharp edges because the white has blurred into the black spaces, and even over the red outline.  To prevent this, I have to clip the blur to shape of the cord. (And hopefully I can do this piecemeal to each of the segments of the cord.)

Here I've created clipping paths for some pieces of the knot and applied a blur.  You can see how the blur now ends sharply at the edge of the piece.

Unfortunately, as I continue implementing this I discover that I can't in fact implement it piece-meal:

As you can see, there are some pretty obvious artifacts at the joints where the clipping areas meet.  (The same locations as the anti-aliasing problems!)  In retrospect, using clipping areas was probably a poor choice.  Difficult to implement and with some predictable problems.  A much better choice is to use a mask.  It's also easier to construct; I just draw into the mask at the same time I'm drawing onto the screen.  I like to leave at least a few stupid dead-ends in these write-ups so that you don't think I'm some kind of super-human coder.  I'm definitely not!

With the mask in place:

If you compare this blur to the earlier full pattern blur, you'll see this one stays cleanly within the pattern.

So why go to all this trouble for blur?  With blur and careful color choice, I can create a faux-3D style:

I can also draw the same knot in gray underneath this knot, offset it and blur it to create a shadow:

I'm not sure this is very useful for map borders, but it is pretty!

That's enough styling (for now).  Now I want to move on to a few capabilities I'll need to use knots in borders.

The first capability I want is to be able to turn a knot 90 degrees.  This way I can draw a knot along the top border, turn it 90 degrees, draw it along the right border and so on.  One way to do this is to always draw it horizontal and then use an SVG transform command to rotate the whole thing.  I might well end up doing this, but I'd like to explore the option of actually rotating the knot pattern before I draw it.

Recall that the knot pattern is just an array filled with values for CROSSING, VERTICAL, and HORIZONTAL.  To rotate that 90 degrees, I need to create a new array with the x and y sizes swapped, and then copy values into that new array.  The non-obvious part is that when copying, I have to swap VERTICAL walls for HORIZONTAL walls, and vice versa.

Okay, so now I can rotate the knot if necessary.

Another feature I need is to be able to repeat a knot to fill a particular length.  For example, to take the above knot and repeat it three times.  Obviously I can draw the knot repeatedly end to end:

But that leaves obvious seams where the knot begins and ends.  What I'd like to do is eliminate the seams by connecting the knot end to end to create a single bigger knot.  This involves repeated copying of the knot and replacing the end walls with crossings (lower image):

Right now my implementation is limited to whole numbers of repeats.  I can imagine situations where it might be nice to have a partial repeat, but I'll cross that bridge if I get to it.

The next feature is the capability to save and restore a knot.  I'm not entirely sure I'll want to be able to save a particularly good knot to use over again, but it doesn't seem too far-fetched.  The knot is defined by it's dimensions and the pattern of crossings and walls encoded in the array.  The array can be saved as a long string of characters representing crossing and walls.  The sample knot I've been using comes out like this:

25,5,.|.|.-.-.-.X.X.-.X.-.|.X.-.X.-.X.X.-.|.-.X.X.-.X.-.X.X.-.-.-.|.X.-.-.-.X.X.-.X.-.X.X.-.

|.-.X.X.-.X.-.|.X.-.X.-.X.X.-.-.-.|.|.

Long, but not intended to be particularly human-friendly.  Restoring involves reading the dimensions and making sure the knot is the correct size, and then loading the long string into the array that represents the knot.

The last (?) feature I know I'll need is to create a random knot.  At some level, creating a random knot is just taking a vanilla knot and randomly dropping in some vertical and horizontal walls (handcrafted on top, random below):

But as this example shows, there are some constraints that need to be met.  The “gaps" need to be maintained, and (for my purposes anyway) the walls around the edge of the knot need to be maintained.

That produces a legal knot, but it's not necessarily very appealing.  And, as this example shows, vertical walls in the same column can chop the knot in two, which probably isn't what I want.  I don't really want a completely random knot; I want one that is semi-random but still “beautiful."

I'm not exactly sure what makes a knot beautiful but one element is symmetry.  Since I'm generating long knots, I will use mirror symmetry on the X axis.  This is easy to implement:  Every time I place a wall, I also place the same wall at the symmetrical position:

This goes a long ways towards creating an acceptable knot.  I can still get placements that chop the knot into pieces:

This is actually three knots.  But I'm not sure this is bad.  Here is another example of a knot getting broken into separate pieces:

This also seems okay to me.  So maybe symmetry is all I need to create an acceptable random knot.  I'll at least start with this and see how it works out.

A sampler of styles:

Next time I'll start working (at long last!) on using Celtic knots in map borders.