The maths behind each landscape's unique sequence of seed numbers
There are 10,000 different landscapes in The Sentinel, numbered from 0000 to 9999. That's a huge number, so huge that Geoff Crammond is on record as saying that he never thought anyone would go so far as to finish the game.
The key to this almost ridiculous number of landscapes is a pseudo-random number generator that can be seeded with the landscape number to generate the same, predictable sequence of numbers for each specific landscape. This same approach is used in games like Elite to spectacular effect - see the Elite deep dive on galaxy and system seeds for example - but The Sentinel takes its random number generation to the next level, using them to generate not only the landscapes, but also the positions of the enemies, the starting point of the player, and even the secret codes that unlock new landscapes to explore:
For more information on how the game generates landscapes, enemies and secrets from sequences of pseudo-random numbers, see the deep dives on generating the landscape, the landscape secret code and adding enemies and trees to the landscape. For this article, we're going to take a look at how those numbers are generated in the first place.
Linear feedback shift register
------------------------------
The numbers that power The Sentinel's 10,000 landscapes are generated by two very short routines. The first two lines of the InitialiseSeeds routine configure the pseudo-random number generator to produce numbers for the specified landscape, and the GetNextSeedNumber routine fetches the next number from that landscape's unique sequence. Because these numbers are used to create landscapes and all they contain, let's refer to them as "seed numbers" that are generated by the "landscape seed generator" routine.
For anyone who's looked into procedural generation on old computers, the maths behind the landscape seed generation will be a familiar one. The Sentinel uses a linear feedback shift register (LFSR) that consists of five bytes stored at seedNumberLFSR(4 3 2 1 0). The register shifts bits to the left, from the low bit to the high bit, and each shift generates one bit of the next seed. So to generate a new random number, we shift the register eight times, and eight new bits will be shifted into the high byte at seedNumberLFSR+4.
The key to the pseudo-random nature of this shifting is the bit that we rotate back into bit 0 during the shift (i.e. the bit that we "feed back" into the feedback shift register). The value that we move into bit 0 is calculated like this:
bit 3 of seedNumberLFSR+2 EOR bit 0 of seedNumberLFSR+4
which is the same as:
bit 19 of seedNumberLFSR(4 3 2 1 0) EOR bit 32 of seedNumberLFSR(4 3 2 1 0)
Here's a diagram showing how the feedback loop works across the whole shift register:
LFSR+4 LFSR+3 LFSR+2 LFSR+1 LFSR+0
32 24 16 8 0
| | | | |
v v v v v
76543210 76543210 76543210 76543210 76543210 <-----+
| | |
| | |
\___ EOR ____/ |
| |
+------------------------------------ +
To do this, the GetNextSeedNumber routine extracts bits 19 and 32 from the shift register in seedNumberLFSR(4 3 2 1 0) and EORs them before shifting the whole register to the left while inserting the result of the EOR into bit 0. This process implements the linear feedback shift and ensures that the numbers that are generated are random enough to create 10,000 landscapes.
The correct term for a bit that we extract and process in order to feed back into a shift register is a "tap", so in the above we are "tapping" the linear feedback shift register in two places. Slightly confusingly, when we talk about tapping, the convention is to start counting the position of the tapped bits from position 1 rather than 0, so although we are extracting bits 19 and 32 from the register before shifting, the correct terminology for this is a "33-bit linear feedback shift register with taps at positions 20 and 33".
If this sounds familiar, then that's perhaps not surprising, as this isn't the only game I've analysed that uses this approach to generate pseudo-random numbers. Lander - the world's first game for the ARM processor and the game that David Braben wrote after Elite - uses exactly the same system to produce its random numbers (though not its beautiful tiled landscape, so it differs from The Sentinel in that aspect).
The algorithm is so versatile that it even appears in the manual for the original ARM Evaluation System; the only difference is that The Sentinel does it in just eight bits, rather than 32. See the Lander deep dive on random numbers for more details, including the page from the ARM Evaluation System manual that describes the algorithm.
Initialising the shift register
-------------------------------
The beauty of the linear feedback shift register is that if you initialise the first two bytes of the register with specific values, then the output of the register is predictable and repeatable. The Sentinel uses this fact to set up the generator so that it produces a consistent stream of seeds for any given landscape.
Specifically, it takes the landscape number in binary coded decimal (BCD) and uses that as the first two bytes of the LFSR. BCD matches the way that humans write down numbers, so as the landscape numbers range from 0000 to 9999, they exactly match the range of a 16-bit BCD number. For example, landscape 1234 would be represented in BCD as &1234, with a high byte of &12 and a low byte of &34, so to initialise the seed generator for this landscape, we would set seedNumberLFSR+1 to the high byte (&12) and seedNumberLFSR to the low byte (&34). All the other bytes in the LFSR are then zeroed to remove any remnants of previous seeds, so there is nothing unpredictable left to feed back into the register.
There is one more initialisation step, and that is performed in the ResetTilesObjects routine, which sets bit 16 of the register. If this wasn't done then landscape 0000 would start with a shift register that was entirely made up of zeroes, and that could only ever produce more zeroes, as 0 EOR 0 = 0. Setting bit 16 ensures that landscape 0000 will also work, without altering the landscape number in bits 0 to 15.
To see how The Sentinel uses these pseudo-random seeds to create the game world, see the deep dive on the generating the landscape. Once that process is done and the game has started, the LFSR goes on to produce rather less predictable random behaviour to drive the gameplay, and there's also a second pseudo-random number generator that powers the dithering effect; see the deep dive on random number generation for details.