Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

three-pathfinding

Package Overview
Dependencies
Maintainers
1
Versions
30
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

three-pathfinding - npm Package Compare versions

Comparing version 0.4.0 to 0.5.0

src/Builder.js

2

package.json
{
"name": "three-pathfinding",
"version": "0.4.0",
"version": "0.5.0",
"description": "Navigation mesh toolkit for three.js, based on PatrolJS",

@@ -5,0 +5,0 @@ "main": "src/index.js",

131

README.md

@@ -5,4 +5,6 @@ # three-pathfinding

## Installation
## Quickstart
### Installation
```

@@ -12,13 +14,14 @@ npm install --save three-pathfinding

## Example
### Example
```js
// Create level.
const ZONE = 'level1';
const zone = Path.buildNodes(this.navMesh.geometry);
Path.setZoneData(ZONE, zone);
// Create level.
const ZONE = 'level1';
// Find path from A to B.
const group = Path.getGroup(ZONE, a);
const path = Path.findPath(a, b, ZONE, group);
const pathfinder = new Path();
pathfinder.setZoneData(ZONE, Path.createZone(this.navMesh.geometry));
// Find path from A to B.
const groupID = pathfinder.getGroup(ZONE, a);
const path = pathfinder.findPath(a, b, ZONE, groupID);
```

@@ -34,22 +37,20 @@

- [buildNodes](#buildnodes)
- [setZoneData](#setzonedata)
- [getGroup](#getgroup)
- [getRandomNode](#getrandomnode)
- [getClosestNode](#getclosestnode)
- [clampStep](#clampstep)
- [findPath](#findpath)
- [Path](#path)
- [setZoneData](#setzonedata)
- [getGroup](#getgroup)
- [getRandomNode](#getrandomnode)
- [getClosestNode](#getclosestnode)
- [findPath](#findpath)
- [clampStep](#clampstep)
- [createZone](#createzone)
- [Zone](#zone)
- [Group](#group)
- [Node](#node)
## buildNodes
## Path
Builds a zone/node set from navigation mesh.
Defines an instance of the pathfinding module, with one or more zones.
**Parameters**
### setZoneData
- `geometry` **THREE.Geometry**
Returns **Path.Zone**
## setZoneData
Sets data for the given zone.

@@ -60,7 +61,7 @@

- `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)**
- `zone` **Path.Zone**
- `zone` **[Zone](#zone)**
## getGroup
### getGroup
Returns closest node group for given position.
Returns closest node group ID for given position.

@@ -72,5 +73,5 @@ **Parameters**

Returns **Path.Group**
Returns **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)**
## getRandomNode
### getRandomNode

@@ -82,9 +83,9 @@ Returns a random node within a given range of a given position.

- `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)**
- `group` **Path.Group**
- `groupID` **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)**
- `nearPosition` **THREE.Vector3**
- `nearRange` **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)**
Returns **Path.Node**
Returns **[Node](#node)**
## getClosestNode
### getClosestNode

@@ -97,9 +98,23 @@ Returns the closest node to the target position.

- `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)**
- `group` **Path.Group**
- `groupID` **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)**
- `checkPolygon` **[boolean](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Boolean)** (optional, default `false`)
Returns **Path.Node**
Returns **[Node](#node)**
## clampStep
### 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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)** ID of current zone.
- `groupID` **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)** Current group ID.
Returns **[Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)<THREE.Vector3>** Array of points defining the path.
### clampStep
Clamps a step along the navmesh, given start and desired endpoint. May be

@@ -112,21 +127,43 @@ used to constrain first-person / WASD controls.

