28

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

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

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?

44

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.

| improve this answer | |
  • 4
    "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/…) – flith Oct 28 '16 at 6:01
  • 1
    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. – wizzwizz4 Oct 28 '16 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. – Nick Westgate Oct 30 '16 at 3:31
  • 1
    @NickWestgate It's fine; kap's answer explains how the description algorithm (goat_soup) works. – wizzwizz4 Oct 30 '16 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 – Nick Westgate Oct 30 '16 at 8:53
9

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.

| improve this answer | |
  • 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. – wizzwizz4 Oct 28 '16 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 Oct 28 '16 at 12:09
  • 1
    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.) – wizzwizz4 Oct 28 '16 at 12:29
5

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.

| improve this answer | |
  • 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. – Tommy Jan 6 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. – fadden Apr 2 at 19:11
2

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.