How Exile works
02 · How Exile works

How Exile builds a world

65,536 tiles from 500 bytes of code: the landscape is never stored — it is a pure function over coordinates, and every carry flag in it is load-bearing.

Exile (Superior Software, 1988) gave the BBC Micro something seemingly impossible: a single coherent world of 256×256 tiles with caverns, shafts, diagonal tunnels, a crashed spaceship, an underground base and all on a machine with 32KB of RAM, most of which was screen memory and game code. Stored naively, the map alone would be 64KB. Twice the machine.

The trick is that the map is never stored. Instead there is a function, get_tile(x, y), living at &17b1 in memory, and every time the game needs to know what’s at some coordinate such as for scrolling, for collisions, and for deciding whether a worm can emerge here it calls the function and the answer is computed using a pure function that given the same inputs gives the same answer, every time. The world is a pure function over coordinates, the same insight that let Elite fit eight galaxies into 22KB, here applied not to a star chart but to terrain you can interact with, fly around and collide with, tile by tile. The whole thing is a little over 500 bytes of 6502 code, 54 bytes of lookup tables, and 1KB of hand-placed data for the set-piece locations. Mind boggling frankly.

This article walks through how that function builds the world, bottom-up: we start with a blank canvas and switch the algorithm on one layer at a time. Every stage links into an interactive demo where you can pan, zoom and toggle the layers yourself. (Everything described here was reimplemented from the disassembly and verified bit-identical against an emulation of the original 6502 code — all 65,536 tiles, twice over: once for the landscape algorithm, once for the display pipeline on top.)

The rules of the machine

One thing colours everything that follows: this is 8-bit arithmetic with a carry flag and that carry flag is, to say the least, important.

On the 6502, a shift instruction (LSR) pushes the bit that falls off the end into the carry flag, and an add instruction (ADC) adds it back in. Exile’s hash functions chain these deliberately:

&17b4  LSR A          ; halve A, bit 0 falls into carry
&17b5  EOR &95        ; mix in tile_x
&17b7  AND #&f8
&17b9  LSR A          ; another bit into carry
&17ba  ADC &95        ; add tile_x PLUS that carry bit
&17bc  LSR A
&17bd  ADC &97        ; add tile_y PLUS the carry from that

Those stray carry bits aren’t sloppiness — they’re free entropy. The whole algorithm is built from little chains like this, and some of the chains cross function boundaries: the carry left over by an add in the sloping passage test at &18ac is silently consumed by the horizontal passage function at &18b7, eleven instructions and two branches later. Get one carry wrong anywhere and you don’t get a slightly different world; you get a completely different one.

The TypeScript engine behind the demos doesn’t reproduce this by simulating an accumulator and a flag. Each hash is an ordinary pure function, and every carry that matters is an explicit named value — the sloping-passage hash returns its final carry, and the horizontal-passage function takes it as a parameter. Same trick, but visible in the function signatures instead of hidden in processor state; the emulator-backed validation is what proves nothing was lost in the translation. Initially I had used a little simulation of the 6502 but I felt it really didn’t provide enough insight into how the algoirthm worked and so switched to a more explicit representation.

(A small companion demo — coming to this site with a later article — steps through these exact sequences: watch the carry move bit by bit, next to a “carry-blind” accumulator computing what a careless port would get. With one particular tile coordinate, the real machine produces an open corridor and the careless port produces solid rock.)

Layer 0: the blank canvas

▶ demo: everything off ⌗ 6502 source

Strip every layer out and Exile’s world is sky above row 78 (&4e) and solid earth below it, forever. That’s the base case of the function, if none of the carving logic fires, the fallback is a routine called leave_with_earth_or_stone and the answer is always “rock”.

Even this empty world hints at the machine underneath: a few thin horizontal slivers of space survive, because the passage functions’ disabled branches still return “empty” for a handful of coordinates.

Layer 1: f1, the hash everything hangs off

▶ demo: + base hash ⌗ 6502 source

The function computes eleven derived values, which the disassembly names f1 through f11. The first, f1, is the seven-instruction hash of (x, y) shown above, and it is the only source of randomness in the entire world. There is no random number generator; f1 and its descendants are re-derived from the coordinates every single call.

