Elite: How a Galaxy Fit Inside a BBC Micro

0:14This jump should be impossible. Usleance and Erbieder are on opposite sides of galaxy seven, 102.5 light years apart. A full fuel tank reaches just 7.0. But Elite says 4.0, accepts the destination and takes only four light years from the tank.

0:52We have just crossed almost the full width of a galaxy. More strangely, this mistake creates the only ordinary jump into a cluster of 27 systems that is otherwise too far from the rest. Elite's arithmetic has punched a wormhole through its own universe. To understand why, we first have to see how six bytes became 256 systems in each of eight galaxies, 2,048 worlds in all.

1:30In 1984, even reviewers struggled to believe it fitted. Personal Computer Games explained that the planets' data files were loaded from disc when needed. They were not. The planets were generated, and the cassette version could not quietly fetch another part of the game anyway. Once its long load was over, everything needed for docking, trading and flying had to remain in memory together.

2:04The two authors were Ian Bell and David Braben. Braben described Elite as a joint project and said it was often difficult to remember who had which idea. Their separate routines still had to become one game inside those 32 kilobytes.

2:26The universe begins with six bytes, the seed from which every system is calculated. A byte is eight binary digits, or bits, so the seed contains 48 bits. Read in pairs, those bytes become three 16-bit numbers, each able to hold a value from zero to 65,535. Braben's starting seed describes Tibedied, the first system in galaxy one. Lave, where every new commander begins, is the eighth system generated from it.

3:04To move from one system to the next, Elite twists those three numbers four times. Each twist discards the first number, moves the other two along, and puts the sum of all three at the end. If that sum passes 65,535, anything beyond sixteen bits is dropped and the count starts again from zero. Watch the numbers move and the first overflow roll round.

3:41Four twists are the stride from one system to the next, so each system grows from the one before it. Repeat that stride 256 times and a galaxy appears. Whenever the Long-range Chart opens, Elite regenerates all 256 systems in order and plots them afresh. This is procedural generation: storing the rules instead of every result.

4:21Braben recalled an original ambition of two to the power of 48 galaxies. With 48 bits in the seed, that is about 281 trillion possibilities. Acornsoft, Elite's publisher, insisted on eight. Bell later said David Johnson-Davies of Acornsoft was right: with a hundred galaxies, players would realise there was no possible way the worlds were all stored in the computer. The shipped game turns its one seed into those eight galaxies. The galactic hyperdrive, a device that moves the commander to the next galaxy, rotates every seed byte's bits one place to the left. The bit that falls off one end returns at the other. After eight rotations, every bit is home again. Eight galaxies need no new planetary tables, only eight arrangements of the same six bytes.

5:22Names come from the seed too. Five bits at a time choose three or four pieces from a table of two-letter pairs, with one choice that prints nothing. While spelling one name, the game twists the seed between picks. Lave is LA, then VE, then the empty choice. Tibedied is TI, BE, DI and ED.

5:52Other bits in the same seed numbers decide where the system sits, whether its inhabitants are human or alien, their species, and the system's economy, government, technology, population and productivity. On the chart, that human-or-alien bit also makes human systems two-pixel dashes and alien systems one-pixel dots. The relationships can be surprisingly literal. A planet's radius, after removing a multiple of 256, leaves its horizontal map coordinate. Lave's radius is 4,116 kilometres. Remove sixteen lots of 256 and 20 remains. Lave sits at horizontal coordinate 20. What looks like a database is several views of the same few numbers.

6:53Now the saving can be counted. The twists, names, system figures, letter-pair table, seed and galaxy rotation occupy 299 bytes. A plain table containing exactly the names and figures those rules produce would need 32, 001 bytes, almost the whole computer. Watch that table fill the machine.

7:23Radius and species add only 82 bytes of rules, bringing the comparable total to 381. Store the same information in a plain table and it grows to 40, 193 bytes, larger than the entire BBC Micro. Even packed as tightly as eight bytes per system, it would still consume half the machine. Elite rebuilt all of it with rules smaller than half a kilobyte.

