How do you path 500 units without dropping frames?

You stop pathing them individually: with 500 units heading to one goal on a 512x512 grid, running A per unit took 904 ms while one flow field took 5.17 ms — 175x faster.* The number that actually changes how you write the code is smaller and stranger: the flow field was already the cheaper option at six units. Not five hundred. Six.

Hardware: Apple M3, 8 cores, 16 GB, macOS 26.4.1, Node v23.5.0. Plain JavaScript, typed arrays, one thread, no dependencies, no engine. This is not a C++ engine and the absolute milliseconds are not the point — a Burst-compiled Unity job beats every figure here. What transfers is the relative scaling: where the crossovers sit, and how many nodes each algorithm expands. Node counts are exact and reproduce from the seed; times are medians of three to five runs under normal desktop load.

The maps, generated deterministically from mulberry32 seeds: open field (128x128 and 512x512, no walls); maze (513x513 recursive-backtracker, one-cell corridors, 131,071 open cells, one route between any two); choke point (512x512 split by a solid wall with one 1-cell gap, 261,633 open cells); and scatter (512x512, 30% randomly blocked, unreachable cells turned to wall, 178,326 open) — closest to a real tower-defense map. Movement is 4-connected with unit step cost unless stated.

The short answer

• A flow field beat per-unit A from six units upward.* On a 512x512 open field: 1 unit — A* 0.96 ms, flow field 4.26 ms. 500 units — A* 904.31 ms, flow field 5.17 ms. It does one pass over the grid however many units read it.
• A one-line tie-breaker on the heuristic was worth 52.7x. Multiplying Manhattan by 1 + 1/1000 cut 100 searches on an open 512x512 map from 2,480,898 expanded nodes to 47,046, and 163.68 ms to 3.93 ms, with the paths exactly the same length — 47,046 either way.
• An inadmissible weighted heuristic buys speed with path quality, and the exchange rate is bad above 1.5x. On scatter: weight 1.5 expanded 8.3x fewer nodes for paths 9.28% longer; weight 5 expanded 15.2x fewer for 28.03% longer.
• A goal with no path is the real disaster. One A* at a walled-in goal expanded all 262,135 reachable cells; 500 units took 8,532 ms. One flood fill answering all 500 took 0.17 ms — about 50,000x.
• JPS expanded 199 nodes where A expanded 1.9 million, and was still 100x slower in wall-clock.* The work moved out of the open list and into the scan, which is not what the node counts advertise.

When does a flow field beat A*?

Three candidates, same goal, same map. A per unit*: one search each, Manhattan heuristic, binary heap. Dijkstra from the goal: one pass over the reachable area storing a next pointer per cell, which every unit walks. Flow field: the same wavefront built with a plain BFS queue (uniform step costs, so no priority queue needed) plus one direction byte per cell, which every unit reads under its feet.

Open field 512x512, all units heading for (510,510), total ms for the batch:

A* per unit is linear in unit count and the constant is brutal: 1.76 seconds for 1000 units, on a map where every unit wants essentially the same path. The flow field grows 1.65 ms across the entire range, because the only per-unit work is following pointers. Sweeping N one at a time to find where the lines cross:

Three to seven units. Flow fields are filed in most people's heads under "optimisation for when you have hundreds of units", and on these maps that is off by two orders of magnitude. If more than half a dozen things are walking to the same place, the shared field is already the cheaper code, and the shorter code. The caveat that makes it a decision rather than a rule: it holds when the units share a goal. A field is per-destination — ten squads with ten targets need ten fields, and the arithmetic starts again.

Does that hold on every map?

Not in the way you would guess. Total milliseconds for 500 units:

On the maze the flow field lost to the Dijkstra tree, 31.16 ms against 17.10 ms, contradicting what I expected when I wrote the harness. The BFS build is the faster build; it is the following that costs. Average maze path here is about 9,880 cells, so 500 units walking step by step is five million pointer hops, and the flow field does more work per hop (read direction, decode to an offset, add) than the tree (read the next index). Short paths, build dominates and the field wins; enormous paths, the follow decides. Both still beat per-unit A* by 20-36x.

Per-unit A* looks worst on the choke map — 1,129 ms and 40.4 million nodes for 500 units — because every search rediscovers the same single gap independently. That is the shape of a tower-defense map.

Which heuristic should you use?

Manhattan, nothing clever, unless you have measured that you can afford worse paths. Scatter map, 100 units, against a Dijkstra ground truth so path quality is exact rather than assumed:

Euclidean distance on a 4-connected grid is a 4.3x mistake. It stays admissible, so paths are optimal, but it systematically underestimates — you cannot move diagonally, so straight-line distance is always short of the truth — and A* pays for a weak heuristic in expanded nodes. The heuristic must match the movement rules: 4-way wants Manhattan, 8-way wants octile.

The weighted rows are the trade nobody puts numbers on. Weight 1.5 is genuinely attractive: 8.3x fewer nodes, 5.5x faster, units walking 9.3% further, which in a game where they already steer around each other is usually invisible. Weight 5 is not — another 1.8x of speed for 28% longer routes, which reads on screen as obviously silly detours.

Worth stating plainly because it surprised me: on the open, maze and choke maps, weighting up to 5x cost exactly zero path quality — +0.00% on all three. On a uniform 4-connected grid every monotone staircase between two points is the same length, so a greedy heuristic has nothing to get wrong, and in a one-cell-wide maze there is only one route. The penalty appears only where the map offers choices. Benchmark weighted A* on an empty grid and you will conclude it is free. It is not.

What does a one-line tie-breaker actually do?

More than anything else here. On an open grid huge numbers of cells share the same f, and a plain heap breaks those ties arbitrarily, fanning the search across the whole diamond between start and goal. Nudging the heuristic by a fraction of a percent makes the tie-break prefer cells nearer the goal. Open 512x512, 100 units, f = g + h * (1 + p):

52.7x fewer nodes, 41x faster, identical path cost, one multiplication. At p = 0.000001 the search expands exactly 47,046 nodes for 100 units — 470 each, which is the path length. It walks straight there.

The honest asterisk: on the cluttered scatter map the same tie-breaker expanded 10% fewer nodes but ran slower (167.12 ms against 125.55 ms), because the float multiply per node costs more than it saves when obstacles are already breaking the ties. Tie-breaking is an open-terrain optimisation — ship it anyway, since open terrain is what spikes your frame time.

What happens when there is no path?

The failure mode that arrives as "the game freezes when I wall off the exit". I sealed a goal inside a one-cell wall ring on an open 512x512 map and ran A* at it.

A single failed search expanded 262,135 nodes — every reachable open cell on the map — because A* cannot know it is beaten until the open list empties, and every unit repeats it. 500 units is 8.5 seconds of freeze, or 511 dropped frames at 60 Hz.

The fix is not a smarter search. One flood fill from the goal labels which cells can reach it; the per-unit check is then a single array read — 0.17 ms for all 500, about 50,000x less work. Where the path does exist that flood fill costs 4.45 ms, which you were going to pay anyway: it is the flow field.

Do diagonals and JPS pay for themselves?

Diagonals yes, JPS no — and the reason is instructive. 100 units, corner cutting allowed in both A* and JPS so the movement rules match; the two agree on total travel distance to the decimal, which is how I know the comparison is fair.

Diagonals shortened total travel by 19.2% on the open map and 21.2% on scatter, for 21% more time once the tie-breaker is in place. Straightforward trade for anything meant to look like it is walking.

JPS expanded 199 nodes across 100 searches — two per unit — and took 482.87 ms where tie-broken A took 4.69 ms.* Both found the identical route. JPS does not remove the work, it moves it into a recursive scan that walks the grid cell by cell hunting jump points, and on an empty map each diagonal step scans a whole row and column. Node counts are a terrible proxy for runtime. JPS earns its reputation with precomputed jump distances (JPS+) — a different algorithm with a build step, and if you will precompute per map, a flow field is simpler and already beat everything here.

Which open-set structure is worth writing?

100 units, tie-break on for the heap and sorted array so they expand identical node counts, three warm-up rounds before timing:

The sorted array is only 1.2-2.4x behind the heap, less than its reputation suggests: splice on a small array is fast, and the open list stays small once the heuristic works. The bucket queue is the interesting one — step costs are integers, so f is an integer and priorities bucket with O(1) push and pop. On scatter it ran 2.2x faster than the binary heap while expanding 4.8% more nodes (1,392,279 against 1,327,932): more searching, more cheaply. For uniform or small-integer costs, write this one.

What does smoothing the path cost?

Raw grid paths look wrong; units walk in stair-steps. String-pulling — skipping ahead to the furthest waypoint with clear Bresenham line of sight — fixed 100 scatter-map paths in 21.74 ms, turning 52,855 waypoints into 6,123, 8.6x fewer. That is 0.22 ms per path, comparable to the search itself, and it applies to flow-field paths too. Budget for it: it is the difference between "pathfinding works" and "pathfinding looks right".

Check it yourself