(You’ll notice the layers below jump from f1 straight to f5. That’s not an omission: f2, f3 and f4 exist, but they aren’t carving functions — rather they’re the addressing chain for the hand-placed map data, deciding whether a tile is mapped and where it lives in the 1KB overlay. The code computes them early; this article builds the world procedural-first, so they get their own section at the end.)

With f1 on, the solid rock stops being uniform. leave_with_earth_or_stone takes three bits of f1 and picks from a nine-entry table of earth and stone tiles — mostly the same two sprites in different horizontal/vertical flips. Flipping is free on this engine (two bits in the tile byte) and it transforms an obvious repeating texture into something that reads as organic rock. Eight bytes of table, and we get a lot more coherent detail.

Layer 2: the surface

▶ demo: + surface ⌗ 6502 source

Row &4e is ground level. A dedicated routine hashes x (not y — the surface is a horizontal feature) and decides between open ground and tufts: earth edges and grass fringes from a four-entry table. The row below it, &4f, is always solid earth so the surface has something to sit on.

Two charming details live here. First, surface cells that come out “empty” aren’t actually the space tile — they’re tile type &00, a placeholder that the display pipeline later dresses with bushes and grass (more on that at the end). Second, there is exactly one hardcoded special case in the whole algorithm: the tile at (&40, &4f) is a vertically-flipped leaf. That’s not décor; it’s the leaf, an object you need in the game, and it’s nailed into the landscape function itself. Efficient.

Layer 3: the edges of the world

▶ demo: + world boundaries ⌗ 6502 source

An infinite procedural cave system needs walls, or the player falls off the maths. The boundary check fills in the left and right margins, wide in the top half of the world (solid before x ≈ &40 and after ≈ &e2), narrower in the bottom half (before ≈ &23, after ≈ &f8). Making the world a rough urn shape, wider at the bottom.

The floor is subtler. Rather than a hard line, the test is (f1 AND &e8) < y and so the deeper you go, the more likely a tile fails it and turns solid. The bottom of the world isn’t a wall, it’s a gradient — caves peter out raggedly into bedrock, differently in every column. One compare instruction giving the floor of the caves a lot more interest.

Note the order of operations: while the boundary checks run, the code temporarily zeroes f1, so boundary rock is plain earth rather than the varied mix. It’s restored immediately after. Little sequencing details like this are exactly what a careless port loses first (I may know from experience!); in the engine it survives as boundary rock literally calling the rock-picker with f1 = 0.

Layer 4: f5 — square caverns

▶ demo: + square caverns ⌗ 6502 source

This is out first carving layer. f5 hashes y into a coarse band value, adds x, and masks with &e8; where the result is exactly zero, the tile is open space. Because of the masking, the zeros come in clumps — rectangular chambers, roughly eight tiles across, scattered on a loose grid through the rock.

In the bottom half of the world (y ≥ &80) these caverns aren’t just empty: they’re filled with variable wind tiles, invisible in the map but very noticeable in the game when they throw your jetpack around. Two specific caverns below the west stone door get a horizontally-flipped wind tile — a permanent downdraft, placed by a three-instruction special case, because the designers wanted that particular descent to be nasty. Like the leaf we get these little design details injected into the landscape generator.

Layer 5: f6 — vertical shafts

▶ demo: + vertical shafts ⌗ 6502 source

f6 mixes f1 with x through a pile of shifts and EORs; where it lands on zero, you get a one-tile-wide vertical shaft. In the eastern half of the world (x ≥ &80) any f6 hit is a shaft; in the west there’s an extra check that breaks the shafts up so they don’t run the full height of the map. The shafts are what turn isolated caverns into a vertical cave system — they’re the ladders between the depths.

The tile they’re made of is not “space”: it’s type &08, the last of the nine placeholder types (&00–&08), and it’s worth pausing on what that means, because it’s the trick that lets a stateless world contain stateful things. get_tile is a pure function — same coordinates, same byte, no memory — so it cannot know that a nest lives in this shaft, and it certainly cannot know whether you’ve thrown the switch next to it. What it can do is emit a placeholder: type &08 doesn’t mean “shaft wall”, it means “a shaft-wall kind of place — ask the object system”.

