!./docs/cover.png

!GitHub Workflow Status (with event)

``bash
> npm install navcat
`

navcat

navcat is a javascript navigation mesh construction and querying library for 3D floor-based navigation.

navcat is ideal for use in games, simulations, and creative websites that require navigation in complex 3D environments.

Features

- Navigation mesh generation from 3D geometry
- Navigation mesh querying
- Single and multi-tile navigation mesh support
- Fully JSON serializable data structures
- Pure javascript, written to be highly tree-shakeable
- Works with any javascript engine/library - Babylon.js, PlayCanvas, Three.js, or your own engine

Documentation

This README provides curated explanations, guides, and examples to help you get started with navcat.

API documentation can be found at navcat.dev/docs.

Installation

navcat is available on npm:

`bash
npm install navcat
`

An example of using navcat without any build tools using unpkg can be found here: https://github.com/isaac-mason/navcat-vanilla-html-js-example

Changelog

See the CHANGELOG.md for a detailed list of changes in each version.

> _NOTE:_ This library is under active development. In the leadup to a v1 release, you can expect APIs to improve and change in minor versions.

Examples

Crowd Simulation	NavMesh Constrained Character Controller	Area Filters
Area Costs	Doors and Keys	Dynamic Obstacles
Dynamic NavMesh	FPS Dynamic NavMesh	Multiple Agent Sizes
Crowd Simulation Stress Test	Flow Field Pathfinding	Find Path
Find Node Path	Find Straight Path	Find Smooth Path
Find Shortest Paths	Find Diverse Paths	Raycast
Off-Mesh Connections	Upload Model	Custom GLTF NavMesh
Solo NavMesh	Tiled NavMesh	Flood Fill Pruning
Find Nearest Poly	Find Random Point	Find Random Point Around Circle
Mark Compact Heightfield Areas	Custom NavMesh Generation	Move Along Surface
Chunky Tri Mesh

Table of Contents

- What is a Navigation Mesh?
- Can navcat be integrated with my engine/library?
- Quick Start / Minimal Example
- Navigation Mesh Querying
- findPath
- findSmoothPath
- findNodePath
- findStraightPath
- moveAlongSurface
- raycast & raycastWithCosts
- findNearestPoly
- findRandomPoint
- findRandomPointAroundCircle
- Crowd Simulation
- Custom Pathfinding Algorithms
- Navigation Mesh Generation
- Overview
- The Structure of a Navigation Mesh
- Single-Tile vs Tiled Navigation Meshes
- Generation Presets
- Generation Process: Deep Dive
- 0. Input and setup
- 1. Mark walkable triangles
- 2. Rasterize triangles into a heightfield, do filtering with the heightfield
- 3. Build compact heightfield, erode walkable area, mark areas
- 4. Build compact heightfield regions
- 5. Build contours from compact heightfield regions
- 6. Build polygon mesh from contours, build detail mesh
- 7. Convert build-time poly mesh and poly mesh detail to runtime navmesh tile format
- 8. Assemble the navigation mesh
- Post-Processing
- Custom Query Filters and Custom Area Types
- Off-Mesh Connections
- Advanced Navigation Mesh APIs
- isValidNodeRef
- getNodeByRef
- getNodeByTileAndPoly
- getPolyHeight
- getClosestPointOnPoly
- getClosestPointOnDetailEdges
- getPortalPoints
- queryPolygons
- queryPolygonsInTile
- Using Externally Created Navigation Meshes
- Saving and Loading NavMeshes
- Debug Utilities
- navcat/three
- How does navcat compare to other libraries?
- Community
- Acknowledgements

What is a Navigation Mesh?

A navigation mesh (or navmesh) is a simplified representation of a 3D environment that is used for pathfinding and AI navigation in video games and simulations. It consists of interconnected polygons that define walkable areas within the environment. These polygons are connected by edges and off-mesh connections, allowing agents (characters) to move from one polygon to another.

!./docs/1-whats-a-navmesh

Can navcat be integrated with my engine/library?

navcat is agnostic of rendering or game engine library, so it will work well with any javascript engine - Babylon.js, PlayCanvas, Three.js, or your own engine.

If you are using threejs, you may make use of the utilities in the navcat/three entrypoint, see the navcat/three docs. Integrations for other engines may be added in future.

navcat adheres to the OpenGL conventions:

- Uses the right-handed coordinate system
- Indices should be in counter-clockwise winding order

If you are importing a navmesh created externally, note that navmesh poly vertices must be indexed / must share vertices between adjacent polygons.

If your environment uses a different coordinate system, you will need to transform coordinates going into and out of navcat.

The examples use threejs for rendering, but the core navcat APIs are completely agnostic of any rendering or game engine libraries.

Quick Start / Minimal Example

Below is a minimal example of using the presets in navcat/blocks to generate a navigation mesh, and then using APIs in navcat to find a path on the generated navmesh.

For information on how to tune these options, and how the generation process works under the hood with images, see the Navigation mesh generation section below.

If you are using threejs, you can find a threejs-specific version of this snippet in the navcat/three section.

`ts
import { DEFAULT_QUERY_FILTER, findPath, type Vec3 } from 'navcat';
import { generateSoloNavMesh, type SoloNavMeshInput, type SoloNavMeshOptions } from 'navcat/blocks';

/ generation input /
// populate positions and indices with your level geometry
// don't include geometry that shouldn't contribute to walkable-surface
// generation, like foliage or small decorative props
const positions = new Float32Array([
/ ... /
]);
const indices = new Uint32Array([
/ ... /
]);

const input: SoloNavMeshInput = {
positions,
indices,
};