One file, no dependencies, Node 18 or newer. It reproduces the headline table, finds the crossover, measures heuristics against a Dijkstra ground truth, and runs the no-path case.

node pathbench.mjs      # 14.7 s on the M3 above

// pathbench.mjs — node 23, no dependencies.  node pathbench.mjs
const W = 512, H = 512, SIZE = W * H;
const rnd32 = (a) => () => { a |= 0; a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
const med = (a) => [...a].sort((x, y) => x - y)[a.length >> 1];
const DX = [1, -1, 0, 0], DY = [0, 0, 1, -1];

function openMap() { return new Uint8Array(SIZE); }
function scatterMap(p, seed) {                       // random obstacles, goal-reachable only
  const w = new Uint8Array(SIZE), r = rnd32(seed);
  for (let i = 0; i < SIZE; i++) if (r() < p) w[i] = 1;
  for (let x = 0; x < W; x++) { w[x] = 1; w[(H - 1) * W + x] = 1; }
  for (let y = 0; y < H; y++) { w[y * W] = 1; w[y * W + W - 1] = 1; }
  w[(H - 3) * W + (W - 3)] = 0;
  const ff = flow(w, W - 3, H - 3);
  for (let i = 0; i < SIZE; i++) if (ff.cost[i] === 0x7fffffff) w[i] = 1;
  return w;
}
function sealedMap(gx, gy) {                          // goal walled in: no path exists
  const w = new Uint8Array(SIZE);
  for (let dy = -1; dy <= 1; dy++) for (let dx = -1; dx <= 1; dx++)
    if (dx || dy) w[(gy + dy) * W + gx + dx] = 1;
  return w;
}

class Heap {
  constructor() { this.n = new Int32Array(1024); this.f = new Float64Array(1024); this.size = 0; }
  clear() { this.size = 0; }
  push(v, f) {
    if (this.size === this.n.length) { const a = new Int32Array(this.size * 2); a.set(this.n); this.n = a; const b = new Float64Array(this.size * 2); b.set(this.f); this.f = b; }
    let i = this.size++; this.n[i] = v; this.f[i] = f;
    while (i) { const p = (i - 1) >> 1; if (this.f[p] <= this.f[i]) break;
      const tn = this.n[p], tf = this.f[p]; this.n[p] = this.n[i]; this.f[p] = this.f[i]; this.n[i] = tn; this.f[i] = tf; i = p; }
  }
  pop() {
    const top = this.n[0], last = --this.size; this.n[0] = this.n[last]; this.f[0] = this.f[last];
    for (let i = 0; ;) { const l = 2 * i + 1, r = l + 1; let s = i;
      if (l < this.size && this.f[l] < this.f[s]) s = l;
      if (r < this.size && this.f[r] < this.f[s]) s = r;
      if (s === i) return top;
      const tn = this.n[s], tf = this.f[s]; this.n[s] = this.n[i]; this.f[s] = this.f[i]; this.n[i] = tn; this.f[i] = tf; i = s; }
  }
}
const g = new Float64Array(SIZE), stamp = new Int32Array(SIZE), closed = new Int32Array(SIZE), parent = new Int32Array(SIZE);
const heap = new Heap(); let RUN = 0;

function astar(walls, sx, sy, gx, gy, weight = 1, tie = 0) {
  const run = ++RUN; heap.clear();
  const s = sy * W + sx, goal = gy * W + gx;
  g[s] = 0; stamp[s] = run; parent[s] = -1;
  heap.push(s, (Math.abs(sx - gx) + Math.abs(sy - gy)) * weight * (1 + tie));
  let expanded = 0;
  while (heap.size) {
    const cur = heap.pop();
    if (closed[cur] === run) continue;
    closed[cur] = run;
    if (cur === goal) return { cost: g[goal], expanded, found: true };
    expanded++;
    const cx = cur % W, cy = (cur / W) | 0, gc = g[cur];
    for (let i = 0; i < 4; i++) {
      const nx = cx + DX[i], ny = cy + DY[i];
      if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
      const ni = ny * W + nx;
      if (walls[ni]) continue;
      const ng = gc + 1;
      if (stamp[ni] === run && g[ni] <= ng) continue;
      stamp[ni] = run; g[ni] = ng; parent[ni] = cur;
      heap.push(ni, ng + (Math.abs(nx - gx) + Math.abs(ny - gy)) * weight * (1 + tie));
    }
  }
  return { cost: Infinity, expanded, found: false };
}

function dijkstra(walls, gx, gy) {                    // shortest-path tree from the goal
  const cost = new Float64Array(SIZE).fill(Infinity), next = new Int32Array(SIZE).fill(-1);
  const done = new Uint8Array(SIZE), hp = new Heap(), goal = gy * W + gx;
  cost[goal] = 0; hp.push(goal, 0);
  while (hp.size) {
    const cur = hp.pop(); if (done[cur]) continue; done[cur] = 1;
    const cx = cur % W, cy = (cur / W) | 0;
    for (let i = 0; i < 4; i++) {
      const nx = cx + DX[i], ny = cy + DY[i];
      if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
      const ni = ny * W + nx; if (walls[ni] || done[ni]) continue;
      const ng = cost[cur] + 1;
      if (ng < cost[ni]) { cost[ni] = ng; next[ni] = cur; hp.push(ni, ng); }
    }
  }
  return { cost, next, bytes: cost.byteLength + next.byteLength + done.byteLength };
}

function flow(walls, gx, gy) {                        // integration field + direction byte
  const cost = new Int32Array(SIZE).fill(0x7fffffff), dir = new Int8Array(SIZE).fill(-1);
  const q = new Int32Array(SIZE); let head = 0, tail = 0;
  const goal = gy * W + gx; cost[goal] = 0; q[tail++] = goal;
  while (head < tail) {
    const cur = q[head++], cx = cur % W, cy = (cur / W) | 0, nc = cost[cur] + 1;
    for (let i = 0; i < 4; i++) {
      const nx = cx + DX[i], ny = cy + DY[i];
      if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
      const ni = ny * W + nx;
      if (walls[ni] || cost[ni] !== 0x7fffffff) continue;
      cost[ni] = nc; dir[ni] = i ^ 1; q[tail++] = ni;
    }
  }
  return { cost, dir, bytes: cost.byteLength + dir.byteLength };
}
const follow = (ff, sx, sy) => { let i = sy * W + sx, n = 0; while (ff.cost[i]) { const d = ff.dir[i]; if (d < 0) return -1; i += DY[d] * W + DX[d]; n++; } return n; };
const walkTree = (t, sx, sy) => { let i = sy * W + sx, n = 0; while (t.cost[i]) { i = t.next[i]; if (i < 0) return -1; n++; } return n; };

function starts(walls, n, seed, goal) {
  const cells = []; for (let i = 0; i < SIZE; i++) if (!walls[i]) cells.push(i);
  const r = rnd32(seed), out = [];
  while (out.length < n) { const c = cells[(r() * cells.length) | 0]; if (c !== goal) out.push([c % W, (c / W) | 0]); }
  return out;
}

// ---------------------------------------------------------------- 1. scaling
const open = openMap(), GX = W - 2, GY = H - 2, all = starts(open, 1000, 4242, GY * W + GX);
console.log(`open ${W}x${H}, all units heading to (${GX},${GY})\n`);
console.log('    N    A* per unit   Dijkstra tree   flow field');
for (const N of [1, 10, 100, 500, 1000]) {
  const st = all.slice(0, N), ta = [], td = [], tf = [];
  for (let r = 0; r < 3; r++) {
    let s = performance.now(); for (const [x, y] of st) astar(open, x, y, GX, GY); ta.push(performance.now() - s);
    s = performance.now(); const t = dijkstra(open, GX, GY); for (const [x, y] of st) walkTree(t, x, y); td.push(performance.now() - s);
    s = performance.now(); const f = flow(open, GX, GY); for (const [x, y] of st) follow(f, x, y); tf.push(performance.now() - s);
  }
  console.log(`${String(N).padStart(5)}  ${med(ta).toFixed(2).padStart(9)} ms  ${med(td).toFixed(2).padStart(9)} ms  ${med(tf).toFixed(2).padStart(9)} ms`);
}

// ---------------------------------------------------------------- 2. crossover
let cross = 0;
for (let N = 1; N <= 32; N++) {
  const st = all.slice(0, N), ta = [], tf = [];
  for (let r = 0; r < 5; r++) {
    let s = performance.now(); for (const [x, y] of st) astar(open, x, y, GX, GY); ta.push(performance.now() - s);
    s = performance.now(); const f = flow(open, GX, GY); for (const [x, y] of st) follow(f, x, y); tf.push(performance.now() - s);
  }
  if (med(tf) < med(ta)) { cross = N; break; }
}
console.log(`\ncrossover: flow field wins from N = ${cross} units`);

// ---------------------------------------------------------------- 3. heuristic
const scat = scatterMap(0.30, 7), SGX = W - 3, SGY = H - 3;
const st100 = starts(scat, 100, 4242, SGY * W + SGX);
const truth = dijkstra(scat, SGX, SGY);
let optimal = 0; for (const [x, y] of st100) optimal += truth.cost[y * W + x];
console.log(`\nscatter map, 30% blocked, 100 units. optimal total path cost = ${optimal}`);
console.log('  heuristic              ms    expanded   path cost   vs optimal');
for (const [name, wt, tie] of [['Manhattan', 1, 0], ['Manhattan +tiebreak', 1, 1e-3], ['Manhattan x1.5', 1.5, 0], ['Manhattan x2', 2, 0], ['Manhattan x5', 5, 0]]) {
  const ts = []; let e = 0, c = 0;
  for (let r = 0; r < 3; r++) { const s = performance.now(); e = 0; c = 0; for (const [x, y] of st100) { const q = astar(scat, x, y, SGX, SGY, wt, tie); e += q.expanded; c += q.cost; } ts.push(performance.now() - s); }
  console.log(`  ${name.padEnd(20)} ${med(ts).toFixed(1).padStart(6)} ${String(e).padStart(10)} ${String(c).padStart(11)}   +${((c / optimal - 1) * 100).toFixed(2)}%`);
}

// ---------------------------------------------------------------- 4. no path
const sealed = sealedMap(400, 400), st500 = starts(sealed, 500, 4242, 400 * W + 400);
let ts = []; let exp = 0;
for (let r = 0; r < 3; r++) { const s = performance.now(); exp = 0; for (const [x, y] of st500.slice(0, 100)) exp += astar(sealed, x, y, 400, 400).expanded; ts.push(performance.now() - s); }
console.log(`\nunreachable goal, 100 units: naive A* ${med(ts).toFixed(1)} ms, ${exp} nodes expanded`);
ts = [];
for (let r = 0; r < 5; r++) { const s = performance.now(); const f = flow(sealed, 400, 400); let bad = 0; for (const [x, y] of st500) if (f.cost[y * W + x] === 0x7fffffff) bad++; ts.push(performance.now() - s); }
console.log(`unreachable goal, 500 units: one flood fill + 500 lookups ${med(ts).toFixed(2)} ms`);

// ---------------------------------------------------------------- 5. memory
const f = flow(open, GX, GY), d = dijkstra(open, GX, GY);
console.log(`\nresident bytes at ${W}x${H}: flow field ${f.bytes / 1024} KiB, dijkstra tree ${d.bytes / 1024} KiB, A* scratch ${(g.byteLength + stamp.byteLength + closed.byteLength + parent.byteLength) / 1024} KiB`);

On the M3 above that prints:

open 512x512, all units heading to (510,510)

    N    A* per unit   Dijkstra tree   flow field
    1       0.96 ms      12.68 ms       4.26 ms
   10       9.67 ms      13.13 ms       4.17 ms
  100     146.48 ms      13.65 ms       4.33 ms
  500     904.31 ms      14.87 ms       5.17 ms
 1000    1756.35 ms      14.50 ms       5.91 ms

crossover: flow field wins from N = 6 units

scatter map, 30% blocked, 100 units. optimal total path cost = 52855
  heuristic              ms    expanded   path cost   vs optimal
  Manhattan             116.3    1719001       52855   +0.00%
  Manhattan +tiebreak   156.1    1539786       52855   +0.00%
  Manhattan x1.5         19.9     207117       57759   +9.28%
  Manhattan x2           13.8     145179       60881   +15.18%
  Manhattan x5           10.4     112789       67669   +28.03%

unreachable goal, 100 units: naive A* 1577.0 ms, 26213500 nodes expanded
unreachable goal, 500 units: one flood fill + 500 lookups 0.14 ms

resident bytes at 512x512: flow field 1280 KiB, dijkstra tree 3328 KiB, A* scratch 5120 KiB

The last line is worth a glance. The flow field is the smallest of the three — one Int32Array of costs plus one Int8Array of directions, 1,280 KiB at 512x512, confirmed against process.memoryUsage() at 1,280.7 KiB. A*'s scratch is 5,120 KiB, the same 5 MB for one unit or a thousand because it is reused. The fastest option here also holds the least memory, which is not how these trades usually go.

Change W, H and the obstacle density at the top and re-run. Two rows decide your frame budget: the crossover line, and the +tiebreak row.

Elsewhere in the game loop: what a sprite atlas actually saves you, where shelf packing matched MaxRects at 1/1500th of the CPU, and what a collision broadphase costs — the other per-unit loop that decides your frame time. For the animation side, CST Animator handles sprite timelines and export.