Rabidgremlin's
Soapbox

23114, 584, 46931, these three numbers were used to create the entire universe for Elite.

Released in 1984, Elite featured cutting edge 3D graphics (with hidden line removal no less) and a rich universe of 2048 planetary systems, spread across 8 galaxies, each with a unique name, offbeat description, technology level, government type and even an economy. It was an instant hit and it set the standard for space combat and trading simulators for years to come.

But the developers of Elite had a bit of a problem, the data for this universe took up a lot of memory, memory that the early microcomputers just did not have. In fact the data for the universe is several hundred kilobytes big. The BBC Micro, one of the launch platforms for the game, only had 32KB of RAM, large for computers of the time but not big enough to hold Elite’s universe, let alone the rest of the game.

So what did the developers do ? Well they used procedural content generation to generate the details of each planetary system as it was needed. In fact, Elite was one of the earliest games to use procedural content generation.

So how did it work? Luckily for us, Ian Bell, one of the authors of Elite, created a text based version of the game to “formalise and archive the definition of the Classic Elite Universe”. The C source code for Text Elite can be found here and I’m going to walk through it in this post, pointing out some of the interesting bits along the way.

So back to our three numbers. These are used as the “seed” of the universe and they are incremented and manipulated in a consistent manner as each galaxy and planetary system is generated. This allows the game universe to be the same for each player, even though the data is generated on the fly.

The basic outline of the process is as follows:

1. Set the seed to our 3 starting numbers (23114, 584, 46931)
2. Figure out which galaxy we are in (1 to 8) and then “twist” the seed as we step through each galaxy to get to our target galaxy
3. Iterate through each of the 256 planetary systems in the galaxy and generate each one’s details using the current seed. “Tweak” the seed during this step of the process so that the next planetary system has a different seed value to generate its data from.

The source for this can be found in the aptly named buildgalaxy function:

/* Original game generated from scratch each time info needed */
void buildgalaxy(uint galaxynum)
{
 uint syscount, galcount;
 seed.w0 = base0; seed.w1 = base1; seed.w2 = base2; /* Initialise seed for galaxy 1 */
 for (galcount = 1; galcount<galaxynum; ++galcount) nextgalaxy(&seed);
 /* Put galaxy data into array of structures */
 for (syscount = 0; syscount<galsize; ++syscount) galaxy[syscount] = makesystem(&seed);
}

Note the comment that the original game generated the info from scratch every time it was need. Since we running on less memory constrained machines, Text Elite can generate all the planetary systems for a single galaxy in one hit.

base0, base1 and base2 are our three starting numbers, defined in hex in the code as:

const uint16 base0 = 0x5A4A;
const uint16 base1 = 0x0248;
const uint16 base2 = 0xB753;  /* Base seed for galaxy 1 */

The nextgalaxy and twist functions handle the adjustment of the seed as we step through the galaxies. This ensures that the seed is set up to generate a unique set of planetary systems for the galaxy we want. The source for these functions looks like this:

uint16 twist(uint16 x)
{
 return (uint16)((256 * rotatel(x >> 8)) + rotatel(x & 255));
}

void nextgalaxy(seedtype *s) /* Apply to base seed; once for galaxy 2 */
{
 (*s).w0 = twist((*s).w0); /* twice for galaxy 3, etc. */
 (*s).w1 = twist((*s).w1); /* Eighth application gives galaxy 1 again*/
 (*s).w2 = twist((*s).w2);
}

Basically some math and bitwise operations to shift the seed numbers left 8 bits.

With the seed set up for our galaxy, we can now generate its 256 planetary systems. The heart of this process is the makesystem function. It uses the current seed to populate a structure looking like this for each planetary system:

typedef struct
{
 uint x;
 uint y; /* One byte unsigned */
 uint economy; /* These two are actually only 0-7 */
 uint govtype;
 uint techlev; /* 0-16 i think */
 uint population; /* One byte */
 uint productivity; /* Two byte */
 uint radius; /* Two byte (not used by game at all) */
 fastseedtype goatsoupseed;
 char name[12];
} plansys;

Here is the makeystem function in all it’s glory:

/**-Generate system info from seed **/

