Random number generator

Overview

The list of planets used by both Elite and Oolite are generated using (pseudo) random number generators. For the constrained 8-bit architectures that the original Elite game operated under there was not enough memory to store all the planetary information the games uses. Instead random number generators starting from a small set of seed numbers generate the Universe in a bottle as needed.

Christian Pinder the author of Elite TNK gives a good overview of pseudo random number generators[1]. The random number generators used in Elite (and the core of Oolite) are more limited with various non-random patterns sometimes becoming noticeable to the player.

Fibonnaci sequence

The random number generator used by Elite for (most of) the planetary properties is based upon a generalized Fibonnaci[2] sequence. As the numerical sequence cannot be allowed to extend to infinity the sequence is used modulo 65536, a generalized Pisano [3] sequence. Elite, for 8-bit architecture machines, was coded to perform valid 16-bit arithmetic here. Labelling these three words as w0 w1 w2, the operation performed (the twist) to generate the next three words has the old value of w1 copied to w0, the old value of w2 is copied to w1 and the three old values w0 w1 w2 are added together (modulo 65536) to give a new value for w2.

The Pisano-like sequence repeats perfectly after 131,072 twists, or 32,768 planets per galaxy - well in excess of the 256 planets per galaxy used in the game. However subsets of the bit-patterns used to generate the planetary information repeat considerably more often. For example the system name Cetiisqu in both Galaxy 1 and Galaxy 5.

Initial seed values for each Galaxy

The starting seed values for the sequence are (in hexadecimal) w0 = 5A4A , w1 = 0248 , w2 = B753, and define some of the properties of planet number 0 in Galaxy 1, Tibedied. Apparently several trials were needed by Braben & Bell to find values that did not give rude names for planets nor leave galaxies looking too clustered, uneven.

Note that the Oolite save file contains the byte-reversed values for w0, w1, w2 : 74 90 , 72 2 , 83 183 as the seed values for Galaxy 1. In Elite, an 8-bit roll-left operation [4] was performed on each of the six bytes to cycle the seed values through the 8 galaxies. For example the starting seed value for the planets in Galaxy 2 are (in hexadecimal) w0 = B494 , w1 = 0490 , w2 = 6FA6.

Note that the eighth role-left would return the seeds (and you) from Galaxy 8 back to Galaxy 1.

Planet properties

Due to the rather bad behavior of the lower 8-bits of each word, the highest-significant-byte (hsb) of each word is usually used. The galactic x-coordinate is the hsb of w1. The y-coordinate is hsb of w0 divided by two, i.e. the upper-most 7 bits of w0. The lower-most 3 bits of the hsb of w0 set the economy type. This overlap between the galactic y-coordinate and economy type is only a partial overlap and hence not noticeable.

The government type is determined by the lower-most 3 bits of the lowest-significant-byte (lsb) of w1, which is rather badly behaved and leaves Galaxy 4 with missing government types. The hsb of w2 is used to calculate both the planet's radius and determine the first two letters, digram [5], of the planet's name. To determine the following letters of the planet's name the twist is performed to generate new values for w2. For each planet the twist is performed 3 times. The fourth twist loads up w0 w1 w2 with the starting values required for the next planet. For instance in Galaxy 1, Qube follows after Tibedied.

Sequence of systems generated by twist performed on six-byte seed for each galaxy.

Planet description string

Four of the six bytes for each planet (w1 & w2) are also used as the seed for a sub-random-number generator that is used for the planet description text string. The generator used is related to the multiply-by-two with carry (MWC) technique [6]. The construction of the string uses tokenization, noting that ascii codes end at byte value 127, higher byte values can thus serve as tokens representing grammar rules or whole words. The starting string for each planet's description string is the byte sequence {143 32 105 115 32 151 46}. Using '\x' to proceed tokens (with values shown in hexadecimal) then this string can be written as "\x8F is \x97.". The token \x8F is expanded into 1 of 5 choices, based on the sub-random-number generator, to the phrase 'This planet' etc. The rules governing the expansion of \x97 are quite complicated [7] but basically each planet is usually fabled for something, usually followed by a caveat warning of a dangerous animal. The construction for the planet Lave is as follows:

\x8F is \x97.
\xB0 is \x97.
Lave is \x97.
Lave is \x82 \x81 for \x8A and \x8A.
Lave is most \x81 for \x8A and \x8A.
Lave is most famous for \x8A and \x8A.
Lave is most famous for its \x83 \x84 and \x8A.
Lave is most famous for its vast \x84 and \x8A.
Lave is most famous for its vast \x94 forests and \x8A.
Lave is most famous for its vast rain forests and \x8A.
Lave is most famous for its vast rain forests and the \xB1 \x98 \x99.
Lave is most famous for its vast rain forests and the Laveian \x98 \x99.
Lave is most famous for its vast rain forests and the Laveian tree \x99.
Lave is most famous for its vast rain forests and the Laveian tree \x92.
Lave is most famous for its vast rain forests and the Laveian tree grub.

Slight differences exist between the BBC model B classic Elite planet description strings and those of Oolite. One issue is the appendage of ian to form adjectives from random names. In classic a name ending with a vowel has that vowel dropped, e.g. Lavian. Although this should only be done for the vowels E and I this was also done for the other vowels, resulting in Cetiisqian evil Stoid etc. In Oolite no vowels are dropped, hence Laveian. Another difference is the treatment for the digram A* where the * is dropped in forming planet names (hence allowing planet names with an odd number of letters, one of which has to be the letter a in both classic and Oolite) but in the planet description string becomes a? in classic, .. Beenrian mountain Esseina?oid but scourged by .. , and a' in Oolite: .. Beenriian mountain A'oid but plagued by ... This example also indicates another issue that sometimes occur. Some strings require the generation of a random name, which uses the same sub-random number generator as the one constructing the planet description string itself. In Oolite such random names are generated after the rest of the description string, whereas in classic it was calculated as needed, thus the output stream of the generator gets redirected to different uses at different points during the construction. The classic and Oolite planet description strings start identically but can then contain different random names, and end with different phrases. For example in classic, This planet is most notable for Tibediedian Arnu brandy but ravaged by unpredictable solar activity., whereas in Oolite: This planet is most notable for Tibediedian Arma brandy but scourged by deadly edible grubs.