or: shit that did and didn’t work
Elite Dangerous simulates the Milky Way. Not a level that looks like the Milky Way — the actual thing, procedurally generated from real astrophysical models: about 400 billion star systems, of which players have personally visited and catalogued some 200 million. I want to be precise about the technical terminology here, so let me state clearly that 400 billion is too many stars. It is the kind of number that mathematicians invented so that other mathematicians would stop asking them for examples.
I love this game with the specific, incurable love of a person who was enamored with space as a child and then became an engineer, which is to say a person who looked at the night sky and thought “I bet that has an index.” Elite was clearly built with love and care, and around it grew a community that produces genuinely heroic volumes of open data — Spansh’s routers and galaxy dumps, Inara’s living encyclopedia, EDSM’s map of what players have actually scanned, the EDDN firehose every tool drinks from — and the community’s cartographers, the EDAstro mapmakers and the surveyors who chart the galaxy’s strange corners for the love of it, whose archaeology this post will owe a very specific debt to before it’s over. We build EDDA, a desktop assistant for the game, and one of EDDA’s jobs is the subject of this post: plotting routes across tens of thousands of light-years, on your desktop, fast enough that asking feels like asking and not like filing a request with a municipal government.
Now, the wrinkle that makes this problem interesting instead of merely large. You do not cross this galaxy by jumping politely from star to star like a reasonable person. You cross it on the neutron highway. A neutron star is the collapsed corpse of a giant sun: a city-sized object spinning hundreds of times a second, screaming twin jets of radiation out of its poles. The game lets you fly your ship into the scream. Doing this “supercharges” your frame shift drive — the engine that jumps you between stars — for one jump: four to six times your normal range, in exchange for the feeling that you are doing something your insurance adjuster should not find out about. Chain enough neutron stars together and a 65,000-light-year crossing becomes an afternoon instead of a career.
But here’s the catch, and it is a beautiful catch, because it is the catch that generates this entire post: your fuel tank is small, most stars cannot refuel you, and a neutron star is one of the ones that can’t. Understand the cruelty of this. The neutron star is the premier roadside attraction for galactic wayfarers. Range boosts to speed up the trip, named keychains (except yours)2 are available for purchase, yet their fuel services went out of operation a long time ago.1 You refuel by skimming the corona of certain main-sequence stars with a fuel scoop, and only about one in ten highway stars keeps such a star close enough to matter. So the routing problem is: string together supercharge jumps across a galaxy-sized graph, staying near the invisible skeleton of usable neutron stars, while never, not once, letting the tank hit empty. Starside assistance is available, but that's embarrassing.
1. Named keychains are theorized fundamental properties of neutron stars. Our scanners are not yet advanced enough to detect them.
2. Neutron stars hate YOU. Just you.
When this story starts, EDDA’s plotter took 7.5 seconds to plot the run from Wongi to Colonia (about 22,000 light-years) in thorough mode, its most patient setting,0 and there existed exactly one route in the whole catalogue — Colonia to a miserable little system called Spase AA-A a108-0 — that it could not complete at all. It would think about Spase until its time budget died of old age, and then apologize.
When the story ends — and I want this number on the record precisely because it sounds made up — three days later: Colonia plots in about a second while digging for better routes than before, the 38,000-light-year run up the arm takes 241 milliseconds, and the unplottable route is not only plotted, it is plotted in one second flat with a route three times shorter than the one we started celebrating. Same hardware. Same 5.8 GB index. Same fuel physics.
And yes — EDDA is written in Rust, so “blazingly fast” appears in this title with full awareness of the meme.1 The difference is that this post comes with receipts, including the receipts for everything that didn’t work, because the graveyard is most of the reason you should trust the trophies.
0. Transcript archaeology later recovered benches from
four days before the story starts: the same plot at 26–65
seconds. The 7.5-second starting line was itself the survivor of days of
tuning nobody thought to archive at the time — which is why this project
now archives everything, and why the recovered pre-history lives in the
repo as docs/benches/retro/.
1. Rust is my daily driver. I am allowed to make this joke in the same way you are allowed to make fun of your own brother.
First, the data problem, briefly, because you cannot route what you cannot load. The community catalogue is about 116 GB of compressed JSON, which is not a thing you ship to players — that is a thing you inflict on data centers. We compact it into a memory-mapped index — a file the operating system lends to the program as if it were memory, pulling in pieces from disk only as they’re touched: 29 bytes per star system (position, star class, one precious bit meaning “there’s a scoopable star parked next to this one,” a name pointer), about 5.8 GB for 199 million systems. The index is divided into 50-light-year grid cells, so the question “who’s within 70 ly of me?” touches a handful of memory pages instead of the whole file. Long-range planning runs on a sub-index of just the roughly 3.85 million highway stars — neutron stars and white dwarfs — in coarser 250 ly cells.
On top of that index sits a planner with three phases, and you need all three in your head for anything below to land:
Coarse: an A* search over the highway sub-index. If you’ve never met A*: it’s the standard algorithm for finding shortest paths when you have a hint. You explore outward from the start, always extending the path that looks most promising, where “promising” is cost-so-far plus an optimistic guess (a heuristic) of the cost remaining — typically the straight-line distance, since no route is ever shorter than the crow flies. The guess steers the search toward the goal instead of flooding outward evenly in all directions like spilled coffee. Three words from A*’s vocabulary recur below, so let’s pay for them once. Each step — take the most promising candidate, look up its neighbours, extend the path to them — is an expansion; expansion counts are how we’ll measure how hard a search worked. The growing boundary of everywhere the search has reached is its frontier. And the optimistic guess must never overestimate — admissible, in the jargon — because a guess that overestimates can talk the search out of the best route entirely. Our coarse search also drags the fuel tank along in its state — rounded into a handful of coarse buckets rather than tracked exactly, because “position × every possible fuel level” is how state spaces explode — and emits not a route but a skeleton: a few dozen waypoints saying which neutron stars to string together.
Refine: every leg between waypoints gets re-planned exactly, in parallel, by a fuel-aware planner that picks the actual stars you’ll jump through, inserts scoop stops where the tank needs them, and runs settling rounds that re-plan any leg whose fuel estimate was off. Refine is not ceremony — refine is the route. A 58-jump Colonia route comes out of a roughly 20-waypoint skeleton; every jump you actually fly, refine picked. Hold onto this fact, because three separate ideas below will die of it: refine polishes the skeleton it is handed. It cannot fix a wrong one.
The portfolio: we don’t run one search. We run a portfolio of variants — different heuristics, different candidate filters, searching forward from the start and, later in this story, from both ends at once — racing in parallel under a time budget, and the best finished route wins. Ideas that are brilliant on one route and catastrophic on another get to be brilliant where they’re brilliant and get quietly outvoted where they’re not. Remember the portfolio too: it is the reason we could afford to be wrong as often as this post admits.
One rule governed the whole campaign, and I’ll state it here so the body count below makes sense: nothing ships on vibes. Every change is benchmarked; a fixed matrix of pinned routes — the same benchmark plots every time, both ships, both directions, every toggle — is the law; a change that makes any pinned route worse fails, no matter how clever it is; and every negative result gets written down permanently, with numbers, so no dead idea gets re-litigated in three months by someone who only remembers it sounding good. We kept an actual ledger. Most of this post is me reading it to you.
Everything in Part I is in chronological order, and the failures appear next to the wins that they caused, because most of the wins exist because a failure pointed at them. To keep score, hold one number in your head: the wall-clock time to plot Wongi → Colonia in thorough mode. It starts at 7.5 seconds. (Why Wongi and not Sol? Because Wongi happened to be where my ship was parked when I began this endeavor. Every benchmark suite is autobiography, if you read it closely enough.)
Remember the portfolio — the gaggle of search variants racing each other? Originally, thorough mode — the patient setting, where the planner gets its whole time budget to hunt for the best route rather than the first good one — waited for all of them to finish. Every plot was exactly as slow as its slowest, dumbest variant, the way a family road trip is exactly as slow as its member with the smallest bladder. The fix was social rather than algorithmic: once the first route lands, the stragglers get a one-second grace window to beat it, and then they are cancelled without counseling.
Write the lesson down, because it will bill us again later with interest: the fastest code is the code that stops waiting.
Before optimizing anything, we spent one afternoon building two instruments, and I will now make the single most transferable claim in this post: that afternoon was worth more than any algorithm below.
First, section timers inside the coarse search — how many microseconds go to scanning candidates, sorting them, relaxing them (textbook-speak for updating a neighbour’s best-known cost), popping the queue — measured once per expansion so the instrument can’t distort the loop it’s measuring. Second, a synthetic galaxy: eighty lines of Python that emit 2.5 million fake star systems — a realistic mix of star classes, a huge void wall in the middle, density thinning toward the rim — piped straight into the production importer. It generates in fifteen seconds, its topology is nasty on purpose, and it comes out identical, bit for bit, on any machine. When you cannot fit 199 million real stars on a laptop, you make a small evil universe you can.
Then we pointed the timers at the planner, and the first two optimizations we had been itching to write died before lunch.
Every algorithms textbook will tell you that A*’s priority queue and its stale pops — the dead entries you pull off the queue only to throw away — are where your time goes, and we believed it, because the textbook has a hardcover and we don’t. When we actually measured, the heap cost 1.1 milliseconds of a 190-millisecond plot, with 2% stale pops. The heap had an alibi. The bucket-queue rewrite we were excited about would have optimized 0.6% of the runtime, which in performance work is called “a hobby.”
70% of the coarse search’s time went to an expensive neighbour rescan that retries at three widening radii, so obviously: cache the candidates per node. The effect was zero. The rescans barely repeat per node — the cost was per-scan, not per-repeat. We were treating a cardiovascular problem with a filing system.
What the timers actually convicted: those rescans — the search’s widen move, where an expansion that finds nothing in reach doubles its radius and asks the neighbourhood again — spent their time probing mostly-empty grid cells, one by one, like a burglar checking every apartment in a building he has been told is vacant. The problem wasn’t compute. It was that our spatial index answered “what’s in this box?” by asking about every cell the box could contain rather than every cell that exists.
Here is a genuinely beautiful idea from 1966 that deserves a proper introduction. Suppose you chop space into grid cells and you want cells that are near each other in space to be near each other in your file, so that reading a neighbourhood is a few long sequential reads instead of a thousand seeks. You cannot do this perfectly — space has three dimensions and a file has one, the universe does not owe you a favor, and the only known technology for cleanly collapsing higher dimensions into lower ones is from The Three-Body Problem, where it is fictional, extremely hostile, and frankly you’d need a singularity. Or something. But you can do it shockingly well with a trick called the Z-order curve, also called Morton order.
Take a cell’s coordinates, write them in binary, and
interleave the bits — one from x, one from y, one from z, like
shuffling three decks of cards into one. The resulting number is the
cell’s position in the file. Plotted, the curve traces an endless
recursive “Z” through space, and it has the property we paid for:
cells that share high bits — big regions of space — are contiguous runs of the
file. And there’s a bonus operation with the delightfully villainous
name BIGMIN: when the curve wanders out of the box you’re
querying, a little bit-arithmetic tells you the exact curve position
where it comes back in. Skip ahead. Touch nothing in between.
BIGMIN skipping every cell outside the box without looking at
it. Chop trailing digits off any cell’s Morton key and you get the key
of the bigger cube containing it — remember that for the next act.Now look at what that does to the shelf from the setup figure. Every
“who’s near me?” question the search asks is really a
box query: take the sphere you care about, round it out to the grid
cells it touches, fetch those cells. And there are exactly two ways to fetch
a box of cells off a shelf. You can probe: compute each
cell’s shelf address, one at a time, and ask “anything
here?” — hundreds of little lookups, most coming back empty-handed,
which is precisely the burglar-in-a-vacant-building routine the timers
convicted in act 1. Or, if the shelf is in Z-order, you can
walk: jump to the first shelf position inside the box and
just… read, in order, because the cells you want are sitting next to
each other — and each time the curve wanders out of the box,
BIGMIN hands you the next position back inside, so the gap is
skipped without being touched.
BIGMIN skipping everything between them. Same data, same
question; one is a sequential read, the other is a scavenger hunt.So we re-shelved the highway index along the Z-order curve and taught the box queries to walk. The long skinny boxes a route search asks for — corridors, thousands of cells at a time — got 2.3–7.7× faster (one Colonia→Beagle corridor scan dropped from 492 to 65 milliseconds). We were ready to call it a win, except—
The part nobody tells you about beautiful ideas from 1966: the crossover matters more than the curve. Walking wins on big boxes. On small boxes — a handful of cells — plain probing is cheaper than any cleverness. So the code picks a strategy per query, and everything hinges on the switch-point between the two: the crossover. Our first deployment set it at 2,048 cells — a nice round number, which is to say, a guess wearing a suit — and the widen rescans we convicted in act 1 were ~1,300-cell boxes, which put them below the threshold: still probing, still slow. The synthetic galaxy caught it, re-measurement moved the crossover to 216 cells, and the widen’s cost dropped by a quarter. The beautiful idea worked only after we stopped guessing where it applied. (And one honest kill from the same measurement: on huge boxes over the dense, full index — every cell packed — walking loses, 0.29×. No production path scans those, but it’s in the ledger, because the ledger is where claims like “walking is faster” go to get footnotes.)
That throwaway line about chopping digits off a Morton key deserves its own act, because it quietly hands us a second data structure for free. Remember how the shelf number was built: bits of x, y, and z, interleaved. That construction has a hidden symmetry — the trailing bits of the number are the fine detail of the position (they came from the low bits of the coordinates, the ones that distinguish a cell from its next-door neighbour), and the leading bits are the big geography. So run the construction backwards. Take a cell’s number and chop off its last three bits — one x bit, one y bit, one z bit. What’s left is a shorter number that no longer says which exact cell you meant… but every one of the eight cells in the same 2×2×2 block chops down to that same shorter number. Congratulations: the truncated number is the block’s name. Chop three more bits, and it names the 4×4×4 block. Keep going and the names get shorter as the cubes get bigger, all the way up to “the entire galaxy.”
Structures you get for free deserve furniture. We gave every block at
every level a four-byte index card: is there any scoopable star in
here? Any neutron? Any white dwarf? What’s the best boost available?
How many stars in total? The whole card catalog (agg250) builds
locally in seconds, and it turns a question like “is there any fuel
within 1,200 ly of me?” from a tour of hundreds of cells into a walk
down the pyramid. Ask the biggest relevant block; its card says
“yes, somewhere in here.” Ask its eight children; five cards say
“no,” and those five no’s just eliminated five-eighths of
the volume for the price of reading twenty bytes. Recurse into the yeses.
Only at the bottom, in the handful of small cubes still standing, do you
look at actual star records — which is why the answer is exact, not
an estimate. Measured, the pyramid answers in about two
microseconds, versus 19–140 microseconds walking the cells —
11–86× faster.
I would love to tell you we built it for a brilliant reason. We built it for a reason that died on contact with the benchmark: pre-checking rescans with “is this sphere even non-empty?” bought a flat nothing, because the sphere is almost never dark — a scan that pushes nothing still sees plenty. The oracle shipped anyway, on the theory that a four-byte-per-cell summary of an entire galaxy would find work. Spoiler: it becomes load-bearing twice in Part II, once in a way nobody predicted.
A fuel-planning interlude. This one was my instruction, verbatim from the ledger: “only stop for fuel when required” — because the eager default tops up at every scoopable star it passes, like a parent on a road trip. The obvious way to grant the wish is to make scoop-or-don’t-scoop a decision inside the search, at every star. The obvious way is also how one search becomes a separate search for every possible combination of stops — two choices per stop multiply, and thirty stops is a billion searches. And fuel is already the expensive part of the bookkeeping: the search tracks every state as a pair of (star, fuel bucket), and plots with fuel tracking switched off already run up to twice as fast on the stall-prone benchmark cells. The last thing that dimension needed was a choice dimension stapled to it.
So we did the opposite: plan normally, then run a rewrite pass over the winning route. Simulate the route with no scoops at all, and wherever the tank would breach the reserve floor — the fuel level you never plan below — re-insert a stop at the latest scoopable star already passed. It’s provably safe, because skipping a scoop only makes the ship lighter, a lighter ship jumps farther, and a plan that worked with extra fuel aboard can only get easier without it. And it’s free: same search effort, same wall-clock time, measured. The headline numbers: a big-tank Explorer went from 13 stops to 2, and a small-tank Mandalay went from 31 to 27, because on a 32-tonne tank most stops are load-bearing. Full provenance on that 13 → 2, because a sharp reader deserves it: we measured it on the synthetic galaxy’s 22,000-ly corridor, which is the same length as the run to Colonia and easy to conflate with it, and there the rewrite returned the identical 62-jump route with eleven fewer stops. The real Colonia corridor, on the current build, reads 58 jumps and 6 stops at defaults, or 58 and 4 with the toggle on (the postscript below gets it to 58 and 2 — patience). And because I refused to accept the synthetic attribution from memory, we went digging through the old transcripts and recovered the real-galaxy records too. In the wild pre-history of this project, real Colonia routes ran as fat as 91 jumps and 35 stops, and the deepest real stop-collapse on record is 35 → 3 in a single afternoon of tuning. And then, timestamped three days before the synthetic run, there it is — the route I actually remembered: the real corridor, 62 jumps, two scoop stops, “the model within a tonne the whole way,” says the arrival log. Not synthetic. Real sky, two stops. And here is the detail that took two machines an embarrassingly long time to notice: that was never a route the planner printed. The planner’s plan that day was 61 jumps and five scoop stops. The two-stop version is what I flew — skipping the top-ups the tank didn’t need, pruning the route by hand from the pilot’s seat. Hold that thought until the postscript, because the archaeology has a confession coming: the machines’ recovery script pulled that exact arrival line into its own evidence file, and the analysis that read the file — tuned for tidy structured benchmark rows — skated straight past the prose where the proof lived, and concluded my memory had collided two numbers. The proof sat at line 84 of the machines’ own file while they explained to me why it didn’t exist. Two things to file about the feature itself. First, the rewrite is opt-in, deliberately: it leaves the tank riding low, one escape jump above the floor, and a low tank is a risk preference, not a default, so the shipped default keeps the comfortable top-ups. Second, once act 13 teaches the planner to price stops in seconds, the default routes start carrying fewer stops on their own — that later judging pass prunes some stops at the moment routes are chosen. The toggle still removes more, at zero jump cost, and that “zero cost” is itself a live investigation: if the rewrite removes stops for free, should routes be judged as if those stops were already gone? The ledger has opinions, pending benchmarks. Search where you must; rewrite where you can.
And a postscript that arrived, I swear, while this post was in final edits — the closing beat of the whole provenance saga above: the remembered route exists — and the planner can find it now. During review I kept insisting the two-stop route was real, the analysis kept telling me my memory had collided two numbers — while the proof sat unread in its own evidence file — and then the machines taught the judge to score each candidate on its pruned truth — simulate the toggle’s thrift over every contender before ranking, so the judge scores the route the pilot will actually fly — and Wongi → Colonia at 58 jumps and 2 stops surfaced immediately.
It had been there the whole time, losing elections because its eager costume wears seven marked top-ups the lean pilot never takes. Four of the six stop-heavy benchmark cells flip winners under pruned-truth judging; the toggle got dramatically stronger on long hauls (the Beagle small-ship climb prunes 115 eager stops to 65). I was told, gently, for a couple of hours, that my memory had collided two numbers — by machines whose own evidence file held the arrival log of the flight. And the real ending is better than vindication: what item 25 taught the judge is what I had been doing in the cockpit on August 28th — flying the pruned route, skipping the ceremonial top-ups — five days before there was an instrument for it. The judge didn’t discover my route. It caught up to my hands.
And the postscript grew a postscript while the machines were fact-checking this act, because I had a standing hypothesis about why lean routes feel better than the stop counts imply: the more we stop, the more we have to stop — every top-up buys tonnes the ship then pays fuel to carry. The machines ran the full eager-versus-lean matrix, 54 cells both ways, priced in fitted pilot-seconds. Confirmed: 187 pilot-minutes saved across the matrix, 52 of 54 cells positive — and the poetry is in the tonnage column, because the feedback loop lives in the big tanks. The explorers save about four percent while scooping 30 to 114 fewer tonnes per route; on Wongi → Colonia the lean route flies the identical 58 jumps while scooping 108 fewer tonnes — a third of the eager route’s fuel existed solely to carry the rest of the fuel. The small-tank Mandalay inverts the intuition and saves least, because on 32 tonnes most stops are load-bearing — the exact sentence this act shipped with, re-vindicated by eighteen cells — except its Beagle ascent, which sheds fifty stop-overheads and gets twenty-four minutes back. Costs on the record, per the covenant: two Mandalay cells regress under the toggle, the suspect is that the toggle bundles three separate changes and one of them can hurt small tanks more than the others recover — and the overnight decomposition confirmed it, with a twist worth savoring: the scan-gate change turned out to author both the flagship 58/2 route and the small-tank regression. Same lever, hero and villain. So the toggle now races both scan modes as portfolio twins and keeps whichever wins the seconds judge: eight cells improved, forty-five identical, one knife-edge flicker documented in the ledger with both arming policies benched. Even the fix got the methodology treatment.
The timers, again. The winning Colonia route finishes around 630 milliseconds… and the plot then sits there for the rest of a fixed 1,000-millisecond grace window, holding the door open for variants that are not coming. So the grace window became proportional to how long the first route took to arrive, with a floor of 500 milliseconds — and the floor is not vibes, because we measured 350 milliseconds and it cost one of the pinned benchmark routes an extra fuel stop. Even the parts of this system that exist to interrupt the other parts get benchmarked.