
## How to use the navigation mesh?

There are many cases to use a navigation mesh: AI and path finding, replace physics for collision detection (only allow player to go where it's possible instead of using collision detection) and many more cases theBabylon.js users will find.

First, create the navigation plugin

```javascript
let navigationPlugin = new BABYLON.RecastJSPlugin();
```

Prepare some parameters for the agent constraints (described below)

```javascript
var parameters = {
  cs: 0.2,
  ch: 0.2,
  walkableSlopeAngle: 35,
  walkableHeight: 1,
  walkableClimb: 1,
  walkableRadius: 1,
  maxEdgeLen: 12,
  maxSimplificationError: 1.3,
  minRegionArea: 8,
  mergeRegionArea: 20,
  maxVertsPerPoly: 6,
  detailSampleDist: 6,
  detailSampleMaxError: 1,
};
```

Call the navigation mesh generation with the parameters and the list of meshes

```javascript
navigationPlugin.createNavMesh([groundMesh, wallMesh1, wallMesh2, stair1, stair2], parameters);
```

And that's it! you can now use the navigation mesh with the crowd system or make queries.

Optionaly, you can get a display of the navmesh to ensure it corresponds to your space constraints

```javascript
navmeshdebug = navigationPlugin.createDebugNavMesh(scene);
var matdebug = new BABYLON.StandardMaterial("matdebug", scene);
matdebug.diffuseColor = new BABYLON.Color3(0.1, 0.2, 1);
matdebug.alpha = 0.2;
navmeshdebug.material = matdebug;
```

## Parameters

cs - The meshes are voxelized in order to compute walkable navmesh. This parameter in world unit define the widthand depth of 1 voxel.

ch - Same as cs but for height of the voxel.

walkableSlopeAngle - Angle in degree for the maximum walkable slop.

walkableHeight - The height in voxel units that is allowd to walk in.

walkableClimb - The delta in voxel units that can be climbed.

walkableRadius - the radius in voxel units of the agents.

maxEdgeLen - The maximum allowed length for contour edges along the border of the mesh. Voxel units.

maxSimplificationError - The maximum distance a simplified contour's border edges should deviate the original raw contour. Voxel units.

minRegionArea - The minimum number of cells allowed to form isolated island areas. Voxel units.

mergeRegionArea - Any regions with a span count smaller than this value will, if possible, be merged with larger regions. Voxel units.

maxVertsPerPoly - The maximum number of vertices allowed for polygons generated during the contour to polygon conversion process. Must be > 3.

detailSampleDist - Sets the sampling distance to use when generating the detail mesh. World units.

detailSampleMaxError - The maximum distance the detail mesh surface should deviate from heightfield data. World Units.

## Queries

Basically, query functions help at getting constraint point and vector by the navigation mesh.

```javascript
getClosestPoint(position: Vector3): Vector3;
getRandomPointAround(position: Vector3, maxRadius: number): Vector3;
moveAlong(position: Vector3, destination: Vector3): Vector3;
```

Respectively:

- get a point on the navmesh close to a world position parameter
- get a random world position, on the navmesh, inside a circle of maxRadius.
- constraint a segment by the navmesh and returns the ending world position. Like walking on the navmesh and stopping at the edge.

When the query can't find a valid solution, the value (0,0,0) is returned.

Those functions use a bounding box for querying the world. The solution returned is within that bound. To properly set the default box extent to get a finer or broader result, call:

```javascript
setDefaultQueryExtent(extent: Vector3): void;
```

If your query returns a point too far from the expected result, use a smaller extent.

It's possible to get a path built for navigation as a point array. It's up to the user to use this array for drawing prediction path, trigger events,...

```javascript
var pathPoints = navigationPlugin.computePath(crowd.getAgentPosition(agent), navigationPlugin.getClosestPoint(destinationPoint));
pathLine = BABYLON.MeshBuilder.CreateDashedLines("ribbon", { points: pathPoints, updatable: true, instance: pathLine }, scene);
```

## Baking result

Building a navigation mesh can take a lot of cpu and network resources. In order to lower the download size and cpu needed, it's possible to bake the result of the navigation mesh computation to a byte stream. That byte stream can later be restored to get the navigation mesh back.

To retrieve the binary representation of the computed navigation mesh:

```javascript
var binaryData = navigationPlugin.getNavmeshData();
```

binaryData is an Uint8Array that you can save to a file for example.
To restore an UInt8Array to a navigation mesh:

```javascript
navigationPlugin.buildFromNavmeshData(uint8array);
```

## Web Worker

Building a navigation mesh can be time and resource heavy. For many use cases, it can be necessary to delegate navmesh computation to a webworker. Work will be done in parallel, letting the engine display the content without slow downs.

To enable web worker, specify a web worker .js script URL to use:

```javascript
let navigationPlugin = new BABYLON.RecastJSPlugin();
navigationPlugin.setWorkerURL("workers/navMeshWorker.js");
```

A default web worker is provided at this URL : https://github.com/BabylonJS/Babylon.js/tree/master/packages/tools/playground/workers/navMeshWorker.js

Then, provide a completion callback to `createNavMesh` method. This callback will be called when the navigation mesh is computed and ready to use by the plugin.

```javascript
navigationPlugin.createNavMesh([staticMesh], navmeshParameters,(navmeshData) =>
{
    console.log("got worker data", navmeshData);
    navigationPlugin.buildFromNavmeshData(navmeshData);
    ...
```

`navMeshData` is a binary version, ready to serialize, of the the navmesh. It can be saved, streamed. User has to call `buildFromNavmeshData` to deserialize datas. Once the navmesh is fully loaded, it's possible to create crowd, query the navmesh,...

Performance note: The navmesh is constructed from geometry datas. If multiple meshes are needed, their geometry will be merged before passing the geometry positions and indices to Recast. This part of the code can be CPU intensive and cannot be done in a worker because of dependencies, copies, memory footprint.

An example of use with web worker : <Playground id="#TN7KNN#2" title="Navigation mesh computation with a web worker" description="Navigation mesh computation with a web worker"/>

## NPM

Loading Recast-Detour NPM module is different between version 1.3.0 and 1.4.0+ as later version is asynchronous. User has to use `await` like this:

```javascript
const recast = await Recast();
```



## Crowds and navigation agents

![a crowd ](/img/features/extensions/navigation/CrowdExample.png)

Now we have a navmesh, we can create autonomous agents and make them navigate within that navmesh constraint.
The agents will find the best path to that destination while avoinding other crowd agents.
An agent is attach to a Transform. That means that you have to attach a mesh to see them but also that you can attach pretty much anything.

A demo can be found at: <Playground id="#X5XCVT#240" title="Crowd and Navigation Agents" description="Crowd and navigation agents."/>

Click anywhere on the navmesh to make the agents go to that location.

## How to use it?

First thing is to create a crowd that all agents will belong to. Parameters are the maximum number of agents in the crowd, the maximum agent radius and the scene.

```
var crowd = navigationPlugin.createCrowd(10, 0.1, scene);
```

Then to create an agent and attach it to a transform, call:

```
var agentIndex = crowd.addAgent(position, agentParameters, transform);
```

And that's it! You will get a non moving agent. We now want to move it.

```
crowd.agentGoto(agentIndex, navigationPlugin.getClosestPoint(endPoint));
```
This code will get the closest position on the navmesh to endPoint. Then it asks the agent to go to that position.
Depending on your agent parameters, it will get there faster of slower.

## Agent Parameters

radius - Radius of the agent. World Unit.

height - Heigh in World Unit.

maxAcceleration - Acceleration max in World Unit per second per second

maxSpeed - Max speed in World Unit per second.

collisionQueryRange - The agent collision system will take care of others within that radius in World Unit.

pathOptimizationRange - How the path will be optimized and made more straight.

separationWeight - How hard the system will try to separate the agent. A Value of 0 means it will not try and agents might collide.

You can update any of these parameters, per agent, by calling :

```
// change speed and max speed
crowd.updateAgentParameters(agentIndex, {maxSpeed:10, maxAcceleration:200});
```

## Teleport

You can teleport an agent to any position using this call:

```
crowd.agentTeleport(agentIndex, navigationPlugin.getClosestPoint(destinationPoint));
```

Please note the navigation state is reseted when teleporting. You'll have to call ```agentGoto``` to choose a new destination.

## Agent orientation and next path target

Recastjs crowd system does not handle agent orientation. But the velocity is available and it's possible to orient the geometry toward it.
To do so, you will need to use Math.atan2 like in the following example. Please take care of the length of the velocity vector. If it's not big enough, you may encounter jittering.

```
let velocity = crowd.getAgentVelocity(agentIndex);
if (velocity.length() > 0.2)
{
    var desiredRotation = Math.atan2(velocity.x, velocity.z);
    // interpolate the rotation on Y to get a smoother orientation change
    ag.mesh.rotation.y = ag.mesh.rotation.y + (desiredRotation - ag.mesh.rotation.y) * 0.05;
}
```
In this PG <Playground id="#6AE0RP" title="Agent Orientation and Next Path Targeting" description="Example of agent orientation and next path targeting."/>

The agent's cube is oriented by the velocity and a grey little box is placed at the position of the next path corner.

## Agent reaching target Observer

An observable automaticaly fires when an agent reaches the destination (ie, is within radius of destination). The radius is by default the agent radius but it can be changed using `reachRadius` number propery in the `IAgentParameters` object.
If there are too many agents in the crowd trying to reach the same destination, a bottleneck can happen and few agents will reach destination. Be sure to properly set those values.
To add an observable, simply add your function:
```
var crowd = navigationPlugin.createCrowd(10, 0.1, scene);
...
crowd.onReachTargetObservable.add((agentInfos) => {
    console.log("agent reach destination: ", agentInfos.agentIndex);
});
```



## Prerequisites

Internaly, navigation mesh with support for obstacles differs from 'standard' use case with one static navigation mesh.
Obstacles mark tiles as dirty. Those tiles need to be reprocessed to compute a portion of the navigation mesh.
To do so, Recast introduces the concept of tiles. Each tile is a square portion of the nav mesh. Tiles a processed each frame.
Making huge changes processed of a couple of frames.

In order to build a Tiled nav mesh instead of a single mesh, add the following lines to the nav mesh creation parameters:

```
var navmeshParameters = {
    cs: 0.2,
    ch: 0.2,
    walkableSlopeAngle: 0,
    walkableHeight: 0.0,
    walkableClimb: 0,
    walkableRadius: 1,
    maxEdgeLen: 12.,
    maxSimplificationError: 1.3,
    minRegionArea: 8,
    mergeRegionArea: 20,
    maxVertsPerPoly: 6,
    detailSampleDist: 6,
    detailSampleMaxError: 15,
    borderSize: 1,
    tileSize:20
    };
```

Note the addition of `tileSize`. It's the world unit size of each tile. If it's not present or has a value a zero, it falls back to the standard use and obstacles won't work.
Also, depending on your use case, this value must be carrefully chosen to trade between too many tiles and too much cpu intensive updates.

## Obstacles API

Once the navigation mesh is updated to take tiles into account, obstacles are accessible thru 3 simple functions:
```
addCylinderObstacle(position: Vector3, radius: number, height: number): IObstacle;
addBoxObstacle(position: Vector3, extent: Vector3, angle: number): IObstacle;
removeObstacle(obstacle: IObstacle): void;
```

Keep a list of added obstacles in order to remove them later. An obstacle that's not colliding with the navigation mesh will have no influence.

<Playground id="#WCSDE1" title="Adding a door to a navigation mesh" description="Example of door simulation using nav mesh obstacles."/>


![Generated Navmesh ](/img/toolsAndResources/navigation/NavMeshGeneration.png)

A Navigation Mesh (or navmesh for short) is a surface topology describing the space where an agent can go based on constraints.
Based on parameters like agent radius, agent climbing capability, agent height,... the navmesh generation computes a topology from source meshes (the world geometry).
Then, this topology can have a debug display (blue mesh on screenshot above) to validate the parameters. 

A demo can be found at: <Playground id="#HFY257#4" title="Crowd Navigation Demo" description="Simple example showcasing the crowd agent and nav mesh systems."/>



## FreeCamera on the Ground

In this example, our player moves on the ground : a character walking, a car driving or anything like we can find in a FPS game.  
The used camera is a FreeCamera. It will keeps on the ground while moving onward, backward, to the right or to the left.  

Let's create a simple data map with a sinus/cosinus function :
```javascript
        // map creation
        var mapSubX = 100;
        var mapSubZ = 100;
        var mapData = new Float32Array(mapSubX * mapSubZ * 3);   
        for (var l = 0; l < mapSubZ; l++) {           
            for (var w = 0; w < mapSubX; w++) {                
                mapData[3 *(l * mapSubX + w)] = (w - mapSubX * 0.5) * 2.0;
                mapData[3 * (l * mapSubX + w) + 1] = w / (l +1) * Math.sin(l / 2) * Math.cos(w / 2) * 2.0;
                mapData[3 * (l * mapSubX + w) + 2] = (l - mapSubZ * 0.5) * 2.0;
           }            
        }

```
The hills have a different height depending on their positions on the map.  

Let's create then a dynamic terrain from this map :
```javascript
        // terrain creation
        var terrainSub = 50;
        var params = {
            mapData: mapData,
            mapSubX: mapSubX,
            mapSubZ: mapSubZ,
            terrainSub: terrainSub
        };
        terrain = new BABYLON.DynamicTerrain("terrain", params, scene);
```
Now we can set the camera altitude on each frame at a fixed elevation above the terrain.  For this, we use the method `getHeightFromMap(x, z)` what returns the height (y coordinate) of the terrain at the passed location _(x, z)_.  

```javascript
    var camElevation = 2.0;
    var camAltitude = 0.0;
    scene.registerBeforeRender(function() {
        camAltitude = terrain.getHeightFromMap(camera.position.x, camera.position.z) + camElevation;
        camera.position.y = camAltitude;
    });
```
If we move the camera with the keyboard arrow keys, it will follow the terrain ground.   

PG: <Playground id="#J6FMJ#6" title="Dynamic Terrain" description="Example Follow Terrain"/>   

We could also make a bigger map and a bigger terrain : 
```javascript
    var mapSubX = 500;
    var mapSubZ = 300;
    var terrainSub = 100;
```
As the player keeps on the ground, he/she can't see very far in the distance, so we can choose to update the terrain only after 8 map quads crossed over either on the X axis, either on the Z axis :
```javascript
    terrain.subToleranceX = 8;
    terrain.subToleranceZ = 8;
```
The terrain is then updated less often, this lets more CPU to manage the player behavior and all what can happen or move in the close area around him.  

Finally, we could also choose to extend the terrain visible size by setting some LOD in the distance.  
By example, `LODLimits = [4, 3, 2, 1, 1]` would mean that :  

* the initial LOD factor (default 1, the one at the camera location) is incremented for all the terrain quads under the 4-th perimetric rows and columns, so it's 1 + 1 = 2 for them, 
* it's incremented once again for all the terrain quads under the 3-th perimetric rows and columns, so it's 2 + 1 = 3 for them,
* it's incremented once again for the ones under the 2-nd rows and columns, so it's 4 for them
* it's incremented finally twice, because there are two `1` in the array, for the quads under the first rows and columns, so 3 + 2 x 1 = 5 for those last ones.  

```javascript
terrain.LODLimits = [4, 3, 2, 1, 1];
```
Let's don't worry if this feature seems complex to understand and let's just remember that it extends the terrain visible size on its perimeter and reduces the rendered map details in the same time.  

PG: <Playground id="#J6FMJ#7" title="Dynamic Terrain" description="Example Larger Map"/>
 

Crowd Navigation System - Extension

In This Category

Creating A Navigation Mesh

Learn how to create a mesh as a confinment system for crowd agents.

Crowd Agents

Learn how to create crowd agents that follow a path along a navigation mesh.

Adding and removing obstacles

Learn how to add and remove obstacles for crowd agents.