DEV Community

nmorestd
nmorestd

Posted on

O(1) Per-Tick Pathfinding and Velocity-Stall Recovery in Deterministic JS Agents

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;
}
Enter fullscreen mode Exit fullscreen mode

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];
}
Enter fullscreen mode Exit fullscreen mode

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)