Grid pathfinding

@codexo/exojs-pathfinding answers one question — how does this actor get from here to there — and it answers it over a world you describe, not one it owns. There is no scene node, no renderer, no asset type and no extension to activate: you build a navigation space, you construct a Pathfinder, and you own both.

Note: pathfinding ships as a separate package. Install it alongside @codexo/exojs:

npm install @codexo/exojs @codexo/exojs-pathfinding

A grid is a window of costs

GridSpace is a rectangular window of cells. Each cell carries a cost: 0 blocks it, 1 is ordinary ground, and anything larger is terrain an actor will walk around when the detour is cheaper than crossing it.

const grid = GridSpace.from(
  64,
  40,
  (x, y) => {
    if (isWall(x, y)) return 0;

    return isMud(x, y) ? 4 : 1;
  },
  { cellSize: 32 },
);

The callback receives absolute cell coordinates — the same numbers your map uses — so the grid never needs to know where its window sits. cellSize is how the grid converts between cells and world pixels, which is what makes coordinate queries and PathResult.points work.

Everything outside the window counts as blocked. That is deliberate, and it is the answer for infinite or streamed maps: size the window to the region your actors are in, and keep it in step as chunks stream by.

grid.setCost(12, 7, 0); // a door slams shut
grid.setCost(12, 7, 1); // and opens again

const revision = grid.revision; // changed, so every path taken before is suspect

Every edit bumps grid.revision, which is how anything holding an older path finds out that the world moved under it.

Querying

const pathfinder = new Pathfinder();

const result = pathfinder.findPathBetween(grid, hero.x, hero.y, target.x, target.y, {
  smooth: true,
  agentSize: 2,
  maxExpandedNodes: 4000,
});

switch (result.status) {
  case 'found':
    hero.follow(result.points);
    break;
  case 'budget-exceeded':
    // A real, traversable prefix. Walk it and ask again next frame.
    hero.follow(result.points);
    break;
  case 'unreachable':
    break;
}

findPath takes node ids; findPathBetween takes world coordinates and resolves them for you. Both return a PathResult whose status is a value, not an exception — “there is no way through” is an ordinary game state, not an error:

A budget-exceeded result is not a guess: it is a real, traversable prefix towards the goal, so an actor can start walking it and ask again next frame. That is the shape a frame budget wants.

Set snapToNearest when “get as close as you can” is the right behaviour — a click on a wall, or a target that has since been walled in.

const plannedAt = result.revision;

const isStale = (): boolean => plannedAt !== grid.revision;

Shaping the route

Diagonals. By default a diagonal step needs both cells it passes between to be walkable, so an actor never clips through the corner where two walls meet. diagonals: 'never' gives four-connected movement; 'always' allows the clip. The policy is fixed when the grid is constructed, because the heuristic and the neighbour rules are derived from it.

Costs. A diagonal costs its length, so √2 cells of ordinary ground. Weighted cells multiply that. The heuristic is scaled by the cheapest walkable cell in the window, which is what keeps it from overestimating on a weighted map — and an overestimating heuristic is exactly how a search stops being optimal.

Clearance. agentSize: 2 restricts the route to cells a two-by-two actor fits through. Clearance is anchored at a cell’s top-left corner, so the last row and column of a window can never hold an actor wider than one cell.

Smoothing. smooth: true string-pulls the staircase out of the result: it keeps a waypoint only where the straight line past it is blocked. The nodes it returns are no longer adjacent — the guarantee is that the straight segment between two consecutive ones stays walkable, and never crosses terrain more expensive than the section it replaces.

Jump-point search comes for free

On a uniform-cost grid with a one-cell actor and the default diagonal policy, the grid hands the search a pruned expansion: jump-point search. It skips whole runs of forced steps and returns the same cost-optimal path from a fraction of the expanded nodes. result.expandedNodes shows the difference, and the Grid Navigation example puts that counter on screen.

Nothing has to be switched on. Painting a single weighted cell switches it back off by itself, because its pruning rules only hold while every walkable cell costs the same.

Feeding it a tilemap

The package has no dependency on @codexo/exojs-tilemap, in either direction. The bridge is the cost callback, and it lives in your game:

// The pathfinding package has no tilemap dependency. The bridge is this
// function, which lives in the game and answers out of whatever the map stores.
const walkCost = (tile: ResolvedTile | null): number => {
  if (tile === null) return 0;

  const definition = tile.tileset.getTileDefinition(tile.localTileId);

  // A tile with authored collision geometry is solid; everything else is
  // walkable, with the terrain's own cost if the map carries one.
  if (definition?.collision !== undefined) return 0;

  return typeof definition?.properties?.moveCost === 'number' ? definition.properties.moveCost : 1;
};

const navigation = GridSpace.from(loaded.width, loaded.height, (x, y) => walkCost(ground.getTileAt(x, y)), {
  originX: loaded.x,
  originY: loaded.y,
  cellSize: ground.tileWidth,
});

Keep the two in step wherever you edit the map:

const setTile = (x: number, y: number, tile: ResolvedTile): void => {
  ground.setTileAt(x, y, tile);
  navigation.setCost(x, y, walkCost(tile));
};

The Tilemap Navigation example does exactly this against a live TileLayer.

Reachable areas

floodFrom walks outwards from a node and reports everything within a cost budget, cheapest first — the “which tiles can this unit still reach” query a turn-based game needs, and the input a flow field for many actors heading to one goal would be built from.

const region = pathfinder.floodFrom(grid, grid.nodeAt(unit.tileX, unit.tileY), {
  maxCost: unit.movement,
});

for (let index = 0; index < region.nodes.length; index++) {
  const node = region.nodes[index]!;

  highlight(grid.nodeX(node), grid.nodeY(node), region.costs[index]!);
}

Determinism and cost

Equal-cost paths are resolved by a pinned tie-break, so the same query on an unmutated grid returns the identical path on every run and every machine. That is what makes a path safe to record in a replay or assert in a test.

One Pathfinder reuses its search buffers across every query, including queries against different spaces of different sizes, so a search allocates nothing that scales with the nodes it visits. The result object is fresh every time — you keep paths, and pooling something you keep is how use-after-reuse bugs happen.

Share a pathfinder freely; just do not mutate a space while a query against it is running.