/ generation options /
// the following are defaults you might start from for a human-sized agent in a 1 m scale world.
// it's generally recommended that you use the library debug helpers to visualize the navmesh
// generation and fine tune these parameters.

// heightfield parameters
const cellSize = 0.15;
const cellHeight = 0.25;

// agent parameters
const walkableRadiusWorld = 0.3;
const walkableHeightWorld = 2.0;
const walkableClimbWorld = 0.5;
const walkableSlopeAngleDegrees = 45;

const walkableRadiusVoxels = Math.ceil(walkableRadiusWorld / cellSize);
const walkableClimbVoxels = Math.ceil(walkableClimbWorld / cellHeight);
const walkableHeightVoxels = Math.ceil(walkableHeightWorld / cellHeight);

// compact heightfield region parameters
const minRegionArea = 8;
const mergeRegionArea = 20;

// polygon generation parameters
const maxSimplificationError = 1.3;
const maxEdgeLength = 12;
const maxVerticesPerPoly = 5;

// detail mesh generation parameters
const detailSampleDistanceVoxels = 6;
const detailSampleMaxErrorVoxels = 1;

const detailSampleDistance = detailSampleDistanceVoxels < 0.9 ? 0 : cellSize * detailSampleDistanceVoxels;
const detailSampleMaxError = cellHeight * detailSampleMaxErrorVoxels;

// border size around each tile, in voxels. 0 for solo navmesh.
const borderSize = 0;

const options: SoloNavMeshOptions = {
cellSize,
cellHeight,
walkableRadiusWorld,
walkableRadiusVoxels,
walkableClimbWorld,
walkableClimbVoxels,
walkableHeightWorld,
walkableHeightVoxels,
walkableSlopeAngleDegrees,
borderSize,
minRegionArea,
mergeRegionArea,
maxSimplificationError,
maxEdgeLength,
maxVerticesPerPoly,
detailSampleDistance,
detailSampleMaxError,
};

/ generate the navmesh /
const result = generateSoloNavMesh(input, options);

const navMesh = result.navMesh; // the nav mesh
const intermediates = result.intermediates; // intermediate data for debugging

console.log('generated navmesh:', navMesh, intermediates);

/ find a path /
const start: Vec3 = [-4, 0, -4];
const end: Vec3 = [4, 0, 4];
const halfExtents: Vec3 = [0.5, 0.5, 0.5];

const path = findPath(navMesh, start, end, halfExtents, DEFAULT_QUERY_FILTER);

console.log(
'path:',
path.path.map((p) => p.position),
);
`

Below is a quick summary of the navmesh generation parameters used above, and how to start tuning them:

| Parameter | Description | Range / Heuristic for 1 = 1m humanoid agents |
| --------------------------- | ----------------------------------------------------------------------------------------------------------------- | -------------------------------------------- |
| cellSize | Horizontal voxel size (XZ). Smaller = finer detail, slower generation. | ≈ walkableRadiusWorld / 3 |
| cellHeight | Vertical voxel size (Y). Controls height resolution. | ≈ walkableClimbWorld / 2 |
| walkableRadiusWorld | Agent radius (half-width). Determines clearance around walls. | 0.2–0.5 m |
| walkableHeightWorld | Agent height. Areas with ceilings lower than this are excluded. | 1.6–2.0 m |
| walkableSlopeAngleDegrees | Max slope angle the agent can walk. This filters out input triangles at the very beginning of navmesh generation. | 35–50° |
| walkableClimbWorld | Max step height. Allows stepping up/down small edges. This filters at the heightfield navmesh generation stage. | 0.3–0.5 m |
| minRegionArea | Smallest isolated region kept. | 4–16 voxels |
| mergeRegionArea | Regions smaller than this merge into neighbors. | 8–32 voxels |
| maxSimplificationError | Edge simplification tolerance (higher = simpler mesh). | 1–2 |
| maxEdgeLength | Max polygon edge length before splitting. | 8–24 |
| maxVerticesPerPoly | Max vertices per polygon. | 3–6 |
| detailSampleDistance | Distance between height samples (affects vertical detail). | cellSize * 4–8, e.g. 0.9 |
| detailSampleMaxError | Allowed height deviation when simplifying detail mesh. | cellHeight * 1–2, e.g. 0.25 |

Navigation Mesh Querying

This section covers the main features you'll use for navigation mesh querying, including pathfinding, agent simulation, and spatial queries on your navigation mesh. For lower-level querying APIs and navmesh internals, see the Advanced Navigation Mesh APIs section.

$3

The findPath function is a convenience wrapper around findNearestPoly, findNodePath, and findStraightPath to get a path between two points on the navigation mesh.

When to use: This is the simplest way to find a complete path. Use this for one-off pathfinding queries, or when you aren't steering agents along a path and re-querying frequently.

`ts
const start: Nav.Vec3 = [1, 0, 1];
const end: Nav.Vec3 = [8, 0, 8];
const halfExtents: Nav.Vec3 = [0.5, 0.5, 0.5];

// find a path from start to end
const findPathResult = Nav.findPath(navMesh, start, end, halfExtents, Nav.DEFAULT_QUERY_FILTER);

