Throughput takes a unique approach to modern city simulation: unlike an agent-based simulation game (standalone cars with a physical location at any given moment), it abstracts to network flow—its closest comparison is to a transport planner’s traffic assignment model.
This allows for extremely fast response to change: a car never has to finish what it’s doing before the city can react. In an agent-based sim, congestion is physical and climbs steeply with load, so a backed-up road has to actually drain before the city recovers. Here, when the routes change, the congestion changes with them. Paths that are typically only optimized once—gated by departure—can be optimized to convergence.
The city can be reoptimized every 4 bars of music—bringing it back to the music brings it back to human scale. Where other games will slow the clock as pathfinding requests pile up, Throughput optimizes to never degrade simulation timing.
Previous upgrades had simulation reroutes finishing in just 30ms, from edit to pixels. That's faster than most websites process your click to the next frame (Google's “good” Interaction to Next Paint benchmark is 200 ms). This meant we could compute and repaint on the boundary of every 4-bar window imperceptibly.
The core Throughput philosophy, however, is to take the infrastructure you’ve built and run it to the red. Just how far can we push it?
Adding subways, internet, and bus and delivery routing pushed up the size of the city not just in terms of breadth, but depth. The milliseconds per each pass were starting to push into visible lag territory again.
Algorithmically, finding a match for a given supply-demand pair is relatively quick. Making sure every match is “optimal” takes longer—and a few more iterations. The next step for performance, then, was to divide the simulation into an immediate “boundary pass” match step, where new edits are consumed quickly, and a longer optimize pass that reexplores existing links in the remaining time.
The quick match is ultimately what makes the simulation feel responsive, so new edits within the 4-bar loop are picked up for the end-of-loop boundary pass.
Instead of kicking off the boundary pass at the actual boundary, we keep track of how long each boundary computation takes. If a boundary computation takes 300ms, the next boundary computation will kick off 360ms prior to the end of the 4th bar—300ms plus 20% leeway.
This is on a damping curve: a sudden spike in computation will snap the next predicted boundary to the spike—but if the next few boundary passes come in significantly faster, it’ll take the predicted value some time to resettle to a lower value.
In Degenerate mode, that is—in Euphoric mode, our city is always growing. Degenerate and Euphoric describe economic states: Euphoric is a frenzied, overshot market bubble, Degenerate describes the inevitable market correction. The boundary pass is surely only going to take longer until we’re back in Degeneration, so our prediction compensates.
A longer optimize step is allowed to take up all the remaining time in the next 4-bar phase. Several optimization passes are typically needed to reach a relatively stable convergence state.
This method is particularly cool, as it allows the simulation to calibrate to whatever machine it’s running on. A typical optimization pass takes significantly less time than is allowed by the optimization window, but we’ll complete as much optimization as we can during that time period.
Benchmarked on my M2 Macbook Air (available on Windows, Mac, and Linux!), it can complete approximately 4 optimization sweeps per 4-bar period after a big disturbance, 5-7 when the city is more settled.
It’s a bit of an approximation to throttle it to other machines, but there isn’t one that can run Godot 4’s engine that won’t complete at least some optimization. An i3 can do quite well.
As long as the lead boundary pass can hit, the simulation stays responsive. As long as some optimization window is left, it’ll eventually converge. Now, graphical performance is a different story, but I’ll leave that one for another day.