At display time, get_tile_and_check_for_tertiary_objects does exactly that. The table of hand-placed tertiary objects such as nests, switches, doors, wall fittings is bucketed by placeholder type, and within a bucket an entry is matched on the x coordinate alone. No y is stored anywhere, the algorithm only produces type &08 in a handful of columns, so within the shaft-wall bucket, “the one at x = such-and-such” is unambiguous. The generator itself is doing half the addressing — that’s a byte of storage per object saved by leaning on the maths. On a match, the object’s current tile is drawn in place of the wall, and the resolved tile carries offsets back into the live table entry, which is where the state lives: a door’s open/closed bit, a switch’s setting, a nest’s aliveness. Flip that bit and the world changes without get_tile ever knowing. No match in the table? The engine falls back to a per-type default (for &08, the plain shaft-wall graphic), keeping the algorithm’s flip bits. There’s more on this pipeline, and the palette system that rides with it, at the end of the article.

Immediately after the shaft check is a guard clause: anything above row &52 gets filled in solid. Passages are not allowed within four rows of the surface so the underground stays sealed except where shafts deliberately break through.

Layer 6: f7 — sloping passages

▶ demo: + sloping passages ⌗ 6502 source

f7 is a function almost entirely of y (masked with &17), and it works as a row selector: rows where f7 is non-zero are candidates for diagonal passages, evaluated by a shared slope routine at &196a that is the single most audacious piece of code in the algorithm.

It handles two families of diagonals. The 45° passages are simple coordinate tests — x + y for one direction, y − x for the other, masked and compared, with x’s bit 3 breaking every passage into eight-tile segments so tunnels don’t cross the whole map.

The creation of sloping caverns is amazing. The routine takes bit 5 of f1, shifts it to the top of the byte, and EORs with &e5. The result is either &65 or &e5 — which happen to be the 6502 opcodes for ADC (add) and SBC (subtract). It then writes that byte into the instruction stream at &1985 and immediately executes it:

&1975  AND #&20        ; isolate bit 5 of f1
&1977  ASL A
&1978  ASL A           ; now &00 or &80
&1979  EOR #&e5        ; now &65 (ADC) or &e5 (SBC)
&197b  STA &1985       ; overwrite the next-but-one instruction
...
&1985  ADC &95         ; ...or SBC &95, depending on f1

Self-modifying code, using one hash bit to decide whether a cavern slopes uphill or downhill because adding x versus subtracting x flips the diagonal. A branch would have cost more bytes. (The TypeScript engine’s entire model of this audacity is a boolean called rising — which is all it ever was.) The slope routine also reports where in a passage you are (empty middle versus edge), and edges get proper slope tiles with a rotation applied from a four-entry flip table, so every diagonal is cleanly walled.

Layer 7: f8 — horizontal passages

▶ demo: + horizontal passages ⌗ 6502 source

Back on the rows where f7 is zero, f8 = (f1 + x + carry) AND &50 decides the corridors, zero means open space. (That + carry is the one left over from the f7 computation, eleven instructions earlier. In the engine the hand-off is explicit: f7Hash returns { f7, carry } and f8Hash takes the carry as an argument which is an incredibly sneaky dependency, promoted to a function signature.) These are the main east–west arteries of the underground, and because f7 selected the rows, they line up into long navigable levels rather than isolated pockets.

Layer 8: f9, f10, f11 — furniture

▶ demo: + passage features ⌗ 6502 source · ▶ + slope features

Corridor cells where f8 is non-zero don’t stay solid rather they become contents. f9 (and for certain values a re-hash, f10) indexes a sixteen-entry table of passage furniture: nests, short and tall bushes, columns, stone blocks, mushrooms, pipes, and more of those placeholder types that the object system will dress later. Two details worth savouring:

f11 does the same job for the edges of sloping passages: a couple of f1 bits decide between a plain slope tile and a feature from an eight-entry table, rotated to match the slope’s direction.

At this point the procedural world is complete: a plausible, fully connected cave system. But it’s anonymous and its not, yet, Exile.

Layer 9: the 1KB overlay — hand-placed somewhere

▶ demo: + map data ⌗ 6502 source · ▶ + irregular caverns = the full map

The set pieces such as the grounded spaceship, your equipment room, Triax’s base, the puzzle rooms are 1,024 hand-authored tile bytes at &afec. The interesting question is: how do you know which (x, y) reads which byte?

