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. 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.

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