Feature Library

Pathfinding on a lazy walk grid

1.37 CPU ms
A still of the Pathfinding on a lazy walk grid demo
Still
The live demo starts when it’s in view.Paint walls · start on a wall to erase · drag A and B · arrow keys move B

A way round walls and props from one blocked(x, z) question.

What it costs a frame

1.37 ms
GPU
not used
CPU, median
1.37 ms
CPU, 95th pct
3.71 ms
Draw calls
0
Weight
Moderate

Measured 3 November 2026 on 13th Gen Intel(R) Core(TM) i9-13900H, Chrome 156, 1920×1080 at 1×. 600 frames × 3 rounds, median kept. What ran: Measured with the start and goal circling the map: the path is planned again every frame (lazy grid, A*, pulling) and the walkers replan within a shared budget of 6,000 cells a frame. The frame time includes the Canvas 2D drawing. Phones: tiers are being measured next.

On every machine it was measured on
MachineGPU msCPU msCPU p95
unknown GPU · 13th Gen Intel(R) Core(TM) i9-13900Hreference · measuring toolnot timed1.373.71
apple · Apple A19 Proin a browser tab · 16 November 2026not timed1.963.34
Intel Arc 140V (Xe2-LPG) · Intel Core Ultra 7 258Vin a browser tab · 15 November 2026not timed1.814.34

Bars against one 16.7 ms frame. A browser-tab run is timed in a visible tab without the tool’s scripted input, so read it as close, not exact.

What it needs

Renders with
Canvas 2DA 2D canvas: every current browser.
Your browser
Runs hereNo WebGPU needed
Depends on
NothingNo other packages

What it’s for

  1. NPCs and guards walking round buildings
  2. Click-to-move in top-down games
  3. Units on a map that changes
  4. Robots and agents in a simulation
  5. Routing round obstacles on a floor plan

Pitfalls, in brief

  1. blocked(x, z) must answer for a whole body, its radius included: the grid samples points (cell centres), so a thin wall between two samples is walked straight through.
  2. A goal it cannot reach is not an error: reached is false and the points end at the nearest cell it got to.
  3. The cap (maxVisited, 3000 by default) is per box: a box that is closed in is searched again three times as wide, so visited can come back at up to twice the cap.
  4. Each plan allocates its grid (about 10 bytes a cell, up to 220 × 220 cells): plan when the straight line is blocked (walkClear first) and when the goal moves, not every frame for every body.
  5. A goal further than the box can hold (maxSide cells less the margins) is planned toward a point on the line to it, and reached is false: plan again as the body gets nearer.
2 more in brief
  1. A start up to 3 cells inside something is moved to the nearest open cell; deeper than that the plan is empty, so handle points.length === 0.
  2. Coordinates are world metres on the ground plane, x and z: on a top-down screen z is your y.
7 pitfalls in full, the hook-up guide, the module source and its tests come with the part.

Where it comes from

From HaTac. Fully custom code.

Hart, Nilsson and Raphael, A* search (1968): The search is A*, with the octile distance as its heuristic for eight-way moves. The algorithm, not code.

Line-of-sight path smoothing (“string pulling”): The well-known technique of joining each point to the furthest later one in sight. The idea, not code.

pathfindinga*gridbinary heapstring pullingpath smoothingnavigationno dependencies

Near it in the frame