# How did Elite (BBC Micro) compress resources?

Elite, an Acornsoft game for the BBC Micro, is a game set in space.

Space is big. Really big. You just won't believe how vastly, hugely, mind-bogglingly big it is.

There are a vast number of planets, resources, other ships... Elite, however, is small (in terms of program size). With so many planets that remain the same, and a detailed description about each, the data must be compressed somehow. How were resources compressed in Elite?

Elite used procedural generation. There's a good description of the algorithm on the Elite Wiki and although the original 6502 source code archives are available on Ian Bell's Elite site he also converted the procedural generation code into C for "Text Elite", so that's probably easier to read.

This extract from the book "Backroom Boys: The Secret Return Of The British Boffin" (by Francis Spufford) has a nice summary of how the game came to be. Here's a relevant snippet:

Hence the [Fibonacci] sequence's value to Bell and Braben. They could encode all the information on a particular solar system in a relatively short row of digits. That number, it occurred to them, wouldn't have to be stored if it were an iteration in a Fibonacci sequence - or a Fibonacci-like sequence, anyway. All you would need would be a starting point, a rule for doing the iterations, and a mechanism for extracting the information from the number.

Some digits controlled the physical specs of the system: the size, the location, the number of planets. Some determined local politics. Others grew into brief flourishes of verbal description - which always read a little weirdly, put together as they were from stray adjectives and nouns. Since the adjective list contained "carnivorous" and the noun list contained "arts graduates", it was possible to land on a planet where all the inhabitants were, yes, carnivorous arts graduates: a little swipe maybe at Cambridge - not random but pseudo-random. As the player entered the star system, then, it swelled into existence as if it had always been there.

David Braben talks about the "compression" and many other programming tricks used in this video.

• "You'd type in a number, a birthday or something, and see what galaxy that came out with," Braben told the Guardian in 2003. "'No, I don't like that. No, I don't like that. That cluster looks horrible' [...] One of the first galaxies we tried had a system called Arse. We couldn't use the whole galaxy. We just threw it away!" (mentalfloss.com/uk/games/37075/…) Commented Oct 28, 2016 at 6:01
• The numbers were generated via this algorithm, but how were the names / descriptions generated? The `goat_soup` function in the C source of "Text Elite" looks to me like it's picking adjectives and nouns from a list, but I can't see where the rest of the sentences are. Commented Oct 28, 2016 at 9:07
• @wizzwizz4 Which sentences exactly? Did you look at the Elite Wiki? A few tables of strings are given there, though I haven't looked for them in the source. Commented Oct 30, 2016 at 3:31
• @NickWestgate It's fine; kap's answer explains how the description algorithm (`goat_soup`) works. Commented Oct 30, 2016 at 8:09
• @wizzwizz4 The Elite Wiki page I linked to has a short description of the algorithm and an example of creating the planet description, and I've added a link to a talk by David Braben Commented Oct 30, 2016 at 8:53

The descriptions are computed via the method `goat_soup` which works recursively. The system description is set by `mySystem.description = goat_soup("\x8F is \x97.",&mySys);`

The description string contains two special characters, `\x8F` and `\x97`. Within `goat_soup` the available set of words and sentences is stored as `desc_choice`. The special characters are replaced via a random element in the list, for example `"\x82 \x81 for \x8A"` is a replacement of `\x97`. This is called recursively and now the new special characters are `\x82`, `\x81` and `\x8A`.

An example for these recursive fillings for `\x97` can then be `very fabled and its \x83 \x84` when always the first element is chosen.

This continues until no special character remains in the string.

My example refers to a modified version of Text Elite I created for a project at university several years ago which is available here: https://github.com/kappmeier/mElite/blob/bfff7375bc85670250015437ac25b8e55ea5c58f/src/txtelite.cpp I do not know to which version of text elite on Ian Bell's homepage this refers.

• That's really clever; thanks for clearing that up. However, that C code is for "Text Elite". If you can read assembly (or have a good Find tool and patience!) you could add information about the original source code. Commented Oct 28, 2016 at 12:06
• My ability to read 6502 assembler is limited, so I will leave that to others. My understanding was that the C version is very near to the original.
– kap
Commented Oct 28, 2016 at 12:09
• Your "modified version of Elite" is, as far as I can tell, actually a modified version of Text Elite. However your information is still useful. (By the way, I'd recommend reading the tour, just so you can say you've read it.) Commented Oct 28, 2016 at 12:29

