Before Flow Fields Had a Name: How Pizza Tycoon Simulated City Traffic on 25 MHz
Source: hackernews
The pizzalegacy.nl breakdown of Pizza Tycoon’s traffic system is worth reading as a case study in what real-time simulation looks like when you have no slack. The game shipped in 1994 for DOS, targeting 486 hardware running at 25 MHz. That machine delivered somewhere between 20 and 40 million integer operations per second, had an 8 KB L1 cache, and in its common SX variant had no integrated floating-point unit. Games ran essentially on bare metal, sharing that CPU budget between rendering, sound, input, game logic, and traffic simulation. Traffic got whatever was left.
The Problem
Pizza Tycoon simulated a city grid where customers traveled by car from homes to restaurants. The visual expectation was a living street network with vehicles moving continuously and plausibly. The simulation expectation was that customers would actually find routes, respond to traffic conditions, and arrive at the right destinations. These two requirements pull in opposite directions when the CPU is slow.
The naive approach, per-vehicle pathfinding every tick using something like Dijkstra’s algorithm, would have been unworkable. Dijkstra on a city-sized grid, run for every vehicle on every game tick, easily saturates a 25 MHz CPU before you have done anything else. A* was known in the literature (Hart, Nilsson, and Raphael published it in 1968) but remained expensive for real-time use in the early 1990s. Even finding one path on a 64x64 tile grid, with multiple vehicles running simultaneously, adds up fast when your total budget is tens of millions of operations per second and rendering already consumes a large portion of that.
The Cellular Automaton Shortcut
The insight that made city simulation tractable on this hardware, used in one form or another by most games of the era, was to invert the question. Instead of asking “where does this vehicle need to go?”, you ask “what is the traffic pressure on each tile?” and let vehicles follow the gradient.
This is a cellular automaton approach to traffic. Each road tile carries a density or pressure value. On each simulation step, these values propagate to adjacent tiles according to simple rules: high-density tiles push pressure toward lower-density neighbors, destinations act as sinks, and sources (residential zones, in a city sim) act as emitters. Individual vehicles then sample the pressure field at their current tile and move toward the adjacent tile with the most favorable value.
The entire update is O(tiles), not O(vehicles * path_length). For a fixed grid size, the cost is constant regardless of how many vehicles are on the road. The propagation step is a simple neighbor comparison over a 2D array, which is cache-friendly if the grid fits in L1 or L2 cache. On a 486 with 8 KB of L1, a 64x64 grid of byte-sized density values takes exactly 4 KB, fitting cleanly.
SimCity (1989) used a variant of this idea, propagating traffic density outward from zones along road connections to determine land value and zone development. The animated cars on SimCity’s streets were decorative; the actual traffic simulation was the density field, not the individual vehicles. Pizza Tycoon’s city sim needed tighter coupling between vehicles and specific destinations, but the core propagation trick is the same.
Fixed-Point Arithmetic and Lookup Tables
With no floating-point unit on many 486 SX machines, fractional position and velocity had to be represented in fixed-point. The standard approach was 16.16 fixed-point: a 32-bit integer where the upper 16 bits are the integer part and the lower 16 are the fractional part. Addition and subtraction work identically to integer arithmetic. Multiplication requires a 32x32 multiply followed by a 16-bit right shift, which a 486 could execute in around 13 to 42 clock cycles depending on operand size. Division was avoided wherever possible, replaced by multiplication by a precomputed reciprocal or by constraining denominators to powers of two so they reduced to bit shifts.
Trigonometric functions (for computing headings, distances, direction choices) were handled with lookup tables. A table of 256 entries for sine and cosine covers the full circle with byte-indexed lookup, no computation required. Distance approximations, often good enough for determining which adjacent tile is nearest to a destination, used absolute-value sums (the taxicab metric) or precomputed small-radius sqrt tables. These tables were small enough to live in L1 cache, making repeated lookups essentially free.
One subtlety worth noting: these lookup tables had to be aligned carefully in memory. A table that straddles a cache line boundary incurs extra cache misses on every other access. DOS programmers of this era often hand-arranged their data segments to ensure hot tables started on 16-byte or 32-byte boundaries.
Temporal Amortization
Not every vehicle needs to make a routing decision every game tick. A common optimization was to spread simulation work across multiple ticks by cycling through subsets of the vehicle list. With 40 vehicles updating 10 per tick at 20 ticks per second, each vehicle gets a routing decision twice per second. At driving speeds on a tile-based grid, this is more than sufficient; a vehicle typically occupies a tile for multiple ticks regardless.
The pressure field itself could be updated on a slower cadence than the game loop. Since the field represents a time-averaged traffic state, updating it every 4 to 8 ticks introduces no visible artifacts. Combined with the cellular automaton’s inherent amortization (spreading the wave front update across the entire grid over many steps), you could maintain a plausible simulation state with very few operations per tick.
This pattern of deliberate under-simulation is harder to justify on modern hardware because it requires accepting a specific fidelity trade-off and defending it. In 1994 the hardware made the decision for you.
Contemporaries and Comparisons
Transport Tycoon, released the same year as Pizza Tycoon, took a different approach. Chris Sawyer wrote most of it in x86 assembly and routed individual trains and road vehicles along pre-baked track and road segments, using a reservation system to avoid collisions. That worked because the road network topology was sparse and constrained: vehicles followed fixed paths between waypoints rather than navigating an open grid. Generalizing this to an open city grid would have required prohibitive memory for precomputed paths between all pairs of tiles.
The Settlers (1993) by Blue Byte simulated hundreds of individual settlers moving along a road network with simple state machines: each settler had a home, a workplace, and a path between them computed at spawn time and cached for reuse. Traffic contention was handled by backing off and retrying rather than dynamic rerouting. This worked well for that game’s particular simulation model, but required a relatively stable network topology.
Caesar III (1998) used a walker system where inhabitants spawned from buildings and followed road tiles forward, never choosing routes, simply walking until they either completed their service loop or fell off a dead end. The appearance of purposeful movement emerged from building placement rather than pathfinding. It was even cheaper than a pressure field, and for that game’s mechanics it was exactly the right trade-off.
The Rediscovery
Flow fields as a named technique entered the broader game AI literature much later. Elijah Emerson’s 2013 GDC presentation on flow field pathfinding for Supreme Commander formalized what 1990s city sim programmers had been doing by necessity: precompute a vector field pointing toward a destination, then have agents follow the field rather than compute individual paths. The difference is that modern flow fields are computed with a backwards Dijkstra from the destination, giving exact shortest-path directions across the field. The cellular automaton pressure propagation of the 1990s games computed approximately the same information through iterative diffusion, at lower accuracy but also lower cost.
For large groups of agents sharing a destination (which is most of what city sims do), the flow field approach scales better than per-agent pathfinding by roughly an order of magnitude. A single field update covers all agents headed to the same destination. Pizza Tycoon’s customers, all heading to one of a small set of restaurants, fit this model naturally.
What the Constraint Produced
The 25 MHz limit forced a choice between simulation fidelity and tractability, and the engineers chose a model that was cheap to update, cache-friendly, and visually convincing even where it was not strictly accurate. Pizza Tycoon’s city looks alive because the pressure field creates emergent congestion patterns: vehicles slow around busy intersections, traffic distributes across alternate routes, and the overall density fluctuates with the game’s time-of-day cycle. None of that required a route-planning algorithm. It required a well-chosen approximation and the discipline to stop there.
That discipline is harder to maintain now. Hardware is fast enough that the expensive naive approach usually works, so the elegant cheap approach rarely gets built. Revisiting how these games actually worked is a useful reminder that interesting engineering often lives in the gap between what you want to compute and what you can afford to compute, and that gap is still worth thinking about even when the numbers have changed.