if (findPathResult.success) {
const points = findPathResult.path.map((p) => p.position);
console.log('path points:', points); // [ [x1, y1, z1], [x2, y2, z2], ... ]
}
`

`ts
/**
* Find a path between two positions on a NavMesh.
*
* If the end node cannot be reached through the navigation graph,
* the last node in the path will be the nearest the end node.
*
* Internally:
* - finds the closest poly for the start and end positions with @see findNearestPoly
* - finds a nav mesh node path with @see findNodePath
* - finds a straight path with @see findStraightPath
*
* If you want more fine tuned behaviour you can call these methods directly.
* For example, for agent movement you might want to find a node path once but regularly re-call @see findStraightPath
*
* @param navMesh The navigation mesh.
* @param start The starting position in world space.
* @param end The ending position in world space.
* @param queryFilter The query filter.
* @returns The result of the pathfinding operation.
*/
export function findPath(navMesh: NavMesh, start: Vec3, end: Vec3, halfExtents: Vec3, queryFilter: QueryFilter): FindPathResult;
`

findPath API Documentation →

Find Path

$3

Combines findNodePath, findStraightPath, and moveAlongSurface to produce a smooth path that respects the navmesh surface.

When to use: Use this when you want a smooth path that follows the navmesh surface without sharp corners, and you need it infrequently (e.g. for visual previews, not for many agents per frame).

`ts
/**
* Find a smooth path between two positions on a NavMesh.
*
* This method computes a smooth path by iteratively moving along the navigation
* mesh surface using the polygon path found between start and end positions.
* The resulting path follows the surface more naturally than a straight path.
*
* If the end node cannot be reached through the navigation graph,
* the path will go as far as possible toward the target.
*
* Internally:
* - finds the closest poly for the start and end positions with @see findNearestPoly
* - finds a nav mesh node path with @see findNodePath
* - computes a smooth path by iteratively moving along the surface with @see moveAlongSurface
*
* @param navMesh The navigation mesh.
* @param start The starting position in world space.
* @param end The ending position in world space.
* @param halfExtents The half extents for nearest polygon queries.
* @param queryFilter The query filter.
* @param stepSize The step size for movement along the surface
* @param slop The distance tolerance for reaching waypoints
* @returns The result of the smooth pathfinding operation, with path points containing position, type, and nodeRef information.
*/
export function findSmoothPath(navMesh: NavMesh, start: Vec3, end: Vec3, halfExtents: Vec3, queryFilter: QueryFilter, stepSize: number, slop: number, maxPoints: number): FindSmoothPathResult;
`

findSmoothPath API Documentation →

Find Smooth Path

$3

Finds a path through the navigation mesh as a sequence of polygon and offmesh connection node references.

When to use: Use this when you want to cache a node path and recalculate the straight path multiple times (e.g., for dynamic agent movement where the start position changes but the destination stays the same). This is more efficient than calling findPath repeatedly.

`ts
const start: Nav.Vec3 = [1, 0, 1];
const end: Nav.Vec3 = [8, 0, 8];
const halfExtents: Nav.Vec3 = [0.5, 0.5, 0.5];

// find the nearest nav mesh poly node to the start position
const startNode = Nav.findNearestPoly(
Nav.createFindNearestPolyResult(),
navMesh,
start,
halfExtents,
Nav.DEFAULT_QUERY_FILTER,
);

// find the nearest nav mesh poly node to the end position
const endNode = Nav.findNearestPoly(Nav.createFindNearestPolyResult(), navMesh, end, halfExtents, Nav.DEFAULT_QUERY_FILTER);

// find a "node" path from start to end
if (startNode.success && endNode.success) {
const nodePath = Nav.findNodePath(
navMesh,
startNode.nodeRef,
endNode.nodeRef,
startNode.position,
endNode.position,
Nav.DEFAULT_QUERY_FILTER,
);

console.log(nodePath.success); // true if a partial or full path was found
console.log(nodePath.path); // [0, 1, 2, ... ]
}
`

`ts
/**
* Find a path between two nodes.
*
* If the end node cannot be reached through the navigation graph,
* the last node in the path will be the nearest the end node.
*
* The start and end positions are used to calculate traversal costs.
* (The y-values impact the result.)
*
* @param startNodeRef The reference ID of the starting node.
* @param endNodeRef The reference ID of the ending node.
* @param startPosition The starting position in world space.
* @param endPosition The ending position in world space.
* @param filter The query filter.
* @returns The result of the pathfinding operation.
*/
export function findNodePath(navMesh: NavMesh, startNodeRef: NodeRef, endNodeRef: NodeRef, startPosition: Vec3, endPosition: Vec3, filter: QueryFilter): FindNodePathResult;
`

findNodePath API Documentation →

$3

Performs "string pulling" to convert a sequence of nodes into a series of waypoints that form the actual path an agent should follow.

When to use: Call this after findNodePath to get the actual waypoint positions. You might recalculate this frequently while keeping the same node path, or when implementing custom path following behavior.

`ts
const start: Nav.Vec3 = [1, 0, 1];
const end: Nav.Vec3 = [8, 0, 8];

// array of nav mesh node refs, often retrieved from a call to findNodePath
const findStraightPathNodes: Nav.NodeRef[] = [
/ ... /
];

// find the nearest nav mesh poly node to the start position
const straightPathResult = Nav.findStraightPath(navMesh, start, end, findStraightPathNodes);

console.log(straightPathResult.success); // true if a partial or full path was found
console.log(straightPathResult.path); // [ { position: [x, y, z], nodeType: NodeType, nodeRef: NodeRef }, ... ]
`

`ts
/**
* This method peforms what is often called 'string pulling'.
*
* The start position is clamped to the first polygon node in the path, and the
* end position is clamped to the last. So the start and end positions should
* normally be within or very near the first and last polygons respectively.
*
* @param navMesh The navigation mesh to use for the search.
* @param start The start position in world space.
* @param end The end position in world space.
* @param pathNodeRefs The list of polygon node references that form the path, generally obtained from findNodePath
* @param maxPoints The maximum number of points to return in the straight path. If null, no limit is applied.
* @param straightPathOptions @see FindStraightPathOptions
* @returns The straight path
*/
export function findStraightPath(navMesh: NavMesh, start: Vec3, end: Vec3, pathNodeRefs: NodeRef[], maxPoints: number | null = null, straightPathOptions = 0): FindStraightPathResult;
`

findStraightPath API Documentation →

$3

Moves along a navmesh from a start position toward an end position along the navmesh surface, constrained to walkable areas.

This should be called with small movement deltas (e.g., per frame) to move an agent while respecting the navmesh boundaries.

When to use: Perfect for simple character controllers where you want to constrain movement to the navmesh without full pathfinding. Ideal for local movement, sliding along walls, or implementing custom movement logic that respects the navmesh.

`ts
const start: Nav.Vec3 = [1, 0, 1];
const end: Nav.Vec3 = [8, 0, 8];
const halfExtents: Nav.Vec3 = [0.5, 0.5, 0.5];

