Teaching monsters to walk

Hello, this week’s post exists because of one unit in one swarm fight. It had been handed an engagement spot on the far side of its target, the spot was unreachable behind two teammates and the target’s own body, and it spent the entire fight jogging a circle around that point at full speed, like a man circling a building that has no entrance. I watched it loop for a good 4 seconds of sim time before accepting that the bug was mine, which I believe is the standard grieving process.

Devlog #6 was about how a unit decides where it wants to be. This post is the half I skipped: how anything in Mutarch actually gets there. It turned out to be two unrelated problems wearing the same name, solved by two systems that share nothing except the idea that moving has a cost.

The overworld is the textbook problem

When a squad marches from your colony to a site, the route is a least-cost path from Dijkstra over a per-cell cost surface on the 448 by 288 region map from #2. The base costs live in buildMoveCost in src/game/world/map/regions.ts, and they are the entire personality of overland travel:

Crossing a river adds 3 per point of river width on top, so on the base surface a river is a wall. Expedition squads then get an overlay (travelCostSurface in travelPath.ts): water flips to truly impassable, because a 60-cost ocean cell is still an invitation to a sufficiently desperate pathfinder. Mountain country gets multiplied by 2.5, and both roads and river cells clamp to 0.25. That last rule is my favorite kind of cheap worldbuilding: a river is a highway along and a wall across, and marches hug the waterways without any code knowing what “scenic” means.

The toy map, but the real rules: the cost surface and the Dijkstra are the shipped code, constants verbatim. The route takes the hint.

The cost also drives the clock: the token spends 0.15 s per cost point (SECONDS_PER_TRAVEL_COST), which produced this system’s one genuine bug. A peaks cell under the squad multiplier costs 14 times 2.5, which is 35, which is 5.25 s of a token standing on one cell of snow. The report was not “mountains are slow”, it was “the march froze”. The fix is MAX_CELL_TIME_COST = 6: the clock cost of a cell is capped at 6 while the routing cost stays at 35, so paths still bend around the high passes but a squad that must cross reads as slow, not stuck. Two costs for one cell, because the router and the player need to be lied to differently.

One small thing: squads march single file, each follower trailing the leader by 2.3 path-points (MARCH_FILE_SPACING). It changes nothing mechanically. It just looks like a war band instead of a stack of tokens.

The arena did not need a pathfinder, until it did

Combat is the opposite problem in every dimension. The arena is 150 by 90 sim units, the sim ticks at 10 Hz, and nothing holds still. For most of development, units moved on pure local steering: seek toward the goal from #6’s decision layer, separation away from neighbors, decelerate on arrival. No search at all, and it was fine, because the arena was an empty field.

Then arenas got rocks, and steering revealed its one great weakness: it is a hill-climber. A unit walking at a stone slides along it if the angle is kind and presses into it forever if it is not. The fix is a real A*, in src/game/combat/nav/pathfind.ts, kept deliberately tiny. The nav grid cell is 6 sim units (NAV_CELL_SIZE, about 1.5 body radii, a unit body being radius 4), which makes the entire arena 25 by 15, or 375 cells. After devlog #2 bragged about 129,024 cells, this is the other end of my ambition. The search is 8-connected with an octile heuristic, blocked cells are rock footprints inflated by one body radius, and the result is string-pulled down to a handful of waypoints that steering then follows, so A* owns the topology and steering still owns every actual step.

The detail I care most about is in the heap. Ties in the open list break deterministically: lower f-score, then lower h-score, then lower cell index. Fights are recorded once and played back (#4), and every recording must replay identically from its seed (#3), so two equal-cost paths around a rock are not equal. One of them is canonical, on every machine, forever.

This scene is computed by the shipped pathfinder: 20 cells walked, 26 nodes expanded, 2 corners kept. Steering walks everything between the red dots.

Paths are sticky: a unit replans only when its path goes stale (at most every 6 ticks, staggered by a hash of the unit id so a big fight never replans everyone on the same tick) or when the goal drifts more than 9 units. Without stickiness, a sliver of line-of-sight opening past a rock edge flips the route choice every tick and the unit vibrates. Two more anti-jitter rules earned their place the hard way: an intermediate corner counts as reached within 3 collision radii, because exact arrival pressed units into the corner they were meant to round, and waypoints spread laterally up to 1.5 radii per unit so five units rounding the same rock stop aiming at the same cell center.

The pathfinder I turned off

Here is the failed approach, and you can still read it in the code. Once rocks routed cleanly, the obvious next thought arrived: bodies are obstacles too, so route around the crowd. I built it properly, in two layers. A soft congestion field stamps every fighter into the grid as a 3 by 3 splat (1 center, 0.35 edges, 0.15 corners), refreshed every 4 ticks; when density on the approach line exceeds 3, about three bodies clumped, A* adds 3.6 per density point and the unit swings around the scrum. A hard layer treats same-side bodies within 48 units of the goal as impassable, with dynamic detours capped at 1.6 times the direct distance.

It worked, in the sense that the code did what it said. It failed, in the sense that fights got worse. Units took long, polite detours around their own crowd instead of doing what melee actually does, which is squeeze and wait. And it did not improve the thing I built it for: surrounding a target was already solved by the encirclement ring handing out slots. The insight I should have had earlier is that search is for geometry that does not move. A rock is a maze; a crowd is a negotiation, and separation forces already speak that language. So NAV_DYNAMIC_BODY_ROUTING in navTunables.ts is false, with the full obituary written in the comment above it, and the machinery stays behind the flag in case denser arenas ever earn it back.

The same assignment, twice. The left panel is still in the codebase, behind a flag set to false.

Which returns us to the orbiting unit from the opening, because its fix turned out to be no pathfinder at all. The unit was circling because its assigned slot was genuinely unreachable, and no algorithm finds a path that does not exist. The fix is stall parking in movementSystem.ts: after 14 movement ticks without a new closest approach to the target (STALL_PARK_TICKS), the unit treats its goal as reached and holds, still striking anything in reach. While parked it takes one probe step every 12 ticks, so when the scrum shifts it is moving again within about a second. The bug was “unit runs in circles”; the diagnosis was “unit is too honest about an impossible assignment”; the fix is teaching it to stand still with intent.

The slot is real; the path to it is not. Parking is the honest answer.

Side note: you might ask why two pathfinders instead of one good one. Cost of failure and cadence. An arena mistake costs a tenth of a second and is corrected by the next replan; a march mistake is a 50 s slog the player watches in real time and cannot interrupt. The arena search runs hundreds of times per fight over 375 cells; the overworld runs once per march over 129,024. One system tuned for both would be worse at each, and the regression tests that pin them (nav.test.ts, movementRockDetour.test.ts, travelPath.test.ts) do not share a single assertion.

As always, let me know what you think.