Skip to navigation

BBC Micro Elite

Twisting the system seeds

How the system seeds are twisted to produce entire galaxies of stars

References: TT54, TT20, Ghy

Data on each star system in Elite's galaxies is generated procedurally, and the core of this process is the set of three 16-bit seeds that describe each system in the universe. Each of the eight galaxies in the game is generated in the same way, by taking an initial set of seeds and "twisting" them to generate 256 systems, one after the other.

Specifically, given the initial set of seeds, we can generate the next system in the sequence by twisting that system's seeds four times. As we do these twists, we can extract the system's data from the seed values - including the system name, which is generated by the subroutine cpl, where you can read about how this aspect works.

It is therefore no exaggeration that the twisting process implemented below is the fundamental building block of Elite's "universe in a bottle" approach, which enabled the authors to squeeze eight galaxies of 256 planets out of nothing more than three initial numbers and a short twisting routine (and they could have had far larger galaxies and many more of them, if they had wanted, but they made the wise decision to limit the number). Let's look at how this twisting process works.

The three seeds that describe a system represent three consecutive numbers in a Tribonacci sequence, where each number is equal to the sum of the preceding three numbers (the name is a play on Fibonacci sequence, in which each number is equal to the sum of the preceding two numbers). Twisting is the process of moving along the sequence by one place. So, say our seeds currently point to these numbers in the sequence:

  0   0   1   1   2   4   7   13   24   44   ...
                      ^   ^    ^

so they are 4, 7 and 13, then twisting would move them all along by one place, like this:

  0   0   1   1   2   4   7   13   24   44   ...
                          ^    ^    ^

giving us 7, 13 and 24. To generalise this, if we start with seeds w0, w1 and w2 and we want to work out their new values after we perform a twist (let's call the new values w0´, w1´ and w2´), then:

  w0´ = w1
  w1´ = w2
  w2´ = w0 + w1 + w2

So given an existing set of seeds in w0, w1 and w2, we can get the new values w0´, w1´ and w2´ simply by doing the above sums. And if we want to do the above in-place without creating three new w´ variables, then we can do the following:

  tmp = w0 + w1
  w0 = w1
  w1 = w2
  w2 = tmp + w1

In Elite, the numbers we're dealing with are two-byte, 16-bit numbers, and because these 16-bit numbers can only hold values up to 65535, the sequence wraps around at the end. But the maths is the same, it just has to be done on 16-bit numbers, one byte at a time.

The seeds are stored as little-endian 16-bit numbers, so the low (least significant) byte is first, followed by the high (most significant) byte. Taking the case of the currently selected system, whose seeds are stored in the six bytes from QQ15, that means our seed values are stored like this:

      low byte  high byte
  w0  QQ15      QQ15+1
  w1  QQ15+2    QQ15+3
  w2  QQ15+4    QQ15+5

If we denote the low byte of w0 as w0_lo and the high byte as w0_hi, then the twist operation above can be rewritten for 16-bit values like this, assuming the additions include the C flag:

  tmp_lo = w0_lo + w1_lo          (tmp = w0 + w1)
  tmp_hi = w0_hi + w1_hi
  w0_lo  = w1_lo                  (w0 = w1)
  w0_hi  = w1_hi
  w1_lo  = w2_lo                  (w1 = w2)
  w1_hi  = w2_hi
  w2_lo  = tmp_lo + w1_lo         (w2 = tmp + w1)
  w2_hi  = tmp_hi + w1_hi

And that's exactly what the TT54 subroutine does to twist our three 16-bit seeds to the next values in the sequence, using X to store tmp_lo and Y to store tmp_hi.

Twisting the galaxy seeds
-------------------------

The Ghy routine updates the galaxy seeds to point to the next galaxy. Using a galactic hyperdrive rotates each seed byte to the left, rolling each byte left within itself like this:

  01234567 -> 12345670

to get the seeds for the next galaxy. So after 8 galactic jumps, the seeds roll round to those of the first galaxy again.