plansys makesystem(seedtype *s)
{
 plansys thissys;
 uint pair1, pair2, pair3, pair4;
 uint16 longnameflag = ((*s).w0) & 64;

 thissys.x = (((*s).w1) >> 8);
 thissys.y = (((*s).w0) >> 8);

 thissys.govtype = ((((*s).w1) >> 3) & 7); /* bits 3,4 &5 of w1 */

 thissys.economy = ((((*s).w0) >> 8) & 7); /* bits 8,9 &A of w0 */
 if (thissys.govtype <= 1)
 {
 thissys.economy = ((thissys.economy) | 2);
 }

 thissys.techlev = ((((*s).w1) >> 8) & 3) + ((thissys.economy) ^ 7);
 thissys.techlev += ((thissys.govtype) >> 1);
 if (((thissys.govtype) & 1) == 1) thissys.techlev += 1;
 /* C simulation of 6502's LSR then ADC */

 thissys.population = 4 * (thissys.techlev) + (thissys.economy);
 thissys.population += (thissys.govtype) + 1;

 thissys.productivity = (((thissys.economy) ^ 7) + 3)*((thissys.govtype) + 4);
 thissys.productivity *= (thissys.population) * 8;

 thissys.radius = 256 * (((((*s).w2) >> 8) & 15) + 11) + thissys.x;

 thissys.goatsoupseed.a = (*s).w1 & 0xFF;;
 thissys.goatsoupseed.b = (*s).w1 >> 8;
 thissys.goatsoupseed.c = (*s).w2 & 0xFF;
 thissys.goatsoupseed.d = (*s).w2 >> 8;

 pair1 = 2 * ((((*s).w2) >> 8) & 31); tweakseed(s);
 pair2 = 2 * ((((*s).w2) >> 8) & 31); tweakseed(s);
 pair3 = 2 * ((((*s).w2) >> 8) & 31); tweakseed(s);
 pair4 = 2 * ((((*s).w2) >> 8) & 31); tweakseed(s);
 /* Always four iterations of random number */

 (thissys.name)[0] = pairs[pair1];
 (thissys.name)[1] = pairs[pair1 + 1];
 (thissys.name)[2] = pairs[pair2];
 (thissys.name)[3] = pairs[pair2 + 1];
 (thissys.name)[4] = pairs[pair3];
 (thissys.name)[5] = pairs[pair3 + 1];

 if (longnameflag) /* bit 6 of ORIGINAL w0 flags a four-pair name */
 {
 (thissys.name)[6] = pairs[pair4];
 (thissys.name)[7] = pairs[pair4 + 1];
 (thissys.name)[8] = 0;
 }
 else (thissys.name)[6] = 0;
 stripout(thissys.name, '.');

 return thissys;
}

As you can see the system’s location, government type and economy are generated by plucking bits out the seed. Next up, the tech level is determined (partially) from the seed and is then adjusted by the economy and government type.

Population is derived from the system’s tech level, economy and government type. Similarly its productivity is a function of its economy, government type and population. The system’s radius is derived from some arbitrary seed bits but is also affected by the system’s galactic x coordinate.

The goatsoupseed is an interesting bit. It is used as a seed for a pseudo-random number generator which, is used to generated the text description of the system using a text template. I won’t cover this step but have a look at the goat_soup function if you are interested in seeing how this works.

The rest of the function focuses on creating the name of the system. It does this by pulling pairs of letters out of the following strings:

char pairs[] = "..LEXEGEZACEBISO"
"USESARMAINDIREA."
"ERATENBERALAVETI"
"EDORQUANTEISRION"; /* Dots should be nullprint characters */

These pairs are made up of a vowel and a consonant and when combined create names that are generally pronounceable. Looking at the code you will see the same part of the seed is used to choose each of the letter pairs. To avoid the same pair being chosen each time, the tweakseed function is called after each selection. This function use a Fibonacci-like sequence to adjust the seed:

void tweakseed(seedtype *s)
{
 uint16 temp;
 temp = ((*s).w0) + ((*s).w1) + ((*s).w2); /* 2 byte aritmetic */
 (*s).w0 = (*s).w1;
 (*s).w1 = (*s).w2;
 (*s).w2 = temp;
}

A  side effect of “tweaking” the seed like this, is that the next system to be generated gets its own unique seed to build from.

The upshot of this whole process is that we get planetary systems such as Lave (your starting system in the game and the 7th in galaxy 1):

• Location: 20,173
• Economy: Rich Agri
• Government: Dictatorship
• Tech level: 5
• Productivity: 7000
• Radius: 4116
• Population: 3bn
• Description: Lave is most famous for its vast rain forests and the Lavian tree grub.

or Enata in galaxy 3:

• Location: 171,179
• Economy: Mainly Ind
• Government: Confederacy
• Tech level: 11
• Productivity: 24696
• Radius: 3499
• Population: 6bn
• Description: This planet is fabled for its unusual tropical forests and its exciting Zero-G cricket

Additionally a list of trade goods are generated for each system. The list of available goods are based on planetary system’s economy type. The game also fluctuates the pricing and keeps track of availability as the player buys and sells goods. Have a look at the genmarket function if you want to see how this works.

As a fun exercise I hacked the Text Elite source to dump out a .csv file containing all the planetary systems. I then used a bit of Processing to generate this map showing the entire Elite universe. I have used the productivity of the planet to size each system and its government type to tweak it’s colour. Lave, your starting point in the game, I have highlighted in green. I have also plotted out the “jump lanes” between the systems as the game only allowed you to jump a maximum of 7 light years at a single time.

Well, that about wraps it up. Source for my hacked Text Elite and the Processing map generation code can be found here. I’d also suggest you check out these great writeups on how Frontier: Elite 2 did its universe creation. Also check out the dev dairy for the just released Elite: Dangerous which uses procedural content generation to create over 400 billion star systems.

If you enjoyed this post then check out my other posts on procedural content generation.