### Quickstart Navmesh Generation and Pathfinding

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

A minimal example demonstrating how to generate a navigation mesh using presets and find a path on it. This is useful for a basic setup.

```typescript
import {
  Navcat,
  NavcatConfig,
  NavcatBlocks,
  NavcatBlocksConfig,
} from "navcat";

// Example usage:
const navcat = new Navcat();
const blocks = new NavcatBlocks();

const navmeshConfig: NavcatConfig = {
  ...NavcatBlocksConfig.DEFAULT,
  // Override default parameters as needed
  walkableRadiusWorld: 0.3,
  walkableHeightWorld: 1.8,
};

const navmesh = blocks.generateNavmesh(navmeshConfig);

const startPoint = { x: 0, y: 0, z: 0 };
const endPoint = { x: 10, y: 0, z: 10 };

const path = navcat.findPath(navmesh, startPoint, endPoint);

console.log("Generated Path:", path);

```

--------------------------------

### Install navcat

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

Install the navcat library using npm. This command is used for project setup.

```bash
npm install navcat
```

--------------------------------

### Initialize and Add Examples to Sidebar

Source: https://github.com/isaac-mason/navcat/blob/main/examples/index.html

This function populates the sidebar with example items, including their titles, descriptions, and tags. It's called on initialization to display the available examples.

```javascript
function addExamplesToSidebar() {
  const examplesList = document.getElementById("examples-list");
  const examplesHTML = Object.entries(examples)
    .map(([key, example]) => {
      const tagsHTML = example.tags
        .map((tag) => `<span class="example-tag">${tag}</span>`)
        .join("");
      return ` <li> <div class="example-item" data-example="${key}"> <div class="example-preview"> <img src="./screenshots/${key}.png" alt="${example.title}" class="example-screenshot">
 <div class="example-info">
 <h3 class="example-title">${example.title}</h3>
 <p class="example-description">${example.description}</p>
 </div>
 </div>
 </div>
 </li> `;
    })
    .join("");
  examplesList.innerHTML = examplesHTML;
}

// initialize examples list
addExamplesToSidebar();
```

--------------------------------

### Implement Example Search Functionality

Source: https://github.com/isaac-mason/navcat/blob/main/examples/index.html

Filters the displayed examples based on a search term entered by the user. It searches within the title, description, and tags of each example.

```javascript
function filterExamples() {
  const searchTerm = searchInput.value.toLowerCase();
  const exampleItems = document.querySelectorAll(".examples-list li");
  exampleItems.forEach((item) => {
    const exampleKey = item
      .querySelector(".example-item")
      .getAttribute("data-example");
    const example = examples[exampleKey];
    // search in title, description, and tags
    const searchableText = [
      example.title,
      example.description,
      ...example.tags,
    ]
      .join(" ")
      .toLowerCase();
    if (searchableText.includes(searchTerm)) {
      item.style.display = "";
    } else {
      item.style.display = "none";
    }
  });
}

// attach search event listener
searchInput.addEventListener("input", filterExamples);
```

--------------------------------

### Load and Display Selected Example

Source: https://github.com/isaac-mason/navcat/blob/main/examples/index.html

Loads a specific example by its key, updating the title, iframe source, and active state of the sidebar item. It also updates the URL hash and the source link.

```javascript
function loadExample(exampleKey, scrollIntoView) {
  const example = examples[exampleKey];
  if (!example) return;
  titleElement.textContent = example.title;
  frameElement.src = `./${exampleKey}.html`;

  // update active item
  const exampleItems = document.querySelectorAll(".example-item");
  let activeItem = null;
  exampleItems.forEach((item) => {
    item.classList.remove("active");
    if (item.getAttribute("data-example") === exampleKey) {
      item.classList.add("active");
      activeItem = item;
    }
  });

  // scroll active item into view
  if (scrollIntoView && activeItem) {
    activeItem.scrollIntoView({ block: "center", behavior: "auto" });
  }

  // update URL
  window.location.hash = exampleKey;

  // update source link
  const sourceLink = document.getElementById("source-link");
  sourceLink.href = `https://github.com/isaac-mason/navcat/blob/main/examples/src/${exampleKey}.ts`;

  // close mobile sidebar
  sidebar.classList.remove("open");
  sidebarOverlay.classList.remove("show");
}
```

--------------------------------

### Handle URL Hash Changes for Example Loading

Source: https://github.com/isaac-mason/navcat/blob/main/examples/index.html

Listens for changes in the URL hash and loads the corresponding example. If no hash is present or valid, it loads the first example by default.

```javascript
function handleHashChange(scrollIntoView = false) {
  const hash = window.location.hash.substring(1);
  if (hash && examples[hash]) {
    loadExample(hash, scrollIntoView);
  } else {
    // load first example by default
    const firstExample = Object.keys(examples)[0];
    loadExample(firstExample, scrollIntoView);
  }
}

