three-pathfinding - npm Package Compare versions

Comparing version 0.3.0 to 0.4.0

package.json

 {
 	"name": "three-pathfinding",
-	"version": "0.3.0",
+	"version": "0.4.0",
 	"description": "Navigation mesh toolkit for three.js, based on PatrolJS",
@@ -8,2 +8,3 @@ "main": "src/index.js",
 		"dev": "budo browser.js:bundle.js --live",
+		"docs": "documentation build src/index.js --shallow -f md | replace-between --target README.md --token API",
 		"postversion": "git push && git push --tags && npm publish"
@@ -29,4 +30,6 @@ },
 		"browserify": "^14.4.0",
-		"budo": "^10.0.4"
+		"budo": "^10.0.4",
+		"documentation": "^5.3.3",
+		"replace-between": "0.0.8"
 	}
 }

README.md

@@ -5,4 +5,123 @@ # three-pathfinding
 
-> Work in progress.
+## Installation
 
+```
+npm install --save three-pathfinding
+```
+
+## Example
+
+```js
+  // Create level.
+  const ZONE = 'level1';
+  const zone = Path.buildNodes(this.navMesh.geometry);
+  Path.setZoneData(ZONE, zone);
+
+  // Find path from A to B.
+  const group = Path.getGroup(ZONE, a);
+  const path = Path.findPath(a, b, ZONE, group);
+```
+
+## API
+
+<!--- API BEGIN --->
+
+<!-- Generated by documentation.js. Update this documentation by updating the source code. -->
+
+### Table of Contents
+
+-   [buildNodes](#buildnodes)
+-   [setZoneData](#setzonedata)
+-   [getGroup](#getgroup)
+-   [getRandomNode](#getrandomnode)
+-   [getClosestNode](#getclosestnode)
+-   [clampStep](#clampstep)
+-   [findPath](#findpath)
+
+## buildNodes
+
+Builds a zone/node set from navigation mesh.
+
+**Parameters**
+
+-   `geometry` **THREE.Geometry** 
+
+Returns **Path.Zone** 
+
+## setZoneData
+
+Sets data for the given zone.
+
+**Parameters**
+
+-   `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)** 
+-   `zone` **Path.Zone** 
+
+## getGroup
+
+Returns closest node group for given position.
+
+**Parameters**
+
+-   `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)** 
+-   `position` **THREE.Vector3** 
+
+Returns **Path.Group** 
+
+## getRandomNode
+
+Returns a random node within a given range of a given position.
+
+**Parameters**
+
+-   `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)** 
+-   `group` **Path.Group** 
+-   `nearPosition` **THREE.Vector3** 
+-   `nearRange` **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)** 
+
+Returns **Path.Node** 
+
+## getClosestNode
+
+Returns the closest node to the target position.
+
+**Parameters**
+
+-   `position` **THREE.Vector3** 
+-   `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)** 
+-   `group` **Path.Group** 
+-   `checkPolygon` **[boolean](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Boolean)**  (optional, default `false`)
+
+Returns **Path.Node** 
+
+## 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` **Path.Node** 
+-   `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)** 
+-   `group` **Path.Group** 
+-   `endTarget` **THREE.Vector3** Updated endpoint.
+
+Returns **Path.Node** Updated node.
+
+## findPath
+
+Returns a path between given start and end points.
+
+**Parameters**
+
+-   `startPosition` **THREE.Vector3** 
+-   `targetPosition` **THREE.Vector3** 
+-   `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)** 
+-   `group` **Path.Group** 
+
+Returns **[Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)&lt;THREE.Vector3>** 
+<!--- API END --->
+
 ## Thanks to
@@ -9,0 +128,0 @@

src/index.js

@@ -0,1 +1,3 @@
+/* global THREE */
+
 const utils = require('./utils');
@@ -203,23 +205,34 @@ const AStar = require('./AStar');
 module.exports = {
+	/**
+	 * Builds a zone/node set from navigation mesh.
+	 * @param  {THREE.Geometry} geometry
+	 * @return {Path.Zone}
+	 */
 	buildNodes: function (geometry) {
-		var navigationMesh = buildNavigationMesh(geometry);
+		return groupNavMesh(buildNavigationMesh(geometry));
+	},
 
-		var zoneNodes = groupNavMesh(navigationMesh);
-
-		return zoneNodes;
+	/**
+	 * Sets data for the given zone.
+	 * @param {string} zoneID
+	 * @param {Path.Zone} zone
+	 */
+	setZoneData: function (zoneID, zone) {
+		zoneNodes[zoneID] = zone;
 	},
-	setZoneData: function (zone, data) {
-		zoneNodes[zone] = data;
-	},
-	getGroup: function (zone, position) {
+	/**
+	 * Returns closest node group for given position.
+	 * @param  {string} zoneID
+	 * @param  {THREE.Vector3} position
+	 * @return {Path.Group}
+	 */
+	getGroup: function (zoneID, position) {
+		if (!zoneNodes[zoneID]) return null;
 
-		if (!zoneNodes[zone]) return null;
+		let closestNodeGroup = null;
+		let distance = Math.pow(50, 2);
 
-		var closestNodeGroup = null;
-
-		var distance = Math.pow(50, 2);
-
-		zoneNodes[zone].groups.forEach((group, index) => {
+		zoneNodes[zoneID].groups.forEach((group, index) => {
 			group.forEach((node) => {
-				var measuredDistance = utils.distanceToSquared(node.centroid, position);
+				const measuredDistance = utils.distanceToSquared(node.centroid, position);
 				if (measuredDistance < distance) {
@@ -234,6 +247,15 @@ closestNodeGroup = index;
 	},
-	getRandomNode: function (zone, group, nearPosition, nearRange) {
 
-		if (!zoneNodes[zone]) return new THREE.Vector3();
+	/**
+	 * Returns a random node within a given range of a given position.
+	 * @param  {string} zoneID
+	 * @param  {Path.Group} group
+	 * @param  {THREE.Vector3} nearPosition
+	 * @param  {number} nearRange
+	 * @return {Path.Node}
+	 */
+	getRandomNode: function (zoneID, group, nearPosition, nearRange) {
 
+		if (!zoneNodes[zoneID]) return new THREE.Vector3();
+
 		nearPosition = nearPosition || null;
@@ -244,3 +266,3 @@ nearRange = nearRange || 0;
 
-		var polygons = zoneNodes[zone].groups[group];
+		var polygons = zoneNodes[zoneID].groups[group];
 
@@ -259,5 +281,14 @@ polygons.forEach((p) => {
 	},
-	getClosestNode: function (position, zone, group, checkPolygon = false) {
-		const nodes = zoneNodes[zone].groups[group];
-		const vertices = zoneNodes[zone].vertices;
+
+	/**
+	 * Returns the closest node to the target position.
+	 * @param  {THREE.Vector3} position
+	 * @param  {string}  zoneID
+	 * @param  {Path.Group}  group
+	 * @param  {boolean} checkPolygon
+	 * @return {Path.Node}
+	 */
+	getClosestNode: function (position, zoneID, group, checkPolygon = false) {
+		const nodes = zoneNodes[zoneID].groups[group];
+		const vertices = zoneNodes[zoneID].vertices;
 		let closestNode = null;
@@ -278,74 +309,96 @@ let closestDistance = Infinity;
 	/**
-	 * Given start- and end-points for a path, and the current Node, returns
-	 * a new end-point along the path that does not leave the nav mesh.
+	 * Clamps a step along the navmesh, given start and desired endpoint. May be
+	 * used to constrain first-person / WASD controls.
+	 *
 	 * @param  {THREE.Vector3} start
-	 * @param  {THREE.Vector3} end
-	 * @param  {Node} node
-	 * @param  {string} zone
-	 * @param  {THREE.Vector3} endTarget
-	 * @return {THREE.Vector3}
+	 * @param  {THREE.Vector3} end Desired endpoint.
+	 * @param  {Path.Node} node
+	 * @param  {string} zoneID
+	 * @param  {Path.Group} group
+	 * @param  {THREE.Vector3} endTarget Updated endpoint.
+	 * @return {Path.Node} Updated node.
 	 */
-	projectPathOnNode: (function () {
+	clampStep: (function () {
+		const point = new THREE.Vector3();
 		const plane = new THREE.Plane();
-		const line = new THREE.Line3();
-		const point = new THREE.Vector3();
+		const triangle = new THREE.Triangle();
 
-		// Decay factor that slows the player down while traversing along an edge,
-		// and prevents precision errors from causing an overstep.
-		const decayFactor = 0.9;
+		let closestNode;
+		let closestPoint = new THREE.Vector3();
+		let closestDistance;
 
-		const projectedPath = new THREE.Vector3();
+		return function (start, end, node, zoneID, group, endTarget) {
+			const vertices = zoneNodes[zoneID].vertices;
+			const nodes = zoneNodes[zoneID].groups[group];
 
-		return function (start, end, node, zone, endTarget) {
-			endTarget = endTarget || new THREE.Vector3();
+			const nodeQueue = [node];
+			const nodeDepth = {};
+			nodeDepth[node.id] = 0;
 
-			const vertices = zoneNodes[zone].vertices;
+			closestNode = undefined;
+			closestPoint.set(0, 0, 0);
+			closestDistance = Infinity;
 
-			// Only handle paths starting within the node and
-			// ending outside it.
-			if (!utils.isVectorInPolygon(start, node, vertices)
-					|| utils.isVectorInPolygon(end, node, vertices)) {
-				return null;
-			}
+			// Project the step along the current node.
+			plane.setFromCoplanarPoints(
+				vertices[node.vertexIds[0]],
+				vertices[node.vertexIds[1]],
+				vertices[node.vertexIds[2]]
+			);
+			plane.projectPoint(end, point);
+			end.copy(point);
 
-			line.set(start, end);
-			projectedPath.copy(end).sub(start);
+			for (let currentNode = nodeQueue.pop(); currentNode; currentNode = nodeQueue.pop()) {
 
-			// For each edge in the node:
-			// (1) Create plane from co-planar points, assuming +Y up.
-			// (2) Intersect path against the plane.
-			// (3) If they intersect, project the path against the plane.
-			for (let i = 0; i < node.vertexIds.length; i++) {
-				point.copy(vertices[node.vertexIds[i]]);
-				point.y += 1;
-				plane.setFromCoplanarPoints(
-					vertices[node.vertexIds[i]],
-					vertices[node.vertexIds[(i + 1) % node.vertexIds.length]],
-					point
+				triangle.set(
+					vertices[currentNode.vertexIds[0]],
+					vertices[currentNode.vertexIds[1]],
+					vertices[currentNode.vertexIds[2]]
 				);
-				if (plane.intersectLine(line, point)) {
-					projectedPath.projectOnPlane(plane.normal);
+
+				if (triangle.containsPoint(end)) {
+					endTarget.copy(end);
+					return currentNode;
 				}
-			}
 
-			// Add re-projected path to starting point.
-			endTarget
-				.copy(start)
-				.add(projectedPath.multiplyScalar(decayFactor));
+				triangle.closestPointToPoint(end, point);
 
-			// TODO: Why does this happen?
-			if (!utils.isVectorInPolygon(endTarget, node, vertices)) {
-				return start;
+				if (point.distanceToSquared(end) < closestDistance) {
+					closestNode = currentNode;
+					closestPoint.copy(point);
+					closestDistance = point.distanceToSquared(end);
+				}
+
+				const depth = nodeDepth[currentNode];
+				if (depth > 2) continue;
+
+				for (let i = 0; i < currentNode.neighbours.length; i++) {
+					const neighbour = nodes[currentNode.neighbours[i]];
+					if (neighbour.id in nodeDepth) continue;
+
+					nodeQueue.push(neighbour);
+					nodeDepth[neighbour.id] = depth + 1;
+				}
 			}
 
-			return endTarget;
+			endTarget.copy(closestPoint);
+			return closestNode;
 		};
 	}()),
-	findPath: function (startPosition, targetPosition, zone, group) {
-		const nodes = zoneNodes[zone].groups[group];
-		const vertices = zoneNodes[zone].vertices;
 
-		const closestNode = this.getClosestNode(startPosition, zone, group);
-		const farthestNode = this.getClosestNode(targetPosition, zone, group, true);
+	/**
+	 * Returns a path between given start and end points.
+	 * @param  {THREE.Vector3} startPosition
+	 * @param  {THREE.Vector3} targetPosition
+	 * @param  {string} zoneID
+	 * @param  {Path.Group} group
+	 * @return {Array<THREE.Vector3>}
+	 */
+	findPath: function (startPosition, targetPosition, zoneID, group) {
+		const nodes = zoneNodes[zoneID].groups[group];
+		const vertices = zoneNodes[zoneID].vertices;
 
+		const closestNode = this.getClosestNode(startPosition, zoneID, group);
+		const farthestNode = this.getClosestNode(targetPosition, zoneID, group, true);
+
 		// If we can't find any node, just go straight to the target
@@ -352,0 +405,0 @@ if (!closestNode || !farthestNode) {

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Filesystem access

Supply chain risk

Accesses the file system, and could potentially read sensitive data.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

276131

increased by1.34%

Lines of code

1701

increased by1.73%

Number of lines in readme file

133

increased by850%

Number of low supply chain risk alerts

1

decreased by-50%

Worsened metrics

Dev dependency count

4

increased by100%

Number of package files

18

decreased by-5.26%

No dependency changes