const startNode = Nav.findNearestPoly(
Nav.createFindNearestPolyResult(),
navMesh,
start,
halfExtents,
Nav.DEFAULT_QUERY_FILTER,
);

const moveAlongSurfaceResult = Nav.moveAlongSurface(navMesh, startNode.nodeRef, start, end, Nav.DEFAULT_QUERY_FILTER);

console.log(moveAlongSurfaceResult.success); // true if the move was successful
console.log(moveAlongSurfaceResult.position); // the resulting position after the move [x, y, z]
console.log(moveAlongSurfaceResult.nodeRef); // the resulting poly node ref after the move, or 0 if none
console.log(moveAlongSurfaceResult.visited); // array of node refs that were visited during the move
`

`ts
/**
* Moves from start position towards end position along the navigation mesh surface.
*
* This method is optimized for small delta movement and a small number of
* polygons. If used for too great a distance, the result set will form an
* incomplete path.
*
* The resultPosition will equal the endPosition if the end is reached.
* Otherwise the closest reachable position will be returned.
*
* The resulting position is projected onto the surface of the navigation mesh with @see getPolyHeight.
*
* @param navMesh The navigation mesh
* @param startNodeRef The reference ID of the starting polygon
* @param startPosition The starting position [(x, y, z)]
* @param endPosition The ending position [(x, y, z)]
* @param filter The query filter.
* @returns Result containing status, final position, and visited polygons
*/
export function moveAlongSurface(navMesh: NavMesh, startNodeRef: NodeRef, startPosition: Vec3, endPosition: Vec3, filter: QueryFilter): MoveAlongSurfaceResult;
`

moveAlongSurface API Documentation →

NavMesh Constrained Character Controller

Move Along Surface

$3

Casts a ray along the navmesh surface to check for walkability and detect obstacles.

When to use: Check line-of-sight between positions, validate if a straight path exists, or detect walls/obstacles. Avoid using this for long rays; it's best suited for short-range checks given its two dimensional nature.

`ts
const start: Nav.Vec3 = [1, 0, 1];
const end: Nav.Vec3 = [8, 0, 8];
const halfExtents: Nav.Vec3 = [0.5, 0.5, 0.5];

const startNode = Nav.findNearestPoly(
Nav.createFindNearestPolyResult(),
navMesh,
start,
halfExtents,
Nav.DEFAULT_QUERY_FILTER,
);

const raycastResult = Nav.raycast(navMesh, startNode.nodeRef, start, end, Nav.DEFAULT_QUERY_FILTER);

console.log(raycastResult.t); // the normalized distance along the ray where an obstruction was found, or 1.0 if none
console.log(raycastResult.hitNormal); // the normal of the obstruction hit, or [0, 0, 0] if none
console.log(raycastResult.hitEdgeIndex); // the index of the edge of the poly that was hit, or -1 if none
console.log(raycastResult.path); // array of node refs that were visited during the raycast
`

`ts
/**
* Casts a 'walkability' ray along the surface of the navigation mesh from
* the start position toward the end position.
*
* This method is meant to be used for quick, short distance checks.
* The raycast ignores the y-value of the end position (2D check).
*
* @param navMesh The navigation mesh to use for the raycast.
* @param startNodeRef The NodeRef for the start polygon
* @param startPosition The starting position in world space.
* @param endPosition The ending position in world space.
* @param filter The query filter to apply.
* @returns The raycast result with hit information and visited polygons (without cost calculation).
*/
export function raycast(navMesh: NavMesh, startNodeRef: NodeRef, startPosition: Vec3, endPosition: Vec3, filter: QueryFilter): RaycastResult;
`

`ts
const start: Nav.Vec3 = [1, 0, 1];
const end: Nav.Vec3 = [8, 0, 8];
const halfExtents: Nav.Vec3 = [0.5, 0.5, 0.5];

const startNode = Nav.findNearestPoly(
Nav.createFindNearestPolyResult(),
navMesh,
start,
halfExtents,
Nav.DEFAULT_QUERY_FILTER,
);

// raycastWithCosts calculates path costs and requires the previous polygon reference
const prevRef = 0; // example
const raycastResult = Nav.raycastWithCosts(navMesh, startNode.nodeRef, start, end, Nav.DEFAULT_QUERY_FILTER, prevRef);

