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.