8:01The cassette version's generator stops there. It has no colourful planetary descriptions. If you remember Lave's rain forests and its Lavian tree grub, that came from the BBC Micro disc version or a later version. There, a recipe Bell called Goat Soup assembled descriptions by choosing and joining reusable phrase fragments. Stored as finished text, the 2,048 descriptions would need 139,676 bytes, more than four BBC Micros. The phrases themselves take 1,109 bytes, with separate code to assemble them. Sometimes the combinations creak: Zaatxe is “ravaged by lethal lethal yaks”.

8:57Choosing the seed was what Braben called a beauty parade. He remembered trying numbers, sometimes birthdays, and rejecting galaxies with ugly clusters or rude names. One candidate had a system called Arse. “We couldn't use the whole galaxy. We just threw it away!”

9:23Later accounts claimed Planet Arse nevertheless appeared in the released game. It did not. To print ARSE as two pieces, the table would need AR followed by SE. But its only piece beginning with S is SO. Hide the A at the end of an earlier piece and the next piece would have to be RS. That does not exist either. The shipped table cannot make ARSE. It does produce Anusa, Xeesanus, Isaanus and Maanusre. Francis Spufford wrote that the starting galaxy was the one the authors checked, and galaxy one contains none of them.

10:06Ian Bell later released the original source, the text Bell and Braben wrote before it was assembled into the 6502 processor's own instructions. Mark Moxon has since documented every line. The source for the cassette game occupied 78,561 bytes on its source disc. That was not memory used by the running game, but it was 2.4 times the memory of the BBC Micro that had to assemble it.

10:41The source was mostly assembly instructions embedded inside seven BBC BASIC programs. All seven could not fit at once, so each assembled its share, loaded the next program over itself, and handed the job onwards like a relay. What the relay produced was the game itself: 21, 952 bytes of code and fixed data in memory.

11:12The BBC Micro Model B had 32,768 bytes of memory. The game took about two-thirds, and nearly another quarter went to the screen. That left 2,880 bytes, less than three kilobytes, for everything else: operating-system workspaces, the processor's stack, the current commander's data, temporary calculations and every nearby object.

11:44The screen was one of the first economies. The BBC's standard Mode 4 was a two-colour display. Elite made its screen eight character positions narrower and one row shorter, bringing it down to 7,936 bytes and saving 2,304. Without that saving, everything beyond the game and screen would have shared just 576 bytes.

12:19Yet Elite still gave the space view high-resolution black and white, while the dashboard below had half as many pixels across and four colours. Braben's split-screen trick made the same screen byte mean two different things. In the space view, one bit represents each pixel, so eight bits become eight pixels in two colours. In the dashboard, two bits represent each pixel, so the same byte becomes four wider pixels in four colours. One area of screen memory can serve both jobs.

12:57The remaining problem was when to change the meaning. A television draws its picture line by line from the top, fifty times a second, so a moment in time corresponds to a place on the screen. Vertical sync, the signal that sends the beam back to the top, triggered a countdown from 14,622 microseconds. It ran out just before the picture reached the dashboard, interrupting the processor so the game could switch the video hardware. Watch the countdown finish immediately before the beam enters the lower section.

13:38The split costs no second screen. The loader placed the dashboard artwork in screen memory once, and the game avoided clearing or redrawing it. The squeeze is clearest at the boundary. The main program ended, one checksum byte followed, and the ship blueprints filled every byte from there to the start of screen memory. Bell and Braben's own build reported a gap of exactly one byte between the program and the ships.

14:15Even the memory saved by removing the screen's last row was put to work. Its 256 bytes held the blueprint for the Python, one of Elite's ships.

