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.
