navcat

For dynamic agent movement, instead of calling the heavy findPath repeatedly, you can split the process into two steps to improve efficiency:

1. findNodePath: Finds a sequence of polygon and offmesh connection node references. You can cache this node path and only recalculate it if the destination changes.
2. findStraightPath: Performs 'string pulling' on the cached node path to convert it into actual waypoint positions. This can be called frequently (e.g., every frame) as the agent's start position changes.

When to use: Use this pattern for high-performance agent steering where the destination is relatively stable but the agent is constantly moving.

// 1. Find the node path (can be cached)
const nodePath = Nav.findNodePath(
    navMesh,
    startNode.nodeRef,
    endNode.nodeRef,
    startNode.position,
    endNode.position,
    Nav.DEFAULT_QUERY_FILTER
);

// 2. Find the actual waypoints (call frequently as agent moves)
if (nodePath.success) {
    const straightPathResult = Nav.findStraightPath(
        navMesh, 
        currentPosition, 
        destinationPosition, 
        nodePath.path
    );
}

When choosing between navcat and recast-navigation-js, consider the following trade-offs:

Advantages of navcat

• Bundle Size & Tree-shaking: navcat is a pure JavaScript library that is highly tree-shakeable, whereas recast-navigation-js has a large bundle size due to its WASM binary and Emscripten glue code.
• Off-Mesh Connections: navcat allows adding/removing off-mesh connections dynamically without regenerating tiles. Connections can be created between any tiles (not just neighbors). It also provides a crowd API with animation hooks.
• Query Filters: Filters in navcat are regular JavaScript functions, offering more flexibility than the area cost tables or include/exclude flags used in Recast.
• External NavMeshes: navcat supports pathfinding with externally provided navigation mesh polys.
• Extensibility & Debugging: navcat uses transparent JavaScript data structures, making it easy to write custom traversal algorithms or debug using standard JS tools. recast-navigation-js uses WASM-wrapped C++ objects which are harder to inspect.
• Memory Management: navcat uses regular JS objects and requires no manual memory management (unlike recast-navigation-js which requires calling .destroy() on certain objects).

Advantages of recast-navigation-js

• Performance: recast-navigation-js typically offers better performance for runtime navmesh generation and querying. However, navcat is highly performant for pathfinding and suitable for many dynamic generation use cases.

To get started, use the generateSoloNavMesh function from navcat/blocks to create a navigation mesh from geometry, and then use findPath from navcat to perform pathfinding.

Workflow:

1. Prepare positions (Float32Array) and indices (Uint32Array) from your level geometry.
2. Define SoloNavMeshInput containing your geometry.
3. Configure SoloNavMeshOptions (see parameter table below).
4. Call generateSoloNavMesh(input, options) to get the navMesh.
5. Use findPath(navMesh, start, end, halfExtents, filter) to find a path.

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

/* generation input */
const positions = new Float32Array([/* ... */]);
const indices = new Uint32Array([/* ... */]);

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

/* generation options */
const options: SoloNavMeshOptions = {
    cellSize: 0.15,
    cellHeight: 0.25,
    walkableRadiusWorld: 0.3,
    walkableRadiusVoxels: Math.ceil(0.3 / 0.15),
    walkableClimbWorld: 0.5,
    walkableClimbVoxels: Math.ceil(0.5 / 0.25),
    walkableHeightWorld: 2.0,
    walkableHeightVoxels: Math.ceil(2.0 / 0.25),
    walkableSlopeAngleDegrees: 45,
    borderSize: 0,
    minRegionArea: 8,
    mergeRegionArea: 20,
    maxSimplificationError: 1.3,
    maxEdgeLength: 12,
    maxVerticesPerPoly: 5,
    detailSampleDistance: 0.15 * 6,
    detailSampleMaxError: 0.25 * 1,
};

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

/* 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));

After building the CompactHeightfield, you must partition the walkable surface into distinct regions.

Steps:

1. Calculate Distance Field: Call buildDistanceField(compactHeightfield) to prepare for partitioning.
2. Partition Regions: Use one of the following algorithms:
   • buildRegions: A watershed-based algorithm. Requires borderSize, minRegionArea, and mergeRegionArea.
   • buildRegionsMonotone: A sweep-line algorithm that creates regions by sweeping the heightfield. It does not generate overlapping regions and is recommended for multi-agent erosion workflows.
   • buildLayerRegions: A sweep-line algorithm that creates layers to handle overlapping walkable areas.

// 1. Prepare distance field
Nav.buildDistanceField(compactHeightfield);

// 2. Partition regions
const borderSize = 0;
const minRegionArea = 8;
const mergeRegionArea = 20;

Nav.buildRegions(ctx, compactHeightfield, borderSize, minRegionArea, mergeRegionArea);