[Jongware]
Most recent update (All By Hand(TM)): 25-Feb-2008 01:23

 

You've been delayed in the real world
How many times have you hit and missed?
Your cat-scan shows disfiguration
I wanna laugh myself to death

Guns 'n Roses, My world

 

The Frontier Galaxy I: My God- It's full of stars!

After years and years, people are still stunned to find millions and millions of unique stars in the old games "Frontier:Elite 2" and "Frontier:First Encounters". Though not easy, it is possible to visit (almost) each and every star and see intricate solar systems, planets and moons whizzing around. Each star has its own name, and though these names are repeated when viewed over the entire galaxy it's a tough job finding a single sector in which two stars share their name.

There are countless rumours concerning the Frontier galaxy; one of the most persistent is the existence of a black hole in the center. Another claim is a planet called LV-24 (or something) can be found -- the home of the notorious Aliens. Now you can find out what is true and what not!

Mapping the galaxy

The Milky Way in Frontier:Elite 2/FFE (hence FFE since most of the algorithms are gleaned from there) is a highly random generated, yet self-containing system. Every 'random' star will be randomly created in exactly the same way every time you generate the Milky Way sector it is in, but you don't need to keep tabs on all 513,982,470 unique star systems in memory or even on disk. This is called a 'semi-random' system; every time you feed it the same seed you get the same result. (Note that it's not that different from the so-called 'random number generator' in various programming languages.)

The galaxy is divided into sectors, and each single sector can hold anything between 0 and 62 stars. Some numbers: the Milky Way is 8,192 sectors wide and equally high. In hex form the internal coordinates range from 0x0000 to 0x1FFF; there are 67,108,864 sectors.

Absolute coordinates for every sector start in the bottom left of the Milky way and go up all the way to (8191,8191) in the top right. Relative sector coordinates as seen in the games are centered on the unremarkable star Sol, in absolute coordinates (5912,5412). Conversion from solar-centred coordinates to an absolute position is done by adding 5912 and 5412 to its x and y value; subtracting them from a Sol-relative sector gives the absolute position.

It can be expected that the stellar maps of the Imperium have Achenar (1,-4) as center, and thus have an offset of 5913 and 5408 in absolute coordinates. (And logically the position of Sol will be (-1,4) on their maps. As game players know, Imperial ships are retrofitted with Federal maps on purchase.)

Random sectors

How can all those millions of sectors be viewed at and travelled through? The trick is to generate only one sector at a time; the initial data for a single sector -- the seed -- is based on the absolute sector coordinates. This seed is modified with some code and tables to produce the stars in that particular sector.

The most important 'table' defines the majour outline of our galaxy; in the executable there is a Milky Way image of 128x128 pixels. Now this image, detailed as it seems, is not enough to generate data for each of the 8,192 x 8,192 sectors; in fact, the image is a factor 64 too small, and every pixel stands for 64x64 sectors.

As you can see in the image below, it's quite naive to just zoom in on the Milky Way to get a closer look.

On the left, a grayscale representation of the Milky Way data. In the games it is displayed upside down, and the star density is remapped nonlinear to 16 colors, so it looks different. Trust me, it's the same data. On the right, a small piece has been enlarged linearly.

So Braben et al. used a trick to get rid of the sharp boundaries. If you zoom in on the Milky Way in the game you see that there are no sharp edges. This same algorithm is used to get a magnified bitmap to be used as star density. It's quite a clever algorithm, and I'm not sure how it works. Apparently, on zooming in the edges are averaged against its neighbor pixels to the bottom and the right.

To avoid seeing the same sector over and over whereever it has the same density, there is a table 'SystemDensity', which holds 128 2-byte values to randomize the contents of a single sector. Unfortunately, this is not enough data to avoid the glaring artefacts visible in the center of the galaxy. Since almost every pixel in there returns a max density, the data in the SystemDensity table is overused and one can clearly see it's all fake.

Here is the same part of the galaxy, now zoomed in "smart". Notice how you can see more detail than in the game because of the larger palette used.

There is a tiny caveat. Averaging against the bottom and right pixels seems fine, but what do you do with edge pixels? Wrapping x values around is actually good enough, since all around the edge of the image there is a wide zero-filled border. The exception is at the bottom: in the original game there is an extra row of 128 zero-bytes just after the image proper. Now there is actually another exception. If you look at the code, values are taken from (x,y), (x+1,y), (x,y+1) and (x+1,y+1). That last value needs another extra zero in the milky way array. Technically, it's missing in the original game; however, the array following this one starts with a zero. So be sure to follow the Milky Way image with an array of at least 129 zero bytes.