// initialize
handleHashChange(true);
attachEventListeners();
window.addEventListener("hashchange", () => handleHashChange(true));
```

--------------------------------

### Move Along Navmesh Surface Example

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Demonstrates how to use moveAlongSurface to move an agent from a start to an end position along the navmesh. Ensure a navmesh and a starting polygon reference are available. Logs the success status, resulting position, and visited polygons.

```typescript
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
```

--------------------------------

### Attach Event Listeners for Example Clicks

Source: https://github.com/isaac-mason/navcat/blob/main/examples/index.html

Adds click event listeners to each example item in the sidebar. Clicking an item triggers the `loadExample` function to display the selected example.

```javascript
function attachEventListeners() {
  const exampleItems = document.querySelectorAll(".example-item");
  exampleItems.forEach((item) => {
    item.addEventListener("click", (e) => {
      e.preventDefault();
      const exampleKey = item.getAttribute("data-example");
      loadExample(exampleKey);
    });
  });
}
```

--------------------------------

### Three.js Navcat Quickstart

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

Extract geometry from a Three.js mesh for navmesh generation and visualize the generated navmesh using Three.js helpers. Requires 'navcat' and 'three' libraries.

```typescript
import * as THREE from "three";
import { getPositionsAndIndices, createNavMeshHelper } from "navcat/three";

// Assuming 'mesh' is a THREE.Mesh object
const geometry = mesh.geometry;
const positionAttribute = geometry.getAttribute("position");
const indexAttribute = geometry.index;

const positions = positionAttribute.array;
const indices = indexAttribute ? indexAttribute.array : getIndicesFromGeometry(geometry);

const navMesh = createNavMesh(positions, indices);
const helper = createNavMeshHelper(navMesh);

// Add helper to your Three.js scene
scene.add(helper);
```

--------------------------------

### Heightfield Generation and Filtering

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

This section outlines the steps and provides code examples for generating a heightfield from walkable triangles and applying filters to refine it.

```APIDOC
## Heightfield Generation and Filtering

This section outlines the steps and provides code examples for generating a heightfield from walkable triangles and applying filters to refine it.

### CONFIGURATION

```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);
```

### PROCESS

1.  **Calculate Mesh Bounds**
    Calculates the bounding box of the input geometry.
    ```ts
    // calculate the bounds of the input geometry
    const bounds: Nav.Box3 = [0, 0, 0, 0, 0, 0];
    Nav.calculateMeshBounds(bounds, positions, indices);
    ```

2.  **Calculate Grid Size**
    Determines the dimensions of the heightfield grid based on bounds and cell size.
    ```ts
    // calculate the grid size of the heightfield
    const [heightfieldWidth, heightfieldHeight] = Nav.calculateGridSize([0, 0], bounds, cellSize);
    ```

3.  **Create Heightfield**
    Initializes an empty heightfield structure.
    ```ts
    // create the heightfield
    const heightfield = Nav.createHeightfield(heightfieldWidth, heightfieldHeight, bounds, cellSize, cellHeight);
    ```

4.  **Rasterize Triangles**
    Populates the heightfield with walkable triangle data.
    ```ts
    // rasterize the walkable triangles into the heightfield
    Nav.rasterizeTriangles(ctx, heightfield, positions, indices, triAreaIds, walkableClimbVoxels);
    ```

5.  **Filter Heightfield**
    Applies various filters to clean up the heightfield.
    ```ts
    // filter walkable surfaces
    Nav.filterLowHangingWalkableObstacles(heightfield, walkableClimbVoxels);
    Nav.filterLedgeSpans(heightfield, walkableHeightVoxels, walkableClimbVoxels);
    Nav.filterWalkableLowHeightSpans(heightfield, walkableHeightVoxels);
    ```
