Improved Automatic Border Generation for TRAVELLER Sectors

Joshua Bell, inexorabletash@gmail.com, http://travellermap.com

Online Demo

To experiment with the algorithm, try out the Interactive Border Generation Demo.

To generate borders for a sector, try out the Border Maker.

Background

Sectors in Traveller are hexagonal grids of 32 by 40 hexes. Each grid space may contain a single star system, represented by a "main world." Further details (multiple stars, multiple worlds) are ignored at this level of representation. The fraction of occupied hexes varies, including at the extreme some large empty areas known as rifts, but outside of rifts the density is generally between 0.3 and 0.6. Each main world has an allegiance to an interstellar polity, or is "non-aligned". Traveller data for sectors has generally consisted of lists of the occupied hexes and the details of the main world compressed into a data format known as Universal World Profile (UWP), commonly shared as "flat" text files with the .SEC extension.

No polity allegiance data is given for empty hexes. It is possible to argue that since there is nothing in such a hex it can't be claimed by a polity, but deep within a large empire it is unlikely that incursions of a foreign force will be viewed with indifference regardless of what hex it lies within. Maps of Traveller sectors — most notably the classic references Supplement 3: The Spinward Marches and Supplement 10: The Solomani Rim, show borders around the edges of polities, thus implicitly claiming the empty hexes.

Recently, several hex maps of Traveller sectors have been produced with polity borders like the following.

Sub-optimal borders

Note the claimed empty hexes (1) that extend outside of the polity with little justification — they don't fall between occupied hexes. Also note the unclaimed empty hexes (2) that are inexplicably unclaimed in the light of similarly claimed hexes nearby (3), and worlds that end up cut off from the main body of the polity due to unclaimed hexes (4).

The features are not present or are rare in the classic Traveller reference materials. One reason is that thanks to fast personal computers and software aids, borders now are often automatically generated.

Spindly borders
Example: Spindly borders c/o T20 Gateway Domain metadata

Automatic Border Generation

One of the best resources for TRAVELLER cartographers today is J. Greely's Gateway to PDF[1] which includes sec2pdf, a tool for generating PDF maps from classic ".SEC" sector format files, and allygen, a tool that "tries to create plausible regional borders for a sector, based on starports, tech level, and population." Greely also defines a ".MSEC" data format for sector metadata beyond simple tables of UWPs, including allegiances, borders, routes, and other features necessary to generate complete sector maps. The tools are provided with full source, and modification and redistribution is encouraged. Sample data is provided for the classic Spinward Marches as well as the Gateway Domain sectors featured in TRAVELLER d20 (T20.)

The allygen and sec2pdf tools also share and define an elegant mechanism for representing borders by defining a traversal from the upper-leftmost hex in a polity proceeding clockwise around the exterior. This is extremely amenable to producing graphical representations of the border.

This author used allygen while generating borders for many sectors for the Traveller Map site (http://travellermap.com), but found that the borders generated suffered from the issues identified above.

The allygen tool determines allegiances for empty hexes per the following heuristics:

This set of heuristics produces reasonable borders, but is prone to the issues noted above. It is also very sensitive to tweaks in the algorithm — reordering or changing any of the heuristics produces very different borders.

The allygen algorithm borders are subjectively most reasonable when dealing with many small polities within a sector, and most notably problematic when dealing with large polities occupying large portions of a sector.

Proposed Algorithm

In order to achieve the goal of automatic border production which matches the hand-crafted borders from Supplement 3: The Spinward Marches and Supplement 10: The Solomani Rim, and are as free from distracting artifacts as possible, a different algorithm must be used.

This algorithm is modeled on formalization of "concave hulls" known as Alpha Shapes[2].

In 2D geometry, a convex hull is the minimal surface surrounding a set of points — consider an elastic band surrounding push-pins on a cork board, and is a well defined shape for a set of points. A so-called "concave hull," by analogy, is an informal notion that humans would tend to draw concave shapes around point sets with obvious concave features — consider the Great Rift separating the Domain of Deneb from the main body of the Imperium.

Imperial border near the Great Rift
The Imperial border is not a convex hull

Alpha Shapes formalize this notion by constructing a convex hull over a set of points via Delaunay triangulation of the set, but disallowing spans over a certain length characterized in the algorithm by α. This tends to produce very reasonable "surfaces" over point sets, when the value of α is carefully chosen.

These algorithms take place in Cartesian space. In the hexagonally quantized space of Traveller, an approximation is used. The following algorithm is proposed.

Rule #1: Erosion

"If a hex is empty, and it has 3 unaligned neighbors, make it unaligned"

This satisfies the heuristic notion that empty hexes that "stick out" from a polity shouldn't be considered part of that polity.

In the following examples, it is assumed that the polity extends above and to the left of the shown worlds. This hints at another challenge when generating borders: the data present in a .SEC file covers only a single sector, so the creation of borders for polities that extend beyond a single sector is problematic. The original allygen tool has some special cases to deal with the fact that .SEC data handles a single sector — a "border" one hex deep is assumed to exist around the sector and may be claimed by various heuristics, but is not unclaimed by others. In the proposed algorithm, the code is extended to load a 3 by 3 grid of .SEC data files so that correct borders can be generated for the central sector.

Iteration 1
Iteration 2
Iteration 3
Iteration 4
Iteration 5
Iteration 6
Iteration 7
Iteration 8
Iteration 9
Iteration 10
Iteration 11

On its own, though, it is not sufficient — this will leave straight spans of empty hexes between filled hexes. In other words, rule 1 produces the convex hull of a polity, but we want the Alpha Shape. Therefore, once a steady state has been reached by applying rule 1, we break out the next heuristic.

Rule #2: Span Breaking

"Break any spans of length greater than 4 - but only in the middle of 3-in-a-row"

Without this rule, "inlets" and "bays" are claimed. For one and two hexes, this is desirable or you end up with "spindly" borders. One notable example is a feature I call the "Horn of Vland." Without this rule, the areas coreward and rimward of the horn would be claimed.

Unlike rule #1, The heuristic does contain "magic numbers" (4, 3) which are derived experimentally:

This is analogous to the careful selection of α-values when producing Alpha Shapes.

The Horn of Vland
Example: The Horn of Vland
Iteration 12
Iteration 13

Then keep repeating rules #1 and #2 until no changes are made. More precisely, apply rule #1 until a steady state is reached, then if rule #2 results in changes, resume applying rule #1.

Iteration 14
Iteration 15

Known Issues and Future Directions

In the following configuration, both hex 1 and 2 are susceptible to erosion, and the occupied worlds become isolated. This can occur in other configurations, such as worlds offset by one column and separated by two hexes. To address this, a new heuristic will need to be introduced.

Known Issue

Non-aligned worlds that end up "within" polities are not considered. In the classic Traveller references, borders are not consistently shown for these hexes.

References

  1. J. Greely, Gateway to PDF, http://dotclue.org/t20/
  2. Ken Clarkson, hull — convex hulls, Delaunay triangulations, alpha shapes, http://www.netlib.org/voronoi/hull.html