Skip to navigation

BBC Micro Elite

Generating random numbers

The algorithm behind Elite's random number generation routines

References: DORND, DORND2
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

  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.