Fly-In

Rush hour on a one-lane mountain road, except the cars are drones and the road is a graph. Someone has to decide who moves, when.

The interesting work here isn't A*. It's the orchestration: turning what looks like a pathfinding problem into a scheduling problem - coordinating who moves on which turn so nobody collides and nobody idles longer than they must.

The Problem

Picture rush hour on a one-lane mountain road. There are single-car bridges, a few tunnels that take twice as long to cross, and a hard cap on how many cars fit in each village along the way. Send everyone at once and you get gridlock. Send them one at a time and you waste the whole day. Someone has to decide who moves, when.

Fly-In is that traffic controller for drones. Given a graph where hubs have strict occupancy caps, edges have throughput caps, and some zones are "restricted" (two turns to cross), it moves N drones from a single start hub to a single end hub. Every hub and every edge is a contended resource. The real problem isn't pathfinding - it's scheduling.

How It Works

You write a map in a small key: value [metadata] language, run the CLI, and get a turn-by-turn movement log. Add --render for a 3D replay.

  map.txt          Parser            Simulator           stdout
┌──────────┐    ┌───────────┐    ┌──────────────┐    ┌────────────┐
│ nb_drones│───▶│ validate  │───▶│ space-time A*│───▶│ D1-h2 ...  │
│ hubs     │    │ + connect │    │ per drone    │    │ D2-h1 ...  │
│ edges    │    │ check     │    │ → Solution   │    └─────┬──────┘
└──────────┘    └───────────┘    └──────────────┘          │
                                          │           ┌─────▼──────┐
                                          └──────────▶│ Ursina 3D  │
                                                      │ (--render) │
                                                      └────────────┘

Architecture

The system is designed on paper before code: three hard boundaries - parsing, the planning engine, and presentation - each owning one job and handing off a single validated object.

The Hard Parts

You can't drop 25 drones into a graph and hope. Three problems had to be solved on purpose.

Planning One Drone at a Time

The honest approach is to plan all drones together - but the search space is the product of every drone's options, and it detonates past a handful of agents. The fix borrows from cooperative pathfinding: plan D1 alone, stamp its route into a shared reservation table (this node is taken at turn 7, this edge at turn 8), then plan D2 so it must respect those stamps, and so on.

The elegant side effect is emergent pipelining. When D2 wants the same optimal corridor as D1, the reservations force it to shift its moves back by exactly one turn - a perfect convoy forms with no scheduler ever written for it. The trade-off is real and I name it plainly: prioritized planning is greedy, not globally optimal.

When a Move Takes Two Turns

A normal graph search treats every hop as one step. Restricted zones break that - they cost two turns, and the search runs over space-time, where reservations are indexed by the turn. A restricted move isn't (u,t) → (v,t+1); it's a dilated transition that holds the edge mid-flight and only lands a turn later:

 normal:      (u,t) ──────────────▶ (v, t+1)      reserve edge@t+1, node@t+1
 
 restricted:  (u,t) ──▶ [on edge] ──▶ (v, t+2)
                 │         │            │
              reserve   reserve      arrive
              edge@t+1  (in transit) node@t+2

The renderer had to mirror this exactly, or the visual would lie about where a drone is. That meant a small state machine in the drone controller - move_to_midpoint → at_midpoint → continue_from_midpoint - so a drone physically pauses halfway across a restricted link for a turn before completing.

A Compass That Counts Turns, Not Distance

A* is only as good as its heuristic, and straight-line distance is the wrong compass here: cost isn't geometric when one tile costs double. So before any drone moves, a backwards Dijkstra from the goal precomputes the true minimum turn cost from every hub. That keeps the heuristic admissible - never overestimating - so A* stays both correct and fast. Priority zones ride along as a tie-breaker baked into the queue key (f, t, -priority_count, u): among equal-arrival routes, the planner steers through more priority hubs without ever sacrificing speed.

Does It Actually Work?

Measured on the Challenger map ("The Impossible Dream"):

The full ladder - 10 maps from easy to challenger - solves in 4, 5, 6 / 8, 11, 7 / 14, 18, 26 / 43 turns respectively. Every map is solved deterministically: same inputs, same schedule, every run.

What I'd Do Differently

• Cache one search, reuse it. Identical drones re-run A* from scratch each time; the reservation-aware search could be incremental.
• Add a fallback to the greedy order. When prioritized planning paints a drone into a corner, a windowed re-plan or priority reshuffle would recover optimality the current single pass can't.
• Decouple render timing from solve. The 3D layer reconstructs transit state by replaying turns; emitting richer per-turn events from the engine would simplify it.