three-pathfinding

Navigation mesh toolkit for ThreeJS, based on PatrolJS. 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, see Creating a Nav Mesh.

Quickstart

Installation

npm install --save three-pathfinding

Example

const Pathfinder = require('three-pathfinding');
const pathfinder = new Pathfinder();

// Create level.
const ZONE = 'level1';
pathfinder.setZoneData(ZONE, Pathfinder.createZone(mesh.geometry));

// Find path from A to B.
const groupID = pathfinder.getGroup(ZONE, a);
const path = pathfinder.findPath(a, b, ZONE, groupID);

Running the demo locally

git clone https://github.com/donmccurdy/three-pathfinding.git
cd three-pathfinding

npm install
npm run dev

The demo will start at http://localhost:9966/demo/demo.html.

API

Table of Contents

• Path
  • setZoneData
  • getGroup
  • getRandomNode
  • getClosestNode
  • findPath
  • clampStep
  • createZone
• Zone
• Group
• Node

Path

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

setZoneData

Sets data for the given zone.

Parameters

• zoneID string
• zone Zone

getGroup

Returns closest node group ID for given position.

Parameters

• zoneID string
• position THREE.Vector3

Returns number

getRandomNode

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

Parameters

• zoneID string
• groupID number
• nearPosition THREE.Vector3
• nearRange number

Returns Node

getClosestNode

Returns the closest node to the target position.

Parameters

• position THREE.Vector3
• zoneID string
• groupID number
• checkPolygon boolean (optional, default false)

Returns Node

findPath

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

Parameters

• startPosition THREE.Vector3 Start position.
• targetPosition THREE.Vector3 Destination.
• zoneID string ID of current zone.
• groupID number Current group ID.

Returns Array<THREE.Vector3> Array of points defining the path.

clampStep

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

Parameters

• start THREE.Vector3
• end THREE.Vector3 Desired endpoint.
• node Node
• zoneID string
• groupID number
• endTarget THREE.Vector3 Updated endpoint.

Returns Node Updated node.

createZone

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

Parameters

• geometry THREE.Geometry

Returns Zone

Zone

Defines a zone of interconnected groups on a navigation mesh.

Properties

• groups Array<Group>

Group

Defines a group within a navigation mesh.

Node

Defines a node (or polygon) within a group.

Properties

• id number
• neighbours Array<number> IDs of neighboring nodes.
• centroid THREE.Vector3
• portals Array<Array<number>> Array of portals, each defined by two vertex IDs.
• closed boolean
• cost number

Thanks to

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