Height-mapped raycasting on a 10MHz 68000

I built a raycasting engine for the TI-89 that does elevation, occluding sprites, and procedurally generated levels. The hardware is a 10MHz Motorola 68000 with no FPU and 32KB of free RAM. Almost every decision in the engine comes down to two numbers: a signed 16-bit divide costs about 158 cycles, and there is no memory to spare. Once you pick the data structures those two facts force on you, most of the engine follows. This post covers three parts worth reusing: height-mapped raycasting, a one-dimensional depth buffer for sprites, and how the 68000's instruction timings shape the architecture.

The engine sits on top of the FAT Engine, a Wolfenstein-style raycaster Thomas Nussbaumer released for these calculators in 2002. I used its texture sampler and core ray loop and added elevation, sprites, procedural generation, and the game on top. The result, a dungeon crawler called Descend, does textured walls, stairs you walk up and down, enemies that occlude correctly, and random levels, at the FAT Engine's quoted 560 to 825 frames per minute.

Elevation without leaving the raycaster's cost model

A classic raycaster is a 2D problem wearing a 3D costume. You march one ray per column through a grid, stop at the first solid cell, and draw a vertical strip scaled by 1/distance. The cost is bounded and the math is trivial, which is why it ran on hardware like this in 1992. The catch is that the floor is one flat plane and every wall rises from it. No stairs, no ledges, no rooms at different heights.

The cheap way to add elevation is to make floor height first-class data instead of bolting on a second dimension. Every tile carries a floor_heights[] value from 0 to 63, in units of 1/64 of a tile. The DDA already visits every tile boundary along the ray; at each crossing it now also compares the new tile's height to the previous one. On a change it emits a short step-wall segment for the delta and keeps marching instead of stopping. The terminating wall is just the last segment.

The non-obvious consequence is that a single screen column can produce several segments before it ends, so each column buffers up to six of them, sorts by screen-space top, and composites in order. Screen position folds in your eye height directly:

screen_bot = VIEW_HALF + (short)(((long)(eye_z - prev_fh) * (long)wall_height) >> 6);

eye_z is your floor height plus a fixed 32-unit eye offset. Stand on a raised tile looking at lower ground and the geometry extends further down the screen, which the eye reads as height. Walking onto a ramp interpolates your own eye_z toward the target at five units per frame, and a 12-unit cap on how far you can step up in one move doubles as collision against walls. None of this needs portals, sectors, or a BSP. It stays inside the original per-column cost envelope, which is the only reason it runs.

Billboards don't need a real z-buffer

Sprite occlusion is where people reach for a depth buffer, and on this hardware a per-pixel z-buffer is unaffordable. You don't need one. Billboard sprites always face the camera, so within any given column their depth is a single constant. That means one distance per column is enough information to occlude them correctly.

During the wall pass the engine records the hit distance for each column into col_dist[]. When it draws a sprite, each of the sprite's columns tests against that array:

if (ci < 48 && col_dist[ci] < fwd_s) continue;  /* wall is nearer, drop this column */

If the wall in that column is nearer than the sprite's forward distance, the strip is skipped. The whole occlusion system is an array the width of the viewport and one comparison per column. Transparency rides on a separate mask plane in the sprite data. When a billboard has one depth per column, a one-dimensional depth buffer is all you need.

The 68000's timing table is the architecture

The reason the engine looks the way it does is that on a 68000 some operations are dramatically more expensive than others, and the gaps are big enough to design around. DIVS.W is roughly 158 cycles. The renderer is full of "scale by 1/distance" work, so a divide in the inner loop would dominate the frame. Instead it precomputes reciprocals for every distance from 1 to 1023 once at startup and turns each divide into a table lookup of about 12 cycles. That single substitution saves on the order of 14,000 cycles per frame, which is most of the reason the frame rate is what it is.

The same move repeats wherever a per-pixel operation is expensive. Texture shades live across two bit planes, and extracting a shade per pixel costs around 78 cycles of shifting and masking; unpacking the texture into a flat shade table once collapses that to a 14-cycle byte read. Row stepping uses pointer arithmetic (lea 12(a0), a0) rather than a multiply per row. Sky and floor fills are unrolled assembly with no C calls in the hot path. The 96x96 view is drawn to an offscreen buffer and blitted to both LCD planes with longword copies to avoid tearing. Everything is fixed-point with a 6-bit fraction, because there is no float hardware to fall back on. The unifying rule is that you pay memory you appear not to have to buy back cycles you definitely don't have, and it works because the tables are small and the large assets sit in Flash.

Procedural generation is the least interesting part, so I'll keep it short: three or four rooms, L-shaped corridors connecting their centers, and a triangle-wave height profile applied to one or two corridors so the floor ramps up and back down, confined to corridors so rooms stay flat. Randomness is a linear congruential generator seeded from the hardware timers, with the Numerical Recipes constants.

A newer calculator that runs less

The TI-89 Titanium is the later, faster revision, and it runs strictly less of this software than the original. The FAT Engine works by loading code into the heap and jumping to it. The Titanium firmware enforces no-execute on the heap, an anti-jailbreak measure, so a dynamically loaded engine is dead on arrival on the newer hardware. This is the same write-xor-execute logic that breaks JITs and loaders on bigger systems, showing up on a calculator.

The fix was a second build with no engine dependency at all: flat-shaded walls picked from the four grays by distance, but the full height-mapping kept. What made it tractable is that you need almost no trigonometry. A 145-entry sine table covering 0 to 90 degrees, plus symmetry for the rest of the circle, computed once at boot, replaces the engine's entire math layer. The textures are gone, but the part I actually cared about, the elevation rendering, runs on the locked-down hardware.

Conway's Life as SIMD-within-a-register

The demo I'm fondest of is a Game of Life that runs maybe 50 to 100 times faster than the scalar version, using a technique worth knowing by name: SWAR, SIMD within a register. Treat each 16-bit word as 16 one-bit cells and operate on all 16 lanes at once.

Shift the three rows around the current row left and right to align all eight neighbor directions, then sum the eight shifted words with a tree of half-adders. The carry-save addition produces a population count for all 16 cells simultaneously, spread across four bit planes. The payoff is that Conway's rule never needs the full count. A cell lives on exactly 3 neighbors, or on 2 if already alive, and 2 (0010) and 3 (0011) differ only in the low bit, so the rule reduces to one boolean expression over the count bits:

alive = ~bit3 & ~bit2 & bit1 & (bit0 | old);

Cell age is carried in two more bit planes and drives the four-level grayscale, so new cells are light and long survivors fade to black. The general idea, packing many independent lanes into one ALU word and letting the carry chain do the parallel arithmetic, is the same trick behind fast popcounts and bitboard move generation.

The host side is the hard part now

The target code is the easy half. It's C and a little 68000 assembly, cross-compiled with GCC4TI inside Docker so I never had to build a decades-old toolchain on my actual machine, run through exePack, and packed into a .89g group with the archive bit set because the binaries don't fit in RAM and have to live in Flash.

Getting bits onto real hardware was the part that actually took time, because the standard transfer libraries don't build on an Apple Silicon Mac. I wrote two senders straight against libusb: one speaking the older DBUS protocol for the original TI-89 over a SilverLink cable, one speaking the direct USB protocol the Titanium uses. If you do retro work today, expect the modern host-side plumbing to cost you more than the vintage target ever will.

What surprised me is how little you give up. Elevation, occluding sprites, and procedural levels all fit inside the cost envelope of a 1992-era raycaster. Source, prebuilt binaries, and demo videos are on GitHub.