HTML5 game publishing
A* Pathfinding on a Grid in JavaScript: Heap, Typed Arrays and Smoothing
A fast A* with a binary heap and typed arrays, octile heuristic, no corner cutting, line-of-sight smoothing and habits for many agents on a phone.
A* is the standard answer to "how does my character get from here to there", and it is also one of the algorithms people implement slowly without noticing. A grid of 100 by 100 cells is only 10,000 nodes, so a clumsy version still works, until you have twenty enemies re-planning every frame on a phone. This post builds A* on a grid in JavaScript, then covers the optimizations that matter: a proper priority queue, a good heuristic, path caching and smoothing.
What A* does
A* explores from the start, always expanding the node with the lowest f = g + h, where g is the cost so far and h is a guess of the remaining cost. If h never overestimates, the first time you reach the goal is the shortest path. A good heuristic makes A* explore far fewer nodes than breadth-first search.
For a 4-direction grid, use Manhattan distance. For 8 directions with equal diagonal cost use Chebyshev. With diagonals costing about 1.41, use octile distance:
function octile(ax, ay, bx, by) {
const dx = Math.abs(ax - bx), dy = Math.abs(ay - by);
return (dx + dy) + (Math.SQRT2 - 2) * Math.min(dx, dy);
}
The data structures decide the speed
Two parts of a naive A* are slow:
- The open list. Scanning an array for the lowest
feach step is O(n). Use a binary heap. - The closed set. A JavaScript
Setof strings is slow and allocates. Use typed arrays indexed by cell.
const W = 128, H = 128, N = W * H;
const g = new Float32Array(N);
const parent = new Int32Array(N);
const state = new Uint8Array(N); // 0 unseen, 1 open, 2 closed
A minimal binary heap keyed by f:
class Heap {
constructor() { this.a = []; this.f = new Float32Array(N); }
push(i, f) { this.f[i] = f; this.a.push(i); this.up(this.a.length - 1); }
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) { a[0] = last; this.down(0); }
return top;
}
up(k) { const a = this.a; while (k > 0) { const p = (k - 1) >> 1;
if (this.f[a[p]] <= this.f[a[k]]) break; [a[p], a[k]] = [a[k], a[p]]; k = p; } }
down(k) { const a = this.a, n = a.length; for (;;) { let m = k;
const l = 2 * k + 1, r = l + 1;
if (l < n && this.f[a[l]] < this.f[a[m]]) m = l;
if (r < n && this.f[a[r]] < this.f[a[m]]) m = r;
if (m === k) break; [a[m], a[k]] = [a[k], a[m]]; k = m; } }
}
The search itself
function findPath(sx, sy, gx, gy, blocked) {
state.fill(0);
const start = sy * W + sx, goal = gy * W + gx;
const heap = new Heap();
g[start] = 0; parent[start] = -1; state[start] = 1;
heap.push(start, octile(sx, sy, gx, gy));
while (heap.a.length) {
const cur = heap.pop();
if (cur === goal) return rebuild(cur);
if (state[cur] === 2) continue;
state[cur] = 2;
const cx = cur % W, cy = (cur / W) | 0;
for (const [dx, dy] of DIRS) {
const nx = cx + dx, ny = cy + dy;
if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
const n = ny * W + nx;
if (blocked[n] || state[n] === 2) continue;
// forbid cutting corners around walls
if (dx && dy && (blocked[cy * W + nx] || blocked[ny * W + cx])) continue;
const ng = g[cur] + (dx && dy ? Math.SQRT2 : 1);
if (state[n] === 0 || ng < g[n]) {
g[n] = ng; parent[n] = cur; state[n] = 1;
heap.push(n, ng + octile(nx, ny, gx, gy));
}
}
}
return null;
}
Notice the handling of duplicates: instead of decreasing a key in the heap, we push the node again with its better cost and skip stale entries when they pop out (the state[cur] === 2 check). That is simpler and fast enough in practice.
Path smoothing
Grid paths look robotic, with staircase zig-zags. A cheap fix is a line-of-sight pass: walk along the path, and from each node jump to the farthest later node that has a clear straight line to it. Delete the nodes in between. This cuts the number of waypoints and gives natural movement.
function smooth(path, blocked) {
const out = [path[0]];
let i = 0;
while (i < path.length - 1) {
let j = path.length - 1;
while (j > i + 1 && !lineClear(path[i], path[j], blocked)) j--;
out.push(path[j]); i = j;
}
return out;
}
Implement lineClear with a Bresenham-style walk over the cells between the two points.
Performance habits for many agents
- Do not re-plan every frame. Plan once, then re-plan only when the target moves more than a few cells or the path is blocked.
- Stagger the work. Spread agents over several frames, with a budget such as two searches per frame.
- Share results. If many enemies chase the same target, run one flood fill from the target and let each enemy step downhill on the distance field. That is one search for any number of followers.
- Cap the search. Limit expanded nodes. If the cap is hit, move toward the best node found rather than freezing.
- Move big searches off the main thread. See Web Workers for heavy game logic.
- Reuse the arrays. The typed arrays above are allocated once. See garbage collection in JavaScript games.
When not to use A*
If your arena is open, with no obstacles, steering toward the target is enough and A* is waste. If you have many agents and one target, use the distance field. If the map is not a grid, such as a navigation mesh, A* still works on the graph of polygons. For elimination games with many actors, the pacing and bot behaviour in designing elimination rounds pairs well with this.


