Giter Club home page Giter Club logo

isaac-mason / recast-navigation-js Goto Github PK

View Code? Open in Web Editor NEW
204.0 7.0 15.0 5.76 MB

JavaScript navigation mesh construction, path-finding, and spatial reasoning toolkit. WebAssembly port of Recast Navigation.

Home Page: https://recast-navigation-js.isaacmason.com

License: MIT License

CMake 1.17% JavaScript 1.26% C++ 16.91% CSS 0.25% HTML 0.19% TypeScript 79.75% Shell 0.35% C 0.12%
crowd-simulation detour javascript navmesh-generation pathfinding recast recastnavigation webassembly

recast-navigation-js's Introduction

cover

Version GitHub Workflow Status (with event) Downloads Bundle Size

recast-navigation-js

  • ๐Ÿ“ โ€Ž NavMesh generation
  • ๐Ÿงญ โ€Ž Pathfinding
  • ๐Ÿง‘โ€๐Ÿคโ€๐Ÿง‘ โ€Ž Crowd simulation
  • ๐Ÿšง โ€Ž Temporary obstacles
  • ๐ŸŒ โ€Ž Web and Node support
  • ๐Ÿ’™ โ€Ž TypeScript friendly
  • ๐Ÿ–‡ โ€Ž Easy integration with three.js via @recast-navigation/three

Overview

recast-navigation-js is a WebAssembly port of the Recast and Detour libraries. Recast is a state of the art navigation mesh construction toolset for games, and Detour is a path-finding and spatial reasoning toolkit.

This library provides high level APIs that make it easy to get started creating navigation meshes, querying them, and simulating crowds. It also provides lower-level APIs that give you fine-grained control over the navmesh generation process.

Examples

Go to the examples website to see the project in action:

Demonstrations of how to use the library in different environments (such as NodeJS, CommonJS) can be found in the examples directory.

Installation

This package ships as both ECMAScript modules and CJS, and is compatible with Node.js and browser environments.

NPM

npm install recast-navigation

Unpkg

<script type="importmap">
  {
    "imports": {
      "@recast-navigation/core": "https://unpkg.com/@recast-navigation/[email protected]/dist/index.mjs",
      "@recast-navigation/generators": "https://unpkg.com/@recast-navigation/[email protected]/dist/index.mjs",
      "@recast-navigation/three": "https://unpkg.com/@recast-navigation/[email protected]/dist/index.mjs"
    }
  }
</script>
<script type="module">
  import { init } from '@recast-navigation/core';

  await init();
</script>

Usage with bundlers

If you are using Vite, you may need to opt recast-navigation out of pre-bundling:

export default defineConfig(() => ({
  optimizeDeps: { exclude: ['recast-navigation'] }
)}

Documentation

API Documentation can be found at https://docs.recast-navigation-js.isaacmason.com.

For information on changes between versions, see CHANGELOG.md

To get the most out of this library, you should have some familiarity with the Recast and Detour libraries. These are some good resources to get started:

Documentation for the Recast and Detour c++ libraries can be found here:

The GitHub issues and Google Discussions are great resources for learning about the library and getting guidance on common issues.

Usage

Initialization

Before you can use the library, you must initialize it. This is an asynchronous operation.

Calling init() after the library has already been initialized will return a promise that resolves immediately.

import { init } from 'recast-navigation';

await init();

Generating a NavMesh

The easiest way to generate a NavMesh is using the high level generator functions from recast-navigation/generators:

  • generateSoloNavMesh - Generates a NavMesh with a single tile. You can use this for smaller environments.
  • generateTiledNavMesh - Generates a NavMesh with multiple tiles. You should use this for larger environments.
  • generateTileCache - Generates a TileCache that supports temporary obstacles. See the Temporary Obstacles section.

The input positions and indices should adhere to OpenGL conventions:

  • Use the right-handed coordinate system
  • Indices should be in counter-clockwise winding order
  • The positions and indices arguments should be flat arrays of numbers
import { generateSoloNavMesh } from 'recast-navigation/generators';

const positions = [
  /* flat array of positions */
  /* e.g. x1, y1, z1, x2, y2, z2, ... */
];

const indices = [
  /* flat array of indices */
];

const navMeshConfig = {
  /* ... */
};

const { success, navMesh } = generateSoloNavMesh(
  positions,
  indices,
  navMeshConfig
);

See the docs for more information on generator options: https://docs.recast-navigation-js.isaacmason.com/modules/generators.html

Advanced Usage

This library provides low-level APIs that aim to match the recast and detour c++ api, allowing you to create custom navigation mesh generators based on your specific needs. You can use the NavMesh generators provided by @recast-navigation/generators as a basis: https://github.com/isaac-mason/recast-navigation-js/tree/main/packages/recast-navigation-generators/src/generators

An example of a custom NavMesh generator with custom areas can be found here: https://recast-navigation-js.isaacmason.com/?path=/story/advanced-custom-areas--compute-path

Please note that not all recast and detour functionality is exposed yet. If you require unexposed functionality, please submit an issue or a pull request.

Querying a NavMesh

import { NavMeshQuery } from 'recast-navigation';

const navMeshQuery = new NavMeshQuery({ navMesh });

/* find the closest point on the NavMesh to the given position */
const position = { x: 0, y: 0, z: 0 };
const { success, status, point, polyRef, isPointOverPoly } =
  navMeshQuery.findClosestPoint(position);

/* get a random point around the given position */
const radius = 0.5;
const {
  success,
  status,
  randomPolyRef,
  randomPoint: initialAgentPosition,
} = navMeshQuery.findRandomPointAroundCircle(position, radius);

/* compute a straight path between two points */
const start = { x: 0, y: 0, z: 0 };
const end = { x: 2, y: 0, z: 0 };
const { success, error, path } = navMeshQuery.computePath(start, end);

Crowds and Agents

First, create a Crowd:

import { Crowd } from 'recast-navigation';

const maxAgents = 10;
const maxAgentRadius = 0.6;

const crowd = new Crowd({ maxAgents, maxAgentRadius, navMesh });

Next, create and interface with agents in the crowd.

const position = { x: 0, y: 0, z: 0 };
const radius = 2;

const {
  success,
  status,
  randomPolyRef,
  randomPoint: initialAgentPosition,
} = navMeshQuery.findRandomPointAroundCircle(position, radius);

const agent = crowd.addAgent(initialAgentPosition, {
  radius: 0.5,
  height: 0.5,
  maxAcceleration: 4.0,
  maxSpeed: 1.0,
  collisionQueryRange: 0.5,
  pathOptimizationRange: 0.0,
  separationWeight: 1.0,
});

/* get information about the agent */
const agentPosition = agent.position();
const agentVelocity = agent.velocity();
const agentNextTargetPath = agent.nextTargetPath();
const agentState = agent.state();
const agentCorners = agent.corners();
const agentParameters = agent.parameters();

/* tell the agent to move to a target position */
const targetPosition = { x: 0, y: 0, z: 0 };
agent.requestMoveTarget(targetPosition);

/* tell the agent to move in a direction */
const targetVelocity = { x: 0, y: 0, z: 0 };
agent.requestMoveVelocity(targetVelocity);

/* reset the agents target */
agent.resetMoveTarget();

/* teleport the agent to a position */
agent.teleport(targetPosition);

/* update an agent parameter */
agent.maxAcceleration = 4;

/* update multiple parameters for an agent */
agent.updateParameters({
  maxAcceleration: 2,
});

/* set all parameters for an agent */
agent.setParameters({
  // any omitted parameters will be set to their default values
});

/* remove the agent */
crowd.removeAgent(agent);

To update the crowd, first set a timeStep, then call update each frame with the delta time.

const dt = 1 / 60;
crowd.timeStep = dt;

// you should call this every frame
crowd.update(dt);

Temporary Obstacles

Recast Navigation supports temporary Box and Cylinder obstacles via a TileCache.

TileCache assumes small tiles (around 32-64 squared). Using tileSize values outside this range may result in unexpected behaviour.

import { generateTileCache } from 'recast-navigation/generators';

/* create a tile cache */
const { success, navMesh, tileCache } = generateTileCache(positions, indices, {
  /* ... */
  tileSize: 16,
});

You can use addCylinderObstacle, addBoxObstacle, and removeObstacle to add and remove obstacles from the TileCache.

After adding or removing obstacles you can call tileCache.update(navMesh) to rebuild navmesh tiles.

Adding or removing an obstacle will internally create an "obstacle request". TileCache supports queuing up to 64 obstacle requests. If the requests queue is full, calls to addCylinderObstacle and addBoxObstacle will fail and return a dtStatus status code DT_BUFFER_TOO_SMALL.

The tileCache.update method returns upToDate, whether the tile cache is fully up to date with obstacle requests and tile rebuilds. If the tile cache isn't up to date another call will continue processing obstacle requests and tile rebuilds; otherwise it will have no effect.

If not many obstacle requests occur between updates, an easy pattern is to call tileCache.update periodically, such as every game update.

If many obstacle requests have been made and you need to avoid reaching the 64 obstacle request limit, you can call tileCache.update multiple times, bailing out when upToDate is true or after a maximum number of updates.

/* add a Box obstacle to the NavMesh */
const position = { x: 0, y: 0, z: 0 };
const extent = { x: 1, y: 1, z: 1 };
const angle = 0;
const addBoxObstacleResult = tileCache.addBoxObstacle(position, extent, angle);
const boxObstacle = addBoxObstacleResult.obstacle;

/* add a Cylinder obstacle to the NavMesh */
const radius = 1;
const height = 1;
const addCylinderObstacleResult = tileCache.addCylinderObstacle(
  position,
  radius,
  height,
  angle
);
const cylinderObstacle = addCylinderObstacleResult.obstacle;

/* remove the obstacles from the NavMesh */
const removeObstacleResult = tileCache.removeObstacle(boxObstacle);

/* update to reflect obstacle changes */
// if few obstacles are added/removed between updates, you could call tileCache.update every game update
tileCache.update(navMesh);

// if your obstacle requests affect many tiles, you may need to call update multiple times
const maxTileCacheUpdates = 5;
for (let i = 0; i < maxTileCacheUpdates; i++) {
  const { upToDate } = tileCache.update(navMesh);
  if (upToDate) break;
}

Off Mesh Connections

Off mesh connections are user-defined connections between two points on a NavMesh. You can use them to create things like ladders, teleporters, jump pads, etc.

Off mesh connections can be bidirectional or unidirectional.

You can provide a list of off mesh connections to the generateSoloNavMesh and generateTiledNavMesh high level generator functions.

const { success, navMesh } = generateSoloNavMesh(positions, indices, {
  // ...
  offMeshConnections: [
    {
      startPosition: { x: 0, y: 5, z: 0 },
      endPosition: { x: 2, y: 0, z: 0 },
      radius: 0.5,
      bidirectional: false,
      area: 0,
      flags: 1,
      userId: 0, // optional
    },
  ],
});

You can use agent.state() to determine if an agent is currently traversing an off mesh connection.

Adding Off Mesh Connections to a TileCache

To add off mesh connections to a TileCache using generateTileCache, you must provide a TileCacheMeshProcess implementation that creates off mesh connections. For example:

const tileCacheMeshProcess = new TileCacheMeshProcess(
  (navMeshCreateParams, polyAreas, polyFlags) => {
    for (let i = 0; i < navMeshCreateParams.polyCount(); ++i) {
      polyAreas.set(i, 0);
      polyFlags.set(i, 1);
    }

    navMeshCreateParams.setOffMeshConnections([
      {
        startPosition: { x: 0, y: 5, z: 0 },
        endPosition: { x: 2, y: 0, z: 0 },
        radius: 0.5,
        bidirectional: false,
        area: 0,
        flags: 1,
      },
    ]);
  }
);

const tileCacheGeneratorConfig = {
  // ... other config ...
  tileCacheMeshProcess,
};

const { success, navMesh, tileCache } = generateTileCache(
  positions,
  indices,
  tileCacheGeneratorConfig
);

Debugging

Debug Nav Mesh

You can use getDebugNavMesh to get a debug representation of the NavMesh.

const debugNavMesh = navMesh.getDebugNavMesh();

const { positions, indices } = debugNavMesh;

If you are using three.js, you can use NavMeshHelper and CrowdHelper to visualize NavMeshes, Crowds, and NavMesh generation intermediates.

See the @recast-navigation/three package README for usage information.

Detour Status Codes

Many Detour APIs return a status property. This is a dtStatus enum, which is a number representing the status of the operation.

You can use the statusToReadableString function to convert a dtStatus to a human-readable string.

import { statusToReadableString } from 'recast-navigation';

console.log(statusToReadableString(status));

If you need to work with status codes programmatically, you can use these utilities:

import {
  statusSucceed,
  statusInProgress,
  statusFailed,
  statusDetail,
} from 'recast-navigation';

// returns true if the status is a success
const succeeded = statusSucceed(status);

// returns true if the status is in progress
const inProgress = statusInProgress(status);

// returns true if the status is a failure
const failed = statusFailed(status);

// get the detail of the status
const detail = statusDetail(status);

// Raw.Detour.WRONG_MAGIC;
// Raw.Detour.WRONG_VERSION;
// Raw.Detour.OUT_OF_MEMORY;
// Raw.Detour.INVALID_PARAM;
// Raw.Detour.BUFFER_TOO_SMALL;
// Raw.Detour.OUT_OF_NODES;
// Raw.Detour.PARTIAL_RESULT;
// Raw.Detour.ALREADY_OCCUPIED;

Importing and Exporting

A NavMesh and TileCache can be imported and exported as a Uint8Array.

See below for an example of exporting then importing a NavMesh:

import { exportNavMesh, importNavMesh } from 'recast-navigation';

/* export */
const navMeshExport: Uint8Array = exportNavMesh(navMesh);

/* import */
const { navMesh } = importNavMesh(navMeshExport);

To export a TileCache and NavMesh, the usage varies slightly:

import { exportNavMesh, importNavMesh } from 'recast-navigation';

/* exporting */
// pass both the navMesh and the tileCache
const navMeshExport: Uint8Array = exportNavMesh(navMesh, tileCache);

/* importing */
// also pass the TileCacheMeshProcess implementation for the tile cache
// if you used `generateTileCache` and didn't provide one, `createDefaultTileCacheMeshProcess` returns the default TileCacheMeshProcess `generateTileCache` uses
const tileCacheMeshProcess = createDefaultTileCacheMeshProcess();

const { navMesh, tileCache } = importNavMesh(
  navMeshExport,
  tileCacheMeshProcess
);

Packages

Functionality is spread across packages in the @recast-navigation/* organization, with the recast-navigation acting as an umbrella package.

You can choose between picking the scoped packages you need, or using the umbrella recast-navigation package, which provides additional entrypoints for specific frameworks and libraries.

All packages ship as ECMAScript modules, and are compatible with Node.js and browser environments.

Version

The umbrella package for recast-navigation.

> npm install recast-navigation

Version

The core library!

> npm install @recast-navigation/core

Version

NavMesh generator implementations. Use these to get started, and as a basis for your own NavMesh generator.

> npm install @recast-navigation/generators

Version

Helpers for three.js.

> npm install @recast-navigation/three

Apps

A website for generating navmeshes for your game. Drag 'n' drop your GLTF, fine tune your settings, and download your navmesh!

(source)

Acknowledgements

recast-navigation-js's People

Contributors

dependabot[bot] avatar github-actions[bot] avatar isaac-mason avatar rob-myers avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar

recast-navigation-js's Issues

Expose Recast (Recast.h) functions

To support advanced use cases the Recast.h functions should be exposed.

The NavMeshGenerator class will stay - it's simpler to use and will cover the majority of use cases. Depending on performance, NavMeshGenerator could be updated to use the exposed js recast functions rather than having the logic in c++

Walkable Slope Angle isn't affecting the generated navmesh

It seems even though the walkableSlopeAngle property is correctly passed to the Recast NavMesh config object, it doesn't affect generation in any way.

Steps to reproduce:

  • Load a model on the NavMesh generator example.
  • Change the property and re-generate.

image

PS Many thanks for your great work!

Create examples that don't use react

The current storybook examples are good for development and manually testing, but they are not so great for folks wanting to understand how to use the library.

This issue tracks creating a collection of examples that don't use react/storybook.

tiled navmesh generation Fails

Drop this file on https://navmesh.isaacmason.com/

Case 1: Generate a tiled mesh with cell size 0.1 and tileSize: 32

Navmesh generation fails with Aborted() error

Also seems the lib isn't recovering, retrying with other params always gives Aborted after the first error.

Case 2: reload, drop the file and generate with 0.2 cell size

The navmesh bounds do not cover the whole input meshes

Screenshot 2023-09-25 at 19 07 09

Also noticed the non recovery issue happens whenever the generation fails (for example after solo generation fails for big scenes, retrying with different params seems to fail instantly)

Add docs and example demonstrating how to generate a NavMesh in a worker

This library already provides primitives that help with generating a nav mesh in a worker, but the worker orchestration needs to be done in user-land.

High-level steps:

  • Inside a web worker, use the library to create a navmesh (e.g. with a high-level generator such as generateSoloNavMesh)
  • Export the navmesh with exportNavMesh to get a transferable uInt8Array
  • Post the uInt8Array nav mesh export to the main thread
  • Use importNavMesh on the main thread, passing in the uInt8Array export

Support separate wasm file as well as inlined wasm file

The main advantages of a separate wasm file are reduced bundle size and faster initialisation.

The downside is there are extra considerations required for supporting bundler configuration or serving the wasm from somewhere.

Continuing to support the existing inlined wasm flavour is important for ease of use.

There are several potential approaches. To name some:

  • Have two versions of the recast-navigation npm package, one with an inlined wasm, one with a separate wasm file
    • rapier.js takes this approach
  • Have one recast-navigation npm package, support passing an instance of @recast-navigation/wasm (separate file, inlined wasm, asm.js, other) to init
    • if there was a default, would need to make sure it could be tree-shaken

Refactor recast-navigation-wasm

Right now everything is in recast-navigation.h and recast-navigation.cpp.

While ideally there should be as little as possible wrapper c++ code, this still desperately needs refactoring. As a start, this should be split out into separate files as appropriate.

Improve memory cleanup functionality and document

Right now manual memory management with this lib is not straightforward, and not everything required is correctly exposed. Also, nothing is documented in the READMEs

This needs fixing!

todo:

  • add destroy() methods where appropriate
  • expose emscripten _free and destroy in @recast-navigation/core for more advanced use cases
  • add memory management information to READMEs

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.