Fast 2D pathfinding library using triangulated navmesh
npm install path-finding-2dFast library for pathfinding in 2D space using triangulated navmesh based on poly-math-2d.
- ✅ Fast pathfinding through triangulated polygons using A* algorithm
- ✅ Complex polygon support including polygons with holes
- ✅ Path optimization using string-pulling algorithm
- ✅ TypeScript support with full type definitions
- ✅ Minimal dependencies - only poly-math-2d
- ✅ High performance - optimized for speed
``bash`
npm install path-finding-2d
`typescript
import { Point, Polygon, PolygonMap } from 'poly-math-2d';
import { NavMesh2d } from 'path-finding-2d';
// Create points for polygon with a hole (as in visualization example)
const outerPoints = [
new Point(50, 50),
new Point(300, 50),
new Point(300, 300),
new Point(50, 300)
];
const holePoints = [
new Point(125, 125),
new Point(225, 125),
new Point(225, 225),
new Point(125, 225)
];
// Create a polygon with a hole
const hole = new Polygon(holePoints);
const polygonWithHole = new Polygon(outerPoints, [hole]);
// Create polygon map and navmesh
const polygonMap = new PolygonMap([polygonWithHole]);
const navMesh = new NavMesh2d(polygonMap);
// Find path between two points
const start = new Point(100, 100);
const end = new Point(250, 250);
const path = navMesh.findPath(start, end);
console.log(path); // Array of path points
`
Main class for working with navmesh.
#### Constructor
`typescript`
constructor(polygonMap: PolygonMap)
Creates a navmesh from a polygon map. PolygonMap should contain polygons that are already triangulated by the poly-math-2d library.
#### Methods
##### isPointInNavMesh(point: Point): boolean
Checks if a point is inside the navmesh.
Parameters:
- point - point to check
Returns: true if the point is inside the navmesh, otherwise false
##### findPath(a: Point, b: Point): Point[]
Finds a path from point A to point B.
Parameters:
- a - start pointb
- - end point
Returns: Array of points representing the path. Empty array if no path is found.
Behavior details:
- If point A is not in the navmesh, returns an empty array
- If point B is not in the navmesh or in hole, finds path to the closest point in the same polygon where A is located
- If A and B are in the same triangle, returns a direct path
- Path is optimized to remove unnecessary points
The library uses the following approach for pathfinding:
1. Triangulation: Polygons are automatically triangulated by poly-math-2d library
2. Neighborhood Graph: Triangles are connected through shared edges (connections in TPolygon)
3. A-star Search: Uses A* algorithm to find optimal path through triangles
4. String Pulling Optimization: Applies advanced string-pulling algorithm to find shortest path through portal edges between triangles
5. Portal System: Uses shared triangle edges as "portals" for optimal traversal
6. Intelligent Optimization: Automatically cuts corners and finds the most efficient route within the navmesh
The library is optimized for maximum speed:
- Uses fast distance calculation algorithms (getDistanceQuick, getDistanceSquared`)
- Pre-calculated triangle centers
- Barycentric coordinates for point-in-triangle checks
- Efficient data structure for A* search
- Advanced String Pulling: Finds optimal paths through portal edges
- Intelligent Optimization: Automatically skips intermediate points when direct path is possible
- Geometric Optimization: Uses projections and vector calculations for precise positioning
MIT
- poly-math-2d - Library for working with 2D polygons, triangulation, and boolean operations