The algorithm behind Elite's random number generation routines
Games like Elite need a steady stream of random numbers. They are used all over the place to add an element of chance to gameplay, whether it's in the main flight loop when deciding whether or not to spawn an angry Thargoid in the depths of space, or on arrival in a new system where the market prices have a random element mixed into the procedural generation, so they are never exactly the same.
Random numbers on Elite are generated by the DORND and DORND2 routines, which use the four seed bytes at RAND to RAND+3 to generate a sequence of pseudo-random numbers. DORND mixes the value of the C flag into the random number generation, while DORND2 is not affected by the value of the C flag on entry, so the latter routine is the one used when we need to ensure that the sequence of random numbers is repeatable - in explosion clouds, for example. See the deep dive on drawing explosion clouds for more on this.
We'll look at the DORND algorithm in a moment, but first let's talk about seeds and number sequences.
Main and feeder sequences
First up, it's important to note that although DORND returns random numbers in A and X, X is actually set to the random number that was returned in A the last time DORND was called. DORND effectively works its way through a sequence of random numbers, calculating each new number from the previous numbers in the sequence, and it returns the last value from the sequence in A, and the previous value in X. Most of the time X is ignored, but if it is used, this relationship between A and X is important to understand (see the deep dive on fixing ship positions for more on this).
The DORND routine manages two sequences of 8-bit numbers. The main sequence is the important one, as it generates each new random number that gets returned in A. There's also a feeder sequence that only exists to feed a random bit into the main sequence calculation.
The main sequence stores its last two values in RAND+1 (the latest value) and RAND+3 (the previous value), and the feeder sequence stores its last two values in RAND (the latest value) and RAND+2 (the previous value). The main sequence calculates one new value in its sequence each time (which is the next random number to be returned from the subroutine), while the feeder sequence calculates two new values in its sequence each time. The calculations for both sequences also affect the flags, and in particular the calculation for the feeder sequence affects the C flag, whose value is incorporated into the calculation for the main sequence.
Let's call the main sequence m0, m1, m2, ... and so on, and let's consider the generator at the point when we have generated m0 and m1 and want to generate m2. Let's call the feeder sequence f0, f1, f2, ... and so on, and let's consider the generator at the point when we have generated f0 and f1, and we want to generate f2 and f3. In terms of memory locations, this is the situation:
- For the feeder sequence:
- f1 = RAND = the latest value in the feeder sequence
- f0 = RAND+2 = the value before that
- For the main sequence:
- m1 = RAND+1 = the latest value in the main sequence, as returned in A by the previous call to DORND
- m0 = RAND+3 = the value before that, as returned in X by the previous call to DORND
These four locations are known as the "seeds" for our random number generator. The values of the feeder seeds in f0 and f1 are not read by any other routine apart from this one, so they are effectively internal to the random number generation routine. In contrast, the previous call to DORND returned X = m0 and A = m1, and the next call will return X = m1 and A = m2, along with random values of the C and V flags. This process generates the random results we're looking for.
The seeds are overwritten in three places:
- f1 is updated in part 1 of the main flight loop, which re-seeds the random number generator for each iteration of the loop. Here, f1 is set to the first byte of the ship data block at K% (which is the x_lo coordinate for the planet, so this is pretty random).
- All four seeds are updated by the EXL2 section as part of the explosion routine in DOEXP, using a STA &FFFD,Y instruction with Y = 2, 3, 4, 5 (so this points the write to zero page location &00, which is where RAND is located, in the first four bytes of memory). This ensures that explosion clouds can be regenerated from the same set of seeds, so they can be erased from the screen before being redrawn.
- m0 is updated in the EX4 section as part of the explosion routine in DOEXP, with m0 being set to the seventh byte of the ship data block at K%+6 (which is the z_lo coordinate for the planet, so again, this is pretty random). This restores some randomness to the seeds after we have drawn an explosion cloud, as otherwise we would have a relationship between explosion clouds and whatever happens next.
Let's look at the algorithm in DORND, and how it updates the seeds on each call.
The DORND routine generates the next two values in the feeder sequence, and then takes the resulting C flag and uses that to generate the next value in the main sequence.
The feeder part of the algorithm takes the current seed values in f0 and f1, as well as the value of the C flag on entry into the routine, and calculates the next two values in the sequence, f2 and f3, as follows:
f2 = (f1 << 1) mod 256 + C flag on entry f3 = f0 + f2 + (1 if bit 7 of f1 is set) C flag set according to the f3 calculation
As noted above, if DORND2 is called instead of DORND, then the C flag is cleared before falling into DORND, which means the value of the C flag when DORND2 is called has no effect on the outcome. This helps us create repeatable sequences of random numbers without having to worry about the value of the C flag each time.
The above addition when calculating f3 will affect the C flag, and this value is used in the calculation for the next value of the main sequence - the C flag from the feeder sequence "feeds" into the main sequence. Let's look at the main sequence now.
The main part of the algorithm takes the current seed values in m0 and m1, as well as the C flag from the feeder sequence, and calculates the next value in the sequence, m2, which is returned in A as the next random number. The calculation is a simple Fibonacci sequence with the addition of the feeder flag, and looks like this:
m2 = m0 + m1 + C flag from feeder calculation
This is a very simple example of what's known as an "additive lagged Fibonacci generator". It doesn't do a terribly good job of generating random numbers, but it's good enough for Elite, and it has the advantage of being quick and easy to implement, as well as supporting repeatable sequences of values (we can set the seeds to known values, and if we use DORND2, these seeds will always generate the same sequence of numbers).
However, you do have to be careful how you use this kind of generator, and if you get it wrong, you may find that your random behaviour isn't random at all. For example, Elite always spawns ships with specific behaviour in the same half of the screen, because it isn't careful with the sequential nature of the DORND routine. You can read all about this in the deep dive on fixing ship positions.
For the most part, though, this simple dual-sequence approach is good enough to make the world of Elite feel different each time, and it only takes a handful of simple and quick assembly instructions.