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.5.2 to 0.5.5

5

dist/three-pathfinding.js

@@ -890,7 +890,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){

if (triangle.containsPoint(end)) {
endTarget.copy(end);
return currentNode;
}
triangle.closestPointToPoint(end, point);

@@ -897,0 +892,0 @@

2

dist/three-pathfinding.min.js

@@ -1,1 +0,1 @@

(function e(r,n,t){function i(u,a){if(!n[u]){if(!r[u]){var s=typeof require=="function"&&require;if(!a&&s)return s(u,!0);if(o)return o(u,!0);var c=new Error("Cannot find module '"+u+"'");throw c.code="MODULE_NOT_FOUND",c}var f=n[u]={exports:{}};r[u][0].call(f.exports,function(e){var n=r[u][1][e];return i(n?n:e)},f,f.exports,e,r,n,t)}return n[u].exports}var o=typeof require=="function"&&require;for(var u=0;u<t.length;u++)i(t[u]);return i})({1:[function(e,r,n){"use strict";THREE.Pathfinding=e("./src")},{"./src":6}],2:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=e("./BinaryHeap");var u=e("./utils.js");var a=function(){function e(){i(this,e)}t(e,null,[{key:"init",value:function e(r){for(var n=0;n<r.length;n++){var t=r[n];t.f=0;t.g=0;t.h=0;t.cost=1;t.visited=false;t.closed=false;t.parent=null}}},{key:"cleanUp",value:function e(r){for(var n=0;n<r.length;n++){var t=r[n];delete t.f;delete t.g;delete t.h;delete t.cost;delete t.visited;delete t.closed;delete t.parent}}},{key:"heap",value:function e(){return new o(function(e){return e.f})}},{key:"search",value:function e(r,n,t){this.init(r);var i=this.heap();i.push(n);while(i.size()>0){var o=i.pop();if(o===t){var u=o;var a=[];while(u.parent){a.push(u);u=u.parent}this.cleanUp(a);return a.reverse()}o.closed=true;var s=this.neighbours(r,o);for(var c=0,f=s.length;c<f;c++){var l=s[c];if(l.closed){continue}var v=o.g+l.cost;var h=l.visited;if(!h||v<l.g){l.visited=true;l.parent=o;if(!l.centroid||!t.centroid)throw new Error("Unexpected state");l.h=l.h||this.heuristic(l.centroid,t.centroid);l.g=v;l.f=l.g+l.h;if(!h){i.push(l)}else{i.rescoreElement(l)}}}}return[]}},{key:"heuristic",value:function e(r,n){return u.distanceToSquared(r,n)}},{key:"neighbours",value:function e(r,n){var t=[];for(var i=0;i<n.neighbours.length;i++){t.push(r[n.neighbours[i]])}return t}}]);return e}();r.exports=a},{"./BinaryHeap":3,"./utils.js":7}],3:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=function(){function e(r){i(this,e);this.content=[];this.scoreFunction=r}t(e,[{key:"push",value:function e(r){this.content.push(r);this.sinkDown(this.content.length-1)}},{key:"pop",value:function e(){var r=this.content[0];var n=this.content.pop();if(this.content.length>0){this.content[0]=n;this.bubbleUp(0)}return r}},{key:"remove",value:function e(r){var n=this.content.indexOf(r);var t=this.content.pop();if(n!==this.content.length-1){this.content[n]=t;if(this.scoreFunction(t)<this.scoreFunction(r)){this.sinkDown(n)}else{this.bubbleUp(n)}}}},{key:"size",value:function e(){return this.content.length}},{key:"rescoreElement",value:function e(r){this.sinkDown(this.content.indexOf(r))}},{key:"sinkDown",value:function e(r){var n=this.content[r];while(r>0){var t=(r+1>>1)-1;var i=this.content[t];if(this.scoreFunction(n)<this.scoreFunction(i)){this.content[t]=n;this.content[r]=i;r=t}else{break}}}},{key:"bubbleUp",value:function e(r){var n=this.content.length,t=this.content[r],i=this.scoreFunction(t);while(true){var o=r+1<<1,u=o-1;var a=null;var s=void 0;if(u<n){var c=this.content[u];s=this.scoreFunction(c);if(s<i){a=u}}if(o<n){var f=this.content[o],l=this.scoreFunction(f);if(l<(a===null?i:s)){a=o}}if(a!==null){this.content[r]=this.content[a];this.content[a]=t;r=a}else{break}}}}]);return e}();r.exports=o},{}],4:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=e("./utils");var u=1;var a=function(){function e(){i(this,e)}t(e,null,[{key:"buildZone",value:function e(r){var n=this;var t=this._buildNavigationMesh(r);var i={};t.vertices.forEach(function(e){e.x=o.roundNumber(e.x,2);e.y=o.roundNumber(e.y,2);e.z=o.roundNumber(e.z,2)});i.vertices=t.vertices;var u=this._buildPolygonGroups(t);i.groups=[];var a=function e(r,n){for(var t=0;t<r.length;t++){if(n===r[t])return t}};u.forEach(function(e){var r=[];e.forEach(function(t){var i=t.neighbours.map(function(r){return a(e,r)});var u=t.neighbours.map(function(e){return n._getSharedVerticesInOrder(t,e)});t.centroid.x=o.roundNumber(t.centroid.x,2);t.centroid.y=o.roundNumber(t.centroid.y,2);t.centroid.z=o.roundNumber(t.centroid.z,2);r.push({id:a(e,t),neighbours:i,vertexIds:t.vertexIds,centroid:t.centroid,portals:u})});i.groups.push(r)});return i}},{key:"_buildNavigationMesh",value:function e(r){o.computeCentroids(r);r.mergeVertices();return this._buildPolygonsFromGeometry(r)}},{key:"_buildPolygonGroups",value:function e(r){var n=r.polygons;var t=[];var i=0;var o=function e(r){r.neighbours.forEach(function(n){if(n.group===undefined){n.group=r.group;e(n)}})};n.forEach(function(e){if(e.group===undefined){e.group=i++;o(e)}if(!t[e.group])t[e.group]=[];t[e.group].push(e)});return t}},{key:"_buildPolygonNeighbours",value:function e(r,n){r.neighbours=[];for(var t=0,i=n.polygons.length;t<i;t++){if(r===n.polygons[t])continue;if(r.centroid.distanceToSquared(n.polygons[t].centroid)>100*100)continue;var u=o.array_intersect(r.vertexIds,n.polygons[t].vertexIds);if(u.length>=2){r.neighbours.push(n.polygons[t])}}}},{key:"_buildPolygonsFromGeometry",value:function e(r){var n=this;var t=[];var i=r.vertices;var o=r.faceVertexUvs;r.faces.forEach(function(e){t.push({id:u++,vertexIds:[e.a,e.b,e.c],centroid:e.centroid,normal:e.normal,neighbours:[]})});var a={polygons:t,vertices:i,faceVertexUvs:o};t.forEach(function(e){n._buildPolygonNeighbours(e,a)});return a}},{key:"_getSharedVerticesInOrder",value:function e(r,n){var t=r.vertexIds;var i=n.vertexIds;var o=[];t.forEach(function(e){if(i.includes(e)){o.push(e)}});if(o.length<2)return[];if(o.includes(t[0])&&o.includes(t[t.length-1])){t.push(t.shift())}if(o.includes(i[0])&&o.includes(i[i.length-1])){i.push(i.shift())}o.length=0;t.forEach(function(e){if(i.includes(e)){o.push(e)}});return o}}]);return e}();r.exports=a},{"./utils":7}],5:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=e("./utils");var u=function(){function e(){i(this,e);this.portals=[]}t(e,[{key:"push",value:function e(r,n){if(n===undefined)n=r;this.portals.push({left:r,right:n})}},{key:"stringPull",value:function e(){var r=this.portals;var n=[];var t=void 0,i=void 0,u=void 0;var a=0,s=0,c=0;t=r[0].left;i=r[0].left;u=r[0].right;n.push(t);for(var f=1;f<r.length;f++){var l=r[f].left;var v=r[f].right;if(o.triarea2(t,u,v)<=0){if(o.vequal(t,u)||o.triarea2(t,i,v)>0){u=v;c=f}else{n.push(i);t=i;a=s;i=t;u=t;s=a;c=a;f=a;continue}}if(o.triarea2(t,i,l)>=0){if(o.vequal(t,i)||o.triarea2(t,u,l)<0){i=l;s=f}else{n.push(u);t=u;a=c;i=t;u=t;s=a;c=a;f=a;continue}}}if(n.length===0||!o.vequal(n[n.length-1],r[r.length-1].left)){n.push(r[r.length-1].left)}this.path=n;return n}}]);return e}();r.exports=u},{"./utils":7}],6:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=e("./utils");var u=e("./AStar");var a=e("./Builder");var s=e("./Channel");var c=function(){function e(){i(this,e);this.zones={}}t(e,[{key:"setZoneData",value:function e(r,n){this.zones[r]=n}},{key:"getGroup",value:function e(r,n){if(!this.zones[r])return null;var t=null;var i=Math.pow(50,2);this.zones[r].groups.forEach(function(e,r){e.forEach(function(e){var u=o.distanceToSquared(e.centroid,n);if(u<i){t=r;i=u}})});return t}},{key:"getRandomNode",value:function e(r,n,t,i){if(!this.zones[r])return new THREE.Vector3;t=t||null;i=i||0;var u=[];var a=this.zones[r].groups[n];a.forEach(function(e){if(t&&i){if(o.distanceToSquared(t,e.centroid)<i*i){u.push(e.centroid)}}else{u.push(e.centroid)}});return o.sample(u)||new THREE.Vector3}},{key:"getClosestNode",value:function e(r,n,t){var i=arguments.length>3&&arguments[3]!==undefined?arguments[3]:false;var u=this.zones[n].groups[t];var a=this.zones[n].vertices;var s=null;var c=Infinity;u.forEach(function(e){var n=o.distanceToSquared(e.centroid,r);if(n<c&&(!i||o.isVectorInPolygon(r,e,a))){s=e;c=n}});return s}},{key:"findPath",value:function e(r,n,t,i){var o=this.zones[t].groups[i];var a=this.zones[t].vertices;var c=this.getClosestNode(r,t,i);var f=this.getClosestNode(n,t,i,true);if(!c||!f){return null}var l=u.search(o,c,f);var v=function e(r,n){for(var t=0;t<r.neighbours.length;t++){if(r.neighbours[t]===n.id){return r.portals[t]}}};var h=new s;h.push(r);for(var d=0;d<l.length;d++){var p=l[d];var g=l[d+1];if(g){var y=v(p,g);h.push(a[y[0]],a[y[1]])}}h.push(n);h.stringPull();var b=h.path.map(function(e){return new THREE.Vector3(e.x,e.y,e.z)});b.shift();return b}}],[{key:"createZone",value:function e(r){return a.buildZone(r)}}]);return e}();c.prototype.clampStep=function(){var e=new THREE.Vector3;var r=new THREE.Plane;var n=new THREE.Triangle;var t=void 0;var i=new THREE.Vector3;var o=void 0;return function(u,a,s,c,f,l){var v=this.zones[c].vertices;var h=this.zones[c].groups[f];var d=[s];var p={};p[s.id]=0;t=undefined;i.set(0,0,0);o=Infinity;r.setFromCoplanarPoints(v[s.vertexIds[0]],v[s.vertexIds[1]],v[s.vertexIds[2]]);r.projectPoint(a,e);a.copy(e);for(var g=d.pop();g;g=d.pop()){n.set(v[g.vertexIds[0]],v[g.vertexIds[1]],v[g.vertexIds[2]]);if(n.containsPoint(a)){l.copy(a);return g}n.closestPointToPoint(a,e);if(e.distanceToSquared(a)<o){t=g;i.copy(e);o=e.distanceToSquared(a)}var y=p[g];if(y>2)continue;for(var b=0;b<g.neighbours.length;b++){var x=h[g.neighbours[b]];if(x.id in p)continue;d.push(x);p[x.id]=y+1}}l.copy(i);return t}}();var f={};var l={};var v={};r.exports=c},{"./AStar":2,"./Builder":4,"./Channel":5,"./utils":7}],7:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=function(){function e(){i(this,e)}t(e,null,[{key:"computeCentroids",value:function e(r){var n,t,i;for(n=0,t=r.faces.length;n<t;n++){i=r.faces[n];i.centroid=new THREE.Vector3(0,0,0);i.centroid.add(r.vertices[i.a]);i.centroid.add(r.vertices[i.b]);i.centroid.add(r.vertices[i.c]);i.centroid.divideScalar(3)}}},{key:"roundNumber",value:function e(r,n){var t=Number(r+"").toFixed(parseInt(n));return parseFloat(t)}},{key:"sample",value:function e(r){return r[Math.floor(Math.random()*r.length)]}},{key:"mergeVertexIds",value:function e(r,n){var t=[];r.forEach(function(e){if(n.indexOf(e)>=0){t.push(e)}});if(t.length<2)return[];if(t.includes(r[0])&&t.includes(r[r.length-1])){r.push(r.shift())}if(t.includes(n[0])&&t.includes(n[n.length-1])){n.push(n.shift())}t=[];r.forEach(function(e){if(n.includes(e)){t.push(e)}});var i=t[1];var o=t[0];var u=r.slice();while(u[0]!==i){u.push(u.shift())}var a=0;var s=n.slice();while(s[0]!==o){s.push(s.shift());if(a++>10)throw new Error("Unexpected state")}s.shift();s.pop();u=u.concat(s);return u}},{key:"setPolygonCentroid",value:function e(r,n){var t=new THREE.Vector3;var i=n.vertices;r.vertexIds.forEach(function(e){t.add(i[e])});t.divideScalar(r.vertexIds.length);r.centroid.copy(t)}},{key:"cleanPolygon",value:function e(r,n){var t=[];var i=n.vertices;for(var o=0;o<r.vertexIds.length;o++){var u=i[r.vertexIds[o]];var a,s;var c,f;if(o===0){a=r.vertexIds[1];s=r.vertexIds[r.vertexIds.length-1]}else if(o===r.vertexIds.length-1){a=r.vertexIds[0];s=r.vertexIds[r.vertexIds.length-2]}else{a=r.vertexIds[o+1];s=r.vertexIds[o-1]}c=i[a];f=i[s];var l=c.clone().sub(u);var v=f.clone().sub(u);var h=l.angleTo(v);if(h>Math.PI-.01&&h<Math.PI+.01){var d=[];r.neighbours.forEach(function(e){if(!e.vertexIds.includes(r.vertexIds[o])){d.push(e)}});r.neighbours=d}else{t.push(r.vertexIds[o])}}r.vertexIds=t;this.setPolygonCentroid(r,n)}},{key:"isConvex",value:function e(r,n){var t=n.vertices;if(r.vertexIds.length<3)return false;var i=true;var o=0;var u=[];for(var a=0;a<r.vertexIds.length;a++){var s=t[r.vertexIds[a]];var c,f;if(a===0){c=t[r.vertexIds[1]];f=t[r.vertexIds[r.vertexIds.length-1]]}else if(a===r.vertexIds.length-1){c=t[r.vertexIds[0]];f=t[r.vertexIds[r.vertexIds.length-2]]}else{c=t[r.vertexIds[a+1]];f=t[r.vertexIds[a-1]]}var l=c.clone().sub(s);var v=f.clone().sub(s);var h=l.angleTo(v);o+=h;if(h===Math.PI||h===0)return false;var d=l.cross(v).y;u.push(d)}u.forEach(function(e){if(e===0)i=false});if(u[0]>0){u.forEach(function(e){if(e<0)i=false})}else{u.forEach(function(e){if(e>0)i=false})}return i}},{key:"distanceToSquared",value:function e(r,n){var t=r.x-n.x;var i=r.y-n.y;var o=r.z-n.z;return t*t+i*i+o*o}},{key:"isPointInPoly",value:function e(r,n){for(var t=false,i=-1,o=r.length,u=o-1;++i<o;u=i){(r[i].z<=n.z&&n.z<r[u].z||r[u].z<=n.z&&n.z<r[i].z)&&n.x<(r[u].x-r[i].x)*(n.z-r[i].z)/(r[u].z-r[i].z)+r[i].x&&(t=!t)}return t}},{key:"isVectorInPolygon",value:function e(r,n,t){var i=1e5;var o=-1e5;var u=[];n.vertexIds.forEach(function(e){i=Math.min(t[e].y,i);o=Math.max(t[e].y,o);u.push(t[e])});if(r.y<o+.5&&r.y>i-.5&&this.isPointInPoly(u,r)){return true}return false}},{key:"triarea2",value:function e(r,n,t){var i=n.x-r.x;var o=n.z-r.z;var u=t.x-r.x;var a=t.z-r.z;return u*o-i*a}},{key:"vequal",value:function e(r,n){return this.distanceToSquared(r,n)<1e-5}},{key:"array_intersect",value:function e(){var r=void 0,n=void 0,t=void 0,i=void 0,o=void 0,u=[],a={},s=void 0;s=arguments.length-1;t=arguments[0].length;n=0;for(r=0;r<=s;r++){i=arguments[r].length;if(i<t){n=r;t=i}}for(r=0;r<=s;r++){i=r===n?0:r||n;o=arguments[i].length;for(var c=0;c<o;c++){var f=arguments[i][c];if(a[f]===r-1){if(r===s){u.push(f);a[f]=0}else{a[f]=r}}else if(r===0){a[f]=0}}}return u}}]);return e}();r.exports=o},{}]},{},[1]);
(function e(r,n,t){function i(u,a){if(!n[u]){if(!r[u]){var s=typeof require=="function"&&require;if(!a&&s)return s(u,!0);if(o)return o(u,!0);var c=new Error("Cannot find module '"+u+"'");throw c.code="MODULE_NOT_FOUND",c}var f=n[u]={exports:{}};r[u][0].call(f.exports,function(e){var n=r[u][1][e];return i(n?n:e)},f,f.exports,e,r,n,t)}return n[u].exports}var o=typeof require=="function"&&require;for(var u=0;u<t.length;u++)i(t[u]);return i})({1:[function(e,r,n){"use strict";THREE.Pathfinding=e("./src")},{"./src":6}],2:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=e("./BinaryHeap");var u=e("./utils.js");var a=function(){function e(){i(this,e)}t(e,null,[{key:"init",value:function e(r){for(var n=0;n<r.length;n++){var t=r[n];t.f=0;t.g=0;t.h=0;t.cost=1;t.visited=false;t.closed=false;t.parent=null}}},{key:"cleanUp",value:function e(r){for(var n=0;n<r.length;n++){var t=r[n];delete t.f;delete t.g;delete t.h;delete t.cost;delete t.visited;delete t.closed;delete t.parent}}},{key:"heap",value:function e(){return new o(function(e){return e.f})}},{key:"search",value:function e(r,n,t){this.init(r);var i=this.heap();i.push(n);while(i.size()>0){var o=i.pop();if(o===t){var u=o;var a=[];while(u.parent){a.push(u);u=u.parent}this.cleanUp(a);return a.reverse()}o.closed=true;var s=this.neighbours(r,o);for(var c=0,f=s.length;c<f;c++){var l=s[c];if(l.closed){continue}var v=o.g+l.cost;var h=l.visited;if(!h||v<l.g){l.visited=true;l.parent=o;if(!l.centroid||!t.centroid)throw new Error("Unexpected state");l.h=l.h||this.heuristic(l.centroid,t.centroid);l.g=v;l.f=l.g+l.h;if(!h){i.push(l)}else{i.rescoreElement(l)}}}}return[]}},{key:"heuristic",value:function e(r,n){return u.distanceToSquared(r,n)}},{key:"neighbours",value:function e(r,n){var t=[];for(var i=0;i<n.neighbours.length;i++){t.push(r[n.neighbours[i]])}return t}}]);return e}();r.exports=a},{"./BinaryHeap":3,"./utils.js":7}],3:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=function(){function e(r){i(this,e);this.content=[];this.scoreFunction=r}t(e,[{key:"push",value:function e(r){this.content.push(r);this.sinkDown(this.content.length-1)}},{key:"pop",value:function e(){var r=this.content[0];var n=this.content.pop();if(this.content.length>0){this.content[0]=n;this.bubbleUp(0)}return r}},{key:"remove",value:function e(r){var n=this.content.indexOf(r);var t=this.content.pop();if(n!==this.content.length-1){this.content[n]=t;if(this.scoreFunction(t)<this.scoreFunction(r)){this.sinkDown(n)}else{this.bubbleUp(n)}}}},{key:"size",value:function e(){return this.content.length}},{key:"rescoreElement",value:function e(r){this.sinkDown(this.content.indexOf(r))}},{key:"sinkDown",value:function e(r){var n=this.content[r];while(r>0){var t=(r+1>>1)-1;var i=this.content[t];if(this.scoreFunction(n)<this.scoreFunction(i)){this.content[t]=n;this.content[r]=i;r=t}else{break}}}},{key:"bubbleUp",value:function e(r){var n=this.content.length,t=this.content[r],i=this.scoreFunction(t);while(true){var o=r+1<<1,u=o-1;var a=null;var s=void 0;if(u<n){var c=this.content[u];s=this.scoreFunction(c);if(s<i){a=u}}if(o<n){var f=this.content[o],l=this.scoreFunction(f);if(l<(a===null?i:s)){a=o}}if(a!==null){this.content[r]=this.content[a];this.content[a]=t;r=a}else{break}}}}]);return e}();r.exports=o},{}],4:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=e("./utils");var u=1;var a=function(){function e(){i(this,e)}t(e,null,[{key:"buildZone",value:function e(r){var n=this;var t=this._buildNavigationMesh(r);var i={};t.vertices.forEach(function(e){e.x=o.roundNumber(e.x,2);e.y=o.roundNumber(e.y,2);e.z=o.roundNumber(e.z,2)});i.vertices=t.vertices;var u=this._buildPolygonGroups(t);i.groups=[];var a=function e(r,n){for(var t=0;t<r.length;t++){if(n===r[t])return t}};u.forEach(function(e){var r=[];e.forEach(function(t){var i=t.neighbours.map(function(r){return a(e,r)});var u=t.neighbours.map(function(e){return n._getSharedVerticesInOrder(t,e)});t.centroid.x=o.roundNumber(t.centroid.x,2);t.centroid.y=o.roundNumber(t.centroid.y,2);t.centroid.z=o.roundNumber(t.centroid.z,2);r.push({id:a(e,t),neighbours:i,vertexIds:t.vertexIds,centroid:t.centroid,portals:u})});i.groups.push(r)});return i}},{key:"_buildNavigationMesh",value:function e(r){o.computeCentroids(r);r.mergeVertices();return this._buildPolygonsFromGeometry(r)}},{key:"_buildPolygonGroups",value:function e(r){var n=r.polygons;var t=[];var i=0;var o=function e(r){r.neighbours.forEach(function(n){if(n.group===undefined){n.group=r.group;e(n)}})};n.forEach(function(e){if(e.group===undefined){e.group=i++;o(e)}if(!t[e.group])t[e.group]=[];t[e.group].push(e)});return t}},{key:"_buildPolygonNeighbours",value:function e(r,n){r.neighbours=[];for(var t=0,i=n.polygons.length;t<i;t++){if(r===n.polygons[t])continue;if(r.centroid.distanceToSquared(n.polygons[t].centroid)>100*100)continue;var u=o.array_intersect(r.vertexIds,n.polygons[t].vertexIds);if(u.length>=2){r.neighbours.push(n.polygons[t])}}}},{key:"_buildPolygonsFromGeometry",value:function e(r){var n=this;var t=[];var i=r.vertices;var o=r.faceVertexUvs;r.faces.forEach(function(e){t.push({id:u++,vertexIds:[e.a,e.b,e.c],centroid:e.centroid,normal:e.normal,neighbours:[]})});var a={polygons:t,vertices:i,faceVertexUvs:o};t.forEach(function(e){n._buildPolygonNeighbours(e,a)});return a}},{key:"_getSharedVerticesInOrder",value:function e(r,n){var t=r.vertexIds;var i=n.vertexIds;var o=[];t.forEach(function(e){if(i.includes(e)){o.push(e)}});if(o.length<2)return[];if(o.includes(t[0])&&o.includes(t[t.length-1])){t.push(t.shift())}if(o.includes(i[0])&&o.includes(i[i.length-1])){i.push(i.shift())}o.length=0;t.forEach(function(e){if(i.includes(e)){o.push(e)}});return o}}]);return e}();r.exports=a},{"./utils":7}],5:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=e("./utils");var u=function(){function e(){i(this,e);this.portals=[]}t(e,[{key:"push",value:function e(r,n){if(n===undefined)n=r;this.portals.push({left:r,right:n})}},{key:"stringPull",value:function e(){var r=this.portals;var n=[];var t=void 0,i=void 0,u=void 0;var a=0,s=0,c=0;t=r[0].left;i=r[0].left;u=r[0].right;n.push(t);for(var f=1;f<r.length;f++){var l=r[f].left;var v=r[f].right;if(o.triarea2(t,u,v)<=0){if(o.vequal(t,u)||o.triarea2(t,i,v)>0){u=v;c=f}else{n.push(i);t=i;a=s;i=t;u=t;s=a;c=a;f=a;continue}}if(o.triarea2(t,i,l)>=0){if(o.vequal(t,i)||o.triarea2(t,u,l)<0){i=l;s=f}else{n.push(u);t=u;a=c;i=t;u=t;s=a;c=a;f=a;continue}}}if(n.length===0||!o.vequal(n[n.length-1],r[r.length-1].left)){n.push(r[r.length-1].left)}this.path=n;return n}}]);return e}();r.exports=u},{"./utils":7}],6:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=e("./utils");var u=e("./AStar");var a=e("./Builder");var s=e("./Channel");var c=function(){function e(){i(this,e);this.zones={}}t(e,[{key:"setZoneData",value:function e(r,n){this.zones[r]=n}},{key:"getGroup",value:function e(r,n){if(!this.zones[r])return null;var t=null;var i=Math.pow(50,2);this.zones[r].groups.forEach(function(e,r){e.forEach(function(e){var u=o.distanceToSquared(e.centroid,n);if(u<i){t=r;i=u}})});return t}},{key:"getRandomNode",value:function e(r,n,t,i){if(!this.zones[r])return new THREE.Vector3;t=t||null;i=i||0;var u=[];var a=this.zones[r].groups[n];a.forEach(function(e){if(t&&i){if(o.distanceToSquared(t,e.centroid)<i*i){u.push(e.centroid)}}else{u.push(e.centroid)}});return o.sample(u)||new THREE.Vector3}},{key:"getClosestNode",value:function e(r,n,t){var i=arguments.length>3&&arguments[3]!==undefined?arguments[3]:false;var u=this.zones[n].groups[t];var a=this.zones[n].vertices;var s=null;var c=Infinity;u.forEach(function(e){var n=o.distanceToSquared(e.centroid,r);if(n<c&&(!i||o.isVectorInPolygon(r,e,a))){s=e;c=n}});return s}},{key:"findPath",value:function e(r,n,t,i){var o=this.zones[t].groups[i];var a=this.zones[t].vertices;var c=this.getClosestNode(r,t,i);var f=this.getClosestNode(n,t,i,true);if(!c||!f){return null}var l=u.search(o,c,f);var v=function e(r,n){for(var t=0;t<r.neighbours.length;t++){if(r.neighbours[t]===n.id){return r.portals[t]}}};var h=new s;h.push(r);for(var d=0;d<l.length;d++){var p=l[d];var g=l[d+1];if(g){var y=v(p,g);h.push(a[y[0]],a[y[1]])}}h.push(n);h.stringPull();var b=h.path.map(function(e){return new THREE.Vector3(e.x,e.y,e.z)});b.shift();return b}}],[{key:"createZone",value:function e(r){return a.buildZone(r)}}]);return e}();c.prototype.clampStep=function(){var e=new THREE.Vector3;var r=new THREE.Plane;var n=new THREE.Triangle;var t=void 0;var i=new THREE.Vector3;var o=void 0;return function(u,a,s,c,f,l){var v=this.zones[c].vertices;var h=this.zones[c].groups[f];var d=[s];var p={};p[s.id]=0;t=undefined;i.set(0,0,0);o=Infinity;r.setFromCoplanarPoints(v[s.vertexIds[0]],v[s.vertexIds[1]],v[s.vertexIds[2]]);r.projectPoint(a,e);a.copy(e);for(var g=d.pop();g;g=d.pop()){n.set(v[g.vertexIds[0]],v[g.vertexIds[1]],v[g.vertexIds[2]]);n.closestPointToPoint(a,e);if(e.distanceToSquared(a)<o){t=g;i.copy(e);o=e.distanceToSquared(a)}var y=p[g];if(y>2)continue;for(var b=0;b<g.neighbours.length;b++){var x=h[g.neighbours[b]];if(x.id in p)continue;d.push(x);p[x.id]=y+1}}l.copy(i);return t}}();var f={};var l={};var v={};r.exports=c},{"./AStar":2,"./Builder":4,"./Channel":5,"./utils":7}],7:[function(e,r,n){"use strict";var t=function(){function e(e,r){for(var n=0;n<r.length;n++){var t=r[n];t.enumerable=t.enumerable||false;t.configurable=true;if("value"in t)t.writable=true;Object.defineProperty(e,t.key,t)}}return function(r,n,t){if(n)e(r.prototype,n);if(t)e(r,t);return r}}();function i(e,r){if(!(e instanceof r)){throw new TypeError("Cannot call a class as a function")}}var o=function(){function e(){i(this,e)}t(e,null,[{key:"computeCentroids",value:function e(r){var n,t,i;for(n=0,t=r.faces.length;n<t;n++){i=r.faces[n];i.centroid=new THREE.Vector3(0,0,0);i.centroid.add(r.vertices[i.a]);i.centroid.add(r.vertices[i.b]);i.centroid.add(r.vertices[i.c]);i.centroid.divideScalar(3)}}},{key:"roundNumber",value:function e(r,n){var t=Number(r+"").toFixed(parseInt(n));return parseFloat(t)}},{key:"sample",value:function e(r){return r[Math.floor(Math.random()*r.length)]}},{key:"mergeVertexIds",value:function e(r,n){var t=[];r.forEach(function(e){if(n.indexOf(e)>=0){t.push(e)}});if(t.length<2)return[];if(t.includes(r[0])&&t.includes(r[r.length-1])){r.push(r.shift())}if(t.includes(n[0])&&t.includes(n[n.length-1])){n.push(n.shift())}t=[];r.forEach(function(e){if(n.includes(e)){t.push(e)}});var i=t[1];var o=t[0];var u=r.slice();while(u[0]!==i){u.push(u.shift())}var a=0;var s=n.slice();while(s[0]!==o){s.push(s.shift());if(a++>10)throw new Error("Unexpected state")}s.shift();s.pop();u=u.concat(s);return u}},{key:"setPolygonCentroid",value:function e(r,n){var t=new THREE.Vector3;var i=n.vertices;r.vertexIds.forEach(function(e){t.add(i[e])});t.divideScalar(r.vertexIds.length);r.centroid.copy(t)}},{key:"cleanPolygon",value:function e(r,n){var t=[];var i=n.vertices;for(var o=0;o<r.vertexIds.length;o++){var u=i[r.vertexIds[o]];var a,s;var c,f;if(o===0){a=r.vertexIds[1];s=r.vertexIds[r.vertexIds.length-1]}else if(o===r.vertexIds.length-1){a=r.vertexIds[0];s=r.vertexIds[r.vertexIds.length-2]}else{a=r.vertexIds[o+1];s=r.vertexIds[o-1]}c=i[a];f=i[s];var l=c.clone().sub(u);var v=f.clone().sub(u);var h=l.angleTo(v);if(h>Math.PI-.01&&h<Math.PI+.01){var d=[];r.neighbours.forEach(function(e){if(!e.vertexIds.includes(r.vertexIds[o])){d.push(e)}});r.neighbours=d}else{t.push(r.vertexIds[o])}}r.vertexIds=t;this.setPolygonCentroid(r,n)}},{key:"isConvex",value:function e(r,n){var t=n.vertices;if(r.vertexIds.length<3)return false;var i=true;var o=0;var u=[];for(var a=0;a<r.vertexIds.length;a++){var s=t[r.vertexIds[a]];var c,f;if(a===0){c=t[r.vertexIds[1]];f=t[r.vertexIds[r.vertexIds.length-1]]}else if(a===r.vertexIds.length-1){c=t[r.vertexIds[0]];f=t[r.vertexIds[r.vertexIds.length-2]]}else{c=t[r.vertexIds[a+1]];f=t[r.vertexIds[a-1]]}var l=c.clone().sub(s);var v=f.clone().sub(s);var h=l.angleTo(v);o+=h;if(h===Math.PI||h===0)return false;var d=l.cross(v).y;u.push(d)}u.forEach(function(e){if(e===0)i=false});if(u[0]>0){u.forEach(function(e){if(e<0)i=false})}else{u.forEach(function(e){if(e>0)i=false})}return i}},{key:"distanceToSquared",value:function e(r,n){var t=r.x-n.x;var i=r.y-n.y;var o=r.z-n.z;return t*t+i*i+o*o}},{key:"isPointInPoly",value:function e(r,n){for(var t=false,i=-1,o=r.length,u=o-1;++i<o;u=i){(r[i].z<=n.z&&n.z<r[u].z||r[u].z<=n.z&&n.z<r[i].z)&&n.x<(r[u].x-r[i].x)*(n.z-r[i].z)/(r[u].z-r[i].z)+r[i].x&&(t=!t)}return t}},{key:"isVectorInPolygon",value:function e(r,n,t){var i=1e5;var o=-1e5;var u=[];n.vertexIds.forEach(function(e){i=Math.min(t[e].y,i);o=Math.max(t[e].y,o);u.push(t[e])});if(r.y<o+.5&&r.y>i-.5&&this.isPointInPoly(u,r)){return true}return false}},{key:"triarea2",value:function e(r,n,t){var i=n.x-r.x;var o=n.z-r.z;var u=t.x-r.x;var a=t.z-r.z;return u*o-i*a}},{key:"vequal",value:function e(r,n){return this.distanceToSquared(r,n)<1e-5}},{key:"array_intersect",value:function e(){var r=void 0,n=void 0,t=void 0,i=void 0,o=void 0,u=[],a={},s=void 0;s=arguments.length-1;t=arguments[0].length;n=0;for(r=0;r<=s;r++){i=arguments[r].length;if(i<t){n=r;t=i}}for(r=0;r<=s;r++){i=r===n?0:r||n;o=arguments[i].length;for(var c=0;c<o;c++){var f=arguments[i][c];if(a[f]===r-1){if(r===s){u.push(f);a[f]=0}else{a[f]=r}}else if(r===0){a[f]=0}}}return u}}]);return e}();r.exports=o},{}]},{},[1]);