- `end` **THREE.Vector3** Desired endpoint.
- `node` **Path.Node**
- `node` **[Node](#node)**
- `zoneID` **[string](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String)**
- `group` **Path.Group**
- `groupID` **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)**
- `endTarget` **THREE.Vector3** Updated endpoint.
Returns **Path.Node** Updated node.
Returns **[Node](#node)** Updated node.
## findPath
### createZone
Returns a path between given start and end points.
(Static) Builds a zone/node set from navigation mesh geometry.
**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**
- `geometry` **THREE.Geometry**
Returns **[Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)<THREE.Vector3>**
Returns **[Zone](#zone)**
## Zone
Defines a zone of interconnected groups on a navigation mesh.
**Properties**
- `groups` **[Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)<[Group](#group)>**
## Group
Defines a group within a navigation mesh.
## Node
Defines a node (or polygon) within a group.
**Properties**
- `id` **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)**
- `neighbours` **[Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)<[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)>** IDs of neighboring nodes.
- `centroid` **THREE.Vector3**
- `portals` **[Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)<[Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)<[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)>>** Array of portals, each defined by two vertex IDs.
- `closed` **[boolean](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Boolean)**
- `cost` **[number](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number)**
<!--- API END --->

@@ -140,2 +177,2 @@

* [Recastnavigation's level mesh](https://github.com/memononen/recastnavigation)
* [Constrained Movement Along Navmesh pt. 3](http://digestingduck.blogspot.com/2010/07/constrained-movement-along-navmesh-pt-3.html?m=1)

478

src/index.js

@@ -5,210 +5,21 @@ /* global THREE */

const AStar = require('./AStar');
const Builder = require('./Builder');
const Channel = require('./Channel');
var polygonId = 1;
var buildPolygonGroups = function (navigationMesh) {
var polygons = navigationMesh.polygons;
var polygonGroups = [];
var groupCount = 0;
var spreadGroupId = function (polygon) {
polygon.neighbours.forEach((neighbour) => {
if (neighbour.group === undefined) {
neighbour.group = polygon.group;
spreadGroupId(neighbour);
}
});
};
polygons.forEach((polygon) => {
if (polygon.group === undefined) {
polygon.group = groupCount++;
// Spread it
spreadGroupId(polygon);
}
if (!polygonGroups[polygon.group]) polygonGroups[polygon.group] = [];
polygonGroups[polygon.group].push(polygon);
});
console.log('Groups built: ', polygonGroups.length);
return polygonGroups;
};
var buildPolygonNeighbours = function (polygon, navigationMesh) {
polygon.neighbours = [];
// All other nodes that contain at least two of our vertices are our neighbours
for (var i = 0, len = navigationMesh.polygons.length; i < len; i++) {
if (polygon === navigationMesh.polygons[i]) continue;
// Don't check polygons that are too far, since the intersection tests take a long time
if (polygon.centroid.distanceToSquared(navigationMesh.polygons[i].centroid) > 100 * 100) continue;
var matches = utils.array_intersect(polygon.vertexIds, navigationMesh.polygons[i].vertexIds);
if (matches.length >= 2) {
polygon.neighbours.push(navigationMesh.polygons[i]);
}
/**
* Defines an instance of the pathfinding module, with one or more zones.
*/
class Path {
constructor () {
this.zones = {};
}
};
var buildPolygonsFromGeometry = function (geometry) {
console.log('Vertices:', geometry.vertices.length, 'polygons:', geometry.faces.length);
var polygons = [];
var vertices = geometry.vertices;
var faceVertexUvs = geometry.faceVertexUvs;
// Convert the faces into a custom format that supports more than 3 vertices
geometry.faces.forEach((face) => {
polygons.push({
id: polygonId++,
vertexIds: [face.a, face.b, face.c],
centroid: face.centroid,
normal: face.normal,
neighbours: []
});
});
var navigationMesh = {
polygons: polygons,
vertices: vertices,
faceVertexUvs: faceVertexUvs
};
// Build a list of adjacent polygons
polygons.forEach((polygon) => {
buildPolygonNeighbours(polygon, navigationMesh);
});
return navigationMesh;
};
var buildNavigationMesh = function (geometry) {
// Prepare geometry
utils.computeCentroids(geometry);
geometry.mergeVertices();
return buildPolygonsFromGeometry(geometry);
};
var getSharedVerticesInOrder = function (a, b) {
var aList = a.vertexIds;
var bList = b.vertexIds;
var sharedVertices = [];
aList.forEach((vId) => {
if (bList.includes(vId)) {
sharedVertices.push(vId);
}
});
if (sharedVertices.length < 2) return [];
// console.log("TRYING aList:", aList, ", bList:", bList, ", sharedVertices:", sharedVertices);
if (sharedVertices.includes(aList[0]) && sharedVertices.includes(aList[aList.length - 1])) {
// Vertices on both edges are bad, so shift them once to the left
aList.push(aList.shift());
}
if (sharedVertices.includes(bList[0]) && sharedVertices.includes(bList[bList.length - 1])) {
// Vertices on both edges are bad, so shift them once to the left
bList.push(bList.shift());
}
// Again!
sharedVertices = [];
aList.forEach((vId) => {
if (bList.includes(vId)) {
sharedVertices.push(vId);
}
});
return sharedVertices;
};
var groupNavMesh = function (navigationMesh) {
var saveObj = {};
navigationMesh.vertices.forEach((v) => {
v.x = utils.roundNumber(v.x, 2);
v.y = utils.roundNumber(v.y, 2);
v.z = utils.roundNumber(v.z, 2);
});
saveObj.vertices = navigationMesh.vertices;
var groups = buildPolygonGroups(navigationMesh);
saveObj.groups = [];
var findPolygonIndex = function (group, p) {
for (var i = 0; i < group.length; i++) {
if (p === group[i]) return i;
}
};
groups.forEach((group) => {
var newGroup = [];
group.forEach((p) => {
var neighbours = [];
p.neighbours.forEach((n) => {
neighbours.push(findPolygonIndex(group, n));
});
// Build a portal list to each neighbour
var portals = [];
p.neighbours.forEach((n) => {
portals.push(getSharedVerticesInOrder(p, n));
});
p.centroid.x = utils.roundNumber(p.centroid.x, 2);
p.centroid.y = utils.roundNumber(p.centroid.y, 2);
p.centroid.z = utils.roundNumber(p.centroid.z, 2);
newGroup.push({
id: findPolygonIndex(group, p),
neighbours: neighbours,
vertexIds: p.vertexIds,
centroid: p.centroid,
portals: portals
});
});
saveObj.groups.push(newGroup);
});
return saveObj;
};
var zoneNodes = {};
module.exports = {
/**
* Builds a zone/node set from navigation mesh.
* (Static) Builds a zone/node set from navigation mesh geometry.
* @param {THREE.Geometry} geometry
* @return {Path.Zone}
* @return {Zone}
*/
buildNodes: function (geometry) {
return groupNavMesh(buildNavigationMesh(geometry));
},
static createZone (geometry) {
return Builder.buildZone(geometry);
}

@@ -218,15 +29,16 @@ /**

* @param {string} zoneID
* @param {Path.Zone} zone
* @param {Zone} zone
*/
setZoneData: function (zoneID, zone) {
zoneNodes[zoneID] = zone;
},
setZoneData (zoneID, zone) {
this.zones[zoneID] = zone;
}
/**
* Returns closest node group for given position.
* Returns closest node group ID for given position.
* @param {string} zoneID
* @param {THREE.Vector3} position
* @return {Path.Group}
* @return {number}
*/
getGroup: function (zoneID, position) {
if (!zoneNodes[zoneID]) return null;
getGroup (zoneID, position) {
if (!this.zones[zoneID]) return null;

@@ -236,3 +48,3 @@ let closestNodeGroup = null;

zoneNodes[zoneID].groups.forEach((group, index) => {
this.zones[zoneID].groups.forEach((group, index) => {
group.forEach((node) => {

@@ -248,3 +60,3 @@ const measuredDistance = utils.distanceToSquared(node.centroid, position);

return closestNodeGroup;
},
}

@@ -254,10 +66,10 @@ /**

* @param {string} zoneID
* @param {Path.Group} group
* @param {number} groupID
* @param {THREE.Vector3} nearPosition
* @param {number} nearRange
* @return {Path.Node}
* @return {Node}
*/
getRandomNode: function (zoneID, group, nearPosition, nearRange) {
getRandomNode (zoneID, groupID, nearPosition, nearRange) {
if (!zoneNodes[zoneID]) return new THREE.Vector3();
if (!this.zones[zoneID]) return new THREE.Vector3();

@@ -267,6 +79,5 @@ nearPosition = nearPosition || null;

var candidates = [];
const candidates = [];
const polygons = this.zones[zoneID].groups[groupID];
var polygons = zoneNodes[zoneID].groups[group];
polygons.forEach((p) => {

@@ -283,3 +94,3 @@ if (nearPosition && nearRange) {

return utils.sample(candidates) || new THREE.Vector3();
},
}

@@ -290,9 +101,9 @@ /**

* @param {string} zoneID
* @param {Path.Group} group
* @param {number} groupID
* @param {boolean} checkPolygon
* @return {Path.Node}
* @return {Node}
*/
getClosestNode: function (position, zoneID, group, checkPolygon = false) {
const nodes = zoneNodes[zoneID].groups[group];
const vertices = zoneNodes[zoneID].vertices;
getClosestNode (position, zoneID, groupID, checkPolygon = false) {
const nodes = this.zones[zoneID].groups[groupID];
const vertices = this.zones[zoneID].vertices;
let closestNode = null;

@@ -311,98 +122,21 @@ let closestDistance = Infinity;

return closestNode;
},
}
/**
* Clamps a step along the navmesh, given start and desired endpoint. May be
* used to constrain first-person / WASD controls.
* Returns a path between given start and end points. If a complete path
* cannot be found, will return the nearest endpoint available.
*
* @param {THREE.Vector3} start
* @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.
* @param {THREE.Vector3} startPosition Start position.
* @param {THREE.Vector3} targetPosition Destination.
* @param {string} zoneID ID of current zone.
* @param {number} groupID Current group ID.
* @return {Array<THREE.Vector3>} Array of points defining the path.
*/
clampStep: (function () {
const point = new THREE.Vector3();
const plane = new THREE.Plane();
const triangle = new THREE.Triangle();
findPath (startPosition, targetPosition, zoneID, groupID) {
const nodes = this.zones[zoneID].groups[groupID];
const vertices = this.zones[zoneID].vertices;
let closestNode;
let closestPoint = new THREE.Vector3();
let closestDistance;
const closestNode = this.getClosestNode(startPosition, zoneID, groupID);
const farthestNode = this.getClosestNode(targetPosition, zoneID, groupID, true);
return function (start, end, node, zoneID, group, endTarget) {
const vertices = zoneNodes[zoneID].vertices;
const nodes = zoneNodes[zoneID].groups[group];
const nodeQueue = [node];
const nodeDepth = {};
nodeDepth[node.id] = 0;
closestNode = undefined;
closestPoint.set(0, 0, 0);
closestDistance = Infinity;
// 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);
for (let currentNode = nodeQueue.pop(); currentNode; currentNode = nodeQueue.pop()) {
triangle.set(
vertices[currentNode.vertexIds[0]],
vertices[currentNode.vertexIds[1]],
vertices[currentNode.vertexIds[2]]
);
if (triangle.containsPoint(end)) {
endTarget.copy(end);
return currentNode;
}
triangle.closestPointToPoint(end, point);
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;
}
}
endTarget.copy(closestPoint);
return closestNode;
};
}()),
/**
* 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

@@ -446,2 +180,114 @@ if (!closestNode || !farthestNode) {

}
};
}
/**
* 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 Desired endpoint.
* @param {Node} node
* @param {string} zoneID
* @param {number} groupID
* @param {THREE.Vector3} endTarget Updated endpoint.
* @return {Node} Updated node.
*/
Path.prototype.clampStep = (function () {
const point = new THREE.Vector3();
const plane = new THREE.Plane();
const triangle = new THREE.Triangle();
let closestNode;
let closestPoint = new THREE.Vector3();
let closestDistance;
return function (start, end, node, zoneID, groupID, endTarget) {
const vertices = this.zones[zoneID].vertices;
const nodes = this.zones[zoneID].groups[groupID];
const nodeQueue = [node];
const nodeDepth = {};
nodeDepth[node.id] = 0;
closestNode = undefined;
closestPoint.set(0, 0, 0);
closestDistance = Infinity;
// 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);
for (let currentNode = nodeQueue.pop(); currentNode; currentNode = nodeQueue.pop()) {
triangle.set(
vertices[currentNode.vertexIds[0]],
vertices[currentNode.vertexIds[1]],
vertices[currentNode.vertexIds[2]]
);
if (triangle.containsPoint(end)) {
endTarget.copy(end);
return currentNode;
}
triangle.closestPointToPoint(end, point);
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;
}
}
endTarget.copy(closestPoint);
return closestNode;
};
}());
/**
* Defines a zone of interconnected groups on a navigation mesh.
*
* @type {Object}
* @property {Array<Group>} groups
* @property {Array<THREE.Vector3} vertices
*/
const Zone = {}; // jshint ignore:line
/**
* Defines a group within a navigation mesh.
*
* @type {Object}
*/
const Group = {}; // jshint ignore:line
/**
* Defines a node (or polygon) within a group.
*
* @type {Object}
* @property {number} id
* @property {Array<number>} neighbours IDs of neighboring nodes.
* @property {Array<number} vertexIds
* @property {THREE.Vector3} centroid
* @property {Array<Array<number>>} portals Array of portals, each defined by two vertex IDs.
* @property {boolean} closed
* @property {number} cost
*/
const Node = {}; // jshint ignore:line
module.exports = Path;

10

src/utils.js

@@ -113,4 +113,2 @@ class Utils {

// console.log("nextVertex: ", nextVertex);
if (i === 0) {

@@ -135,10 +133,4 @@ nextVertexId = polygon.vertexIds[1];

// console.log(angle);
if (angle > Math.PI - 0.01 && angle < Math.PI + 0.01) {
// Unneccesary vertex
// console.log("Unneccesary vertex: ", polygon.vertexIds[i]);
// console.log("Angle between "+previousVertexId+", "+polygon.vertexIds[i]+" "+nextVertexId+" was: ", angle);
// Remove the neighbours who had this vertex

@@ -161,4 +153,2 @@ var goodNeighbours = [];

// console.log("New vertexIds: ", newVertexIds);
polygon.vertexIds = newVertexIds;

@@ -165,0 +155,0 @@ 

demo/demo.html

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc