@web-engine-dev/pathfinding

Navigation and pathfinding systems including A*, JPS, HPA*, flow fields, NavMesh, and RVO.

Features

• A* Pathfinding: Classic grid-based pathfinding
• Jump Point Search: Optimized A* for uniform grids
• HPA*: Hierarchical pathfinding for large maps
• Flow Fields: Group movement for many agents
• NavMesh: 3D navigation mesh pathfinding
• RVO: Reciprocal Velocity Obstacles for avoidance

Installation

npm install @web-engine-dev/pathfinding
# or
pnpm add @web-engine-dev/pathfinding

Quick Start

import { Grid, AStar, NavMesh } from '@web-engine-dev/pathfinding';

// Grid-based pathfinding
const grid = new Grid(100, 100);
grid.setWalkable(5, 5, false); // Add obstacle

const astar = new AStar(grid);
const path = astar.findPath({ x: 0, y: 0 }, { x: 50, y: 50 });

// NavMesh pathfinding
const navmesh = NavMesh.fromGeometry(levelGeometry);
const path3d = navmesh.findPath(start, end);

API Overview

Grid

const grid = new Grid(width, height, {
  defaultWalkable: true,
  diagonal: true,
  diagonalCost: 1.414,
});

grid.setWalkable(x, y, walkable);
grid.setCost(x, y, cost);
grid.isWalkable(x, y);

A* Algorithm

const astar = new AStar(grid, {
  heuristic: 'manhattan', // 'manhattan', 'euclidean', 'octile'
  diagonalMovement: true,
  maxIterations: 10000,
});

const path = astar.findPath(start, end);

Jump Point Search

const jps = new JumpPointSearch(grid);
const path = jps.findPath(start, end);
// Much faster than A* for uniform-cost grids

Flow Fields

const flowField = new FlowField(grid);
flowField.setGoal(goalX, goalY);
flowField.build();

// Get direction at any point
const direction = flowField.getDirection(x, y);

NavMesh

const navmesh = NavMesh.fromGeometry(geometry);

const path = navmesh.findPath(start, end);
const smoothPath = navmesh.smooth(path);

// Check if point is on navmesh
const onMesh = navmesh.isPointOnMesh(point);

// Get nearest point on navmesh
const closest = navmesh.getClosestPoint(point);

RVO (Collision Avoidance)

const rvo = new RVOSimulator({
  timeHorizon: 2.0,
  neighborDist: 5.0,
  maxNeighbors: 10,
});

rvo.addAgent(position, velocity, radius);
rvo.setGoal(agentId, targetPosition);
rvo.update(deltaTime);

const newVelocity = rvo.getAgentVelocity(agentId);