The answer is with more hashing. Before any of the layers above run, get_tile derives f2, f3 and f4 from the coordinates. First y is folded into bands:

Which stacks three widely separated slices of the world (around the surface, and the deep south) into one contiguous coordinate space, with everything else excluded. Then the f2/f3/f4 chain scrambles band-y and x together, and if both f2 and f4 come out under &20, the tile is mapped: the byte is fetched from map_data[(f4 AND 3) × 256 + ((f4 × 8) EOR f2)].

Here’s the remarkable part. If you enumerate all 65,536 coordinates, exactly 1,024 of them pass that gate, and they map onto exactly the 1,024 bytes of the table. A perfect bijection, no collisions, no waste. The hash isn’t approximately carving out a region; it is the memory addressing scheme. The authors effectively drew their set pieces through the hash’s distorted lens, so that the hash reads them back out straight. I imagine they developed a tool to help with this but that might just be my perspective nearly 40 years later - I don’t think thats certain!

Two footnotes to this layer. Values of f4 just outside the mapped range (&20–&3c) return empty space and give the “irregular caverns”, a ring of organic hollows around each mapped structure, so the hand-built rooms sit in caves rather than being embedded in blank rock. And if the crashed ship looks strangely dismembered on the map: it is. The Pericles was disassembled for parts in the game’s backstory, and its hull sections are genuinely stored as scattered pieces, hanging in the caverns where the story left them. I’d love to know what game first - the story or the world.

After the map: what you actually see

Everything above describes the byte get_tile returns: two flip bits and a tile type. Between that byte and the screen sit two more systems, and they’re why screenshots of the real game look richer than a raw tile plot.

Placeholders and tertiary objects. Tile types &00–&08 mean “space, but ask the object system”. A table of 254 hand-placed tertiary objects (keyed, economically, on x alone) can substitute a door, a switch, a transporter, wall equipment. If nothing matches, a per-type default applies — tall bush, short bush, stone, plain space. This is how one placeholder type in a shaft wall becomes a nest in one place and a switch in another, without the landscape function storing either.

Dynamic palettes. Tiles don’t carry colours; tile types carry palette classes, resolved at draw time. Stone recolours every 16 rows and earth every 32, from a table of strata palettes — that’s the geological banding that makes depth legible. Bushes pick one of four colour schemes from a hash of position and flip. Spaceship parts are red-and-white in the top half of the world and switch to Triax’s green-and-yellow in the bottom half — same tiles, recoloured by y, so one set of sprites builds both ships. Mushrooms are red on floors and blue on ceilings, keyed off their flip bit — which is why that flip at row &e0 matters.

And one thing the map has no tiles for at all: water. The flooded caverns at the bottom of the world are four waterline variables (one per x-range of the map) and a raster interrupt that reprograms the background colour register mid-frame — cyan for one scanline at the surface, blue below. The water you remember swimming through is, in tile terms, not there.

Why this still impresses

I probably don’t have to explain this but still… its worth repeating as its mind boggling.

The numbers: roughly 500 bytes of algorithm, 54 bytes of tile tables, 1,024 bytes of map data, and a 254-entry object overlay — call it 2.5KB — producing a 64KB world with a consistent geology, a connected transport network, landmark architecture, and enough local detail that players drew their own maps for years without suspecting the caves were maths.

The design lesson holds up. Long before the rush of Roguelikes and the glut of procedurally generated worlds Exile doesn’t generate content and store it; it defines the world as a deterministic function and queries it. The hand-made parts aren’t outside the system, they’re addressed through the same hash that makes the wilderness. And where the code needed one more bit of expressiveness than the byte budget allowed, it rewrote its own instructions.

The interactive demo lets you toggle each layer, ghost the removed ones, and inspect any tile. Its engine is written as ordinary pure functions — every important carry an explicit value and the self-modifying opcode a boolean. The result is tested bit-identical against the original code for every tile in the world, which is what licenses taking those liberties. A companion article covers the other half of the story: how the graphics are stored in 3.3KB and what the sprite plotter does with them.

Exile © 1988 Peter Irvin and Jeremy Smith · published by Superior Software
Reconstructed by James Randall from the enhanced version disassembly created by level7
Presented as a tribute to its authors.