Pathfinding

@casko/pathfinding is a TypeScript library for 2D grid pathfinding. It provides a shared typed API and implementations of:

• A*
• BFS
• Dijkstra
• Greedy Best-First Search
• Jump Point Search
• Theta*

Install

npm install @casko/pathfinding

Demo

Run the visual browser demo locally:

npm install
npm run demo

Create a static demo bundle:

npm run demo:build

Quick Start

import { astar, type GridLike } from "@casko/pathfinding";

const grid: GridLike = {
  isUniformCost: true,
  isWithinBounds: ({ x, y }) => x >= 0 && x < 10 && y >= 0 && y < 10,
  isWalkableAt: ({ x, y }) => !(x === 4 && y >= 2 && y <= 7),
  getCost: () => 1,
};

const result = astar(grid, {
  start: { x: 0, y: 0 },
  goal: { x: 9, y: 9 },
  diagonalMovement: "always",
});

if (result.found) {
  console.log(result.path, result.cost);
}

API

All algorithms are pure functions that accept a GridLike and SearchOptions, then return a SearchResult.

GridLike

interface GridLike {
  isWithinBounds(coordinate: GridCoordinate): boolean;
  isWalkableAt(coordinate: GridCoordinate): boolean;
  getCost(from: GridCoordinate, to: GridCoordinate): number;
  hasLineOfSight?(from: GridCoordinate, to: GridCoordinate): boolean;
  isUniformCost?: boolean;
}

SearchOptions

interface SearchOptions {
  start: GridCoordinate;
  goal: GridCoordinate;
  diagonalMovement?: "never" | "always" | "ifAtMostOneObstacle" | "onlyWhenNoObstacles";
  heuristic?: Heuristic;
  heuristicWeight?: number;
  maxIterations?: number;
}

SearchResult

interface SearchResult {
  found: boolean;
  path: GridCoordinate[];
  cost: number;
  visited: number;
  expanded: number;
  metadata: {
    algorithm: string;
    frontierPeak: number;
    pathLength: number;
  };
}

Heuristics

The package exports:

• manhattan
• euclidean
• octile
• defaultHeuristic

If no heuristic is provided, orthogonal searches use Manhattan distance and diagonal-enabled searches use Octile distance.

Diagonal Movement

Supported diagonal movement policies:

• never
• always
• ifAtMostOneObstacle
• onlyWhenNoObstacles

Algorithm Notes

• bfs is optimal only for unweighted movement.
• dijkstra finds the least-cost path for non-negative weights.
• astar matches Dijkstra’s optimality when the heuristic is admissible.
• greedyBestFirst is often faster but may return non-optimal paths.
• jumpPointSearch only supports uniform-cost grids. Set grid.isUniformCost to false for weighted grids so unsupported usage fails fast.
• thetaStar uses grid.hasLineOfSight when available. Otherwise it falls back to a built-in Bresenham-style visibility check over walkable cells.

Errors And Failure Cases

• Invalid or non-walkable start/goal coordinates throw an error.
• When no route exists, algorithms return found: false, an empty path, and cost: Infinity.