NavMesh()

Implementation of a navigation mesh. A navigation mesh is a network of convex polygons which define the walkable areas of a game environment. A convex polygon allows unobstructed travel from any point in the polygon to any other. This is useful because it enables the navigation mesh to be represented using a graph where each node represents a convex polygon and their respective edges represent the neighborly relations to other polygons. More compact navigation graphs lead to faster graph search execution.

This particular implementation is able to merge convex polygons into bigger ones as long as they keep their convexity and coplanarity. The performance of the path finding process and convex region tests for complex navigation meshes can be improved by using a spatial index like CellSpacePartitioning.

Constructs a new navigation mesh.

Author:

Members

epsilonContainsTest :Number
navigation/navmesh/NavMesh.js, line 74

The tolerance value for the containment test.

Default Value:
  • 1

epsilonCoplanarTest :Number
navigation/navmesh/NavMesh.js, line 67

The tolerance value for the coplanar test.

Default Value:
  • 1e-3

graph :Graph
navigation/navmesh/NavMesh.js, line 46

The internal navigation graph of this navigation mesh representing neighboring polygons.

mergeConvexRegions :Boolean
navigation/navmesh/NavMesh.js, line 81

Whether convex regions should be merged or not.

Default Value:
  • true

regions :Array.<Polygon>
navigation/navmesh/NavMesh.js, line 53

The list of convex regions.

nullable spatialIndex :CellSpacePartitioning
navigation/navmesh/NavMesh.js, line 60

A reference to a spatial index.

Default Value:
  • null

Methods

clampMovement(currentRegion, startPosition, endPosition, clampPosition) → {Polygon}
navigation/navmesh/NavMesh.js, line 388

This method can be used to restrict the movement of a game entity on the navigation mesh. Instead of preventing any form of translation when a game entity hits a border edge, the movement is clamped along the contour of the navigation mesh. The computational overhead of this method for complex navigation meshes can be reduced by using a spatial index.

Parameters:
Name Type Description
currentRegion Polygon

The current convex region of the game entity.
startPosition Vector3

The original start position of the entity for the current simulation step.
endPosition Vector3

The original end position of the entity for the current simulation step.
clampPosition Vector3

The clamped position of the entity for the current simulation step.
Returns:
Polygon -

The new convex region the game entity is in.

clear() → {NavMesh}
navigation/navmesh/NavMesh.js, line 182

Clears the internal state of this navigation mesh.

Returns:
NavMesh -

A reference to this navigation mesh.

findPath(from, to) → {Array.<Vector3>}
navigation/navmesh/NavMesh.js, line 305

Returns the shortest path that leads from the given start position to the end position. The computational overhead of this method for complex navigation meshes can greatly reduced by using a spatial index.

Parameters:
Name Type Description
from Vector3

The start/source position.
to Vector3

The end/destination position.
Returns:
Array.<Vector3> -

The shortest path as an array of points.

fromPolygons(polygons) → {NavMesh}
navigation/navmesh/NavMesh.js, line 95

Creates the navigation mesh from an array of convex polygons.

Parameters:
Name Type Description
polygons Array.<Polygon>

An array of convex polygons.
Returns:
NavMesh -

A reference to this navigation mesh.

getClosestRegion(point) → {Polygon}
navigation/navmesh/NavMesh.js, line 198

Returns the closest convex region for the given point in 3D space.

Parameters:
Name Type Description
point Vector3

A point in 3D space.
Returns:
Polygon -

The closest convex region.

getNodeIndex(region) → {Number}
navigation/navmesh/NavMesh.js, line 290

Returns the node index for the given region. The index represents the navigation node of a region in the navigation graph.

Parameters:
Name Type Description
region Polygon

The convex region.
Returns:
Number -

The respective node index.

getRandomRegion() → {Polygon}
navigation/navmesh/NavMesh.js, line 229

Returns at random a convex region from the navigation mesh.

Returns:
Polygon -

The convex region.

getRegionForPoint(point, epsilon) → {Polygon}
navigation/navmesh/NavMesh.js, line 250

Returns the region that contains the given point. The computational overhead of this method for complex navigation meshes can be reduced by using a spatial index. If no convex region contains the point, null is returned.

Parameters:
Name Type Default Description
point Vector3

A point in 3D space.
epsilon Number 0.001

Tolerance value for the containment test.
Returns:
Polygon -

The convex region that contains the point.

updateSpatialIndex() → {NavMesh}
navigation/navmesh/NavMesh.js, line 481

Updates the spatial index by assigning all convex regions to the partitions of the spatial index.

Returns:
NavMesh -

A reference to this navigation mesh.