TheMilkyWay

unsigned char TheMilkyWay[] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, ...
    // Oww, COME ON! You're not expecting me to list the entire image, are you?
	// Click here to get the entire file; it's the 16384 values for the data itself,
	// followed with 128 zeros to prevent overflow artifacts.

SystemDensity

unsigned int SystemDensity[] = {
    0xBF78, 0x5B2F, 0xDF85, 0x3C14, 0xDADD, 0x38DF, 0xE08F, 0x88D7,
    0xB3AB, 0xEA86, 0x1200, 0x8DB3, 0xFF0D, 0xA593, 0xEC66, 0x1988,
    0x8500, 0xC1E7, 0x9281, 0xD7EB, 0x5F77, 0xD6A5, 0x310B, 0x2C98,
    0x906E, 0x2CB6, 0xF137, 0x8ADC, 0x0FC7, 0x76B8, 0xB587, 0x2D1B,
    0xAD4C, 0x1AEB, 0xB749, 0xC60D, 0xB914, 0x1B3A, 0xAA5E, 0x3764,
    0xD7A0, 0x650E, 0xDB8D, 0x3E98, 0x1DDD, 0xD3BB, 0x54A4, 0x66BA,
    0x164F, 0xF3B8, 0x7460, 0xBF9A, 0x7AA7, 0x459C, 0x61EC, 0xF706,
    0x958C, 0x8B54, 0x86E8, 0xC653, 0x5D7C, 0x6AC9, 0xAD35, 0x8B1F,
    0x30C6, 0x7EF7, 0x4E4F, 0xD1F3, 0xD042, 0x4AAC, 0x6F5A, 0x15C4,
    0x4DC3, 0x923C, 0x04E2, 0x2C8B, 0xAB14, 0x9689, 0x5553, 0x92F7,
    0x3BC6, 0x7C86, 0x5E8D, 0xFF7F, 0x8F5C, 0x0450, 0x0BD3, 0xB01F,
    0x2744, 0xDF20, 0xE40E, 0x932C, 0x8B90, 0xCF40, 0x6E2B, 0x81BE,
    0x200B, 0xA64F, 0x2BA4, 0xDCB8, 0xEA35, 0xACC4, 0x1421, 0x9025,
    0x9A98, 0x4993, 0x99EF, 0xB4FD, 0x0BCF, 0x7434, 0x7287, 0xC67F,
    0x1967, 0xF486, 0x12AD, 0xDF33, 0xDF74, 0x2913, 0x2FF4, 0xD76B,
    0x5A2A, 0x8B80, 0xCB01, 0x742B, 0x09B4, 0xC203, 0x56AF, 0xDAD6,
    0x8000, 0x5555, 0x4000, 0x3333, 0x2AAA, 0x2492, 0x1FF0, 0x1C71,
    0x1999, 0x1745, 0x1555, 0x13B1, 0x1249, 0x1111, 0x0FF0, 0x0F0F
};

generate_sector

int generate_sector (unsigned int coordx, unsigned int coordy, int galaxyScale)
{
    unsigned long p1,p2,p3,p4;
    unsigned long eax,ebx,ecx,edx,esi,edi;
    int pixelval;
    if (coordx > 0x1fff || coordy > 0x1fff) return 0;
    pixelval = (coordx/64)+2*(coordy & 0x1fc0);
    p1 = TheMilkyWay[pixelval];    // Current center
    p3 = TheMilkyWay[pixelval+128];    // Next row
    p4 = TheMilkyWay[pixelval+129];    // Next row, next column
    p2 = TheMilkyWay[pixelval+1];    // Next column
    coordx = (coordx * 0x200) & 0x7e00;
    coordy = (coordy * 0x200) & 0x7e00;
    ebx = (p2-p1)*coordx + (p3-p1)*coordy;    // -0x0FB0400...0x0FB0400
    esi = (coordx*coordy)>>15;        // 0..0x7C08
    edi = p4 - p3 - p2 + p1;
    esi *= edi;
    ebx += esi;
    ebx += ebx;
    p1 <<= 16;                // p1 is now VVVV.VVVV.0000.0000
    ebx += p1;
    ecx = ebx >> 8;
    if (galaxyScale < 16)
    {
        ebx = coordx + ecx;
        eax =coordx * coordy;
        (signed long)eax >>= 15;
        ebx ^= eax;
        (signed long)ebx >>= 5;
        ebx &= 0x7f;
        eax = SystemDensity[ebx];
        if (galaxyScale)
        {
            edx = 16-galaxyScale;
            edx *= eax;
            (signed long)edx >>= 5;
            eax = 0xffff-edx;
            ecx *= eax;
            ecx >>= 16;
        } else
        {
            ecx *= eax;
            ecx >>= 16;
        }
    }
    p1 = ecx;
    p1 >>= 10;
    return (int)p1;
}

