Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
three-pathfinding
Advanced tools
three-pathfinding - npm Package Compare versions
Comparing version 0.5.5 to 0.6.0
@@ -1,1281 +0,2 @@ | ||
| (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){ | ||
| 'use strict'; | ||
| THREE.Pathfinding = require('./src'); | ||
| },{"./src":6}],2:[function(require,module,exports){ | ||
| 'use strict'; | ||
| var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }(); | ||
| function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } } | ||
| var BinaryHeap = require('./BinaryHeap'); | ||
| var utils = require('./utils.js'); | ||
| var AStar = function () { | ||
| function AStar() { | ||
| _classCallCheck(this, AStar); | ||
| } | ||
| _createClass(AStar, null, [{ | ||
| key: 'init', | ||
| value: function init(graph) { | ||
| for (var x = 0; x < graph.length; x++) { | ||
| //for(var x in graph) { | ||
| var node = graph[x]; | ||
| node.f = 0; | ||
| node.g = 0; | ||
| node.h = 0; | ||
| node.cost = 1.0; | ||
| node.visited = false; | ||
| node.closed = false; | ||
| node.parent = null; | ||
| } | ||
| } | ||
| }, { | ||
| key: 'cleanUp', | ||
| value: function cleanUp(graph) { | ||
| for (var x = 0; x < graph.length; x++) { | ||
| var node = graph[x]; | ||
| delete node.f; | ||
| delete node.g; | ||
| delete node.h; | ||
| delete node.cost; | ||
| delete node.visited; | ||
| delete node.closed; | ||
| delete node.parent; | ||
| } | ||
| } | ||
| }, { | ||
| key: 'heap', | ||
| value: function heap() { | ||
| return new BinaryHeap(function (node) { | ||
| return node.f; | ||
| }); | ||
| } | ||
| }, { | ||
| key: 'search', | ||
| value: function search(graph, start, end) { | ||
| this.init(graph); | ||
| //heuristic = heuristic || astar.manhattan; | ||
| var openHeap = this.heap(); | ||
| openHeap.push(start); | ||
| while (openHeap.size() > 0) { | ||
| // Grab the lowest f(x) to process next. Heap keeps this sorted for us. | ||
| var currentNode = openHeap.pop(); | ||
| // End case -- result has been found, return the traced path. | ||
| if (currentNode === end) { | ||
| var curr = currentNode; | ||
| var ret = []; | ||
| while (curr.parent) { | ||
| ret.push(curr); | ||
| curr = curr.parent; | ||
| } | ||
| this.cleanUp(ret); | ||
| return ret.reverse(); | ||
| } | ||
| // Normal case -- move currentNode from open to closed, process each of its neighbours. | ||
| currentNode.closed = true; | ||
| // Find all neighbours for the current node. Optionally find diagonal neighbours as well (false by default). | ||
| var neighbours = this.neighbours(graph, currentNode); | ||
| for (var i = 0, il = neighbours.length; i < il; i++) { | ||
| var neighbour = neighbours[i]; | ||
| if (neighbour.closed) { | ||
| // Not a valid node to process, skip to next neighbour. | ||
| continue; | ||
| } | ||
| // The g score is the shortest distance from start to current node. | ||
| // We need to check if the path we have arrived at this neighbour is the shortest one we have seen yet. | ||
| var gScore = currentNode.g + neighbour.cost; | ||
| var beenVisited = neighbour.visited; | ||
| if (!beenVisited || gScore < neighbour.g) { | ||
| // Found an optimal (so far) path to this node. Take score for node to see how good it is. | ||
| neighbour.visited = true; | ||
| neighbour.parent = currentNode; | ||
| if (!neighbour.centroid || !end.centroid) throw new Error('Unexpected state'); | ||
| neighbour.h = neighbour.h || this.heuristic(neighbour.centroid, end.centroid); | ||
| neighbour.g = gScore; | ||
| neighbour.f = neighbour.g + neighbour.h; | ||
| if (!beenVisited) { | ||
| // Pushing to heap will put it in proper place based on the 'f' value. | ||
| openHeap.push(neighbour); | ||
| } else { | ||
| // Already seen the node, but since it has been rescored we need to reorder it in the heap | ||
| openHeap.rescoreElement(neighbour); | ||
| } | ||
| } | ||
| } | ||
| } | ||
| // No result was found - empty array signifies failure to find path. | ||
| return []; | ||
| } | ||
| }, { | ||
| key: 'heuristic', | ||
| value: function heuristic(pos1, pos2) { | ||
| return utils.distanceToSquared(pos1, pos2); | ||
| } | ||
| }, { | ||
| key: 'neighbours', | ||
| value: function neighbours(graph, node) { | ||
| var ret = []; | ||
| for (var e = 0; e < node.neighbours.length; e++) { | ||
| ret.push(graph[node.neighbours[e]]); | ||
| } | ||
| return ret; | ||
| } | ||
| }]); | ||
| return AStar; | ||
| }(); | ||
| module.exports = AStar; | ||
| },{"./BinaryHeap":3,"./utils.js":7}],3:[function(require,module,exports){ | ||
| "use strict"; | ||
| var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }(); | ||
| function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } } | ||
| // javascript-astar | ||
| // http://github.com/bgrins/javascript-astar | ||
| // Freely distributable under the MIT License. | ||
| // Implements the astar search algorithm in javascript using a binary heap. | ||
| var BinaryHeap = function () { | ||
| function BinaryHeap(scoreFunction) { | ||
| _classCallCheck(this, BinaryHeap); | ||
| this.content = []; | ||
| this.scoreFunction = scoreFunction; | ||
| } | ||
| _createClass(BinaryHeap, [{ | ||
| key: "push", | ||
| value: function push(element) { | ||
| // Add the new element to the end of the array. | ||
| this.content.push(element); | ||
| // Allow it to sink down. | ||
| this.sinkDown(this.content.length - 1); | ||
| } | ||
| }, { | ||
| key: "pop", | ||
| value: function pop() { | ||
| // Store the first element so we can return it later. | ||
| var result = this.content[0]; | ||
| // Get the element at the end of the array. | ||
| var end = this.content.pop(); | ||
| // If there are any elements left, put the end element at the | ||
| // start, and let it bubble up. | ||
| if (this.content.length > 0) { | ||
| this.content[0] = end; | ||
| this.bubbleUp(0); | ||
| } | ||
| return result; | ||
| } | ||
| }, { | ||
| key: "remove", | ||
| value: function remove(node) { | ||
| var i = this.content.indexOf(node); | ||
| // When it is found, the process seen in 'pop' is repeated | ||
| // to fill up the hole. | ||
| var end = this.content.pop(); | ||
| if (i !== this.content.length - 1) { | ||
| this.content[i] = end; | ||
| if (this.scoreFunction(end) < this.scoreFunction(node)) { | ||
| this.sinkDown(i); | ||
| } else { | ||
| this.bubbleUp(i); | ||
| } | ||
| } | ||
| } | ||
| }, { | ||
| key: "size", | ||
| value: function size() { | ||
| return this.content.length; | ||
| } | ||
| }, { | ||
| key: "rescoreElement", | ||
| value: function rescoreElement(node) { | ||
| this.sinkDown(this.content.indexOf(node)); | ||
| } | ||
| }, { | ||
| key: "sinkDown", | ||
| value: function sinkDown(n) { | ||
| // Fetch the element that has to be sunk. | ||
| var element = this.content[n]; | ||
| // When at 0, an element can not sink any further. | ||
| while (n > 0) { | ||
| // Compute the parent element's index, and fetch it. | ||
| var parentN = (n + 1 >> 1) - 1; | ||
| var parent = this.content[parentN]; | ||
| if (this.scoreFunction(element) < this.scoreFunction(parent)) { | ||
| // Swap the elements if the parent is greater. | ||
| this.content[parentN] = element; | ||
| this.content[n] = parent; | ||
| // Update 'n' to continue at the new position. | ||
| n = parentN; | ||
| } else { | ||
| // Found a parent that is less, no need to sink any further. | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| }, { | ||
| key: "bubbleUp", | ||
| value: function bubbleUp(n) { | ||
| // Look up the target element and its score. | ||
| var length = this.content.length, | ||
| element = this.content[n], | ||
| elemScore = this.scoreFunction(element); | ||
| while (true) { | ||
| // Compute the indices of the child elements. | ||
| var child2N = n + 1 << 1, | ||
| child1N = child2N - 1; | ||
| // This is used to store the new position of the element, | ||
| // if any. | ||
| var swap = null; | ||
| var child1Score = void 0; | ||
| // If the first child exists (is inside the array)... | ||
| if (child1N < length) { | ||
| // Look it up and compute its score. | ||
| var child1 = this.content[child1N]; | ||
| child1Score = this.scoreFunction(child1); | ||
| // If the score is less than our element's, we need to swap. | ||
| if (child1Score < elemScore) { | ||
| swap = child1N; | ||
| } | ||
| } | ||
| // Do the same checks for the other child. | ||
| if (child2N < length) { | ||
| var child2 = this.content[child2N], | ||
| child2Score = this.scoreFunction(child2); | ||
| if (child2Score < (swap === null ? elemScore : child1Score)) { | ||
| swap = child2N; | ||
| } | ||
| } | ||
| // If the element needs to be moved, swap it, and continue. | ||
| if (swap !== null) { | ||
| this.content[n] = this.content[swap]; | ||
| this.content[swap] = element; | ||
| n = swap; | ||
| } | ||
| // Otherwise, we are done. | ||
| else { | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| }]); | ||
| return BinaryHeap; | ||
| }(); | ||
| module.exports = BinaryHeap; | ||
| },{}],4:[function(require,module,exports){ | ||
| 'use strict'; | ||
| var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }(); | ||
| function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } } | ||
| var utils = require('./utils'); | ||
| var polygonId = 1; | ||
| var Builder = function () { | ||
| function Builder() { | ||
| _classCallCheck(this, Builder); | ||
| } | ||
| _createClass(Builder, null, [{ | ||
| key: 'buildZone', | ||
| /** | ||
| * Constructs groups from the given navigation mesh. | ||
| * @param {THREE.Geometry} geometry | ||
| * @return {Zone} | ||
| */ | ||
| value: function buildZone(geometry) { | ||
| var _this = this; | ||
| var navMesh = this._buildNavigationMesh(geometry); | ||
| var zone = {}; | ||
| navMesh.vertices.forEach(function (v) { | ||
| v.x = utils.roundNumber(v.x, 2); | ||
| v.y = utils.roundNumber(v.y, 2); | ||
| v.z = utils.roundNumber(v.z, 2); | ||
| }); | ||
| zone.vertices = navMesh.vertices; | ||
| var groups = this._buildPolygonGroups(navMesh); | ||
| zone.groups = []; | ||
| var findPolygonIndex = function findPolygonIndex(group, p) { | ||
| for (var i = 0; i < group.length; i++) { | ||
| if (p === group[i]) return i; | ||
| } | ||
| }; | ||
| groups.forEach(function (group) { | ||
| var newGroup = []; | ||
| group.forEach(function (p) { | ||
| var neighbours = p.neighbours.map(function (n) { | ||
| return findPolygonIndex(group, n); | ||
| }); | ||
| // Build a portal list to each neighbour | ||
| var portals = p.neighbours.map(function (n) { | ||
| return _this._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 | ||
| }); | ||
| }); | ||
| zone.groups.push(newGroup); | ||
| }); | ||
| return zone; | ||
| } | ||
| /** | ||
| * Constructs a navigation mesh from the given geometry. | ||
| * @param {THREE.Geometry} geometry | ||
| * @return {Object} | ||
| */ | ||
| }, { | ||
| key: '_buildNavigationMesh', | ||
| value: function _buildNavigationMesh(geometry) { | ||
| utils.computeCentroids(geometry); | ||
| geometry.mergeVertices(); | ||
| return this._buildPolygonsFromGeometry(geometry); | ||
| } | ||
| }, { | ||
| key: '_buildPolygonGroups', | ||
| value: function _buildPolygonGroups(navigationMesh) { | ||
| var polygons = navigationMesh.polygons; | ||
| var polygonGroups = []; | ||
| var groupCount = 0; | ||
| var spreadGroupId = function spreadGroupId(polygon) { | ||
| polygon.neighbours.forEach(function (neighbour) { | ||
| if (neighbour.group === undefined) { | ||
| neighbour.group = polygon.group; | ||
| spreadGroupId(neighbour); | ||
| } | ||
| }); | ||
| }; | ||
| polygons.forEach(function (polygon) { | ||
| if (polygon.group === undefined) { | ||
| polygon.group = groupCount++; | ||
| // Spread it | ||
| spreadGroupId(polygon); | ||
| } | ||
| if (!polygonGroups[polygon.group]) polygonGroups[polygon.group] = []; | ||
| polygonGroups[polygon.group].push(polygon); | ||
| }); | ||
| return polygonGroups; | ||
| } | ||
| }, { | ||
| key: '_buildPolygonNeighbours', | ||
| value: function _buildPolygonNeighbours(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]); | ||
| } | ||
| } | ||
| } | ||
| }, { | ||
| key: '_buildPolygonsFromGeometry', | ||
| value: function _buildPolygonsFromGeometry(geometry) { | ||
| var _this2 = this; | ||
| 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(function (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(function (polygon) { | ||
| _this2._buildPolygonNeighbours(polygon, navigationMesh); | ||
| }); | ||
| return navigationMesh; | ||
| } | ||
| }, { | ||
| key: '_getSharedVerticesInOrder', | ||
| value: function _getSharedVerticesInOrder(a, b) { | ||
| var aList = a.vertexIds; | ||
| var bList = b.vertexIds; | ||
| var sharedVertices = []; | ||
| aList.forEach(function (vId) { | ||
| if (bList.includes(vId)) { | ||
| sharedVertices.push(vId); | ||
| } | ||
| }); | ||
| if (sharedVertices.length < 2) return []; | ||
| 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.length = 0; | ||
| aList.forEach(function (vId) { | ||
| if (bList.includes(vId)) { | ||
| sharedVertices.push(vId); | ||
| } | ||
| }); | ||
| return sharedVertices; | ||
| } | ||
| }]); | ||
| return Builder; | ||
| }(); | ||
| module.exports = Builder; | ||
| },{"./utils":7}],5:[function(require,module,exports){ | ||
| 'use strict'; | ||
| var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }(); | ||
| function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } } | ||
| var utils = require('./utils'); | ||
| var Channel = function () { | ||
| function Channel() { | ||
| _classCallCheck(this, Channel); | ||
| this.portals = []; | ||
| } | ||
| _createClass(Channel, [{ | ||
| key: 'push', | ||
| value: function push(p1, p2) { | ||
| if (p2 === undefined) p2 = p1; | ||
| this.portals.push({ | ||
| left: p1, | ||
| right: p2 | ||
| }); | ||
| } | ||
| }, { | ||
| key: 'stringPull', | ||
| value: function stringPull() { | ||
| var portals = this.portals; | ||
| var pts = []; | ||
| // Init scan state | ||
| var portalApex = void 0, | ||
| portalLeft = void 0, | ||
| portalRight = void 0; | ||
| var apexIndex = 0, | ||
| leftIndex = 0, | ||
| rightIndex = 0; | ||
| portalApex = portals[0].left; | ||
| portalLeft = portals[0].left; | ||
| portalRight = portals[0].right; | ||
| // Add start point. | ||
| pts.push(portalApex); | ||
| for (var i = 1; i < portals.length; i++) { | ||
| var left = portals[i].left; | ||
| var right = portals[i].right; | ||
| // Update right vertex. | ||
| if (utils.triarea2(portalApex, portalRight, right) <= 0.0) { | ||
| if (utils.vequal(portalApex, portalRight) || utils.triarea2(portalApex, portalLeft, right) > 0.0) { | ||
| // Tighten the funnel. | ||
| portalRight = right; | ||
| rightIndex = i; | ||
| } else { | ||
| // Right over left, insert left to path and restart scan from portal left point. | ||
| pts.push(portalLeft); | ||
| // Make current left the new apex. | ||
| portalApex = portalLeft; | ||
| apexIndex = leftIndex; | ||
| // Reset portal | ||
| portalLeft = portalApex; | ||
| portalRight = portalApex; | ||
| leftIndex = apexIndex; | ||
| rightIndex = apexIndex; | ||
| // Restart scan | ||
| i = apexIndex; | ||
| continue; | ||
| } | ||
| } | ||
| // Update left vertex. | ||
| if (utils.triarea2(portalApex, portalLeft, left) >= 0.0) { | ||
| if (utils.vequal(portalApex, portalLeft) || utils.triarea2(portalApex, portalRight, left) < 0.0) { | ||
| // Tighten the funnel. | ||
| portalLeft = left; | ||
| leftIndex = i; | ||
| } else { | ||
| // Left over right, insert right to path and restart scan from portal right point. | ||
| pts.push(portalRight); | ||
| // Make current right the new apex. | ||
| portalApex = portalRight; | ||
| apexIndex = rightIndex; | ||
| // Reset portal | ||
| portalLeft = portalApex; | ||
| portalRight = portalApex; | ||
| leftIndex = apexIndex; | ||
| rightIndex = apexIndex; | ||
| // Restart scan | ||
| i = apexIndex; | ||
| continue; | ||
| } | ||
| } | ||
| } | ||
| if (pts.length === 0 || !utils.vequal(pts[pts.length - 1], portals[portals.length - 1].left)) { | ||
| // Append last point to path. | ||
| pts.push(portals[portals.length - 1].left); | ||
| } | ||
| this.path = pts; | ||
| return pts; | ||
| } | ||
| }]); | ||
| return Channel; | ||
| }(); | ||
| module.exports = Channel; | ||
| },{"./utils":7}],6:[function(require,module,exports){ | ||
| 'use strict'; | ||
| var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }(); | ||
| function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } } | ||
| /* global THREE */ | ||
| var utils = require('./utils'); | ||
| var AStar = require('./AStar'); | ||
| var Builder = require('./Builder'); | ||
| var Channel = require('./Channel'); | ||
| /** | ||
| * Defines an instance of the pathfinding module, with one or more zones. | ||
| */ | ||
| var Path = function () { | ||
| function Path() { | ||
| _classCallCheck(this, Path); | ||
| this.zones = {}; | ||
| } | ||
| /** | ||
| * (Static) Builds a zone/node set from navigation mesh geometry. | ||
| * @param {THREE.Geometry} geometry | ||
| * @return {Zone} | ||
| */ | ||
| _createClass(Path, [{ | ||
| key: 'setZoneData', | ||
| /** | ||
| * Sets data for the given zone. | ||
| * @param {string} zoneID | ||
| * @param {Zone} zone | ||
| */ | ||
| value: function setZoneData(zoneID, zone) { | ||
| this.zones[zoneID] = zone; | ||
| } | ||
| /** | ||
| * Returns closest node group ID for given position. | ||
| * @param {string} zoneID | ||
| * @param {THREE.Vector3} position | ||
| * @return {number} | ||
| */ | ||
| }, { | ||
| key: 'getGroup', | ||
| value: function getGroup(zoneID, position) { | ||
| if (!this.zones[zoneID]) return null; | ||
| var closestNodeGroup = null; | ||
| var distance = Math.pow(50, 2); | ||
| this.zones[zoneID].groups.forEach(function (group, index) { | ||
| group.forEach(function (node) { | ||
| var measuredDistance = utils.distanceToSquared(node.centroid, position); | ||
| if (measuredDistance < distance) { | ||
| closestNodeGroup = index; | ||
| distance = measuredDistance; | ||
| } | ||
| }); | ||
| }); | ||
| return closestNodeGroup; | ||
| } | ||
| /** | ||
| * Returns a random node within a given range of a given position. | ||
| * @param {string} zoneID | ||
| * @param {number} groupID | ||
| * @param {THREE.Vector3} nearPosition | ||
| * @param {number} nearRange | ||
| * @return {Node} | ||
| */ | ||
| }, { | ||
| key: 'getRandomNode', | ||
| value: function getRandomNode(zoneID, groupID, nearPosition, nearRange) { | ||
| if (!this.zones[zoneID]) return new THREE.Vector3(); | ||
| nearPosition = nearPosition || null; | ||
| nearRange = nearRange || 0; | ||
| var candidates = []; | ||
| var polygons = this.zones[zoneID].groups[groupID]; | ||
| polygons.forEach(function (p) { | ||
| if (nearPosition && nearRange) { | ||
| if (utils.distanceToSquared(nearPosition, p.centroid) < nearRange * nearRange) { | ||
| candidates.push(p.centroid); | ||
| } | ||
| } else { | ||
| candidates.push(p.centroid); | ||
| } | ||
| }); | ||
| return utils.sample(candidates) || new THREE.Vector3(); | ||
| } | ||
| /** | ||
| * Returns the closest node to the target position. | ||
| * @param {THREE.Vector3} position | ||
| * @param {string} zoneID | ||
| * @param {number} groupID | ||
| * @param {boolean} checkPolygon | ||
| * @return {Node} | ||
| */ | ||
| }, { | ||
| key: 'getClosestNode', | ||
| value: function getClosestNode(position, zoneID, groupID) { | ||
| var checkPolygon = arguments.length > 3 && arguments[3] !== undefined ? arguments[3] : false; | ||
| var nodes = this.zones[zoneID].groups[groupID]; | ||
| var vertices = this.zones[zoneID].vertices; | ||
| var closestNode = null; | ||
| var closestDistance = Infinity; | ||
| nodes.forEach(function (node) { | ||
| var distance = utils.distanceToSquared(node.centroid, position); | ||
| if (distance < closestDistance && (!checkPolygon || utils.isVectorInPolygon(position, node, vertices))) { | ||
| closestNode = node; | ||
| closestDistance = distance; | ||
| } | ||
| }); | ||
| return closestNode; | ||
| } | ||
| /** | ||
| * 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} 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. | ||
| */ | ||
| }, { | ||
| key: 'findPath', | ||
| value: function findPath(startPosition, targetPosition, zoneID, groupID) { | ||
| var nodes = this.zones[zoneID].groups[groupID]; | ||
| var vertices = this.zones[zoneID].vertices; | ||
| var closestNode = this.getClosestNode(startPosition, zoneID, groupID); | ||
| var farthestNode = this.getClosestNode(targetPosition, zoneID, groupID, true); | ||
| // If we can't find any node, just go straight to the target | ||
| if (!closestNode || !farthestNode) { | ||
| return null; | ||
| } | ||
| var paths = AStar.search(nodes, closestNode, farthestNode); | ||
| var getPortalFromTo = function getPortalFromTo(a, b) { | ||
| for (var i = 0; i < a.neighbours.length; i++) { | ||
| if (a.neighbours[i] === b.id) { | ||
| return a.portals[i]; | ||
| } | ||
| } | ||
| }; | ||
| // We have the corridor, now pull the rope. | ||
| var channel = new Channel(); | ||
| channel.push(startPosition); | ||
| for (var i = 0; i < paths.length; i++) { | ||
| var polygon = paths[i]; | ||
| var nextPolygon = paths[i + 1]; | ||
| if (nextPolygon) { | ||
| var portals = getPortalFromTo(polygon, nextPolygon); | ||
| channel.push(vertices[portals[0]], vertices[portals[1]]); | ||
| } | ||
| } | ||
| channel.push(targetPosition); | ||
| channel.stringPull(); | ||
| // Return the path, omitting first position (which is already known). | ||
| var path = channel.path.map(function (c) { | ||
| return new THREE.Vector3(c.x, c.y, c.z); | ||
| }); | ||
| path.shift(); | ||
| return path; | ||
| } | ||
| }], [{ | ||
| key: 'createZone', | ||
| value: function createZone(geometry) { | ||
| return Builder.buildZone(geometry); | ||
| } | ||
| }]); | ||
| return Path; | ||
| }(); | ||
| /** | ||
| * 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 () { | ||
| var point = new THREE.Vector3(); | ||
| var plane = new THREE.Plane(); | ||
| var triangle = new THREE.Triangle(); | ||
| var closestNode = void 0; | ||
| var closestPoint = new THREE.Vector3(); | ||
| var closestDistance = void 0; | ||
| return function (start, end, node, zoneID, groupID, endTarget) { | ||
| var vertices = this.zones[zoneID].vertices; | ||
| var nodes = this.zones[zoneID].groups[groupID]; | ||
| var nodeQueue = [node]; | ||
| var 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 (var currentNode = nodeQueue.pop(); currentNode; currentNode = nodeQueue.pop()) { | ||
| triangle.set(vertices[currentNode.vertexIds[0]], vertices[currentNode.vertexIds[1]], vertices[currentNode.vertexIds[2]]); | ||
| triangle.closestPointToPoint(end, point); | ||
| if (point.distanceToSquared(end) < closestDistance) { | ||
| closestNode = currentNode; | ||
| closestPoint.copy(point); | ||
| closestDistance = point.distanceToSquared(end); | ||
| } | ||
| var depth = nodeDepth[currentNode]; | ||
| if (depth > 2) continue; | ||
| for (var i = 0; i < currentNode.neighbours.length; i++) { | ||
| var 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 | ||
| */ | ||
| var Zone = {}; // jshint ignore:line | ||
| /** | ||
| * Defines a group within a navigation mesh. | ||
| * | ||
| * @type {Object} | ||
| */ | ||
| var 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 | ||
| */ | ||
| var Node = {}; // jshint ignore:line | ||
| module.exports = Path; | ||
| },{"./AStar":2,"./Builder":4,"./Channel":5,"./utils":7}],7:[function(require,module,exports){ | ||
| 'use strict'; | ||
| var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }(); | ||
| function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } } | ||
| var Utils = function () { | ||
| function Utils() { | ||
| _classCallCheck(this, Utils); | ||
| } | ||
| _createClass(Utils, null, [{ | ||
| key: 'computeCentroids', | ||
| value: function computeCentroids(geometry) { | ||
| var f, fl, face; | ||
| for (f = 0, fl = geometry.faces.length; f < fl; f++) { | ||
| face = geometry.faces[f]; | ||
| face.centroid = new THREE.Vector3(0, 0, 0); | ||
| face.centroid.add(geometry.vertices[face.a]); | ||
| face.centroid.add(geometry.vertices[face.b]); | ||
| face.centroid.add(geometry.vertices[face.c]); | ||
| face.centroid.divideScalar(3); | ||
| } | ||
| } | ||
| }, { | ||
| key: 'roundNumber', | ||
| value: function roundNumber(number, decimals) { | ||
| var newnumber = Number(number + '').toFixed(parseInt(decimals)); | ||
| return parseFloat(newnumber); | ||
| } | ||
| }, { | ||
| key: 'sample', | ||
| value: function sample(list) { | ||
| return list[Math.floor(Math.random() * list.length)]; | ||
| } | ||
| }, { | ||
| key: 'mergeVertexIds', | ||
| value: function mergeVertexIds(aList, bList) { | ||
| var sharedVertices = []; | ||
| aList.forEach(function (vID) { | ||
| if (bList.indexOf(vID) >= 0) { | ||
| sharedVertices.push(vID); | ||
| } | ||
| }); | ||
| if (sharedVertices.length < 2) return []; | ||
| 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(function (vId) { | ||
| if (bList.includes(vId)) { | ||
| sharedVertices.push(vId); | ||
| } | ||
| }); | ||
| var clockwiseMostSharedVertex = sharedVertices[1]; | ||
| var counterClockwiseMostSharedVertex = sharedVertices[0]; | ||
| var cList = aList.slice(); | ||
| while (cList[0] !== clockwiseMostSharedVertex) { | ||
| cList.push(cList.shift()); | ||
| } | ||
| var c = 0; | ||
| var temp = bList.slice(); | ||
| while (temp[0] !== counterClockwiseMostSharedVertex) { | ||
| temp.push(temp.shift()); | ||
| if (c++ > 10) throw new Error('Unexpected state'); | ||
| } | ||
| // Shave | ||
| temp.shift(); | ||
| temp.pop(); | ||
| cList = cList.concat(temp); | ||
| return cList; | ||
| } | ||
| }, { | ||
| key: 'setPolygonCentroid', | ||
| value: function setPolygonCentroid(polygon, navigationMesh) { | ||
| var sum = new THREE.Vector3(); | ||
| var vertices = navigationMesh.vertices; | ||
| polygon.vertexIds.forEach(function (vId) { | ||
| sum.add(vertices[vId]); | ||
| }); | ||
| sum.divideScalar(polygon.vertexIds.length); | ||
| polygon.centroid.copy(sum); | ||
| } | ||
| }, { | ||
| key: 'cleanPolygon', | ||
| value: function cleanPolygon(polygon, navigationMesh) { | ||
| var newVertexIds = []; | ||
| var vertices = navigationMesh.vertices; | ||
| for (var i = 0; i < polygon.vertexIds.length; i++) { | ||
| var vertex = vertices[polygon.vertexIds[i]]; | ||
| var nextVertexId, previousVertexId; | ||
| var nextVertex, previousVertex; | ||
| if (i === 0) { | ||
| nextVertexId = polygon.vertexIds[1]; | ||
| previousVertexId = polygon.vertexIds[polygon.vertexIds.length - 1]; | ||
| } else if (i === polygon.vertexIds.length - 1) { | ||
| nextVertexId = polygon.vertexIds[0]; | ||
| previousVertexId = polygon.vertexIds[polygon.vertexIds.length - 2]; | ||
| } else { | ||
| nextVertexId = polygon.vertexIds[i + 1]; | ||
| previousVertexId = polygon.vertexIds[i - 1]; | ||
| } | ||
| nextVertex = vertices[nextVertexId]; | ||
| previousVertex = vertices[previousVertexId]; | ||
| var a = nextVertex.clone().sub(vertex); | ||
| var b = previousVertex.clone().sub(vertex); | ||
| var angle = a.angleTo(b); | ||
| if (angle > Math.PI - 0.01 && angle < Math.PI + 0.01) { | ||
| // Remove the neighbours who had this vertex | ||
| var goodNeighbours = []; | ||
| polygon.neighbours.forEach(function (neighbour) { | ||
| if (!neighbour.vertexIds.includes(polygon.vertexIds[i])) { | ||
| goodNeighbours.push(neighbour); | ||
| } | ||
| }); | ||
| polygon.neighbours = goodNeighbours; | ||
| // TODO cleanup the list of vertices and rebuild vertexIds for all polygons | ||
| } else { | ||
| newVertexIds.push(polygon.vertexIds[i]); | ||
| } | ||
| } | ||
| polygon.vertexIds = newVertexIds; | ||
| this.setPolygonCentroid(polygon, navigationMesh); | ||
| } | ||
| }, { | ||
| key: 'isConvex', | ||
| value: function isConvex(polygon, navigationMesh) { | ||
| var vertices = navigationMesh.vertices; | ||
| if (polygon.vertexIds.length < 3) return false; | ||
| var convex = true; | ||
| var total = 0; | ||
| var results = []; | ||
| for (var i = 0; i < polygon.vertexIds.length; i++) { | ||
| var vertex = vertices[polygon.vertexIds[i]]; | ||
| var nextVertex, previousVertex; | ||
| if (i === 0) { | ||
| nextVertex = vertices[polygon.vertexIds[1]]; | ||
| previousVertex = vertices[polygon.vertexIds[polygon.vertexIds.length - 1]]; | ||
| } else if (i === polygon.vertexIds.length - 1) { | ||
| nextVertex = vertices[polygon.vertexIds[0]]; | ||
| previousVertex = vertices[polygon.vertexIds[polygon.vertexIds.length - 2]]; | ||
| } else { | ||
| nextVertex = vertices[polygon.vertexIds[i + 1]]; | ||
| previousVertex = vertices[polygon.vertexIds[i - 1]]; | ||
| } | ||
| var a = nextVertex.clone().sub(vertex); | ||
| var b = previousVertex.clone().sub(vertex); | ||
| var angle = a.angleTo(b); | ||
| total += angle; | ||
| if (angle === Math.PI || angle === 0) return false; | ||
| var r = a.cross(b).y; | ||
| results.push(r); | ||
| } | ||
| // if ( total > (polygon.vertexIds.length-2)*Math.PI ) return false; | ||
| results.forEach(function (r) { | ||
| if (r === 0) convex = false; | ||
| }); | ||
| if (results[0] > 0) { | ||
| results.forEach(function (r) { | ||
| if (r < 0) convex = false; | ||
| }); | ||
| } else { | ||
| results.forEach(function (r) { | ||
| if (r > 0) convex = false; | ||
| }); | ||
| } | ||
| return convex; | ||
| } | ||
| }, { | ||
| key: 'distanceToSquared', | ||
| value: function distanceToSquared(a, b) { | ||
| var dx = a.x - b.x; | ||
| var dy = a.y - b.y; | ||
| var dz = a.z - b.z; | ||
| return dx * dx + dy * dy + dz * dz; | ||
| } | ||
| //+ Jonas Raoni Soares Silva | ||
| //@ http://jsfromhell.com/math/is-point-in-poly [rev. #0] | ||
| }, { | ||
| key: 'isPointInPoly', | ||
| value: function isPointInPoly(poly, pt) { | ||
| for (var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i) { | ||
| (poly[i].z <= pt.z && pt.z < poly[j].z || poly[j].z <= pt.z && pt.z < poly[i].z) && pt.x < (poly[j].x - poly[i].x) * (pt.z - poly[i].z) / (poly[j].z - poly[i].z) + poly[i].x && (c = !c); | ||
| }return c; | ||
| } | ||
| }, { | ||
| key: 'isVectorInPolygon', | ||
| value: function isVectorInPolygon(vector, polygon, vertices) { | ||
| // reference point will be the centroid of the polygon | ||
| // We need to rotate the vector as well as all the points which the polygon uses | ||
| var lowestPoint = 100000; | ||
| var highestPoint = -100000; | ||
| var polygonVertices = []; | ||
| polygon.vertexIds.forEach(function (vId) { | ||
| lowestPoint = Math.min(vertices[vId].y, lowestPoint); | ||
| highestPoint = Math.max(vertices[vId].y, highestPoint); | ||
| polygonVertices.push(vertices[vId]); | ||
| }); | ||
| if (vector.y < highestPoint + 0.5 && vector.y > lowestPoint - 0.5 && this.isPointInPoly(polygonVertices, vector)) { | ||
| return true; | ||
| } | ||
| return false; | ||
| } | ||
| }, { | ||
| key: 'triarea2', | ||
| value: function triarea2(a, b, c) { | ||
| var ax = b.x - a.x; | ||
| var az = b.z - a.z; | ||
| var bx = c.x - a.x; | ||
| var bz = c.z - a.z; | ||
| return bx * az - ax * bz; | ||
| } | ||
| }, { | ||
| key: 'vequal', | ||
| value: function vequal(a, b) { | ||
| return this.distanceToSquared(a, b) < 0.00001; | ||
| } | ||
| }, { | ||
| key: 'array_intersect', | ||
| value: function array_intersect() { | ||
| var i = void 0, | ||
| shortest = void 0, | ||
| nShortest = void 0, | ||
| n = void 0, | ||
| len = void 0, | ||
| ret = [], | ||
| obj = {}, | ||
| nOthers = void 0; | ||
| nOthers = arguments.length - 1; | ||
| nShortest = arguments[0].length; | ||
| shortest = 0; | ||
| for (i = 0; i <= nOthers; i++) { | ||
| n = arguments[i].length; | ||
| if (n < nShortest) { | ||
| shortest = i; | ||
| nShortest = n; | ||
| } | ||
| } | ||
| for (i = 0; i <= nOthers; i++) { | ||
| n = i === shortest ? 0 : i || shortest; //Read the shortest array first. Read the first array instead of the shortest | ||
| len = arguments[n].length; | ||
| for (var j = 0; j < len; j++) { | ||
| var elem = arguments[n][j]; | ||
| if (obj[elem] === i - 1) { | ||
| if (i === nOthers) { | ||
| ret.push(elem); | ||
| obj[elem] = 0; | ||
| } else { | ||
| obj[elem] = i; | ||
| } | ||
| } else if (i === 0) { | ||
| obj[elem] = 0; | ||
| } | ||
| } | ||
| } | ||
| return ret; | ||
| } | ||
| }]); | ||
| return Utils; | ||
| }(); | ||
| module.exports = Utils; | ||
| },{}]},{},[1]); | ||
| var e=function(){};e.computeCentroids=function(e){var t,n,r;for(t=0,n=e.faces.length;t<n;t++)(r=e.faces[t]).centroid=new THREE.Vector3(0,0,0),r.centroid.add(e.vertices[r.a]),r.centroid.add(e.vertices[r.b]),r.centroid.add(e.vertices[r.c]),r.centroid.divideScalar(3)},e.roundNumber=function(e,t){var n=Number(e+"").toFixed(parseInt(t));return parseFloat(n)},e.sample=function(e){return e[Math.floor(Math.random()*e.length)]},e.mergeVertexIds=function(e,t){var n=[];if(e.forEach(function(e){t.indexOf(e)>=0&&n.push(e)}),n.length<2)return[];n.includes(e[0])&&n.includes(e[e.length-1])&&e.push(e.shift()),n.includes(t[0])&&n.includes(t[t.length-1])&&t.push(t.shift()),n=[],e.forEach(function(e){t.includes(e)&&n.push(e)});for(var r=n[1],o=n[0],i=e.slice();i[0]!==r;)i.push(i.shift());for(var s=0,u=t.slice();u[0]!==o;)if(u.push(u.shift()),s++>10)throw new Error("Unexpected state");return u.shift(),u.pop(),i=i.concat(u)},e.setPolygonCentroid=function(e,t){var n=new THREE.Vector3,r=t.vertices;e.vertexIds.forEach(function(e){n.add(r[e])}),n.divideScalar(e.vertexIds.length),e.centroid.copy(n)},e.cleanPolygon=function(e,t){for(var n=[],r=t.vertices,o=0;o<e.vertexIds.length;o++){var i,s,u,c=r[e.vertexIds[o]];0===o?(i=e.vertexIds[1],s=e.vertexIds[e.vertexIds.length-1]):o===e.vertexIds.length-1?(i=e.vertexIds[0],s=e.vertexIds[e.vertexIds.length-2]):(i=e.vertexIds[o+1],s=e.vertexIds[o-1]),u=r[s];var h=r[i].clone().sub(c),a=u.clone().sub(c),d=h.angleTo(a);if(d>Math.PI-.01&&d<Math.PI+.01){var f=[];e.neighbours.forEach(function(t){t.vertexIds.includes(e.vertexIds[o])||f.push(t)}),e.neighbours=f}else n.push(e.vertexIds[o])}e.vertexIds=n,this.setPolygonCentroid(e,t)},e.isConvex=function(e,t){var n=t.vertices;if(e.vertexIds.length<3)return!1;for(var r=!0,o=[],i=0;i<e.vertexIds.length;i++){var s,u,c=n[e.vertexIds[i]];0===i?(s=n[e.vertexIds[1]],u=n[e.vertexIds[e.vertexIds.length-1]]):i===e.vertexIds.length-1?(s=n[e.vertexIds[0]],u=n[e.vertexIds[e.vertexIds.length-2]]):(s=n[e.vertexIds[i+1]],u=n[e.vertexIds[i-1]]);var h=s.clone().sub(c),a=u.clone().sub(c),d=h.angleTo(a);if(d===Math.PI||0===d)return!1;var f=h.cross(a).y;o.push(f)}return o.forEach(function(e){0===e&&(r=!1)}),o.forEach(o[0]>0?function(e){e<0&&(r=!1)}:function(e){e>0&&(r=!1)}),r},e.distanceToSquared=function(e,t){var n=e.x-t.x,r=e.y-t.y,o=e.z-t.z;return n*n+r*r+o*o},e.isPointInPoly=function(e,t){for(var n=!1,r=-1,o=e.length,i=o-1;++r<o;i=r)(e[r].z<=t.z&&t.z<e[i].z||e[i].z<=t.z&&t.z<e[r].z)&&t.x<(e[i].x-e[r].x)*(t.z-e[r].z)/(e[i].z-e[r].z)+e[r].x&&(n=!n);return n},e.isVectorInPolygon=function(e,t,n){var r=1e5,o=-1e5,i=[];return t.vertexIds.forEach(function(e){r=Math.min(n[e].y,r),o=Math.max(n[e].y,o),i.push(n[e])}),!!(e.y<o+.5&&e.y>r-.5&&this.isPointInPoly(i,e))},e.triarea2=function(e,t,n){return(n.x-e.x)*(t.z-e.z)-(t.x-e.x)*(n.z-e.z)},e.vequal=function(e,t){return this.distanceToSquared(e,t)<1e-5},e.array_intersect=function(){var e,t,n,r,o,i,s=arguments,u=[],c={};for(i=arguments.length-1,n=arguments[0].length,t=0,e=0;e<=i;e++)(r=s[e].length)<n&&(t=e,n=r);for(e=0;e<=i;e++){o=s[r=e===t?0:e||t].length;for(var h=0;h<o;h++){var a=s[r][h];c[a]===e-1?e===i?(u.push(a),c[a]=0):c[a]=e:0===e&&(c[a]=0)}}return u};var t=function(e){this.content=[],this.scoreFunction=e};t.prototype.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},t.prototype.pop=function(){var e=this.content[0],t=this.content.pop();return this.content.length>0&&(this.content[0]=t,this.bubbleUp(0)),e},t.prototype.remove=function(e){var t=this.content.indexOf(e),n=this.content.pop();t!==this.content.length-1&&(this.content[t]=n,this.scoreFunction(n)<this.scoreFunction(e)?this.sinkDown(t):this.bubbleUp(t))},t.prototype.size=function(){return this.content.length},t.prototype.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},t.prototype.sinkDown=function(e){for(var t=this.content[e];e>0;){var n=(e+1>>1)-1,r=this.content[n];if(!(this.scoreFunction(t)<this.scoreFunction(r)))break;this.content[n]=t,this.content[e]=r,e=n}},t.prototype.bubbleUp=function(e){for(var t=this.content.length,n=this.content[e],r=this.scoreFunction(n);;){var o=e+1<<1,i=o-1,s=null,u=void 0;if(i<t)(u=this.scoreFunction(this.content[i]))<r&&(s=i);if(o<t)this.scoreFunction(this.content[o])<(null===s?r:u)&&(s=o);if(null===s)break;this.content[e]=this.content[s],this.content[s]=n,e=s}};var n=function(){};n.init=function(e){for(var t=0;t<e.length;t++){var n=e[t];n.f=0,n.g=0,n.h=0,n.cost=1,n.visited=!1,n.closed=!1,n.parent=null}},n.cleanUp=function(e){for(var t=0;t<e.length;t++){var n=e[t];delete n.f,delete n.g,delete n.h,delete n.cost,delete n.visited,delete n.closed,delete n.parent}},n.heap=function(){return new t(function(e){return e.f})},n.search=function(e,t,n){this.init(e);var r=this.heap();for(r.push(t);r.size()>0;){var o=r.pop();if(o===n){for(var i=o,s=[];i.parent;)s.push(i),i=i.parent;return this.cleanUp(s),s.reverse()}o.closed=!0;for(var u=this.neighbours(e,o),c=0,h=u.length;c<h;c++){var a=u[c];if(!a.closed){var d=o.g+a.cost,f=a.visited;if(!f||d<a.g){if(a.visited=!0,a.parent=o,!a.centroid||!n.centroid)throw new Error("Unexpected state");a.h=a.h||this.heuristic(a.centroid,n.centroid),a.g=d,a.f=a.g+a.h,f?r.rescoreElement(a):r.push(a)}}}}return[]},n.heuristic=function(t,n){return e.distanceToSquared(t,n)},n.neighbours=function(e,t){for(var n=[],r=0;r<t.neighbours.length;r++)n.push(e[t.neighbours[r]]);return n};var r=1,o=function(){};o.buildZone=function(t){var n=this,r=this._buildNavigationMesh(t),o={};r.vertices.forEach(function(t){t.x=e.roundNumber(t.x,2),t.y=e.roundNumber(t.y,2),t.z=e.roundNumber(t.z,2)}),o.vertices=r.vertices;var i=this._buildPolygonGroups(r);o.groups=[];var s=function(e,t){for(var n=0;n<e.length;n++)if(t===e[n])return n};return i.forEach(function(t){var r=[];t.forEach(function(o){var i=o.neighbours.map(function(e){return s(t,e)}),u=o.neighbours.map(function(e){return n._getSharedVerticesInOrder(o,e)});o.centroid.x=e.roundNumber(o.centroid.x,2),o.centroid.y=e.roundNumber(o.centroid.y,2),o.centroid.z=e.roundNumber(o.centroid.z,2),r.push({id:s(t,o),neighbours:i,vertexIds:o.vertexIds,centroid:o.centroid,portals:u})}),o.groups.push(r)}),o},o._buildNavigationMesh=function(t){return e.computeCentroids(t),t.mergeVertices(),this._buildPolygonsFromGeometry(t)},o._buildPolygonGroups=function(e){var t=[],n=0,r=function(e){e.neighbours.forEach(function(t){void 0===t.group&&(t.group=e.group,r(t))})};return e.polygons.forEach(function(e){void 0===e.group&&(e.group=n++,r(e)),t[e.group]||(t[e.group]=[]),t[e.group].push(e)}),t},o._buildPolygonNeighbours=function(t,n){t.neighbours=[];for(var r=0,o=n.polygons.length;r<o;r++){if(t!==n.polygons[r])if(!(t.centroid.distanceToSquared(n.polygons[r].centroid)>1e4))e.array_intersect(t.vertexIds,n.polygons[r].vertexIds).length>=2&&t.neighbours.push(n.polygons[r])}},o._buildPolygonsFromGeometry=function(e){var t=this,n=[],o=e.vertices,i=e.faceVertexUvs;e.faces.forEach(function(e){n.push({id:r++,vertexIds:[e.a,e.b,e.c],centroid:e.centroid,normal:e.normal,neighbours:[]})});var s={polygons:n,vertices:o,faceVertexUvs:i};return n.forEach(function(e){t._buildPolygonNeighbours(e,s)}),s},o._getSharedVerticesInOrder=function(e,t){var n=e.vertexIds,r=t.vertexIds,o=[];return n.forEach(function(e){r.includes(e)&&o.push(e)}),o.length<2?[]:(o.includes(n[0])&&o.includes(n[n.length-1])&&n.push(n.shift()),o.includes(r[0])&&o.includes(r[r.length-1])&&r.push(r.shift()),o.length=0,n.forEach(function(e){r.includes(e)&&o.push(e)}),o)};var i=function(){this.portals=[]};i.prototype.push=function(e,t){void 0===t&&(t=e),this.portals.push({left:e,right:t})},i.prototype.stringPull=function(){var t,n,r,o=this.portals,i=[],s=0,u=0,c=0;n=o[0].left,r=o[0].right,i.push(t=o[0].left);for(var h=1;h<o.length;h++){var a=o[h].left,d=o[h].right;if(e.triarea2(t,r,d)<=0){if(!(e.vequal(t,r)||e.triarea2(t,n,d)>0)){i.push(n),n=t=n,r=t,u=s=u,c=s,h=s;continue}r=d,c=h}if(e.triarea2(t,n,a)>=0){if(!(e.vequal(t,n)||e.triarea2(t,r,a)<0)){i.push(r),n=t=r,r=t,u=s=c,c=s,h=s;continue}n=a,u=h}}return 0!==i.length&&e.vequal(i[i.length-1],o[o.length-1].left)||i.push(o[o.length-1].left),this.path=i,i};var s,u,c,h,a,d,f=function(){this.zones={}};f.createZone=function(e){return o.buildZone(e)},f.prototype.setZoneData=function(e,t){this.zones[e]=t},f.prototype.getGroup=function(t,n){if(!this.zones[t])return null;var r=null,o=Math.pow(50,2);return this.zones[t].groups.forEach(function(t,i){t.forEach(function(t){var s=e.distanceToSquared(t.centroid,n);s<o&&(r=i,o=s)})}),r},f.prototype.getRandomNode=function(t,n,r,o){if(!this.zones[t])return new THREE.Vector3;r=r||null,o=o||0;var i=[];return this.zones[t].groups[n].forEach(function(t){r&&o?e.distanceToSquared(r,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),e.sample(i)||new THREE.Vector3},f.prototype.getClosestNode=function(t,n,r,o){void 0===o&&(o=!1);var i=this.zones[n].vertices,s=null,u=Infinity;return this.zones[n].groups[r].forEach(function(n){var r=e.distanceToSquared(n.centroid,t);r<u&&(!o||e.isVectorInPolygon(t,n,i))&&(s=n,u=r)}),s},f.prototype.findPath=function(e,t,r,o){var s=this.zones[r].groups[o],u=this.zones[r].vertices,c=this.getClosestNode(e,r,o),h=this.getClosestNode(t,r,o,!0);if(!c||!h)return null;var a=n.search(s,c,h),d=function(e,t){for(var n=0;n<e.neighbours.length;n++)if(e.neighbours[n]===t.id)return e.portals[n]},f=new i;f.push(e);for(var l=0;l<a.length;l++){var v=a[l+1];if(v){var p=d(a[l],v);f.push(u[p[0]],u[p[1]])}}f.push(t),f.stringPull();var g=f.path.map(function(e){return new THREE.Vector3(e.x,e.y,e.z)});return g.shift(),g},f.prototype.clampStep=(c=new THREE.Vector3,h=new THREE.Plane,a=new THREE.Triangle,d=new THREE.Vector3,function(e,t,n,r,o,i){var f=this.zones[r].vertices,l=this.zones[r].groups[o],v=[n],p={};p[n.id]=0,s=void 0,d.set(0,0,0),u=Infinity,h.setFromCoplanarPoints(f[n.vertexIds[0]],f[n.vertexIds[1]],f[n.vertexIds[2]]),h.projectPoint(t,c),t.copy(c);for(var g=v.pop();g;g=v.pop()){a.set(f[g.vertexIds[0]],f[g.vertexIds[1]],f[g.vertexIds[2]]),a.closestPointToPoint(t,c),c.distanceToSquared(t)<u&&(s=g,d.copy(c),u=c.distanceToSquared(t));var x=p[g];if(!(x>2))for(var y=0;y<g.neighbours.length;y++){var I=l[g.neighbours[y]];I.id in p||(v.push(I),p[I.id]=x+1)}}return i.copy(d),s}),exports.Pathfinding=f; | ||
| //# sourceMappingURL=three-pathfinding.js.map |
| { | ||
| "name": "three-pathfinding", | ||
| "version": "0.5.5", | ||
| "version": "0.6.0", | ||
| "description": "Navigation mesh toolkit for three.js, based on PatrolJS", | ||
| "main": "src/index.js", | ||
| "author": "Don McCurdy <dm@donmccurdy.com>", | ||
| "license": "MIT", | ||
| "repository": { | ||
| "type": "git", | ||
| "url": "git+https://github.com/donmccurdy/three-pathfinding.git" | ||
| }, | ||
| "main": "dist/three-pathfinding.js", | ||
| "module": "dist/three-pathfinding.module.js", | ||
| "source": "src/index.js", | ||
| "scripts": { | ||
| "dev": "budo browser.js:bundle.js --live", | ||
| "dev": "concurrently \"microbundle watch --target browser\" \"serve --listen 5000\"", | ||
| "docs": "documentation build src/index.js --shallow -f md | replace-between --target README.md --token API", | ||
| "dist": "browserify browser.js -o dist/three-pathfinding.js && uglifyjs dist/three-pathfinding.js --mangle > dist/three-pathfinding.min.js", | ||
| "dist": "microbundle --target browser", | ||
| "version": "npm run dist && git add -A dist", | ||
@@ -27,26 +35,10 @@ "postversion": "git push && git push --tags && npm publish" | ||
| ], | ||
| "author": "Don McCurdy <dm@donmccurdy.com>", | ||
| "license": "MIT", | ||
| "devDependencies": { | ||
| "babel-core": "^6.26.0", | ||
| "babel-preset-env": "^1.6.1", | ||
| "babelify": "^8.0.0", | ||
| "browserify": "^14.4.0", | ||
| "budo": "^10.0.4", | ||
| "concurrently": "^3.6.0", | ||
| "documentation": "^5.3.3", | ||
| "microbundle": "^0.5.1", | ||
| "replace-between": "0.0.8", | ||
| "serve": "^9.2.0", | ||
| "uglify-js": "^3.3.3" | ||
| }, | ||
| "browserify": { | ||
| "transform": [ | ||
| [ | ||
| "babelify", | ||
| { | ||
| "presets": [ | ||
| "env" | ||
| ] | ||
| } | ||
| ] | ||
| ] | ||
| } | ||
| } |
@@ -5,4 +5,12 @@ # three-pathfinding | ||
| Thanks to [Nick Janssen](https://github.com/nickjanssen) for creating [PatrolJS](https://github.com/nickjanssen/PatrolJS), which was the basis for this library. | ||
|  | ||
| ## Introduction | ||
| 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](http://www.ai-blog.net/archives/000152.html). | ||
| ## Quickstart | ||
@@ -16,5 +24,28 @@ | ||
| ### Creating a Navigation Mesh | ||
| This library does not build navigation meshes for you — instead, create a navigation mesh using [Blender](https://youtu.be/v4d_6ZCGlAg?t=6m8s), [Recast](https://github.com/recastnavigation/recastnavigation) ([CLI](https://github.com/but0n/recastCLI.js)), or another tool. | ||
| The library accepts a [THREE.Geometry](https://threejs.org/docs/#api/core/Geometry) instance, which can be loaded with any three.js loader and converted from BufferGeometry if necessary. | ||
| ### Example | ||
| Loading a mesh from a `.gltf` file: | ||
| ```js | ||
| let mesh; | ||
| const loader = new THREE.GLTFLoader(); | ||
| loader.load( 'navmesh.gltf', ({scene}) => { | ||
| scene.traverse((node) => { | ||
| if (node.isMesh) mesh = node; | ||
| }); | ||
| }, undefined, (e) => { | ||
| console.error(e); | ||
| }); | ||
| ``` | ||
| Initializing the library, creating a level, and finding a path: | ||
| ```js | ||
| const Pathfinder = require('three-pathfinding'); | ||
@@ -21,0 +52,0 @@ const pathfinder = new Pathfinder(); |
@@ -1,3 +0,3 @@ | ||
| const BinaryHeap = require('./BinaryHeap'); | ||
| const utils = require('./utils.js'); | ||
| import { BinaryHeap } from './BinaryHeap'; | ||
| import { Utils } from './Utils.js'; | ||
@@ -109,3 +109,3 @@ class AStar { | ||
| static heuristic (pos1, pos2) { | ||
| return utils.distanceToSquared(pos1, pos2); | ||
| return Utils.distanceToSquared(pos1, pos2); | ||
| } | ||
@@ -124,2 +124,2 @@ | ||
| module.exports = AStar; | ||
| export { AStar }; |
@@ -134,2 +134,2 @@ // javascript-astar | ||
| module.exports = BinaryHeap; | ||
| export { BinaryHeap }; |
@@ -1,2 +0,2 @@ | ||
| const utils = require('./utils'); | ||
| import { Utils } from './Utils'; | ||
@@ -18,5 +18,5 @@ let polygonId = 1; | ||
| navMesh.vertices.forEach((v) => { | ||
| v.x = utils.roundNumber(v.x, 2); | ||
| v.y = utils.roundNumber(v.y, 2); | ||
| v.z = utils.roundNumber(v.z, 2); | ||
| v.x = Utils.roundNumber(v.x, 2); | ||
| v.y = Utils.roundNumber(v.y, 2); | ||
| v.z = Utils.roundNumber(v.z, 2); | ||
| }); | ||
@@ -47,5 +47,5 @@ | ||
| 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); | ||
| 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); | ||
@@ -74,3 +74,3 @@ newGroup.push({ | ||
| static _buildNavigationMesh (geometry) { | ||
| utils.computeCentroids(geometry); | ||
| Utils.computeCentroids(geometry); | ||
| geometry.mergeVertices(); | ||
@@ -122,3 +122,3 @@ return this._buildPolygonsFromGeometry(geometry); | ||
| const matches = utils.array_intersect(polygon.vertexIds, navigationMesh.polygons[i].vertexIds); | ||
| const matches = Utils.array_intersect(polygon.vertexIds, navigationMesh.polygons[i].vertexIds); | ||
@@ -200,2 +200,2 @@ if (matches.length >= 2) { | ||
| module.exports = Builder; | ||
| export { Builder }; |
@@ -1,2 +0,2 @@ | ||
| const utils = require('./utils'); | ||
| import { Utils } from './Utils'; | ||
@@ -37,4 +37,4 @@ class Channel { | ||
| // Update right vertex. | ||
| if (utils.triarea2(portalApex, portalRight, right) <= 0.0) { | ||
| if (utils.vequal(portalApex, portalRight) || utils.triarea2(portalApex, portalLeft, right) > 0.0) { | ||
| if (Utils.triarea2(portalApex, portalRight, right) <= 0.0) { | ||
| if (Utils.vequal(portalApex, portalRight) || Utils.triarea2(portalApex, portalLeft, right) > 0.0) { | ||
| // Tighten the funnel. | ||
@@ -61,4 +61,4 @@ portalRight = right; | ||
| // Update left vertex. | ||
| if (utils.triarea2(portalApex, portalLeft, left) >= 0.0) { | ||
| if (utils.vequal(portalApex, portalLeft) || utils.triarea2(portalApex, portalRight, left) < 0.0) { | ||
| if (Utils.triarea2(portalApex, portalLeft, left) >= 0.0) { | ||
| if (Utils.vequal(portalApex, portalLeft) || Utils.triarea2(portalApex, portalRight, left) < 0.0) { | ||
| // Tighten the funnel. | ||
@@ -85,3 +85,3 @@ portalLeft = left; | ||
| if ((pts.length === 0) || (!utils.vequal(pts[pts.length - 1], portals[portals.length - 1].left))) { | ||
| if ((pts.length === 0) || (!Utils.vequal(pts[pts.length - 1], portals[portals.length - 1].left))) { | ||
| // Append last point to path. | ||
@@ -96,2 +96,2 @@ pts.push(portals[portals.length - 1].left); | ||
| module.exports = Channel; | ||
| export { Channel }; |
| /* global THREE */ | ||
| const utils = require('./utils'); | ||
| const AStar = require('./AStar'); | ||
| const Builder = require('./Builder'); | ||
| const Channel = require('./Channel'); | ||
| import { Utils } from './Utils'; | ||
| import { AStar } from './AStar'; | ||
| import { Builder } from './Builder'; | ||
| import { Channel } from './Channel'; | ||
@@ -11,3 +11,3 @@ /** | ||
| */ | ||
| class Path { | ||
| class Pathfinding { | ||
| constructor () { | ||
@@ -49,3 +49,3 @@ this.zones = {}; | ||
| group.forEach((node) => { | ||
| const measuredDistance = utils.distanceToSquared(node.centroid, position); | ||
| const measuredDistance = Utils.distanceToSquared(node.centroid, position); | ||
| if (measuredDistance < distance) { | ||
@@ -81,3 +81,3 @@ closestNodeGroup = index; | ||
| if (nearPosition && nearRange) { | ||
| if (utils.distanceToSquared(nearPosition, p.centroid) < nearRange * nearRange) { | ||
| if (Utils.distanceToSquared(nearPosition, p.centroid) < nearRange * nearRange) { | ||
| candidates.push(p.centroid); | ||
@@ -90,3 +90,3 @@ } | ||
| return utils.sample(candidates) || new THREE.Vector3(); | ||
| return Utils.sample(candidates) || new THREE.Vector3(); | ||
| } | ||
@@ -109,5 +109,5 @@ | ||
| nodes.forEach((node) => { | ||
| const distance = utils.distanceToSquared(node.centroid, position); | ||
| const distance = Utils.distanceToSquared(node.centroid, position); | ||
| if (distance < closestDistance | ||
| && (!checkPolygon || utils.isVectorInPolygon(position, node, vertices))) { | ||
| && (!checkPolygon || Utils.isVectorInPolygon(position, node, vertices))) { | ||
| closestNode = node; | ||
@@ -190,3 +190,3 @@ closestDistance = distance; | ||
| */ | ||
| Path.prototype.clampStep = (function () { | ||
| Pathfinding.prototype.clampStep = (function () { | ||
| const point = new THREE.Vector3(); | ||
@@ -284,2 +284,2 @@ const plane = new THREE.Plane(); | ||
| module.exports = Path; | ||
| export { Pathfinding }; |
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis 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
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
No repository
Supply chain riskPackage does not have a linked source code repository. Without this field, a package will have no reference to the location of the source code use to generate the package.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by40.32%
470044
- Dev dependency count
- decreased by-25%
6
- Number of package files
- increased by23.81%
26
- Number of lines in readme file
- increased by16.76%
216
- Number of low supply chain risk alerts
- decreased by-60%
2
Worsened metrics
- Lines of code
- decreased by-32.4%
1913
No dependency changes