Feature Library

Desire paths and meander

0.07 CPU ms
A still of the Desire paths and meander demo
Still
The live demo starts when it’s in view.Drag A and B (or tap to send B there) · arrow keys move B, Shift moves A

The trail people would wear between two places, worked out from the land.

What it costs a frame

0.07 ms
GPU
not used
CPU, median
0.07 ms
CPU, 95th pct
0.18 ms
Draw calls
0
Weight
Light

Measured 13 November 2026 on RTX 4060 Laptop, 13th Gen Intel(R) Core(TM) i9-13900H, Chrome 157, 1920×1080 at 1×. 600 frames × 3 rounds, median kept (rounds ranged CPU 0.07–0.09 ms). What ran: Measured with the far end B circling the knoll: the trail is settled again (A* over about 15,000 cells, pulled straight, corners cut) every 0.4 s, then wandered and widened; the walkers move every 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
RTX 4060 Laptop · 13th Gen Intel(R) Core(TM) i9-13900Hreference · measuring toolnot timed0.070.18
apple · Apple A19 Proin a browser tab · 16 November 2026not timed0.100.26
Intel Arc 140V (Xe2-LPG) · Intel Core Ultra 7 258Vin a browser tab · 15 November 2026not timed0.150.39

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. Footpaths and animal tracks in an open-world or strategy map
  2. A level editor where a rough line settles onto the land
  3. Paths across a park, campus or garden plan that people would really walk
  4. Streams, tracks and lanes that wander instead of running ruler-straight
  5. Hiking routes that zigzag up a hill rather than straight over it

Pitfalls, in brief

  1. heightAt is asked for every grid cell and every check of a straight stretch (tens of thousands of calls a settle): make it cheap, and smooth (bilinear, not nearest), or the grades jump at cell edges and the trail zigzags on flat ground.
  2. Settling is A* over up to 90,000 cells times 17 ways in: a few to a few tens of milliseconds for 100–200 m.
  3. The ends are free even inside an obstacle’s clearance (a door, a gate), but a point in the middle put on something is moved to the nearest open cell within 8 m.
  4. Water deeper than DESIRE.wade (5 cm) blocks the trail: give it a ford (or a bridge as an obstacle-free strip) where it may cross, or it goes the long way round, or nowhere.
  5. maxGrade is a hard limit: where no way is gentle enough it settles the least steep way with a warning, so a cliff between the ends is crossed anyway.
3 more in brief
  1. The wander and width are drawn on top of the settled line: a wander larger than the clearance can push the trodden edge into a trunk.
  2. Distances along the line (s) stay those of the line as settled, not of its wandering copy: read the room list and anything placed by distance with s, and a wandered stretch is a little longer than s says.
  3. Coordinates are metres on the ground plane, x and z (y up).
8 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, here over cells and the way each was entered, so turning can cost. The algorithm, not code.

George Chaikin, corner cutting (1974): The two passes that round the pulled corners. The idea, not code.

Fowler–Noll–Vo hash (FNV-1a): Seeds from names (seedOfText). The published algorithm and its constants.

xxHash 32-bit primes (Yann Collet) and MurmurHash2’s multiplier (Austin Appleby): Constants in the lattice hash under the meander noise. The owner’s own mixing, with these well-known constants.

Catmull–Rom splines (1974): The smooth value noise through the lattice, and reading the room between its stations.

desire linestrailsfootpathspathfindinga*terrainswitchbacksslopeobstaclesmeanderstreamsvalue noiseseededdeterministiccanvas 2dno dependencies

Near it in the frame