Repository files navigation

Navigation mesh toolkit for ThreeJS, based onPatrolJS. Computes paths between points on a 3D nav mesh, supports multiple zones, and clamps movement vectors for FPS controls. To learn how to create a navigation mesh using Blender, seeCreating a Nav Mesh.

Thanks toNick Janssen for creatingPatrolJS, which was the basis for this library.

Traditionally games and 3D apps used waypoints to help their AI agents navigate. This is bad and has a lot of problems, but is generally easier to implement than navigation meshes. Navmeshes are far more accurate, faster, and take into account the size of the AI agent (e.g. tanks require move space to maneuver than soldiers).

For a thorough introduction to Navigation mesh pathfinding, see AI Blog's article,Fixing Pathfinding Once and For All.

npm install --save three-pathfinding

This library does not build navigation meshes for you — instead, create a navigation mesh usingBlender,Recast (CLI), or another tool.

Currently, this library does not accept the custom navigation mesh file formats created by tools like Recast.Instead, you will need to export the navigation mesh to a 3D model format (like OBJ or glTF) and then load itwith one of the three.js loaders, like THREE.OBJLoader or THREE.GLTFLoader. The library accepts aTHREE.BufferGeometry instance, and follows the +Y=Up convention of three.js and glTF.

Loading a mesh from a.gltf file:

// For ES6, see: https://github.com/mrdoob/three.js/issues/9562// CommonJSconstTHREE=window.THREE=require('three');require('three/examples/js/loaders/GLTFLoader.js');letnavmesh;constloader=newTHREE.GLTFLoader();loader.load('navmesh.gltf',({scene})=>{scene.traverse((node)=>{if(node.isMesh)navmesh=node;});},undefined,(e)=>{console.error(e);});

Initializing the library, creating a level, and finding a path:

// ES6import{Pathfinding}from'three-pathfinding';// CommonJSconst{ Pathfinding}=require('three-pathfinding');// UMDconstPathfinding=window.threePathfinding.Pathfinding;// Create level.constpathfinding=newPathfinding();constZONE='level1';pathfinding.setZoneData(ZONE,Pathfinding.createZone(navmesh.geometry));// Find path from A to B.constgroupID=pathfinding.getGroup(ZONE,a);constpath=pathfinding.findPath(a,b,ZONE,groupID);

The origin of an agent should initially be placed on the surface of the nav mesh. If needed, a dummy object can be used for pathfinding logic, and the rendered model for that agent may be placed at on offset as needed.

git clone https://github.com/donmccurdy/three-pathfinding.gitcd three-pathfindingnpm installnpm run dev

The demo will start athttp://localhost:3000/.

• Pathfinding
  • setZoneData
  • getRandomNode
  • getClosestNode
  • findPath
  • getGroup
  • clampStep
  • createZone
• PathfindingHelper
  • setPath
  • setPlayerPosition
  • setTargetPosition
  • setNodePosition
  • setStepPosition
  • reset
• Zone
• Group
• Node

Defines an instance of the pathfinding module, with one or more zones.

Sets data for the given zone.

• zoneIDstring
• zoneZone

Returns a random node within a given range of a given position.

• zoneIDstring
• groupIDnumber
• nearPositionVector3
• nearRangenumber

ReturnsNode

Returns the closest node to the target position.

• positionVector3
• zoneIDstring
• groupIDnumber
• checkPolygonboolean (optional, defaultfalse)

ReturnsNode

Returns a path between given start and end points. If a complete pathcannot be found, will return the nearest endpoint available.

• startPositionVector3 Start position.
• targetPositionVector3 Destination.
• zoneIDstring ID of current zone.
• groupIDnumber Current group ID.

ReturnsArray<Vector3> Array of points defining the path.

Returns closest node group ID for given position.

• zoneIDstring
• positionVector3

Returnsnumber

Clamps a step along the navmesh, given start and desired endpoint. May beused to constrain first-person / WASD controls.

• startVector3
• endVector3 Desired endpoint.
• nodeNode
• zoneIDstring
• groupIDnumber
• endTargetVector3 Updated endpoint.

ReturnsNode Updated node.

(Static) Builds a zone/node set from navigation mesh geometry.

• geometryBufferGeometry
• tolerancenumber Vertex welding tolerance. (optional, default1e-4)

ReturnsZone

Extends Object3D

Helper for debugging pathfinding behavior.

• pathArray<Vector3>

Returnsthis

• positionVector3

Returnsthis

• positionVector3

Returnsthis

• positionVector3

Returnsthis

• positionVector3

Returnsthis

Hides all markers.

Returnsthis

Defines a zone of interconnected groups on a navigation mesh.

Type:Object

• groupsArray<Group>
• verticesArray<Vector3>

Defines a group within a navigation mesh.

Type:Object

Defines a node (or polygon) within a group.

Type:Object

• idnumber
• neighboursArray<number> IDs of neighboring nodes.
• vertexIdsArray<number>
• centroidVector3
• portalsArray<Array<number>> Array of portals, each defined by two vertex IDs.
• closedboolean
• costnumber

• PatrolJS
• bgrin's astar library
• Digesting Duck's Simple Stupid Funnel Algorithm
• Recastnavigation's level mesh
• Constrained Movement Along Navmesh pt. 3