```

--------------------------------

### findSmoothPath

Source: https://context7.com/isaac-mason/navcat/llms.txt

An all-in-one function that finds the nearest start and end polygons, performs A* pathfinding, string-pulls the path, and refines it to lie exactly on the walkable mesh surface.

```APIDOC
## `findSmoothPath` — High-level smooth path with automatic nearest-poly lookup

All-in-one helper that locates start/end polygons, runs A*, string-pulls, and then refines the path by iteratively moving along the mesh surface so the returned points lie exactly on the walkable surface.

```typescript
import { findSmoothPath, DEFAULT_QUERY_FILTER, FindSmoothPathResultFlags } from 'navcat';

const smooth = findSmoothPath(
    navMesh,
    [1, 0, 1],  // start
    [9, 0, 9],  // end
    [2, 2, 2],  // search half-extents for nearest poly lookup
    DEFAULT_QUERY_FILTER,
);

if (smooth.flags & FindSmoothPathResultFlags.SUCCESS) {
    console.log('smooth waypoints:', smooth.path.length);
    smooth.path.forEach(pt => console.log(pt.position));
}
```
```

--------------------------------

### Visualize Navcat Debug Primitives

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

Use these functions to draw debug primitives like triangles, lines, points, and boxes for visualizing navmesh data. Ensure you have the necessary graphics library setup.

```typescript
import { DebugPrimitive, DebugTriangles, DebugLines, DebugPoints, DebugBoxes } from "navcat";

// Assuming you have a graphics context and functions to draw primitives
function drawDebugPrimitives(debugPrimitives: DebugPrimitive[]) {
    debugPrimitives.forEach(primitive => {
        if (primitive instanceof DebugTriangles) {
            // Draw triangles
        } else if (primitive instanceof DebugLines) {
            // Draw lines
        } else if (primitive instanceof DebugPoints) {
            // Draw points
        } else if (primitive instanceof DebugBoxes) {
            // Draw boxes
        }
    });
}
```

--------------------------------

### moveAlongSurface

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

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.

```APIDOC
## `moveAlongSurface`

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

### 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.

### Method Signature
```typescript
moveAlongSurface(start: Vector3, end: Vector3, options?: MoveOptions): Vector3
```

### Parameters
- **start** (Vector3): The starting position.
- **end** (Vector3): The target position to move towards.
- **options** (MoveOptions, optional): Additional options for movement.

### Returns
- Vector3: The final position after moving along the surface.
```

--------------------------------

### raycast / raycastWithCosts

Source: https://context7.com/isaac-mason/navcat/llms.txt

Performs a 2D (XZ-plane) raycast along the navigation mesh surface from a starting polygon. It returns the hit parameter `t`, the wall normal if a wall is hit, and all traversed polygon references. `raycastWithCosts` additionally calculates traversal costs for any-angle pathfinding.

```APIDOC
## `raycast` / `raycastWithCosts` — Walkability ray test

Casts a 2D (XZ-plane) ray along the navigation mesh surface from a start polygon. Returns the hit parameter `t` along the segment (`Number.MAX_VALUE` = no wall hit), the wall normal, and all traversed polygon refs. `raycastWithCosts` additionally accumulates traversal costs for any-angle pathfinding.

```typescript
import { raycast, DEFAULT_QUERY_FILTER } from 'navcat';

const ray = raycast(
    navMesh,
    currentPolyRef,
    [2, 0, 2],   // start
    [8, 0, 2],   // end
    DEFAULT_QUERY_FILTER,
);

if (ray.t === Number.MAX_VALUE) {
    console.log('clear line of sight, visited', ray.path.length, 'polygons');
} else {
    const hitX = 2 + (8 - 2) * ray.t;
    console.log('wall hit at', hitX, '— normal:', ray.hitNormal);
}
```
```

--------------------------------

### Find Node Path with NavCat

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Use this to cache a node path and recalculate the straight path multiple times. This is more efficient than calling findPath repeatedly. Ensure you have found the nearest poly nodes to your start and end points first.

```typescript
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, ... ]
}
```

```typescript
/**
 * 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.
 * @param options Optional configuration for the pathfinding operation.
 * @returns The result of the pathfinding operation.
 */
