Now for the idea I was proudest of, which is of course the one that died.
A* is only as good as its optimistic guess, and straight-line distance is a weak guess in a galaxy with holes in it — it happily assumes you can fly through a 5,000 ly void that contains nothing to jump to. The literature’s classic upgrade is ALT (A*, Landmarks, Triangle inequality): pick a handful of landmark points, precompute the true travel distance from every cell of the grid to each landmark, and use the triangle inequality to turn those tables into a much smarter lower bound. The intuition: if I know the true cost from you to the lighthouse, and from the goal to the lighthouse, the difference between the two is a floor on the cost from you to the goal — and that floor knows about the holes, because the precomputed distances had to route around them.
We built it exactly to spec. Sixteen landmarks, placed by farthest-point sampling — each new landmark is the point farthest from all the ones already chosen, so they spread to the galaxy’s corners. We added a safety slack so the bound stayed honest at cell resolution, and we tested the never-overestimate promise against every pair of points in the fixture. On the synthetic galaxy’s void it worked beautifully — the bound rose over the hole, the search felt the wall and steered. On the real galaxy it… never bound. Not once. At every probe, the bound sat about a thousand light-years under the plain straight-line guess — our safety slack was bigger than the signal it protected, eating exactly the local detours ALT exists to detect.
Built to spec, correct by construction, and useless by measurement. A cousin idea — a heuristic that precomputed a rough cost field over the coarse cells — did worse: slower and wrong, 49 seconds against 42, with a worse route to show for it. Both went in the ledger with their numbers. The autopsy mattered more than the corpse: the stalls we aimed ALT at weren’t a guidance problem at all. The longest jump the search can make reaches about 1,200 ly, and some gaps in this galaxy are 11,000. No admissible heuristic can route what the graph cannot cross. Keep the receipt. This corpse gets exhumed in Part II, and the exhumation is my favorite part of the whole story.
If no heuristic can route what the graph cannot cross, then the answer is to build the missing roads. We derived a cell graph from the highway index — the galaxy diced into 250-light-year cells, 475,000 of them occupied, joined by roughly 18 million edges — and, crucially, we added gap edges: where the graph falls apart into disconnected islands, we connect the islands at their closest shores, priced honestly at plain-jump rates, with no boosts pretended. The void is now in the map, labeled with what it actually costs to swim it.
The first thing we did with this graph was plan on it directly — find a cell-level path first, then hand it to refine as a skeleton. We measured it, and the measurement said: worse everywhere. Every plot came out between 0.2 and 11 seconds slower, with worse routes at the end of it (301 jumps on the hardest cell of the benchmarks, against the portfolio’s 214). This was the third rehearsal of the refine lesson: waypoints at cell granularity mandate a corridor, refine polishes whatever corridor it’s mandated, and no amount of polish fixes wrong. We demoted the idea to a fallback that runs only when everything else returns nothing — the one situation where a rough route beats an apology.
Then we ran the first full benchmark matrix — the pinned benchmark routes crossed with both ships, both directions, and every toggle — and the matrix handed us the strangest gift of the campaign: direction asymmetry. Beagle Point → Wongi found a route thirty jumps shorter than Wongi → Beagle Point did, in one one-hundredth of the planning time. Same two endpoints, same physics — and the route home was radically better than the route out.
The reason is geography. Flying inward, toward the dense core, every expansion of the search shops from a rich shelf of candidate stars — the search converges like water finding a drain. Flying outward, into the thinning rim, the search starves, grinds, and settles for what it can get. Watch it happen:
This asymmetry becomes a load-bearing clue twice in what follows, so file it next to the heap’s alibi.
Asymmetry suggests a delicious hack: when the hard direction grinds, plan the easy direction and flip the route. For the record — and I get to say this because the ledger backs me up — I called the outcome before a line of it was written: this won’t work, because the supercharge belongs to the star you depart. Flip a route and every boost changes ends; the physics doesn’t survive being read backwards. But I greenlit the experiment anyway, and I did it on an explicit hypothesis: even if flipping died — when flipping died — whatever the benchmarks taught us about planning from the destination would matter for something better. Hold that thought through two funerals.
The called shot, now with a number on it: between 5 and 8 percent of the flipped hops are simply illegal. The supercharge belongs to the star you depart — flip the route and the boost changes ends. A 340-light-year hop that was funded by a neutron jet at one end becomes, reversed, a 340-light-year hop funded by hope.
So flip only the chain — the stars themselves don’t care which way you fly through them — and re-run refine on every leg in the true direction. This one was feasible. It also cost 16 percent more jumps, every single time: at each point where the reversal loses a boost, the mandated next waypoint forces filler hops to reach it. We tried sparser waypoints and made it catastrophically worse — two to four times the jumps — because on a highway route the hop chain is the skeleton. That was the refine lesson’s fourth rehearsal. But this corpse pointed somewhere: if planning backward from the destination finds better chains, and flipping them is what ruins them… what if we never flip? That question is where my greenlight had been aimed the whole time.
This one was mine, and it arrived in the form most of my good ideas arrived in on this project: an offhand sentence at one in the morning. “Could be a Google-Maps-type search where they search from origin and destination and see where they get close…”
Bidirectional search is a classic for a reason. Run two frontiers — one expanding from the start, one from the goal — and stop when they meet. The geometry argument is the pretty one: a search frontier is roughly a sphere, a sphere’s volume grows as the cube of its radius, and two half-radius spheres hold a quarter of the volume of one full one. But the real prize here was never the volume. Each frontier flows downhill into its own dense end — remember the asymmetry — and both half-chains are built right-way-round from birth. Nothing is ever flipped, so nothing ever breaks. Even the textbook’s standard warning dissolves here. Searching backward is supposed to be fiddly when edges cost different amounts in different directions — and ours do, because the boost belongs to the departure star — but the backward frontier just asks “could this candidate boost me the other way?”, and the code that scans a star’s neighbours already knows how to answer.
Then we measured. Wongi → Blaa Hypai went from 22.4 seconds to 556 milliseconds — and found a better route, 38 jumps against 45. Wongi → Colonia found 57 jumps under a ceiling that had stood since the campaign began. The synthetic galaxy reproduced it independently: a shorter route at exactly half the expansions, which is to say half the search effort. Meeting in the middle doesn’t just dodge the grind; it finds chains that a one-directional search, dragging its optimistic heuristic uphill, walks straight past.
Two finishing moves for the voids, and they entangle beautifully. First, the desert widen: when a frontier’s scan comes up empty, it now doubles its scan radius until the far shore appears, priced as ordinary jumps — the gap edges’ idea, transplanted from the map into the search itself. Colonia → Spase, the route that used to think until its budget died, completed for the first time.
Second — and this is the part I want a jury to hear — I looked at the gap edges and said: re-bench ALT. This is why we bench.
Follow the reasoning, because it’s the best piece of thinking in this post and, for once, it’s mine. ALT died because “the stalls are reachability, not guidance” — no heuristic can route what the graph cannot cross. But the gap edges made the voids crossable. The premise of the null result had quietly dissolved. Worse: with voids crossable, the straight-line guess becomes actively misleading — it prices a void crossing as a pleasant flight — while landmark distances, rebuilt over the gap-edge graph, know exactly what the crossing costs. The idea we buried with full honors in act 6 wasn’t wrong. It was early.
We retried it on the new map, and it works. On the synthetic void corridor it produced the same routes at roughly twice the speed on both ships — and wall-clock time dropped by more than search effort did, because the dead-ends ALT prunes are disproportionately the expensive kind, the ones that trigger the widen. The resurrection held up in production, eventually, after surviving a sequence of events I can only describe as a true-crime podcast about a benchmark:
Audit one. On routes with no desert in them, ALT was charging 25% more wall-clock time while doing precisely the same amount of searching — the expansion counts came back identical in every configuration. A bound that inflates every estimate uniformly reorders nothing; you are paying to consult an oracle whose answer cannot change the outcome. So we shipped a once-per-plot precheck that samples the bound along the straight line and keeps ALT only where the inflation is non-uniform — where there’s an actual wall in the way. In the same sweep, an earlier celebration — “ALT completes the hardest cell of the pinned benchmark matrix!” — was retracted as timing noise between variants. Rigor was prevailing everywhere, apparently.
Audit two, of audit one. The other machine, cross-checking, caught the precheck discarding the synthetic desert’s measured 2× win. The line-sampler had been skipping any sample point that fell in an empty cell of the grid — no stars there, no data, move along. But an empty cell is the desert; its emptiness is the entire testimony. Skip the empty points, and every point you actually measure sits in a populated cell — the desert’s edges, its shores — and populated cells look perfectly normal. The survey could cross five thousand light-years of nothing and report that everything it agreed to measure was fine.
A desert can’t testify if you only interview its shores.
Audit three, in which the retraction is retracted. Fixing the sampler forced a re-measurement, and the re-measurement exposed the “noise” verdict for what it was: the head-to-head comparison behind it had matched ALT-off against ALT-off, because the buggy precheck had silently disabled the very thing being measured, on both sides of the experiment. With the oracle genuinely consulted, the hardest cell came in at 20.6 to 21.0 seconds and 265 jumps, four runs out of four, against 37.8 to 47.5 seconds and roughly 300 jumps without. The retraction was the artifact. The win was real all along.
The final shape: ALT is free where it can’t help, roughly doubles the speed where a desert dominates the line, and ships on by default. And the epitaph from act 6 gets its correction: the ledger’s negatives aren’t tombstones, they’re bookmarks. Its trophies get audited. Sometimes an audit gives one back.