14:30Ian Bell said in 1984 that there was “not a single free byte in the program”. Between the program and its ship models, he was right. Across the whole machine, however, 144 bytes were unused. They included the operating system's printer buffer, which Elite never needed, and a spare copy of a multiplication routine that nothing called. Separately, 18 scrambled bytes hid an unused notice: “(C)Bell/Braben1984”. Near bursting point is not quite the same as perfectly tidy.

15:15A generated galaxy still had to become a moving view. Braben's ship-plotting routine did not store the Cobra Mark Three as a picture. Its blueprint contains 28 points, 38 edges and 13 faces. The routine turns those three-dimensional points into positions on the flat screen, but it does not waste time drawing every edge.

15:44This shortcut works because the ship is convex, with no dents or hollows. A face pointing away from us must therefore be hidden behind the hull. Elite decides which way a face points with a dot product: it multiplies matching parts of the face's direction and our line of sight, then adds them. The sign of that total gives the answer. A negative result means the face points towards us. An edge is drawn if either of the two faces meeting at it is visible. Watch the edges at the back disappear only when both adjoining faces turn away.

16:29The screen itself helps with erasure. Drawing a line flips every pixel it crosses. Draw the same line again and those pixels flip back, so the line disappears. Each ship keeps a compact list of the lines used for its previous position. Elite redraws that old list to erase the ship, then builds and draws its replacement. A clean second copy of the screen would cost another 7, 936 bytes, nearly three times everything the game and screen left free. Elite never keeps one.

17:08When the commander pitches, pointing the nose up or down, or rolls around the ship's flight axis, Elite holds the player's ship still and rotates everything nearby around it. This was Bell's part of the project: movement and rotations. Each other ship carries three arrows saying where its nose, roof and side point. They should remain the same length and at right angles. Because our ship stays fixed, every nearby ship's three arrows must turn, frame after frame.

17:48A full trigonometric rotation would be expensive, so the code pushes each arrow a small step sideways instead. That is faster and almost right for a small turn. But almost right, repeated frame after frame, distorts the arrows and pulls them away from right angles. A routine called TIDY regularly draws them back into shape. Watch the ship on the right, running without TIDY. Its arrows drift out of square. On the left, TIDY keeps pulling the errors back.

18:34Without TIDY, at frame 400 the nose arrow has shrunk by about a quarter, the side arrow has grown by about a fifth, and the nose and roof are 13 degrees away from a right angle. With TIDY, the arrows wobble a little between repairs and are repeatedly pulled back. Across the same test, their worst angle error stays under eight degrees. Elite accepts a small error because it is cheap, then repairs it before the illusion comes apart.

19:10There was no fixed frame rate. Every visible Cobra has to be turned, tested, erased and redrawn on each frame. With one Cobra Mark Three tumbling ahead, the cassette game manages about 14 frames a second. Put five identical Cobras in view and it falls below four. Ships move a fixed step each frame, so the crowded scene does not merely look less smooth. It unfolds at about a quarter of the pace.

19:52Those five Cobras also reveal how little of the enormous universe exists around the player at one time. From the 2,880 bytes left after the game and screen, Elite reserves a block of just 1,088 for its local universe, everything nearby enough to matter. Each ship has a record of its current state that stacks upwards from the bottom. The list of lines needed to erase it stacks downwards from the top. A new object can exist only while both pieces fit in the gap.

20:29The block has 12 slots: one for the planet, a second reserved slot, and ten for ships. But the variable line lists mean the bytes can run out before the slots. A Cobra needs 189 bytes in all. With the planet, sun and five Cobras present, only 70 bytes remain. Watch the gap close, then see what happens when a sixth Cobra and a smaller Sidewinder try to enter.

21:02This limit reaches the controls. Fire a missile while the block is full and the missile cannot be created. The screen reports “MISSILE JAMMED”, although nothing electrical has jammed and the missile is not consumed. With one Cobra fewer, the same key launches it normally.