export function findNodePath(navMesh: NavMesh, startNodeRef: NodeRef, endNodeRef: NodeRef, startPosition: Vec3, endPosition: Vec3, filter: QueryFilter, options?: FindNodePathOptions): FindNodePathResult;
```

--------------------------------

### raycastWithCosts

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

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 and ignores the y-value of the end position (2D check).

```APIDOC
## raycastWithCosts

### Description
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 and ignores the y-value of the end position (2D check).

### Method
`raycastWithCosts(navMesh: NavMesh, startNodeRef: NodeRef, startPosition: Vec3, endPosition: Vec3, filter: QueryFilter, prevRef: NodeRef): RaycastResult`

### Parameters
- **navMesh** (NavMesh) - The navigation mesh to use for the raycast.
- **startNodeRef** (NodeRef) - The NodeRef for the start polygon.
- **startPosition** (Vec3) - The starting position in world space.
- **endPosition** (Vec3) - The ending position in world space.
- **filter** (QueryFilter) - The query filter to apply.
- **prevRef** (NodeRef) - The reference to the polygon we came from (for accurate cost calculations).

### Returns
- **RaycastResult** - The raycast result with hit information, visited polygons, and accumulated path costs.

### Request Example
```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
```
```

--------------------------------

### Find Straight Path with NavCat

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Use this after findNodePath to convert a sequence of nodes into waypoints for an agent's path. Recalculate this frequently while keeping the same node path, or when implementing custom path following. The start and end positions are clamped to the first and last polygons in the path.

```typescript
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 }, ... ]
```

```typescript
/**
 * 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;
```

--------------------------------

### getPolyHeight

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Gets the height of a polygon at a given point, utilizing the detail mesh if available. This function populates a provided result object.

```APIDOC
## getPolyHeight

### Description
Gets the height of a polygon at a given point using detail mesh if available.

### Method
`Nav.getPolyHeight(result, tile, poly, polyIndex, pos)`

### Parameters
- **result**: The `GetPolyHeightResult` object to populate with the height information.
- **tile**: The `NavMeshTile` containing the polygon.
- **poly**: The `NavMeshPoly` for which to get the height.
- **polyIndex**: The index of the polygon within the tile.
- **pos**: The `Vec3` position for which to determine the height.

### Returns
- `GetPolyHeightResult`: The result object containing a `success` flag and the calculated `height`.
```

--------------------------------

### Initialize Navcat Build Context

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

Sets up the build context for navigation mesh generation, capturing diagnostic messages. Ensure input positions adhere to OpenGL conventions.

```typescript
const buildContext = new BuildContext();
const { triangles } = await loadEnvironment();

// Input positions should adhere to OpenGL conventions (right-handed coordinate system, counter-clockwise winding order).
```

--------------------------------

### Initialize Navcat Build Context and Input Data

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Sets up the necessary input data (positions, indices) and initializes a build context for capturing diagnostic messages during navigation mesh generation.

```typescript
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();
```

```typescript
export type BuildContextState = {
    logs: BuildContextLog[];
    times: BuildContextTime[];
    _startTimes: Record<string, number>;
};
```

--------------------------------

### Find Straight Path with Navcat

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

Call this after `findNodePath` to get the actual waypoint positions. You might recalculate this frequently while keeping the same node path.

```typescript
const straightPath = findStraightPath(navmesh, nodePath, startPosition, endPosition);

```

--------------------------------

### Build Navigation Mesh Tile

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Builds a navigation mesh tile from the provided parameters. This function constructs a BV-tree and initializes runtime tile properties.

```ts
export function buildTile(params: NavMeshTileParams): NavMeshTile;
```

--------------------------------

### floodFillNavMesh

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Performs a flood fill on the navigation mesh starting from specified seed nodes to identify reachable and unreachable areas. This is useful for pruning isolated regions.

```APIDOC
## floodFillNavMesh

### Description
Performs a flood fill on the navigation mesh from given "seed points" to exclude isolated or unreachable areas.

### Method
export function floodFillNavMesh(navMesh: NavMesh, startNodeRefs: NodeRef[]): {
    reachable: NodeRef[];
    unreachable: NodeRef[];
};

### Parameters
#### Path Parameters
- **navMesh** (NavMesh) - The navigation mesh to perform the flood fill on.
- **startNodeRefs** (NodeRef[]) - An array of node references representing the starting points for the flood fill.
```

--------------------------------

### Flood Fill NavMesh Pruning

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

Utilizes the `floodFillNavMesh` utility to prune isolated or unreachable areas from a generated navigation mesh, starting from specified seed points.

```typescript
floodFillNavMesh(navMesh, startRegion);
```

--------------------------------

### buildTile

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Builds a navigation mesh tile from the provided parameters. This function constructs a BV-tree and initializes runtime tile properties.

```APIDOC
## buildTile

### Description
Builds a navmesh tile from the given parameters. This builds a BV-tree, and initialises runtime tile properties.

### Method
export function buildTile(params: NavMeshTileParams): NavMeshTile;
```

--------------------------------

### Sliced (async) pathfinding

Source: https://context7.com/isaac-mason/navcat/llms.txt

Provides asynchronous pathfinding capabilities by spreading the A* search across multiple frames. Initialize with `initSlicedFindNodePath`, update per frame with `updateSlicedFindNodePath`, and finalize with `finalizeSlicedFindNodePath`.

```APIDOC
## Sliced (async) pathfinding — `initSlicedFindNodePath` / `updateSlicedFindNodePath` / `finalizeSlicedFindNodePath`

Spreads the A* search across multiple frames to avoid frame-time spikes. Initialize once, call update each frame with a budget of iterations, then finalize when status becomes `SUCCESS`.

```typescript
import {
    createSlicedNodePathQuery,
    initSlicedFindNodePath,
    updateSlicedFindNodePath,
    finalizeSlicedFindNodePath,
    SlicedFindNodePathStatusFlags,
    SlicedFindNodePathInitFlags,
    DEFAULT_QUERY_FILTER,
} from 'navcat';

const query = createSlicedNodePathQuery();

initSlicedFindNodePath(
    navMesh,
    query,
    startNodeRef,
    endNodeRef,
    [1, 0, 1],
    [9, 0, 9],
    DEFAULT_QUERY_FILTER,
    SlicedFindNodePathInitFlags.ANY_ANGLE, // enable any-angle shortcutting
);

// per-frame update loop
function tick() {
    if (query.status & SlicedFindNodePathStatusFlags.IN_PROGRESS) {
        updateSlicedFindNodePath(navMesh, query, 100 /* max iterations per frame */);
    } else {
        const { status, path } = finalizeSlicedFindNodePath(navMesh, query);
        if (status & SlicedFindNodePathStatusFlags.SUCCESS) {
            console.log('async path done, polys:', path.length);
        }
    }
}
```
```