2

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

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

16

README.md
# three-pathfinding
Navigation mesh toolkit for ThreeJS, based on [PatrolJS](https://github.com/nickjanssen/PatrolJS).
Navigation mesh toolkit for ThreeJS, based on [PatrolJS](https://github.com/nickjanssen/PatrolJS). Computes paths between points on a 3D nav mesh, supports multiple zones, and clamps movement vectors for FPS controls. To learn how to create a navigation mesh using Blender, see [Creating a Nav Mesh](https://www.donmccurdy.com/2017/08/20/creating-a-nav-mesh-for-a-webvr-scene/).
![screenshot](https://user-images.githubusercontent.com/1848368/34424850-d79e5a24-ebf4-11e7-87c4-afc75cdc41bd.png)
## Quickstart

@@ -28,2 +30,14 @@

### Running the demo locally
```
git clone https://github.com/donmccurdy/three-pathfinding.git
cd three-pathfinding
npm install
npm run dev
```
The demo will start at http://localhost:9966/demo/demo.html.
## API

@@ -30,0 +44,0 @@

5

src/index.js

@@ -223,7 +223,2 @@ /* global THREE */

if (triangle.containsPoint(end)) {
endTarget.copy(end);
return currentNode;
}
triangle.closestPointToPoint(end, point);

@@ -230,0 +225,0 @@

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