console.log(raycastResult.t); // the normalized distance along the ray where an obstruction was found, or 1.0 if none
console.log(raycastResult.hitNormal); // the normal of the obstruction hit, or [0, 0, 0] if none
console.log(raycastResult.hitEdgeIndex); // the index of the edge of the poly that was hit, or -1 if none
console.log(raycastResult.path); // array of node refs that were visited during the raycast
console.log(raycastResult.pathCost); // accumulated cost along the raycast path
`

`ts
/**
* Casts a 'walkability' ray along the surface of the navigation mesh from
* the start position toward the end position, calculating accumulated path costs.
*
* This method is meant to be used for quick, short distance checks.
* The raycast ignores the y-value of the end position (2D check).
*
* @param navMesh The navigation mesh to use for the raycast.
* @param startNodeRef The NodeRef for the start polygon
* @param startPosition The starting position in world space.
* @param endPosition The ending position in world space.
* @param filter The query filter to apply.
* @param prevRef The reference to the polygon we came from (for accurate cost calculations).
* @returns The raycast result with hit information, visited polygons, and accumulated path costs.
*/
export function raycastWithCosts(navMesh: NavMesh, startNodeRef: NodeRef, startPosition: Vec3, endPosition: Vec3, filter: QueryFilter, prevRef: NodeRef): RaycastResult;
`

raycast API Documentation →

raycastWithCosts API Documentation →

Raycast

$3

Finds the nearest polygon on the navmesh to a given world position.

When to use: This is often your first step - use it to "snap" world positions onto the navmesh before pathfinding or querying. Essential when placing agents, checking if a position is on the navmesh, or converting world coordinates to navmesh coordinates.

`ts
const position: Nav.Vec3 = [1, 0, 1];
const halfExtents: Nav.Vec3 = [0.5, 0.5, 0.5];

// find the nearest nav mesh poly node to the position
const findNearestPolyResult = Nav.createFindNearestPolyResult();
Nav.findNearestPoly(findNearestPolyResult, navMesh, position, halfExtents, Nav.DEFAULT_QUERY_FILTER);

console.log(findNearestPolyResult.success); // true if a nearest poly was found
console.log(findNearestPolyResult.nodeRef); // the nearest poly's node ref, or 0 if none found
console.log(findNearestPolyResult.position); // the nearest point on the poly in world space [x, y, z]
`

`ts
export function findNearestPoly(result: FindNearestPolyResult, navMesh: NavMesh, center: Vec3, halfExtents: Vec3, queryFilter: QueryFilter): FindNearestPolyResult;
`

findNearestPoly API Documentation →

Find Nearest Poly

$3

Finds a random walkable point anywhere on the navmesh.

When to use: Spawn points, random patrol destinations, procedural NPC placement, or testing. Great for open-world scenarios where agents need random destinations across the entire navigable area.

`ts
const randomPoint = Nav.findRandomPoint(navMesh, Nav.DEFAULT_QUERY_FILTER, Math.random);

console.log(randomPoint.success); // true if a random point was found
console.log(randomPoint.position); // [x, y, z]
console.log(randomPoint.nodeRef); // the poly node ref that the random point is on
`

`ts
/**
* Finds a random point on the navigation mesh.
* This function is using reservoir sampling and can fail in rare occurences even if there is an actual solution.
*
* @param navMesh The navigation mesh
* @param filter Query filter to apply to polygons
* @param rand Function that returns random values between [0,1]
* @returns The result object with success flag, random point, and polygon reference
*/
export function findRandomPoint(navMesh: NavMesh, filter: QueryFilter, rand: () => number): FindRandomPointResult;
`

findRandomPoint API Documentation →

Find Random Point

$3

Finds a random walkable point within a circular radius around a center position.

When to use: Local randomization like scatter formations, patrol areas around a point, or finding nearby positions. Perfect for "move near target" AI behaviors or creating natural-looking patrol patterns.

`ts
const center: Nav.Vec3 = [5, 0, 5];
const radius = 3.0; // world units

const halfExtents: Nav.Vec3 = [0.5, 0.5, 0.5];

const centerNode = Nav.findNearestPoly(
Nav.createFindNearestPolyResult(),
navMesh,
center,
halfExtents,
Nav.DEFAULT_QUERY_FILTER,
);

if (centerNode.success) {
const randomPointAroundCircle = Nav.findRandomPointAroundCircle(
navMesh,
centerNode.nodeRef,
center,
radius,
Nav.DEFAULT_QUERY_FILTER,
Math.random,
);

console.log(randomPointAroundCircle.success); // true if a random point was found
console.log(randomPointAroundCircle.position); // [x, y, z]
console.log(randomPointAroundCircle.nodeRef); // the poly node ref that the random point is on
}
`

`ts
/**
* Finds a random point around a center position on the navigation mesh.
* The location is not exactly constrained by the circle, but it limits the visited polygons.
*
* Uses Dijkstra-like search to explore reachable polygons within the circle,
* then selects a random polygon weighted by area, and finally generates
* a random point within that polygon.
* This function is using reservoir sampling and can fail in rare occurences even if there is an actual solution.
*
* @param navMesh The navigation mesh
* @param startNodeRef Reference to the polygon to start the search from
* @param position Center position of the search circle
* @param maxRadius Maximum radius of the search circle
* @param filter Query filter to apply to polygons
* @param rand Function that returns random values [0,1]
* @returns The result object with success flag, random point, and polygon reference
*/
export function findRandomPointAroundCircle(navMesh: NavMesh, startNodeRef: NodeRef, position: Vec3, maxRadius: number, filter: QueryFilter, rand: () => number): FindRandomPointAroundCircleResult;
`

findRandomPointAroundCircle API Documentation →

Find Random Point Around Circle

Crowd Simulation

The crowd API in navcat/blocks provides a high-level agent simulation system built on top of navcat's pathfinding and local steering capabilities.

For simple use cases you can use it directly, and for more advanced use cases you might copy it into your project and modify it as needed.

- Agent management: add/remove agents, set target positions or velocities
- Frame-distributed pathfinding to maintain performance with many agents
- Agent-to-agent and wall avoidance
- Off-mesh connection support with animation hooks

It internally makes use of other navcat/blocks APIs like pathCorridor, localBoundary, and obstacleAvoidance to manage agent node corridors and handle obstacle avoidance.

See the docs for API specifics:

- crowd: https://navcat.dev/docs/modules/navcat_blocks.crowd.html
- pathCorridor: https://navcat.dev/docs/modules/navcat_blocks.pathCorridor.html
- localBoundary: https://navcat.dev/docs/modules/navcat_blocks.localBoundary.html
- obstacleAvoidance: https://navcat.dev/docs/modules/navcat_blocks.obstacleAvoidance.html

And see the below for interactive examples:

Crowd Simulation

Crowd Simulation Stress Test

Custom Pathfinding Algorithms

If your use case is not covered by built-in high level APIs, navcat provides lower-level access to the navigation mesh structure to enable building custom pathfinding algorithms.

The Advanced Navigation Mesh APIs section below covers APIs for working with the navigation mesh structure.

See the examples below for demonstrations of userland pathfinding algorithms:

Flow Field Pathfinding

Find Shortest Paths

Find Diverse Paths

Navigation Mesh Generation

$3

Navigation mesh generation is the process of transforming 3D geometry into a graph of walkable polygons. This graph is then used for pathfinding and navigation queries.

#### The Structure of a Navigation Mesh

A navigation mesh is organized into one or more tiles. Each tile contains walkable polygons and height detail information. For most projects, a single tile covering your entire level is perfect. For larger or dynamic worlds, you can split the navmesh into a grid of tiles.

Behind the scenes, navcat maintains a graph of nodes (representing polygons) and links (representing connections between polygons). This graph is what powers pathfinding - when you query for a path, navcat searches this graph to find the route.

If you want to dig deeper into the internal structure (useful for advanced cases like building custom pathfinding algorithms), the navigation mesh data is fully accessible. Check out the "Flow Field Pathfinding" example to see custom graph traversal in action.

#### Single-Tile vs Tiled Navigation Meshes

Most projects should start with a single-tile navmesh - it's simpler and covers the majority of use cases.

Consider using tiled navmeshes when you need:

- Dynamic updates (rebuild only affected tiles when geometry changes)
- Memory management (stream tiles in/out based on player location)
- Parallel generation (generate tiles independently)
- Large worlds (tiled navmesh generation can give better results over large areas)

For smaller, static scenes, a single-tile navmesh is simpler and sufficient.

How you want to manage tiles is up to you. You can create and add all navmesh tiles for a level at once, or you can create and add/remove tiles dynamically at runtime.

If you remove and re-add tiles at given coordinates, note that the node references for polygons will become invalidated. Any custom pathfinding logic you write that references polygons will need to call isValidNodeRef to check if a node reference is still valid before using it.

$3

The navcat/blocks entrypoint provides generateSoloNavMesh and generateTiledNavMesh presets that bundle together the common steps of the navigation mesh generation process into easy-to-use functions.

If your use case is simple, you can use these presets to get started quickly. As your use case becomes more complex, you can eject from these presets by copying the functions (that are separate from navcat core) into your project and modifying them as needed.

You can find API docs for these blocks in the API docs:

- https://navcat.dev/docs/functions/navcat_blocks.generateSoloNavMesh.html
- https://navcat.dev/docs/functions/navcat_blocks.generateTiledNavMesh.html

See the Solo NavMesh and Tiled NavMesh examples for interactive examples of using these presets:

Solo NavMesh

Tiled NavMesh

$3

This section provides a deep-dive into how navigation mesh generation works. Understanding this process is useful for tuning parameters to get the best results for your specific environment and agent requirements.

The core of the navigation mesh generation approach is based on the recastnavigation library's voxelization-based approach.

At a high-level:

- Input triangles are rasterized into voxels / into a heightfield
- Voxels in areas where agents (defined by your parameters) would not be able to move are filtered and removed
- Walkable areas described by the voxel grid are divided into sets of polygonal regions
- Navigation mesh polygons are created by triangulating the generated polygonal regions

Like recast, navcat supports both single and tiled navigation meshes. Single-tile meshes are suitable for many simple, static cases and are easy to work with. Tiled navmeshes are more complex to work with but better support larger, more dynamic environments, and enable advanced use cases like re-baking, navmesh data-streaming.

If you want an interactive example / starter, see the examples:

- https://navcat.dev/examples#example-generate-navmesh
- ./examples/src/example-solo-navmesh.ts
- ./blocks/generate-solo-nav-mesh.ts

#### 0. Input and setup

The input to the navigation mesh generation process is a set of 3D triangles that define the environment. These triangles should represent the collision surfaces in the environment, and shouldn't include any non-collidable decorative geometry that shouldn't affect navigation.

The input positions should adhere to the OpenGL conventions (right-handed coordinate system, counter-clockwise winding order).

The navigation mesh generation process emits diagnostic messages, warnings, and errors. These are captured with a build context object.

`ts
import * as Nav from 'navcat';

// flat array of vertex positions [x1, y1, z1, x2, y2, z2, ...]
const positions: number[] = [];

// flat array of triangle vertex indices
const indices: number[] = [];

// build context to capture diagnostic messages, warnings, and errors
const ctx = Nav.BuildContext.create();
`

!2-1-navmesh-gen-input

`ts
export type BuildContextState = {
logs: BuildContextLog[];
times: BuildContextTime[];
_startTimes: Record;
};
`

#### 1. Mark walkable triangles

The first step is to filter the input triangles to find the walkable triangles. This is done by checking the slope of each triangle against a maximum walkable slope angle. Triangles that are walkable are marked with the WALKABLE_AREA (1) area type.

`ts
// CONFIG: agent walkable slope angle
const walkableSlopeAngleDegrees = 45;