--------------------------------

### Get NavMesh Node by Reference

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Retrieves a navigation mesh node using its reference. Avoid storing node objects directly as they can be reused when tiles are removed and added.

```typescript
const node = Nav.getNodeByRef(navMesh, nodeRef);
console.log(node);
```

```typescript
/**
 * Gets a navigation mesh node by its reference.
 * Note that navmesh nodes are pooled and may be reused on removing then adding tiles, so do not store node objects.
 * @param navMesh the navigation mesh
 * @param nodeRef the node reference
 * @returns the navigation mesh node
 */
export function getNodeByRef(navMesh: NavMesh, nodeRef: NodeRef);
```

--------------------------------

### Build Regions

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Partitions the walkable surface into simple regions without holes.

```APIDOC
## buildRegions

### Description
Partitions the walkable surface into simple regions without holes.

### Method
`buildRegions`

### Parameters
#### Path Parameters
- **ctx** (BuildContextState) - Required - The build context state.
- **compactHeightfield** (CompactHeightfield) - Required - The compact heightfield to process.
- **borderSize** (number) - Required - The size of the border.
- **minRegionArea** (number) - Required - The minimum region area.
- **mergeRegionArea** (number) - Required - The merge region area.

### Code Example
```ts
Nav.buildRegions(ctx, compactHeightfield, borderSize, minRegionArea, mergeRegionArea);
```
```

--------------------------------

### Retrieve Off-Mesh Connection Attachment Info

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Gets details about which polygons an off-mesh connection is linked to. This is useful for debugging or understanding the connection's placement within the navmesh.

