What do you call a 141x Algorithmic Improvement?
There’s an ancient computing proverb that goes something like this: “If you improve something 1.2x, you probably just did something smart. If you improve something 10x, you probably just stopped doing something stupid.” One might wonder how this extrapolates to a 141x improvement. In this case, it’s something like “you probably planned to be stupid.”
Throughput is a city builder game: simulated people have homes, they go to work, they buy things. I wanted to make the simulation as dynamic as possible—if someone found a job with a shorter commute, I want them to take it!
This means it’s a gigantic pathfinding network flow problem—and it was beginning to have some problems. On “large” games, I was already starting to see visible simulation slowdown.
The visibility and interaction slowdown I mitigated via threading and by holding copies of the simulation while the thread completes. Still, Throughput is a game in time with music, and I intend for simulation refreshes to be snappy—it’s an intuitive feel problem if it isn’t. And I knew I wanted my games to get 10x larger.
The work I did threading the simulation built a solid foundation of feature-specific tests via automating Test Driven Development. Crucially, I also created save games that I then use as benchmarked test fixtures. These guardrails are the “plan to be stupid” I made right before I blindly tell Claude to optimize against the benchmark.
The core of our simulation uses Dijkstra’s pathfinding algorithm. Most of our calls are multi-target, so we don’t go for A*. Ironically, this is where the first 36x optimization came from: removing early-termination that would make sense for the single-target case.
Dijkstra from a single source is already naturally a multi-target algorithm. If you let it run, the first time it pops node X is the moment it knows the cost-min distance from source to X. That's true for every node, simultaneously, from one expansion.
The rest of it? Depth pruning: We don’t need to expand paths that are already worse than the current one.
But the actual how is just the artifact of how I found it. Everything is ultimately a search problem: if there’s something you want to achieve, there exists a path to get you there. Search is the act of finding it—so execution of your strategy rests on your search tactics.
In this case we employ a particular tactic for working with black box systems: you look at your inputs and outputs. I knew my inputs (test fixture), and I had the expected outputs (unit tests, benchmarking).
It’s often repeated that you should “be specific” when talking to computers, but it’s important to examine what that actually means. A figure takes shape only via its negative space—being specific is as much about what you don’t require as much as it is about what you do. That flexibility is what makes room for what you care about.
It’s fine that the first implementation wasn’t optimal—it did what it needed to until it didn’t. That’s what iteration is for. In fact, at its core O(VlogV) Dijkstra still shows pretty uncontained growth; now that the truly naïve implementations are fixed, we’re going to have more specific tradeoffs to make.