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. These routines use the four seed bytes at RAND to RAND+3 to generate random numbers, though I am still trying to work out how this works, and the difference between the two different entry points, one of which clears the C flag first.
Let's look at the algorithm, anyway.
There are two calculations of two 8-bit numbers in the DORND routine. The first pair is at RAND and RAND+2 (let's call them r0 and r2) and the second pair is at RAND+1 and RAND+3 (let's call them r1 and r3).
The values of r0 and r2 are not read by any other routine apart from this one, so they are effectively internal to the random number generation routine. r1 and r3, meanwhile, are returned in A and X with each call to DORND, and along with the returned values of the C and V flags, form the the random results we're looking for.
The seeds are overwritten in three places:
- All four locations are updated by EXL2, 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).
- r0 is written to at the start of M% in the main loop, to seed the random number generator. Here, r0 is set to the first byte of the ship data block at K% (which is the x_lo coordinate for the planet).
- r3 is written to in EX4 as part of the explosion routine, with r3 being set to the seventh byte of the ship data block at K%+6 (which is the z_lo coordinate for the planet).
r0 and r2 follow the following sequence through successive calls to DORND, going from r0 and r2 to r0´ and r2´ with each call:
r2´ = ((r0 << 1) mod 256) + C r0´ = r2´ + r2 + bit 7 of r0
C is the C flag on entry to the routine. If this routine is entered with the C flag clear, e.g. via DORND2, then if bit 0 of RAND+2 is 0, it will remain at 0.
r1 and r3 (which are returned in A and X) follow this number sequence through successive calls to DORND, going from r1 and r3 to r1´ and r3´:
A = r1´ = r1 + r3 + C X = r3´ = r1
C is the C flag from the calculation of r0´ above, i.e. from the addition of r2´ with r2 and bit 7 of r0. Because r3´ is set to r1, this can be thought of as a number sequence, with A being the next number in the sequence and X being the value of A from the previous call.
In DORND2, we enter with the C flag clear, which changes the calculations in DORND to:
r2´ = ((r0 << 1) mod 256) r0´ = r2´ + r2 + bit 7 of r0
so r2´ always has bit 0 cleared, i.e. r2 is always a multiple of 2.