```typescript
const offMeshConnectionAttachment = navMesh.offMeshConnectionAttachments[bidirectionalOffMeshConnectionId];

if (offMeshConnectionAttachment) {
    console.log(offMeshConnectionAttachment.startPolyNode);
    console.log(offMeshConnectionAttachment.endPolyNode);
}
```

--------------------------------

### Raycast with Costs on Navmesh with Navcat

Source: https://github.com/isaac-mason/navcat/blob/main/docs/README.template.md

Casts a ray along the navmesh surface to check for walkability and detect obstacles, also returning costs. Avoid using this for long rays; it's best suited for short-range checks.

```typescript
const hit = raycastWithCosts(navmesh, startPosition, endPosition);

```

--------------------------------

### Find Smooth Path Following Navmesh Surface

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Use this when you need a smooth path that respects the navmesh surface without sharp corners, suitable for infrequent use like visual previews. It combines node pathfinding with surface movement.

```typescript
/**
 * 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 options Configuration for the smooth pathfinding operation.
 * @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, options: FindSmoothPathOptions): FindSmoothPathResult;
```

--------------------------------

### findNearestPoly

Source: https://context7.com/isaac-mason/navcat/llms.txt

Finds the navigation mesh polygon closest to a given world point. This function is essential for initiating pathfinding queries by locating the starting polygon and the nearest point on its surface.

```APIDOC
## findNearestPoly

### Description
Finds the nearest polygon to a world point. Locates the closest nav mesh polygon within a bounding box centered on `center`. Returns the polygon's `NodeRef` and the nearest point on its surface — the typical starting step before any pathfinding query.

### Method
```typescript
import { findNearestPoly, createFindNearestPolyResult, DEFAULT_QUERY_FILTER } from 'navcat';

const result = createFindNearestPolyResult();
findNearestPoly(result, navMesh, center, halfExtents, queryFilter);
```

### Parameters
- **result** (object) - An object to store the query result. Use `createFindNearestPolyResult()` to initialize.
- **navMesh** (NavMesh) - The navigation mesh to query.
- **center** (Vec3) - The center point of the search box `[x, y, z]`.
- **halfExtents** (Vec3) - The half-extents of the search box `[x, y, z]`.
- **queryFilter** (QueryFilter) - The filter to apply to polygon queries. Use `DEFAULT_QUERY_FILTER` for default behavior.

### Response
#### Success Response
- **success** (boolean) - True if a polygon was found.
- **nodeRef** (NodeRef) - The reference to the nearest polygon.
- **position** (Vec3) - The nearest point on the surface of the found polygon `[x, y, z]`.

### Request Example
```typescript
import {
    findNearestPoly,
    createFindNearestPolyResult,
    DEFAULT_QUERY_FILTER,
} from 'navcat';

const result = createFindNearestPolyResult();

findNearestPoly(
    result,
    navMesh,
    [5, 0, 5],           // center
    [2, 2, 2],           // half-extents of search box
    DEFAULT_QUERY_FILTER,
);

if (result.success) {
    console.log('polyRef:', result.nodeRef);
    console.log('snapped position:', result.position); // [x, y, z] on mesh surface
}
```
```

--------------------------------

### Build Distance Field and Regions for NavMesh

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Prepares the compact heightfield by calculating a distance field and then partitions the walkable surface into simple regions. Configuration options include border size, minimum region area, and merge region area.

```typescript
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);
```

--------------------------------

### Get NavMesh Node by Tile and Polygon Index

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Retrieves a navigation mesh node using its tile and polygon index. This is useful for direct access when the tile and polygon are known.

```typescript
const node = Nav.getNodeByTileAndPoly(navMesh, tile, polyIndex);
console.log(node);
```

```typescript
/**
 * Gets a navigation mesh node by its tile and polygon index.
 * @param navMesh the navigation mesh
 * @param tile the navigation mesh tile
 * @param polyIndex the polygon index
 * @returns the navigation mesh node
 */
export function getNodeByTileAndPoly(navMesh: NavMesh, tile: NavMeshTile, polyIndex: number);
```

--------------------------------

### Perform a Raycast on Navmesh

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Use this to check for walkability and detect obstacles along a path. It's best for short-range checks and ignores the y-value of the end position. The result includes the normalized distance to obstruction, hit normal, edge index, and visited polygons.