21:35The reserved slot is shared by the sun and the station, along with the same line-list space. They are never present together. As the station appears near the planet, it takes the sun's place in the local universe. The full solar system is not waiting beyond the screen. Elite keeps only the few things that can matter now.

22:00The market is similarly compact. On arrival, one random byte combines with the system's economy to create every price and initial stock level. Prices stay fixed for that visit. Buying reduces the stock, while selling does not add to it. But the same 16-bit limit that rolled the seed past 65, 535 can reach into the commander's wallet too. Elite counts money in tenths of a credit. On this market, selling 100 kilograms of platinum stays below the 16-bit maximum. A 102-kilogram sale should pay 6,568.8 credits, which is 65,688 tenths, just beyond 65,535. Watch the counter cross the limit.

23:01The count begins again at zero. Instead of 6,568.8 credits, the commander receives just 15.2.

23:12Procedural generation saved nearly all the memory a stored universe would need. It also meant the chosen seed could leave patterns nobody designed individually. Government comes from three seed bits, giving eight possible patterns for eight kinds of government. The low bits of the twisted numbers repeat quickly, and in galaxy four the governments repeat every eight systems. In galaxy four's repeating pattern, one government bit never becomes one, so only four of the eight patterns can appear. Its systems divide evenly between anarchies, multi-governments, communist worlds and democracies. Nobody banned dictators. One repeating bit did.

24:03Five systems share their coordinates with systems generated earlier. The chart selects whichever came first. In galaxy five, Tezabi lies exactly beneath Divees. The Short-range Chart prints both names beside one dot, but no position of the crosshairs ever selects Tezabi. It exists in the generator and on the screen, but not as a destination.

24:42Another hidden system, Esusale, lies beneath Cecees, the fixed arrival point when the galactic hyperdrive enters galaxy eight. Seven more systems sit beyond the fuel range of the rest of their galaxies. Oresrati's nearest neighbour is 8.2 light years away, while a full tank holds 7.0. That makes five overlapping ghosts and seven isolated worlds, 12 of the 2,048 systems that the cassette game can never visit. Bell later acknowledged the worlds beyond fuel range, and said extra tanks were something they probably would have added if they had not run out of memory.

25:27Yet the same numerical limits accidentally connect other places. Elite measures a jump by squaring the horizontal gap and half the vertical gap, adding them, taking the whole-number square root, then multiplying by four to give tenths of a light year. Between Cemave and Beenri, the two squares total 65,773. The same kind of 16-bit counter can hold only 65, 535, so anything beyond that starts again from zero. Watch the excess roll round.

26:12The chart has turned a real separation of 102.6 light years into 6.0. Mark Moxon documented this overflow and its correction in the later BBC Master version. Mapping the cassette galaxies, we found 30 pairs where systems on opposite edges become false neighbours. Every real distance is between 102.4 and 102.7 light years, but the game shows between 2.4 and 6.8. The rollover appears only when the separation reaches about the galaxy's full width, which is why the false neighbours always join opposite edges.

27:04One false link cuts the shortest journey from Lave to Sori from 21 jumps to 11. None of the 30 reaches any of the seven isolated worlds. The pair from our opening is the same overflow: Usleance and Erbieder are 102.5 light years apart, shown as 4.0. Without that wrong answer, no ordinary hyperspace jump would connect galaxy seven's main 229 systems to its separated cluster of 27. The bug does not merely put a wrong number on the chart. It redraws which parts of the generated universe connect.

27:51Elite did not squeeze a stored galaxy into the BBC Micro. It squeezed in rules that could rebuild one whenever it was needed, then made the screen, the ships, the markets and the local universe share what remained. Its galaxy without dictators, worlds that cannot be selected and wormholes punched through arithmetic are fingerprints of that decision. The universe feels larger than the machine because the machine never has to hold it all.

28:24If you enjoy seeing old machines give up their secrets one byte at a time, subscribe to Retro Computer TV. And if this journey across Elite's impossible galaxy was worth the fuel, you can like the film too.