The variable names betray the origin of the routine: a disassembled version...

What does this routine do? It returns the number of stars in a sector, between 0 and 62. (To get the exact same number as in the games you should check if the result is 63 -- in that case, use 62.)

Call it with the absolute coordinates of your sector of interest. The parameter galaxyScale should have a value equal to the zoom value you want; you can see where it's checked against the threshold "16" to kick in additional randomization of the star field to show more detail. The value should be "0" if you're gonna use this number to generate individual stars from.

Random stars

Every single star in a star map sector needs 5 items of data: its x-, y-, and z-coordinates, its main star type (Braben uses the Hertzsprung-Russell classification), and its multiple status (e.g., single star, double star, etc.). All these are generated in one swoop per sector. The routine to do that expects the sector coordinates, the number of stars to generate, and a place to put'em:

struct {
    signed char x,y,z;
    unsigned char stardesc,multiple;
} coords_t;

and it's not a bad idea to make it a global array:

coords_t coord[64];
// 64? ah well let's make it a (binary) round number anyway. Though YOU can make it 62 if you like.

Now we don't want to generate the same positions over and over for different sectors, we'll need some randomization in that too. So, let's first define a routine to shuffle numbers a bit. The two unsigned dwords SystemParam_0 and SystemParam_1 MUST be globals, since they are used again and again. Don't worry, they'll be initialized below.

rotate_some

void rotate_some (void)
{
    unsigned long Tmp1,Tmp2;

    Tmp1 = (SystemParam_0 << 3) | (SystemParam_0 >> 29);
    Tmp2 = SystemParam_0 + SystemParam_1;
    Tmp1 += Tmp2;
    SystemParam_0 = Tmp1;
    SystemParam_1 = (Tmp2 << 5) | (Tmp2 >> 27);
}

This kind of routine pops up again and again in all of the code for stars, planets, space ships, and even the names of towns, orbiters and clients to assasinate. Its purpose is obvious: given some linear number, rotate it so-and-so, so the output won't be a linear number anymore. Duh.

Before we continue to see stars let's add some real world spicing. The distribution of spectral types between small red and bright white giant stars is not equal, so we want some of the randomization evened out. These tables are copied verbatim from the executable.

int StarChance_Type[] = {
    0, 0, 0, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1,
    2, 2, 2, 2, 2, 3, 3, 3,
    3, 4, 4, 4, 5, 6, 7, 8
};

David states that faint red and orange stars make up 75% of the Milky Way; actually, this percentage may be much, much higher. Not too bad, though ;)

These numbers correspond to the following star spectral types, and if you want to show a descriptive string use these:

char *StarDesc[]
    "Type'M'flare star",     //  0
    "Faint type'M'red star", //  1
    "Type'M'red star",       //  2
    "Type'K'orange star",    //  3
    "Type'G'yellow star",    //  4
    "Type'F'white star",     //  5
    "Type'A'hot white star", //  6
    "White dwarf star",      //  7
    "Red giant star"         //  8

There are a few more star types, but these are never "generated": they are used in the predefined systems. Their codes are:

    "Bright giant star",     //  9
    "Type'B'hot blue star",  // 10
    "Supergiant star",       // 11
    "Blue supergiant star",  // 12
    "Contact binary star"    // 13

And here is the denormalized distribution of the number of multiple stars:

int StarChance_Multiples[] = {
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 1, 1, 1, 1, 1,
    1, 1, 2, 2, 2, 3, 4, 5
};

... where '0' stands for a single star, then Binary, Ternary, Quaternary, Quintuple and Sextuple systems. The star we're about to generate is dubbed the 'Primary star' for the system.

Right. Let's create stars.

Shuffle_Coordinates

void Shuffle_Coordinates (unsigned int coordx, unsigned int coordy, int number_of_systems)
{
    int i;

    SystemParam_0 = (coordx<<16)+coordy;
    SystemParam_1 = (coordy<<16)+coordx;

    rotate_some();
    rotate_some();
    rotate_some();

    for (i=0; i<number_of_systems; i++)
    {
        rotate_some();

        coords[i].z = (SystemParam_0 & 0xFF0000)>>16;
        coords[i].y = (SystemParam_0 >> 8);
        coords[i].y /= 2;
        coords[i].x = (SystemParam_0 & 0x0001FE)>> 1;
        coords[i].x /= 2;
        coords[i].multiple = StarChance_Multiples[SystemParam_1 & 0x1f];
        coords[i].stardesc = StarChance_Type[(SystemParam_1 >> 16) & 0x1f];
    }
}