```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;
```

--------------------------------

### Is Off-Mesh Connection Connected

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Checks if the off-mesh connection with the given ID is currently connected to the navmesh. A connection might be disconnected if its start or end points lack nearby valid polygons.

```APIDOC
## isOffMeshConnectionConnected

### Description
Returns whether the off mesh connection with the given ID is currently connected to the navmesh. An off mesh connection may be disconnected if the start or end positions have no valid polygons nearby to connect to.

### Method
export function isOffMeshConnectionConnected(navMesh: NavMesh, offMeshConnectionId: number): boolean;

### Parameters
#### Path Parameters
- **navMesh** (NavMesh) - The navmesh.
- **offMeshConnectionId** (number) - The ID of the off mesh connection.

### Returns
- **boolean** - Whether the off mesh connection is connected.
```

--------------------------------

### Configure and Generate Heightfield

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Sets up configuration parameters like cell size and agent climb/height, calculates mesh bounds and grid size, creates the heightfield, and then rasterizes walkable triangles into it. Finally, it applies several filtering functions to clean up the heightfield.

```typescript
const cellSize = 0.2;
const cellHeight = 0.2;

const walkableClimbWorld = 0.5; // in world units
const walkableClimbVoxels = Math.ceil(walkableClimbWorld / cellHeight);

const walkableHeightWorld = 1.0; // in world units
const walkableHeightVoxels = Math.ceil(walkableHeightWorld / cellHeight);

const bounds: Nav.Box3 = [0, 0, 0, 0, 0, 0];
Nav.calculateMeshBounds(bounds, positions, indices);

const [heightfieldWidth, heightfieldHeight] = Nav.calculateGridSize([0, 0], bounds, cellSize);

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

Nav.rasterizeTriangles(ctx, heightfield, positions, indices, triAreaIds, walkableClimbVoxels);

Nav.filterLowHangingWalkableObstacles(heightfield, walkableClimbVoxels);
Nav.filterLedgeSpans(heightfield, walkableHeightVoxels, walkableClimbVoxels);
Nav.filterWalkableLowHeightSpans(heightfield, walkableHeightVoxels);
```

--------------------------------

### Flood Fill Navigation Mesh

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Performs a flood fill on the navigation mesh starting from specified seed nodes. It identifies reachable and unreachable areas, useful for pruning isolated regions.

```ts
export function floodFillNavMesh(navMesh: NavMesh, startNodeRefs: NodeRef[]): {
    reachable: NodeRef[];
    unreachable: NodeRef[];
};
```

--------------------------------

### Sliced Pathfinding for Frame-Time Spikes

Source: https://context7.com/isaac-mason/navcat/llms.txt

Initialize, update, and finalize sliced pathfinding queries to spread A* search across multiple frames. Avoids frame-time spikes by processing a budget of iterations per frame.

```typescript
import {
    createSlicedNodePathQuery,
    initSlicedFindNodePath,
    updateSlicedFindNodePath,
    finalizeSlicedFindNodePath,
    SlicedFindNodePathStatusFlags,
    SlicedFindNodePathInitFlags,
    DEFAULT_QUERY_FILTER,
} from 'navcat';

const query = createSlicedNodePathQuery();

initSlicedNodePath(
    navMesh,
    query,
    startNodeRef,
    endNodeRef,
    [1, 0, 1],
    [9, 0, 9],
    DEFAULT_QUERY_FILTER,
    SlicedFindNodePathInitFlags.ANY_ANGLE, // enable any-angle shortcutting
);

// per-frame update loop
function tick() {
    if (query.status & SlicedFindNodePathStatusFlags.IN_PROGRESS) {
        updateSlicedFindNodePath(navMesh, query, 100 /* max iterations per frame */);
    } else {
        const { status, path } = finalizeSlicedFindNodePath(navMesh, query);
        if (status & SlicedFindNodePathStatusFlags.SUCCESS) {
            console.log('async path done, polys:', path.length);
        }
    }
}
```

--------------------------------

### Build Regions Monotone

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Builds regions using the monotone partitioning algorithm. This alternative to `buildRegions` creates non-overlapping regions by sweeping the heightfield.

