TypeScript port of Polyanya — compromise-free any-angle pathfinding on navigation meshes.
Based on the algorithm from Cui, Harabor & Grastien, "Compromise-free Pathfinding on a Navigation Mesh" (IJCAI 2017).
bun add polyanyaimport { Mesh, SearchInstance } from "polyanya"
const mesh = Mesh.fromString(`mesh
2
5 4
0 1 3 -1 1 0
1 0 3 -1 0 3
0 -1 3 -1 3 2
-1 0 3 -1 2 1
0 0 4 0 1 2 3
3 4 1 0 1 3 -1
3 4 0 3 2 0 -1
3 4 3 2 3 1 -1
3 4 2 1 0 2 -1`)
const search = new SearchInstance(mesh)
search.setStartGoal({ x: 0.5, y: 0.5 }, { x: -0.5, y: -0.5 })
search.search()
const path = search.getPathPoints()
// [{ x: 0.5, y: 0.5 }, { x: -0.5, y: -0.5 }]Build a navigation mesh from rectangular obstacles using the built-in CDT builder:
import { cdtTriangulate, rectToPolygon, buildMeshFromRegions, SearchInstance } from "polyanya"
const obstacles = [
rectToPolygon(0, 0, 4, 4, 0.5), // rect at (0,0), size 4x4, clearance 0.5
]
const regions = cdtTriangulate({
bounds: { minX: -10, maxX: 10, minY: -10, maxY: 10 },
obstacles,
})
const mesh = buildMeshFromRegions({ regions })
const search = new SearchInstance(mesh)
search.setStartGoal({ x: -8, y: 0 }, { x: 8, y: 0 })
search.search()
const path = search.getPathPoints()
const cost = search.getCost()Step through the algorithm one node at a time to visualize internals:
import { Mesh, SearchInstance, StepEventType } from "polyanya"
const mesh = Mesh.fromString(meshData)
const search = new SearchInstance(mesh)
search.setStartGoal(start, goal)
// Initialize search
const initEvents = search.searchInit()
// Step one node at a time
while (!search.isSearchComplete()) {
const events = search.step()
for (const event of events) {
switch (event.type) {
case StepEventType.NODE_POPPED:
console.log("Popped:", event.node)
break
case StepEventType.NODE_EXPANDED:
console.log("Expanded:", event.successors?.length, "successors")
break
case StepEventType.NODE_PUSHED:
console.log("Pushed:", event.node)
break
case StepEventType.NODE_PRUNED:
console.log("Pruned:", event.message)
break
case StepEventType.GOAL_REACHED:
console.log("Goal reached!")
break
}
}
}
// Get the open list at any point
const openNodes = search.getOpenListNodes()Load .mesh files (version 2 format):
const meshData = await Bun.file("arena.mesh").text()
const mesh = Mesh.fromString(meshData)Build from convex polygon regions:
import { buildMeshFromRegions, SearchInstance } from "polyanya"
const mesh = buildMeshFromRegions({
regions: [
[{ x: 0, y: 0 }, { x: 1, y: 0 }, { x: 0, y: 1 }],
[{ x: 0, y: 0 }, { x: 0, y: 1 }, { x: -1, y: 0 }],
],
})
const search = new SearchInstance(mesh)Parse a .mesh file string.
Build a mesh from vertex and polygon arrays.
Build a mesh from convex regions (arrays of points in CCW order).
CDT-triangulate free space inside bounds around obstacle polygons. Returns triangle regions.
Expand a rectangle into a polygon with clearance buffer.
| Method | Description |
|---|---|
setStartGoal(start, goal) |
Set start and goal points |
search(): boolean |
Run full search, returns true if path found |
searchInit(): StepEvent[] |
Initialize step-through search |
step(): StepEvent[] |
Execute one search step |
isSearchComplete(): boolean |
Check if search is done |
getPathPoints(): Point[] |
Get path waypoints |
getCost(): number |
Get path cost (-1 if not found) |
getOpenListNodes(): SearchNode[] |
Get current open list |
getSearchTree(): SearchNode[] |
Get search tree from final node |
After a search, these fields are available on the SearchInstance:
nodesGenerated— Total nodes creatednodesPushed— Nodes pushed onto open listnodesPopped— Nodes popped from open listnodesPrunedPostPop— Nodes pruned after pop (root-level pruning)successorCalls— Times successor generation was called
| Event Type | Description |
|---|---|
INIT |
Search initialized |
NODE_POPPED |
Node removed from open list |
NODE_EXPANDED |
Node expanded, successors generated |
NODE_PUSHED |
Node pushed onto open list |
NODE_PRUNED |
Node pruned (better path to same root exists) |
GOAL_REACHED |
Goal polygon reached |
SEARCH_EXHAUSTED |
Open list empty, no path exists |
Polyanya finds optimal any-angle paths on navigation meshes:
- Point Location: Locate start and goal in the mesh using a slab-based spatial index
- Initial Nodes: Generate search intervals on all edges of the start polygon
- A* Search: Expand intervals through polygons using a priority queue
- Successor Generation: For each polygon, compute observable and non-observable intervals using orientation tests and binary search
- Collinear Collapsing: When a single successor has the same root, skip the open list and expand immediately
- Root Pruning: Track best g-value per root vertex to prune dominated nodes
The algorithm guarantees optimal paths with no grid artifacts or suboptimal compromises.
Version 2 .mesh files:
mesh
2
V P # vertex count, polygon count
x y n p0 p1 ... pn-1 # per vertex: position, neighbor polygons (-1 = obstacle)
n v0 v1 ... vn-1 p0 p1 ... # per polygon: vertices (CCW), adjacent polygons
See the examples/ directory:
basic-search.ts— Simple pathfindingstep-through.ts— Algorithm step visualizationarena-pathfinding.ts— Larger mesh from Dragon Age: Originswith-convex-regions.ts— Building a mesh from obstacles
Run with:
bun examples/basic-search.ts
bun examples/step-through.ts- Algorithm: Cui, Harabor & Grastien (IJCAI 2017)
- C++ reference: bitbucket.org/dharabor/pathfinding