[Jongware]
Most recent update (All By Hand(TM)): 1-Apr-2006 01:04

 

Gründlich durchgecheckt steht sie da
Und wartet auf den Start. Alles klar.
Experten streiten sich um ein paar Daten,
Die Crew hat dann noch ein paar Fragen,
Doch der Countdown läuft.

Peter Schilling, Major Tom

 

The Frontier Galaxy VI: Random Synaptic Firings

By this time people may think all I do is peering to computer screens. Actually, I do that 9 to 5 for a living; so every now and then I slump down on my couch in a thouroughly non-ergonomic way, grab a favourite book off the pile to my right (this pile being sort of First In, Last Out stack — but the actual movement of a single book is much, much more complicated, where some individual book, or series, or writer can fall in or out of favour for various lengths of time), and read quietly for any lengths of time, frequently passing the midnight hour until I get to the "good" part. People are generally non-plussed when I reveal that I read my favourite books over and over again, leaving them discussing my mental sanity in general and specifically my memory capacity. But it's not as if I don't know the end anymore, or forgot about the main plot or major surprises. It's the little things that grab my attention, little puzzles, cunning sub-plots, inside jokes, and word play. If you have no idea what I'm talking about, just read Neal Stephenson's Cryptonomicon once, cover to cover. Think about it for a few weeks, pick it up, and start reading again at page 1; I am 100% positive that, although you know how it all ends — unless you have a really bad memory-related problem — it still is a very good read, and you just have to go through it all again.

When reading a really good book, I tend to get sucked into the universe created in the writer's mind; and if I find myself capable to actually believe in that universe I deem the book worthy of rereading. If there are more books that take place in the same 'universe', I read those as well; other work of the same author gets at least a serious look. It all started with the space operas by Leiber, Vance, Niven and Russell, and nowadays, since these writers all appear to have been abducted by envious aliens (some of them for good, some to be returned with radically altered memories, rendering them uncapable of returning to their previous magnificence), Bruce Sterling, William Gibson, Terry Pratchett, Alastair Reynolds, Stel Pavlou, and Peter F. Hamilton.

The latter stunned the world a few years ago with the publication of the Night's Dawn trilogy. If you love science fiction and you've never heard of it, give it a try; Hamilton creates a universe well worthy of scifi giants long gone. One of his imaginative alien races are called the Tyrathca, and they have an original way of designating stars and planets... Now I'm getting to the point!

Their planets and star names — and their individual designations as well — are composed of two or three syllables, followed by an hyphen and two or three capital letters; their home world, for example, is called "Hesperi-LN". A very simple scheme; in fact, so simple I thought "why not try and fit it into Frontier?"