```APIDOC
## buildRegionsMonotone

### Description
Builds regions using the monotone partitioning algorithm. This alternative to `buildRegions` creates non-overlapping regions by sweeping the heightfield.

### Method
`buildRegionsMonotone`

### Parameters
#### Path Parameters
- **compactHeightfield** (CompactHeightfield) - Required - The compact heightfield to process.
- **borderSize** (number) - Required - The size of the border.
- **minRegionArea** (number) - Required - The minimum region area.
- **mergeRegionArea** (number) - Required - The merge region area.

### Return Value
- **boolean** - True if regions were built successfully, false otherwise.

### Code Example
```ts
Nav.buildRegionsMonotone(compactHeightfield, borderSize, minRegionArea, mergeRegionArea);
```
```

--------------------------------

### Get Closest Point on Polygon

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Finds the closest point on a polygon to a given world-space position. This function returns whether the point was found, if it was inside the polygon, and the coordinates of the closest point.

```typescript
const polyRef = findNearestPolyResult.nodeRef;
const getClosestPointOnPolyResult = Nav.createGetClosestPointOnPolyResult();

Nav.getClosestPointOnPoly(getClosestPointOnPolyResult, navMesh, polyRef, position);

console.log(getClosestPointOnPolyResult.success); // true if a closest point was found
console.log(getClosestPointOnPolyResult.isOverPoly); // true if the position was inside the poly
console.log(getClosestPointOnPolyResult.position); // the closest point on the poly in world space [x, y, z]
```

```typescript
/**
 * Gets the closest point on a polygon to a given point
 * @param result the result object to populate
 * @param navMesh the navigation mesh
 * @param nodeRef the polygon node reference
 * @param position the point to find the closest point to
 * @returns the result object
 */
export function getClosestPointOnPoly(result: GetClosestPointOnPolyResult, navMesh: NavMesh, nodeRef: NodeRef, position: Vec3): GetClosestPointOnPolyResult;
```

--------------------------------

### Create Navcat Debug Helpers

Source: https://github.com/isaac-mason/navcat/blob/main/README.md

Use these functions to create visual helpers for different navcat data structures. Ensure the corresponding data structures (e.g., positions, indices, heightfield, contourSet, polyMesh, navMesh) are available.

```typescript
const triangleAreaIdsHelper = Nav.createTriangleAreaIdsHelper({ positions, indices }, triAreaIds);

const heightfieldHelper = Nav.createHeightfieldHelper(heightfield);

const compactHeightfieldSolidHelper = Nav.createCompactHeightfieldSolidHelper(compactHeightfield);

const compactHeightfieldDistancesHelper = Nav.createCompactHeightfieldDistancesHelper(compactHeightfield);

const compactHeightfieldRegionsHelper = Nav.createCompactHeightfieldRegionsHelper(compactHeightfield);

const rawContoursHelper = Nav.createRawContoursHelper(contourSet);

const simplifiedContoursHelper = Nav.createSimplifiedContoursHelper(contourSet);

const polyMeshHelper = Nav.createPolyMeshHelper(polyMesh);

const polyMeshDetailHelper = Nav.createPolyMeshDetailHelper(polyMeshDetail);

const navMeshHelper = Nav.createNavMeshHelper(navMesh);

const navMeshTileHelper = Nav.createNavMeshTileHelper(Object.values(navMesh.tiles)[0]);

const navMeshPolyHelper = Nav.createNavMeshPolyHelper(navMesh, 0);

const navMeshTileBvTreeHelper = Nav.createNavMeshTileBvTreeHelper(tile);

const navMeshBvTreeHelper = Nav.createNavMeshBvTreeHelper(navMesh);

const navMeshLinksHelper = Nav.createNavMeshLinksHelper(navMesh);

const navMeshTilePortalsHelper = Nav.createNavMeshTilePortalsHelper(tile);

const navMeshPortalsHelper = Nav.createNavMeshPortalsHelper(navMesh);

const findNodePathResult = Nav.findNodePath(navMesh, 0, 0, [1, 0, 1], [8, 0, 8], Nav.DEFAULT_QUERY_FILTER);
const searchNodesHelper = Nav.createSearchNodesHelper(findNodePathResult.nodes);

const navMeshOffMeshConnectionsHelper = Nav.createNavMeshOffMeshConnectionsHelper(navMesh);
```