Earlier answers describe the procedural generation system of the Elite "galaxy". Also relevant, I think, is the way the ships were designed to be both easy to render quickly on an 8-bit micro, and to take up as little space as possible.

All of the original Elite ships were convex hulls with the possible exception of isolated spikes representing externally mounted guns. This allowed the use of a very efficient hidden-line-removal algorithm, without which it would not have been possible to render even wireframe 3D graphics in realtime using only a 2MHz 6502.

They were also symmetric over at least one axis, and often two. This allowed a significant reduction in the number of vertices, edges, and faces that had to be stored for each ship, since the fact of reflection took less space to encode than the extra vertices for the other half of the ship.

Obviously, they were also not stored as floating-point, but as tightly packed small integers:

Each vertex has 6 bytes of data. Bytes X,Y,Z are the magnitudes of the 3D coordinate. The signs for each component are stored in bits 7,6,5 of Byte S. The lower 5 bits are a visibility distance, with a maximum value of 31 ensuring the vertex is processed for all distances until the ship is plotted as a large dot. The 4 faces associated with each vertex are stored in the 4 nibbles of Bytes F1 and F2.

Each edge has 4 bytes of data. The visibility distance is stored in Byte V, with a maximum value of 31. The 2 faces associated with each edge are stored in the 2 nibbles of Byte F. Byte N1 contains the vertex id (*4) for one end of the line, Byte N2 the other end.

Each face has 4 bytes of data. The signs for each normal component are stored in bits 7,6,5 of Byte S. The lower 5 bits are a visibility distance, with a maximum value of 31 ensuring the face is processed for all distances until the ship is plotted as a large dot. The magnitudes of the normal's 3 components are stored in Bytes X,Y,Z.

The resulting hull shapes are still used in today's Elite:Dangerous, though with much more detail added.

• It's not a ship but the missile model is interesting for being the only thing (I think) with non-convex faces, due to its fins. So they have the same habit as the other spikes of disappearing at slightly the wrong moment, and also don't get the free solid-esque hidden face removal that the convex objects usually do. But they're small and missiles move quickly. Commented Jan 6, 2020 at 14:45
• FWIW, the data format does not take advantage of the symmetry. All vertices and edges are explicitly listed. The Transporter was not symmetric, as it had the author's initials on it. See 6502disassembly.com/a2-elite/meshes.html#coord-handedness . One trick was re-use of parts: the Thargon defines its own vertices and faces, but uses the edge list from the cargo canister. Commented Apr 2, 2020 at 19:11

To extend and compliment (and not compete with) the answer above also check out bbcelite.com

Fully documented source code for Elite on the BBC Micro

The algorithms behind the procedural generation of system data

I know stackexchange convention is to quote the source a) in case the source later no longer exists (I'd certainly hope not with bbcelite.com) and b) for context for answering, so here are some excerpts:

The Data on System screen is, under the hood, a work of mathematical art. Every bit of data on that screen is procedurally generated from the system seeds,

Galaxy and system seeds

Famously, Elite's galaxy and system data is generated procedurally, using a set of three 16-bit seed numbers and the Tribonnaci series.

Twisting the system seeds

(which sounds a bit like a lyric from a song performed by Happy Mondays)

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.

• Didn't Elite originally have even more galaxies, but they capped it at 8 for the sake of being tractable? That might be apocryphal. Commented Feb 24, 2021 at 14:19

It wasn't compressed. The data was calculated using a Fibonacci Sequence. I don't know what seed numbers they used.

The new Elite Dangerous does the same.

https://en.wikipedia.org/wiki/Fibonacci_number

The whole galaxy and all the planets were generated on the fly from a few small sets of strings and a pseudo-random number generator. The fact that the number generating sequence always started with the same seed meant it always made the same names and planets!

It's actually quite easy to do something similar in BASIC, using RANDOMIZE and RND.

Make a string like "KAKEKIKOKUFAFEFIFFOFULALELILOLUOSONAX"