This routine should be called with the sector's absolute coordinates and the number of systems that should be generated for that particular sector (the number found in generate_sector). The position of each star in the array is its System number as seen in the games.

You see that the initial SystemParam's are the seed for the rest of the routine; note also the three shuffles at the beginning and the single one inside the loop. The strange division of coordinates y and z by two is just to satisfy my compiler into making them signed characters, by the way.

Now you have your array filled with 3d coordinates! The coordinates range from -63 to +63 for the x and y axes, and -128 to +127 in the z-axis; one star sector measures 128 x 128 x 256 units in this system.

Plot'em and enjoy, I'd say. Hmmm... lemme give you a few pointers about sizes and colors.

int SizeForStar[] = {
    300, 300, 350, 400,
    450, 500, 500, 200,
    700, 900, 800, 1100,
    1400, 600
};

The units here are arbitrary; these radii should be z-scaled anyways for a nice depth-cued display.

int ColorForStar[] = {
    RGB(200,  0,  0),    // Type'M'flare star
    RGB(200,  0,  0),    // Faint type'M'red star
    RGB(200,  0,  0),    // Type'M'red star
    RGB(200,136,  0),    // Type'K'orange star
    RGB(200,200,  0),    // Type'G'yellow star
    RGB(200,200,200),    // Type'F'white star
    RGB(200,200,200),    // Type'A'hot white star
    RGB(200,200,200),    // White dwarf star
    RGB(200,  0,  0),    // Red giant star
    RGB(200,200,200),    // Bright giant star
    RGB(168,200,232),    // Type'B'hot blue star
    RGB(192,136,  0),    // Supergiant star
    RGB(168,200,232),    // Blue supergiant star
    RGB(200,200,  0),    // Contact binary star
};

These colors are a straight conversion from the 5x5x5 bit 'real' color system used throughout the games. Personally I think they look a bit bland in true high color.

SANITY WARNING To display a star n please use "SizeForStar[coords[n].stardesc & 0x1f]" and "ColorForStar[coords[n].stardesc & 0x1f]", and as descriptive text "StarDesc[coords[n].stardesc & 0x0f]"; the higher bits may be used in predefined systems, explained later.

Random star names

Now how are you gonna store the names for the 500 million-and some stars? Err.. you don't.

Make 32 sounds as if you're trying to speak while being beaten in the stomach:

char *namepart[] = {
    "en" , "la" , "can", "be" ,
    "and", "phi", "eth", "ol" ,
    "ve" , "ho" , "a"  , "lia",
    "an" , "ar" , "ur" , "mi" ,
    "in" , "ti" , "qu" , "so" ,
    "ed" , "ess", "ex" , "io" ,
    "ce" , "ze" , "fa" , "ay" ,
    "wa" , "da" , "ack", "gre"
};

..an' bung them together at (semi-)random.

void GetSystemName(unsigned int coordx,unsigned int coordy, int Sysnum, char *dest)
{
    coordx += Sysnum;
    coordy += coordx;
    coordx = _rotl (coordx, 3);
    coordx += coordy;
    coordy = _rotl (coordy, 5);
    coordy += coordx;
    coordy = _rotl (coordy, 4);
    coordx = _rotl (coordx, Sysnum);
    coordx += coordy;

    strcpy (dest, namepart[(coordx>>2) & 31]);
    coordx = _rotr (coordx, 5);
    strcat (dest, namepart[(coordx>>2) & 31]);
    coordx = _rotr (coordx, 5);
    strcat (dest, namepart[(coordx>>2) & 31]);
    dest[0] ^= 0x20;
}

... where coordx and coordy are the absolute sector coordinates, Sysnum is the star's System number and dest points to enough space to store the name in.

Dave really let us down here: there are only 32 different syllables in three permutations, adding up to no more than 32,768 unique names. So, there are about 15,000 stars named "Aaa", "Hohoho" and "Lalala". Fortunately they are spaced out *very* far, in the order of 2,000 sectors apart (that's a rough guess).

It is quite possible to enter other and/or more syllables, or to chance this routine somewhat more to resemble, for example, Doomdark's Revenge. This game used a similar routine, but had different first, second and third syllables. That would result in stars called "Fangrim", "Fangrorn", or "Varorthorn", and never "Ararar".

But wait a minute! No way you can combine these letters to form 'Sol', 'Aldebaran', or 'CD-3715492' or even 'Leesti', 'Lave' or 'Diso'. So where do these come from? That's for another time to find 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.