Due to the way my memory is wired, I was sure there were lots and lots of examples of those names in the 1150-odd pages of the entire trilogy. Not so, though. Scanning for this specific pattern revealed only 14 different occurrences! Now, being a bithead, I like my binary numbers to be round, and so I added another name from the book (having this same pattern, though he's not one of the aliens) and number 16 popped up in memory because of the pattern. The list, therefore, looks like this:

Anthi-CL
Baulona-PWM
Coastuc-RT
Danversi-YV
Hesperi-LN
Lalarin-MG
Mastrit-PJ
Quantook-LOU
Rittagu-FHU
Sireth-AFL
Swantic-LI
Tanjuntic-RI
Tojolt-HI
Waboto-YAU
Twelve-T
Saturn-V

Next, I tried to find a way to divide these names into separate parts which could be joined "at random"; and preferrably not leading to repeating syllables such as "Ackackack" or unpronouncable as "Essququ". I decided to split each name into three parts — not on a syllable boundary, but ensuring they could be joined together again in as many 'reasonable' ways as possible. The words were therefore broken up like this (discarding the part after the hyphen):

"A",   "nth",  "i",
"Bau", "lon",  "a",
"Coa", "st",   "uc",
"Dan", "ver",  "si",
"Hes", "per",  "i",
"La",  "la",   "rin",
"Ma",  "str",  "it",
"Qua", "nt",   "ook",
"Ri",  "tt",   "agu",
"Si",  "r",    "eth",
"Swa", "nt",   "ec",
"Tan", "junt", "ic",
"To",  "j",    "olt",
"Wa",  "b",    "oto",
"Twe", "lv",   "e",
"Sa",  "t",    "urn"

Note how I changed a couple of strings (the ending -ic, for example) because they occured more than once.

The part after the hyphen seems to consist of two or three random characters, and I decided to handle those in the code.

The code I came up with is this:

char *altname[16][3] = {
    "A",   "nth",  "i",
    "Bau", "lon",  "a",
    "Coa", "st",   "uc",
    "Dan", "ver",  "si",
    "Hes", "per",  "i",
    "La",  "lar",  "in",
    "Ma",  "str",  "it",
    "Qua", "nt",   "ook",
    "Ri",  "tt",   "agu",
    "Si",  "r",    "eth",
    "Swa", "nt",   "ec",
    "Tan", "junt", "ic",
    "To",  "j",    "olt",
    "Wa",  "b",    "oto",
    "Twe", "lv",   "e",
    "Sa",  "t",    "urn" };

void GetSystemName (int xl,int yl,int Sysnum, char *dest)
{
    int bx;

    bx = 48;
    do
    {
        if (KnownSpaceCoord[bx-1][0] == xl &&
            KnownSpaceCoord[bx-1][1] == yl)
            break;
        bx--;
    } while (bx > 0);

    if (bx > 0)
    {
        bx--;
        strcpy (dest,KnownSpace[KnownSpaceName[bx]+Sysnum]);
        return;
    }

    for (int i=0; i<sizeof(ForcedNames)/sizeof(ForcedNames[0]); i++)
    {
        if ((Sysnum<<26)+(yl<<13)+xl == ForcedNames[i].Coordinate)
        {
            strcpy (dest, ForcedNames[i].Name);
            return;
        }
    }

    xl += Sysnum;
    yl += xl;
    xl = _rotl (xl, 3);
    xl += yl;
    yl = _rotl (yl, 5);
    yl += xl;
    yl = _rotl (yl, 4);
    xl = _rotl (xl, Sysnum);
    xl += yl;

    strcpy (dest, altname[xl & 15][0]);
    xl = _rotr (xl, 4);
    strcat (dest, altname[xl & 15][1]);
    xl = _rotr (xl, 4);
    strcat (dest, altname[xl & 15][2]);
    strcat (dest, "-123");
    xl = _rotr (xl, 4);
    dest[strlen(dest)-3] = 'A'+(xl % 26);
    xl = _rotr (xl, 5);
    dest[strlen(dest)-2] = 'A'+(xl % 26);
    xl = _rotr (xl, 5);
    if ((xl & 31) < 26)
        dest[strlen(dest)-1] = 'A'+(xl & 31);
    else
        dest[strlen(dest)-1] = 0;
}

If you exchange the existing GetSystemName routine with this one you will see pretty cool Hamiltonian names — and fully at random, too! Compare the image of Sector (0,3) below with the original, all stars are in the same position but their names are different.

There is a drawback to ruthlessly replacing the name generating routine. "Tiesscan", "Veurve", "Anlave" and "Sodagre", though alien-sounding, are actually deep inside the Human Colonized space, and thus should have human-sounding names. Another flaw is that the rest of the entire galaxy gets Tyrathca names, which makes them look a lot more powerful than they appear in the books.

An aesthetically pleasing solution would be to do a distance check to some central star or sector — similar to what is done in the routine GetSystemDescription — and to generate a 'human' name for worlds obviously belonging to 'us', Tyrathca names for 'them', and some unbiased pattern for the rest of the galaxy, for example, a few uppercase letters, followed by a hyphen and a number (the return of 'LV-42'!).

A scientific scheme

Elaborating on that: using only two letters and two numbers is not remotely good enough. A quick calculation, using only alphabetics, shows that 267 is just a tad more than the 232 possible stars (this is the absolute maximum number of stars, based on the fact that sector coordinates and system number always can be packed into a single unique dword). Now 7 random letters do not make interesting names. Divide 232 by 1000 (and append up to 3 decimal digits) and you end up with 5 letters. Divide by 10000 and you get 4 letters and 4 digits. Hey, not too bad! The advantage of using this method is that it ensures that every single star gets its own unique name.

 

Let's get that down in code. Here is another GetSystemName.

void GetSystemName (int xl,int yl,int Sysnum, char *dest)
{
    int bx;
    unsigned long uniqueid;

    bx = 48;
    do
    {
        if (KnownSpaceCoord[bx-1][0] == xl &&
            KnownSpaceCoord[bx-1][1] == yl)
            break;
        bx--;
    } while (bx > 0);

    if (bx > 0)
    {
        bx--;
        strcpy (dest,KnownSpace[KnownSpaceName[bx]+Sysnum]);
        return;
    }

    for (int i=0; i<sizeof(ForcedNames)/sizeof(ForcedNames[0]); i++)
    {
        if ((Sysnum<<26)+(yl<<13)+xl == ForcedNames[i].Coordinate)
        {
            strcpy (dest, ForcedNames[i].Name);
            return;
        }
    }

    // First, generate a unique id for this system
    uniqueid = (((unsigned long)Sysnum)<<26)+(((unsigned long)xl)<<13)+yl;
    // Jingle the numbers a bit
    uniqueid ^= (((uniqueid >> 11) ^ (uniqueid << (32-11))));
    uniqueid ^= (((uniqueid >> 4) ^ (uniqueid << (32-4))));
    uniqueid ^= (((uniqueid >> 11) ^ (uniqueid << (32-11))));

    // generate the 4 letters
    *dest = 'A'+(uniqueid % 26);
    dest++;
    uniqueid /= 26;
    *dest = 'A'+(uniqueid % 26);
    dest++;
    uniqueid /= 26;
    *dest = 'A'+(uniqueid % 26);
    dest++;
    uniqueid /= 26;
    *dest = 'A'+(uniqueid % 26);
    dest++;
    uniqueid /= 26;

    // A hyphen
    *dest = '-';
    dest++;

    // What's left in decimal, anything up to 4 digits
    sprintf (dest, "%04d", uniqueid);
}

The uniqueid doesn't need to be constructed in the same way the actual system's UniqueId is; all we care for now are is that the entire bit range is being used.

The jingle part uses only xor so the total amount of bits set and unset will remain the same! The bit shuffle is necessary because we want the names inside any given sector to be as different from each other as possible.

If you are proficient in math and it really doesn't work that way, please don't kill me! I am just assuming this to hold... If you read this 6-Sep-2005, the changes in the bit jingling are due to a pattern I discovered!

A major difference with the original GetSystemName routine is that bits don't get masked using the and operator, I want the full range of characters available. Hence the mod operators for the letters. After subtracting these from the generated number there should be anything from 1 to 4 decimal digits left, they are just appended at the end.

To get an idea how this 'scientific' map looks, here is the output of my ASCII map generator. It is centered on Phekda (unchanged because the predefined names are still checked). Again, if you compare it with the actual game map of (-2,5) you will see that the star positions are all the same.

+-(1,6)--------------------------+-(2,6)--------------------------+-(3,6)--------------------------+
|                                |                                |                                |
|                                |                                |      * SNXG-5691               |
|          * Megrez              |                                |                                |
|                                |                                |                                |
|                                |           * GWWR-5398          |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |  * LYSS-5554                   |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |                                |                 RXPY-5571      |
|                                |                                |FPFV-4947            *          |
|                                |                                |   * XPTH-5847   MVTX-5415 *    |
|                                |                                |                                |
|                                |                                |                                |
+-(1,5)--------------------------+-(2,5)--------------------------+-(3,5)--------------------------+
|                                |                                |                                |
|                                |                                |                                |
|XLTY-5968                       |                                |                                |
|   *          * AOPZ-6124       |                                |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |* Phekda                        |                                |
|                                |                                |                     Merak *    |
|                                |                                |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |                                |                                |
|                                |                                |                                |
+-(1,4)--------------------------+-(2,4)--------------------------+-(3,4)--------------------------+
|* SQUS-6831        *NDJB-6437 * |             * HILJ-5793        |                  FEAR-6122 *   |
|      *        GRWC-5308        |                                |                                |
|  VLWM-5739                     |                                |                                |
|                                |                                |                                |
|* YIJR-6005   * NANK-6712       |GLRN-6573   * ENJP-6885         |                                |
|               XSQT-6987 **     |   *    *    *  * JPFQ-7041     |                                |
|                 *LTSD-5464 *   |    SEZL-6261                   |   * BFOD-7022                  |
|                 * IBNA-6281    |        *     * JGTH-5481       |                                |
|                                |  * LNNO-6729                   |       * WCSC-6866              |
|                                |         * ZEDL-6105            |                                |
|            * BELL-4913         |                                |                                |
|                  * LWOU-5188   |    XGVM-6417                   |                 RMKU-6746      |
|               * IYQJ-6556      |        *    UCHK-5949        * |                     *          |
|                                |                 *  * CGPI-5637 |                                |
|  * QJAM-5583                   |                                |             MKOT-6590 *        |
|                                |                                |                                |
+--------------------------------+--------------------------------+--------------------------------+

A nice side effect is that not the entire range of "AAAA-0000" through "ZZZZ-9999" will be used, since only 500 million stars out of the 4 billion possible are generated; not one sector is filled to its theoretical capacity of 63 stars.

See the interesting names BELL-4913 in Sector (1,4) and FEAR-6122 in (3,4)? All kinds of four-letter words are going to pop up in unexpected places...

 

Just random thoughts, really, but it's stuff like this that will make your map stand out!

<< Previous :: Next >>

[Jongware]

Based on original data and algorithms from Frontier:Elite 2 and Frontier:First Encounters by David Braben (Frontier Developments)

Original copyright holders:
Elite 4: The Next Encounter © David Braben 2011?
First Encounters © David Braben 1995
Frontier © David Braben 1993
Elite © David Braben and Ian Bell 1984

 

For any real questions -- I will not provide the complete source code! -- you can drop me a mail at jongware.