// allocate an array to hold the area ids for each triangle
const triAreaIds = new Uint8Array(indices.length / 3).fill(0);

// mark triangles as walkable or not depending on their slope angle
Nav.markWalkableTriangles(positions, indices, triAreaIds, walkableSlopeAngleDegrees);
`

!2-2-walkable-triangles

`ts
/**
* Marks triangles as walkable based on their slope angle
* @param inVertices Array of vertex coordinates [x0, y0, z0, x1, y1, z1, ...]
* @param inIndices Array of triangle indices [i0, i1, i2, i3, i4, i5, ...]
* @param outTriAreaIds Output array of triangle area IDs, with a length equal to inIndices.length / 3
* @param walkableSlopeAngle Maximum walkable slope angle in degrees (default: 45)
*/
export function markWalkableTriangles(inVertices: ArrayLike, inIndices: ArrayLike, outTriAreaIds: ArrayLike, walkableSlopeAngle = 45.0);
`

`ts
export function createTriangleAreaIdsHelper(input: {
positions: ArrayLike;
indices: ArrayLike;
}, triAreaIds: ArrayLike): DebugPrimitive[];
`

#### 2. Rasterize triangles into a heightfield, do filtering with the heightfield

The walkable triangles are then voxelized into a heightfield, taking the triangle's "walkability" into each span.

Some filtering is done to the heightfield to remove spans where a character cannot stand, and unwanted overhangs are removed.

The heightfield resolution is configurable, and greatly affects the fidelity of the resulting navigation mesh, and the performance of the navigation mesh generation process.

`ts
// CONFIG: heightfield cell size and height, in world units
const cellSize = 0.2;
const cellHeight = 0.2;

// CONFIG: agent walkable climb
const walkableClimbWorld = 0.5; // in world units
const walkableClimbVoxels = Math.ceil(walkableClimbWorld / cellHeight);

// CONFIG: agent walkable height
const walkableHeightWorld = 1.0; // in world units
const walkableHeightVoxels = Math.ceil(walkableHeightWorld / cellHeight);

// calculate the bounds of the input geometry
const bounds: Nav.Box3 = [[0, 0, 0], [0, 0, 0]];
Nav.calculateMeshBounds(bounds, positions, indices);

// calculate the grid size of the heightfield
const [heightfieldWidth, heightfieldHeight] = Nav.calculateGridSize([0, 0], bounds, cellSize);

// create the heightfield
const heightfield = Nav.createHeightfield(heightfieldWidth, heightfieldHeight, bounds, cellSize, cellHeight);

// rasterize the walkable triangles into the heightfield
Nav.rasterizeTriangles(ctx, heightfield, positions, indices, triAreaIds, walkableClimbVoxels);

