Retrocomputing Stack Exchange is a question and answer site for vintage-computer hobbyists interested in restoring, preserving, and using the classic computer and gaming systems of yesteryear. It only takes a minute to sign up.
Sign up to join this community
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.
— 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?
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.
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.
goat_soup) works.
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.
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.
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,
Famously, Elite's galaxy and system data is generated procedurally, using a set of three 16-bit seed numbers and the Tribonnaci series.
(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.
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.
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"
Start with a seed via RANDOMIZE - say RANDOMIZE seed+planet.no
Generate a number with RND to be the length of the name, and with a FOR loop, generate a random odd number, and add the 2 characters in the above string starting at that position to the planet name until you hit the needed length.
The above string will give you names like "Kafila", "Liax", "Nakefi", and "Kukuos". The more combinations you add, the more diverse the names.
Generate all the random data you want for that planet - tech level, planet size, whatever. You can make some based on formulas, like population based on size x tech level or whatever suits your purpose. Get as complex as you want.
Now, the trick is, because computer random number generators are not truly random, every time you start a RANDOMIZE with the same seed, you'll get the same planet, no matter how much data you generate! This way its possible to have literally thousands of planets, which will always be the same, yet only have the data for the one current planet in memory or even stored on disk.
