Random number generator

Overview

The list of planets used by both Elite and Oolite are generated using (psuedo) 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.

Planet properties

The random number generator used by Elite for (most of) the planetary properties is based upon a Fibonnaci[2] sequence. As the numerical sequence cannot be allowed extend to infinity the sequence is used modulo 65536. Elite, for 8-bit architecture machines, was coded to perform valid 16-bit arithmetic here. The sequence used is not exactly a Pisano [3] sequence as the game is keeping track of three, not two, 16 bit words. 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 seed values (in Hexadecimal) are w0 = 5A4A , w1 = 0248 , w2 = B753, and define some of the properties of planet number 0 in Galaxy 1, Tibedied. 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 hsb of w2 is used to calculate both the planet's radius and determine the first two letters 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 of Galaxy 1, Qube.

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 seed value for the planets in Galaxy 2 are (in Hexadecimal) w0 = B494 , w1 = 0490 , w2 = 6FA6.

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.

Planet description string

Four of the six bytes for each planet 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 [5]. 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 [6] but basically each planet is usually fabled for something, usually followed by a caveat warning of a dangerous animal.

Slight differences exist between the BBC model B classic 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. 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) but becomes a? in Classic Beenrian mountain Esseina?oid and a' in Oolite: Beenriian mountain A'oid. 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. Thus the description strings start identically, can create different random names, and end with different phrases, e.g. 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.