Elite had eight galaxies of 256 star systems each, every one with a name, a position on the chart, an economy and a government, on a BBC Micro with 32K of memory that also had to hold the screen. None of those systems was stored. The program worked each one out from three numbers whenever it was needed, and got the same answer every time. That is procedural generation: content made by an algorithm instead of drawn, typed in and saved. On the machines of the early 1980s it was often the only way to fit a big world into a small memory, and the best programs used it to make something that could not have been built by hand.
Fast facts
- What it is: generating levels, maps, worlds, names or items with a program, usually from a pseudo-random number generator.
- The key idea: a seeded generator produces the same sequence every time it starts from the same number, so a world can be “stored” as its seed.
- Two uses: the same world every time (Elite, The Sentinel, River Raid, Captive), or a new one every game (Rogue).
- What it saves: memory and design time.
- What it costs: less control. The generator must be kept from producing unfair or impossible layouts.
Pseudo-random, and repeatable
A computer’s “random” numbers usually come from a pseudo-random number generator: a short calculation that turns one number into the next. The Random numbers entry covers how they work. Start such a generator from the same value, its seed, and it produces the same sequence. For a game that wants variety, that is a problem to solve by seeding from something unpredictable, such as a timer. For a game that wants a huge but fixed world, it is the whole trick: store the seed and the rules, and regenerate the world whenever it is visited.
Carol Shaw used exactly that trick for River Raid (Activision, 1982) on the Atari 2600. “It was only 4 kilobytes of ROM, so you don’t have space to store a lot of graphics,” she told Benj Edwards in 2011. She drew only the transitions between one width of river and the next, divided the river into sections of 32 lines, and “used a pseudorandom number generator to decide what the next width was going to be… you do a couple of shifts and an add or something and generate the next pseudorandom number, and that decides what the next part of the river is going to look like”. Because the generator started from the same seed, “every time you play the game, it will look the same.” Activision’s later ZX Spectrum version took the opposite approach: its annotated disassembly shows 48 levels stored as data, 12,288 bytes of terrain and another 12,288 of enemy positions, almost half the program.
Shaw’s game sits within the wider history of women’s contributions to computing: programming a landscape was one of several kinds of technical and creative work involved in making games.
Elite: galaxies from six bytes
Ian Bell and David Braben’s Elite (Acornsoft, 1984) is the best-known case. Bell later remembered the struggle of “compressing all the data down to 22K”. The galaxy generator, which Bell’s list of who wrote what credits to Braben, describes each star system with three 16-bit numbers, six bytes of “seeds”. Galaxy 1 starts at the system Tibedied, whose seeds are &5A4A, &0248 and &B753 in hexadecimal.
To move to the next system, the program “twists” the seeds. Mark Moxon’s annotated edition of the game’s source describes the step, which is based on the Tribonacci series, a relative of the Fibonacci sequence in which each number is the sum of the three before it:
- the new first seed is the old second seed;
- the new second seed is the old third seed;
- the new third seed is the sum of all three, keeping only the low 16 bits.
Four twists take you from one system to the next, so Tibedied’s seeds become &0248, &B753 and &13E5 after the first. Twenty-eight twists from Tibedied reach system 7, Lave, where every player’s game begins.
Bits of the seeds then become the system’s properties. At Lave the high byte of the second seed, 20, is the x-coordinate on the galactic chart and the high byte of the first seed, 173, is the y-coordinate. Three bits give the government (a dictatorship) and three the economy, and the technology level is worked out from those and two more bits. The name comes from a table of two-letter pairs such as LA, VE, IN and TI. Five bits of the third seed pick a pair, the seeds are twisted, and the next pair is picked, three or four times depending on another bit. One of the pairs is empty, which is how names come out shorter: Lave is LA, VE and a blank.
The eight galaxies cost almost nothing more. Using the galactic hyperdrive rotates every seed byte one bit to the left, which gives a new starting point and a new set of 256 systems. Eight rotations bring every byte back to where it started, so the eighth jump returns you to galaxy 1. The whole universe of 2,048 systems comes from the three starting numbers and a few dozen bytes of code and tables.
Players met the result without being told how it worked. ZZAP!64’s review of the Commodore 64 version in May 1985 promised “2000 planets” and told readers that “there are eight galaxies in all and 250 planets in each one, so running out of planets is pretty hard to do”. (There are 256.)
The Sentinel: 10,000 landscapes by number
Geoff Crammond’s The Sentinel (Firebird, 1986) made the landscapes the game. ZZAP!64 gave it a Gold Medal and described “10,000 worlds”, each “a landscape comprising of three-dimensional solids arranged to form hills, valleys and chequered plateaus on which trees are planted”, with the Sentinel always on the highest point and the player’s Synthoid always on the lowest. Each landscape had a number and an eight-digit code shown when you completed the one before, so that “the Synthoid can progress through the 10,000 levels without having to start from the first planet every time”.
Moxon’s annotated edition of the BBC Micro version shows how the landscapes are made. The landscape number, from 0000 to 9999, is written as a binary-coded decimal number into a 33-bit linear feedback shift register, a generator that produces pseudo-random bits by shifting and combining two of its own bits. (One extra bit is set so that landscape 0000 does not start from all zeroes, which would never produce anything else.) The generator fills a 32 × 32 grid of tile corners with random heights, the program smooths them by averaging each corner with its neighbours, then scales them to eleven levels of altitude. The same number always gives the same landscape, and the secret codes come from the same sequence. Firebird’s Herbie Wright, collecting a ZZAP! readers’ award for the game, said it proved that “in these days of clones (and clones of clones)… originality still counts”.
Rogue: a new dungeon every game
Rogue went the other way. Written by Michael Toy and Glenn Wichman with Ken Arnold, and dated in its copyright notice from 1980, it deals a fresh dungeon every time you play, and it lets you die for good, so no two games are alike. Its later source code, released under a BSD licence, shows how each level is built:
- the 80 × 24 screen is divided into a 3 × 3 grid, one room per cell, nine in all;
- up to three cells are left without a room and hold only a junction for corridors;
- starting from a random room, the program joins rooms to neighbours not yet connected until every cell is reachable, then adds up to four extra corridors so there is more than one route;
- each corridor runs from a door, jogs sideways once at a random point, and carries on to the next room.
Items get the same treatment. Potions, scrolls and wands have their appearances shuffled each game, so a plaid potion might heal you in one game and send you to sleep in the next. The game designer Randy Smith, writing in Edge in 2010, compared Rogue to a card game, “infinitely the same and unique… Before every hand the cards are shuffled and dealt”, and counted its descendants as “a hallowed tradition of 30 years and numerous denominations: ADOM, Spelunky, NetHack and, yes, even Dwarf Fortress”. The roguelike entry follows that family.
Captive: a level generator with rules
By 1990 the idea had reached 16-bit role-playing games. Tony Crowther’s Captive (Mindscape, 1990) built its bases with a program called The Architect. “There are only a certain number of levels you can fit in if you use pre-set data,” he told The One. “Each level has a fixed random seed, so they’ll be the same on all machines… It takes just three seconds to produce a level.” Crowther put the total at about 65,000 levels; ACE counted 64,900 bases and gave the Amiga version 930.
Crowther also named the hard part. A generator does whatever its rules allow, so the rules have to rule out the impossible. “The only problem I had with it was with keys being placed behind the door they open. The generator has to know where it can safely position keys.” In his words, “I’ve only told the program what it can’t do”.
Frontier: a galaxy by astronomy
Braben returned to the idea on a far larger scale in Frontier: Elite II (1993). Its box promised “100,000,000,000 planets generated in accordance with current theories of planet formation”, as Amiga Power noted drily. For nearby stars Braben used real astronomical data; for the rest, he told CU Amiga, “I’ve tried to generate the planets according to the current theories of how planets form, so you end up with systems that are ‘very likely to be’”. He explained to ST Format why it fitted on one disk: the simulation of planet formation ran quickly enough for the game to do it on the fly, “generating data as and when it needs it”. It worked out the dust likely to be in each system, split it into planets, and from their temperatures the likely elements and atmospheres.
Later use
The technique never went away. Spelunky, a free PC game from 2008 remade for the Xbox 360 in 2012, builds a new cave on every visit. Edge found that it was “procedural, then, but it still feels handmade”, partly because much of it is fixed: the worlds come in the same order and certain objects are always somewhere to be found. Hello Games’ No Man’s Sky generates a universe of some 18 quintillion planets. Frontier Developments’ Elite Dangerous, the descendant of Elite, generates its galaxy too: Frontier’s 2013 prospectus described the game as recreating “the 100 billion star systems of the Milky Way galaxy”.
Sources
- Benj Edwards, “VC&G Interview: Carol Shaw, Atari’s First Female Video Game Developer”, Vintage Computing and Gaming, 12 October 2011 (interview conducted May 2011; primary retrospective testimony): River Raid’s 4K ROM and river generator. https://www.vintagecomputing.com/index.php/archives/800/vcg-interview-carol-shaw-female-video-game-pioneer-2
- River Raid (ZX Spectrum) annotated disassembly, “Level data stored wastefully” (web, secondary): 48 levels of stored terrain and object data. https://river-raid.github.io/river-raid-disasm/
- “The making of Elite”, Edge issue 88, September 2000: Bell on “compressing all the data down to 22K”.
- Ian Bell, Elite FAQ, Autumn 1999 (web, secondary): the galaxy generation credited to Braben. http://www.iancgbell.clara.net/elite/faq.htm
- Mark Moxon, Elite on the 6502, “Galaxy and system seeds” and “Twisting the system seeds” (web, secondary): the three seeds, Tibedied’s starting values, the Tribonacci twist, four twists per system, the bits for coordinates, economy, government and name, the galactic hyperdrive’s byte rotation. https://elite.bbcelite.com/deep_dives/
- ZZAP!64 issue 1, May 1985, pp. 14–19: Elite on the Commodore 64 (“2000 planets”; “250 planets in each one”).
- ZZAP!64 issue 20, December 1986, pp. 22–23: The Sentinel review, Gold Medal (10,000 worlds; the security codes). Issue 23, March 1987, pp. 82–84: readers’ awards (Herbie Wright).
- Mark Moxon, The Sentinel on the BBC Micro, “The maths behind each landscape’s unique sequence of seed numbers” and “Using procedural generation to create the 10,000 landscapes” (web, secondary): the 33-bit shift register, the BCD landscape number, the 32 × 32 corners, smoothing and eleven altitudes. https://thesentinel.bbcelite.com/deep_dives/
- Michael Toy, Ken Arnold and Glenn Wichman, Rogue: Exploring the Dungeons of Doom, source code,
rooms.c,passages.candrogue.h(BSD licence; copyright 1980–1983, 1985, 1999): the 3 × 3 grid, missing rooms, the connection graph and corridors. - Randy Smith, “Blessed procedural content”, Edge issue 213, April 2010: Rogue and its descendants.
- Laurence Scotford, Captive feature and interview with Tony Crowther, The One issue 25, October 1990, p. 26: The Architect, fixed seeds, the key problem, 65,000 levels.
- ACE issue 37, October 1990, pp. 48–49: Captive review (64,900 bases; the Architect; 930).
- Amiga Power issue 32, December 1993: Frontier’s box (“100,000,000,000 planets…”).
- CU Amiga, November 1993, p. 63: interview with David Braben on Frontier’s planets.
- ST Format issue 54, January 1994, pp. 24–25: Braben on generating data on the fly.
- Edge issue 244, September 2012, p. 88: Spelunky review (Xbox 360; on the PC since 2008).
- Wireframe issue 12, April 2019: the 18 quintillion planets of No Man’s Sky.
- Frontier Developments plc, AIM admission document, 9 July 2013 (web, secondary): Elite Dangerous and “the 100 billion star systems of the Milky Way galaxy”. https://frontier-drupal.s3-eu-west-1.amazonaws.com/development/frontier-corp/s3fs-public/FrontierDevelopments_plc_Admission_Document.pdf