When writing real-time simulation bots or game-loop controllers with strict per-tick CPU budgets (such as 10ms/tick in deterministic arenas), running A* or Dijkstra per unit on every frame quickly hits timeout ceilings.
Here is the exact pattern we use in our JavaScript controller (nmore-vanguard) to keep per-tick pathfinding strictly O(1) with zero allocations during gameplay.
1. Precompute Multi-Source Distance Fields Once in hello()
At match initialization, precompute a flat Int32Array Dijkstra cost field from every static objective and spawn point using a typed-array binary min-heap:
const MAX_WH = 16384;
const sharedHeapIdx = new Int32Array(MAX_WH + 8);
const sharedHeapKey = new Int32Array(MAX_WH + 8);
function buildDistanceField(W, H, tileCost, passable, gx, gy) {
const dist = new Int32Array(W * H).fill(0x3fffffff);
const start = gy * W + gx;
dist[start] = 0;
let size = 1;
sharedHeapIdx[1] = start;
sharedHeapKey[1] = 0;
while (size > 0) {
const cur = sharedHeapIdx[1];
const curD = sharedHeapKey[1];
sharedHeapIdx[1] = sharedHeapIdx[size];
sharedHeapKey[1] = sharedHeapKey[size--];
// sift down...
if (curD > dist[cur]) continue;
const cx = cur % W, cy = (cur / W) | 0;
for (const [dx, dy, mult] of DIRS8) {
const nx = cx + dx, ny = cy + dy;
if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
const ni = ny * W + nx;
if (!passable[ni]) continue;
const nd = curD + ((tileCost[ni] * mult) >> 3);
if (nd < dist[ni]) {
dist[ni] = nd;
// push onto heap...
}
}
}
return dist;
}
2. O(1) Greedy Gradient Descent per Tick
During each tick, any unit navigating toward an objective simply follows the steepest descent over 4 lookahead tiles on the precomputed Int32Array — zero heap allocations, ~0.01ms CPU time:
function waypointFromField(field, W, H, ux, uy, lookahead = 4) {
let cx = ux >> 16, cy = uy >> 16;
for (let step = 0; step < lookahead; step++) {
let bestCost = field[cy * W + cx];
let bx = cx, by = cy;
for (const [dx, dy] of DIRS8) {
const nx = cx + dx, ny = cy + dy;
if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
const c = field[ny * W + nx];
if (c < bestCost) { bestCost = c; bx = nx; by = ny; }
}
if (bx === cx && by === cy) break;
cx = bx; cy = by;
}
return [(cx << 16) + 32768, (cy << 16) + 32768];
}
3. Velocity-Based Stall Recovery
Physics engines often report blocked = false even when a tracked vehicle slides sideways against a steep hill tile. Tracking actual Euclidean displacement (hypot(dx, dy) < 400) over 5 consecutive throttle ticks catches silent deadlocks and triggers a deterministic reverse-and-steer recovery window.
Full source code is open on GitHub and runs live on battle.training.
Top comments (0)