// filter walkable surfaces
Nav.filterLowHangingWalkableObstacles(heightfield, walkableClimbVoxels);
Nav.filterLedgeSpans(heightfield, walkableHeightVoxels, walkableClimbVoxels);
Nav.filterWalkableLowHeightSpans(heightfield, walkableHeightVoxels);
`

!2-3-heightfield

`ts
export type Heightfield = {
/* the width of the heightfield (along x axis in cell units) /
width: number;
/* the height of the heightfield (along z axis in cell units) /
height: number;
/* the bounds in world space /
bounds: Box3;
/* the vertical size of each cell (minimum increment along y) /
cellHeight: number;
/* the vertical size of each cell (minimum increment along x and z) /
cellSize: number;
/* the heightfield of spans, (widthheight) */
spans: (HeightfieldSpan | null)[];
};
`

`ts
export type HeightfieldSpan = {
/* the lower limit of the span /
min: number;
/* the upper limit of the span /
max: number;
/* the area id assigned to the span /
area: number;
/* the next heightfield span /
next: HeightfieldSpan | null;
};
`

`ts
export function calculateMeshBounds(outBounds: Box3, inVertices: ArrayLike, inIndices: ArrayLike): Box3;
`

`ts
export function calculateGridSize(outGridSize: Vec2, bounds: Box3, cellSize: number): [
width: number,
height: number
];
`

`ts
export function createHeightfield(width: number, height: number, bounds: Box3, cellSize: number, cellHeight: number): Heightfield;
`

`ts
export function rasterizeTriangles(ctx: BuildContextState, heightfield: Heightfield, vertices: ArrayLike, indices: ArrayLike, triAreaIds: ArrayLike, flagMergeThreshold = 1);
`

`ts
export function filterLowHangingWalkableObstacles(heightfield: Heightfield, walkableClimb: number);
`

`ts
export function filterLedgeSpans(heightfield: Heightfield, walkableHeight: number, walkableClimb: number);
`

`ts
export function filterWalkableLowHeightSpans(heightfield: Heightfield, walkableHeight: number);
`

`ts
export function createHeightfieldHelper(heightfield: Heightfield): DebugPrimitive[];
`

#### 3. Build compact heightfield, erode walkable area, mark areas

The heightfield is then compacted to only represent the top walkable surfaces.

The compact heightfield is generally eroded by the agent radius to ensure that the resulting navigation mesh is navigable by agents of the specified radius.

`ts
// build the compact heightfield
const compactHeightfield = Nav.buildCompactHeightfield(ctx, walkableHeightVoxels, walkableClimbVoxels, heightfield);

// CONFIG: agent radius
const walkableRadiusWorld = 0.6; // in world units
const walkableRadiusVoxels = Math.ceil(walkableRadiusWorld / cellSize);

// erode the walkable area by the agent radius / walkable radius
Nav.erodeWalkableArea(walkableRadiusVoxels, compactHeightfield);

// OPTIONAL: you can use utilities like markBoxArea here on the compact heightfield to mark custom areas
// see the "Custom Query Filters and Custom Area Types" section of the docs for more info
`

!2-4-compact-heightfield

`ts
export type CompactHeightfield = {
/* the width of the heightfield (along x axis in cell units) /
width: number;
/* the height of the heightfield (along z axis in cell units) /
height: number;
/* the number of spans in the heightfield /
spanCount: number;
/* the walkable height used during the build of the heightfield /
walkableHeightVoxels: number;
/* the walkable climb used during the build of the heightfield /
walkableClimbVoxels: number;
/* the AABB border size used during the build of the heightfield /
borderSize: number;
/* the maxiumum distance value of any span within the heightfield /
maxDistance: number;
/* the maximum region id of any span within the heightfield /
maxRegions: number;
/* the heightfield bounds in world space /
bounds: Box3;
/* the size of each cell /
cellSize: number;
/* the height of each cell /
cellHeight: number;
/* array of cells, size = widthheight */
cells: CompactHeightfieldCell[];
/* array of spans, size = spanCount /
spans: CompactHeightfieldSpan[];
/* array containing area id data, size = spanCount /
areas: number[];
/* array containing distance field data, size = spanCount /
distances: number[];
};
`

`ts
export type CompactHeightfieldCell = {
/* index to the first span in the column /
index: number;
/* number of spans in the column /
count: number;
};
`

`ts
export type CompactHeightfieldSpan = {
/* the lower extent of the span. measured from the heightfields base. /
y: number;
/* the id of the region the span belongs to, or zero if not in a region /
region: number;
/* packed neighbour connection data /
con: number;
/* the height of the span, measured from y /
h: number;
};
`

`ts
export function buildCompactHeightfield(ctx: BuildContextState, walkableHeightVoxels: number, walkableClimbVoxels: number, heightfield: Heightfield): CompactHeightfield;
`

`ts
export function erodeWalkableArea(walkableRadiusVoxels: number, compactHeightfield: CompactHeightfield);
`

`ts
/**
* Erodes the walkable area for a base agent radius and marks restricted areas for larger agents based on given walkable radius thresholds.
*
* Note that this function requires careful tuning of the build parameters to get a good result:
* - The cellSize needs to be small enough to accurately represent narrow passages. Generally you need to use smaller cellSizes than you otherwise would for single agent navmesh builds.
* - The thresholds should not be so small that the resulting regions are too small to successfully build good navmesh polygons for. Values like 1-2 voxels will likely lead to poor results.
* - You may get a better result using "buildRegionsMonotone" over "buildRegions" as this will better handle the many small clusters of areas that may be created from smaller thresholds.
*
* A typical workflow for using this utility to implement multi-agent support:
* 1. Call erodeAndMarkWalkableAreas with your smallest agent radius and list of restricted areas
* 2. Continue with buildDistanceField, buildRegionsMonotone, etc.
* 3. Configure query filters so large agents exclude the narrow/restricted area IDs
*
* @param baseWalkableRadiusVoxels the smallest agent radius in voxels (used for erosion)
* @param thresholds array of area ids and their corresponding walkable radius in voxels.
* @param compactHeightfield the compact heightfield to process
*/
export function erodeAndMarkWalkableAreas(baseWalkableRadiusVoxels: number, thresholds: Array<{
areaId: number;
walkableRadiusVoxels: number;
}>, compactHeightfield: CompactHeightfield);
`

`ts
export function createCompactHeightfieldSolidHelper(compactHeightfield: CompactHeightfield): DebugPrimitive[];
`

#### 4. Build compact heightfield regions

The compact heightfield is then analyzed to identify distinct walkable regions. These regions are used to create the final navigation mesh.

Some of the region generation algorithms compute a distance field to identify regions.

`ts
// prepare for region partitioning by calculating a distance field along the walkable surface
Nav.buildDistanceField(compactHeightfield);

// CONFIG: borderSize, relevant if you are building a tiled navmesh
const borderSize = 0;

// CONFIG: minRegionArea
const minRegionArea = 8; // voxel units

// CONFIG: mergeRegionArea
const mergeRegionArea = 20; // voxel units

// partition the walkable surface into simple regions without holes
Nav.buildRegions(ctx, compactHeightfield, borderSize, minRegionArea, mergeRegionArea);
`

!2-5-distance-field

!2-6-regions

`ts
export function buildDistanceField(compactHeightfield: CompactHeightfield): void;
`

`ts
export function buildRegions(ctx: BuildContextState, compactHeightfield: CompactHeightfield, borderSize: number, minRegionArea: number, mergeRegionArea: number): boolean;
`

`ts
/**
* Build regions using monotone partitioning algorithm.
* This is an alternative to the watershed-based buildRegions function.
* Monotone partitioning creates regions by sweeping the heightfield and
* does not generate overlapping regions.
*/
export function buildRegionsMonotone(compactHeightfield: CompactHeightfield, borderSize: number, minRegionArea: number, mergeRegionArea: number): boolean;
`

`ts
/**
* Build layer regions using sweep-line algorithm.
* This creates regions that can be used for building navigation mesh layers.
* Layer regions handle overlapping walkable areas by creating separate layers.
*/
export function buildLayerRegions(compactHeightfield: CompactHeightfield, borderSize: number, minRegionArea: number): boolean;
`

`ts
export function createCompactHeightfieldDistancesHelper(compactHeightfield: CompactHeightfield): DebugPrimitive[];
`

`ts
export function createCompactHeightfieldRegionsHelper(compactHeightfield: CompactHeightfield): DebugPrimitive[];
``

#### 5. Build contours from compact heightfield regions

Contours are generated around the edges of the regions. These contours are simplified to reduce the number of vertices