Pathfinding

GPU-accelerated shortest path finding on 2D weighted grids. Uses wavefront expansion (parallel Dijkstra) — each iteration expands all frontier cells simultaneously, leveraging massive GPU parallelism.

Usage

import { createPathfinder } from './pathfinding';

const pathfinder = createPathfinder(device, { width: 256, height: 256 });

// Set terrain costs (1.0 = normal, higher = slower, negative = impassable)
pathfinder.setCostGrid(costs);

// Find shortest path
const result = await pathfinder.findPath({
  startX: 10,
  startY: 10,
  endX: 240,
  endY: 240
});

if (result.found) {
  console.log(`Path length: ${result.path.length}, distance: ${result.distance}`);
  // result.path is an array of cell indices (start → end)
}

// Read the full distance field (useful for visualization or multi-target queries)
const distField = await pathfinder.getDistanceField();

pathfinder.destroy();

API

createPathfinder(device, options)

Returns a Pathfinder instance.

Option	Type	Default	Description
width	number	(required)	Grid width in cells
height	number	(required)	Grid height in cells

pathfinder.setCostGrid(costs)

Upload terrain costs. costs is a Float32Array of width * height values.

• 1.0 = normal traversal cost
• > 1.0 = slower terrain (e.g., 3.0 for swamp)
• < 0 = impassable (wall)

The cost grid persists between findPath calls until you call setCostGrid again.

pathfinder.findPath(options)

Returns a Promise<PathResult>.

Option	Type	Default	Description
startX	number	(required)	Start cell X coordinate
startY	number	(required)	Start cell Y coordinate
endX	number	(required)	End cell X coordinate
endY	number	(required)	End cell Y coordinate
maxIterations	number	width + height	Max wavefront iterations

PathResult:

Field	Type	Description
path	number[]	Cell indices from start to end
distance	number	Total path cost
found	boolean	Whether a path exists

Cell indices can be converted to coordinates: x = index % width, y = Math.floor(index / width).

pathfinder.getDistanceField()

Returns the full distance field as a Float32Array. Each cell contains the shortest distance from the start position. Unreachable cells have Infinity. Useful for visualization, heatmaps, or multi-target queries.

pathfinder.destroy()

Releases all GPU buffers.

Algorithm

Wavefront expansion is a parallel variant of Dijkstra's algorithm optimized for the GPU:

1. Initialize — Set start cell distance to 0, all others to infinity.
2. Expand — Each cell checks if it can offer a shorter path to its 4-connected neighbours. Uses atomicMin for conflict-free distance updates — multiple threads can relax the same cell safely.
3. Converge — Repeat until no cell is updated (frontier flag stays 0).
4. Trace — Backtrack from end to start using parent pointers.

Unlike CPU A* (which uses a priority queue), this approach processes all frontier cells in parallel each iteration. On a GPU with thousands of cores, this is dramatically faster for large grids.

The distance field is stored as fixed-point u32 (float × 1000) to enable atomicMin operations, since WebGPU doesn't support atomic float operations.

Overflow constraint: The maximum representable distance is ~4,000,000 cost units. For a grid of size W × H with max terrain cost C, the worst-case path cost is W × H × C. Keep this product below 4,000,000 — for example, a 1024×1024 grid with max cost 3.0 works fine (~3.1M), but max cost 5.0 would overflow.

WGSL loading

The default import uses Vite's ?raw suffix:

import shaderSource from './pathfinding.wgsl?raw';

If you're not using a bundler, load via fetch:

const shaderSource = await fetch(new URL('./pathfinding.wgsl', import.meta.url)).then((r) =>
  r.text()
);

Modifying

Add diagonal movement (8-connected)

Extend the DX/DY arrays to 8 directions and add diagonal cost (typically sqrt(2) ≈ 1.414):

const DX: array<i32, 8> = array<i32, 8>(0, 0, -1, 1, -1, 1, -1, 1);
const DY: array<i32, 8> = array<i32, 8>(-1, 1, 0, 0, -1, -1, 1, 1);
const COST_MUL: array<f32, 8> = array<f32, 8>(1.0, 1.0, 1.0, 1.0, 1.414, 1.414, 1.414, 1.414);

Add A* heuristic

To prioritize cells closer to the target, add a heuristic term to the distance comparison in the expand kernel. Store g + h for ordering but only g for the actual distance. This requires an additional buffer for the heuristic-adjusted costs.

Multiple pathfinding queries

The distance field from a single findPath call gives shortest distances to all cells from the start. For multiple targets from the same start, call findPath once and read individual distances from getDistanceField().

3D grids

Extend to 3D by adding a Z dimension, 6-connected neighbours, and a 3D grid index. The wavefront approach scales well to 3D since each cell is independent.

Flow fields

Instead of tracing a single path, use the distance field as a flow field: each cell's gradient points toward the shortest path to the target. This is commonly used for crowd simulation where many agents need to navigate to the same destination.