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.12.1 to 0.13.0

package-lock.json

2

dist/three-pathfinding.js

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

var e=require("three"),t=function(){};t.roundNumber=function(e,t){var r=Math.pow(10,t);return Math.round(e*r)/r},t.sample=function(e){return e[Math.floor(Math.random()*e.length)]},t.distanceToSquared=function(e,t){var r=e.x-t.x,n=e.y-t.y,o=e.z-t.z;return r*r+n*n+o*o},t.isPointInPoly=function(e,t){for(var r=!1,n=-1,o=e.length,i=o-1;++n<o;i=n)(e[n].z<=t.z&&t.z<e[i].z||e[i].z<=t.z&&t.z<e[n].z)&&t.x<(e[i].x-e[n].x)*(t.z-e[n].z)/(e[i].z-e[n].z)+e[n].x&&(r=!r);return r},t.isVectorInPolygon=function(e,t,r){var n=1e5,o=-1e5,i=[];return t.vertexIds.forEach(function(e){n=Math.min(r[e].y,n),o=Math.max(r[e].y,o),i.push(r[e])}),!!(e.y<o+.5&&e.y>n-.5&&this.isPointInPoly(i,e))},t.triarea2=function(e,t,r){return(r.x-e.x)*(t.z-e.z)-(t.x-e.x)*(r.z-e.z)},t.vequal=function(e,t){return this.distanceToSquared(e,t)<1e-5};var r=function(e){this.content=[],this.scoreFunction=e};r.prototype.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},r.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},r.prototype.remove=function(e){var t=this.content.indexOf(e),r=this.content.pop();t!==this.content.length-1&&(this.content[t]=r,this.scoreFunction(r)<this.scoreFunction(e)?this.sinkDown(t):this.bubbleUp(t))},r.prototype.size=function(){return this.content.length},r.prototype.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},r.prototype.sinkDown=function(e){for(var t=this.content[e];e>0;){var r=(e+1>>1)-1,n=this.content[r];if(!(this.scoreFunction(t)<this.scoreFunction(n)))break;this.content[r]=t,this.content[e]=n,e=r}},r.prototype.bubbleUp=function(e){for(var t=this.content.length,r=this.content[e],n=this.scoreFunction(r);;){var o=e+1<<1,i=o-1,s=null,a=void 0;if(i<t&&(a=this.scoreFunction(this.content[i]))<n&&(s=i),o<t&&this.scoreFunction(this.content[o])<(null===s?n:a)&&(s=o),null===s)break;this.content[e]=this.content[s],this.content[s]=r,e=s}};var n=function(){};n.init=function(e){for(var t=0;t<e.length;t++){var r=e[t];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}},n.cleanUp=function(e){for(var t=0;t<e.length;t++){var r=e[t];delete r.f,delete r.g,delete r.h,delete r.cost,delete r.visited,delete r.closed,delete r.parent}},n.heap=function(){return new r(function(e){return e.f})},n.search=function(e,t,r){this.init(e);var n=this.heap();for(n.push(t);n.size()>0;){var o=n.pop();if(o===r){for(var i=o,s=[];i.parent;)s.push(i),i=i.parent;return this.cleanUp(s),s.reverse()}o.closed=!0;for(var a=this.neighbours(e,o),h=0,c=a.length;h<c;h++){var u=a[h];if(!u.closed){var p=o.g+u.cost,l=u.visited;if(!l||p<u.g){if(u.visited=!0,u.parent=o,!u.centroid||!r.centroid)throw new Error("Unexpected state");u.h=u.h||this.heuristic(u.centroid,r.centroid),u.g=p,u.f=u.g+u.h,l?n.rescoreElement(u):n.push(u)}}}}return[]},n.heuristic=function(e,r){return t.distanceToSquared(e,r)},n.neighbours=function(e,t){for(var r=[],n=0;n<t.neighbours.length;n++)r.push(e[t.neighbours[n]]);return r};var o=function(){};o.buildZone=function(r){var n=this,o=this._buildNavigationMesh(r),i={};o.vertices.forEach(function(e){e.x=t.roundNumber(e.x,2),e.y=t.roundNumber(e.y,2),e.z=t.roundNumber(e.z,2)}),i.vertices=o.vertices;var s=this._buildPolygonGroups(o);return i.groups=new Array(s.length),s.forEach(function(r,o){var s=new Map;r.forEach(function(e,t){s.set(e,t)});var a=new Array(r.length);r.forEach(function(r,o){var h=[];r.neighbours.forEach(function(e){return h.push(s.get(e))});var c=[];r.neighbours.forEach(function(e){return c.push(n._getSharedVerticesInOrder(r,e))});var u=new e.Vector3(0,0,0);u.add(i.vertices[r.vertexIds[0]]),u.add(i.vertices[r.vertexIds[1]]),u.add(i.vertices[r.vertexIds[2]]),u.divideScalar(3),u.x=t.roundNumber(u.x,2),u.y=t.roundNumber(u.y,2),u.z=t.roundNumber(u.z,2),a[o]={id:o,neighbours:h,vertexIds:r.vertexIds,centroid:u,portals:c}}),i.groups[o]=a}),i},o._buildNavigationMesh=function(e){return e.mergeVertices(),this._buildPolygonsFromGeometry(e)},o._buildPolygonGroups=function(e){var t=[],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?t[e.group].push(e):(e.group=t.length,r(e),t.push([e]))}),t},o._buildPolygonNeighbours=function(e,t){var r=new Set,n=t[e.vertexIds[1]],o=t[e.vertexIds[2]];return t[e.vertexIds[0]].forEach(function(t){t!==e&&(n.includes(t)||o.includes(t))&&r.add(t)}),n.forEach(function(t){t!==e&&o.includes(t)&&r.add(t)}),r},o._buildPolygonsFromGeometry=function(e){for(var t=this,r=[],n=e.vertices,o=new Array(n.length),i=0;i<n.length;i++)o[i]=[];return e.faces.forEach(function(e){var t={vertexIds:[e.a,e.b,e.c],neighbours:null};r.push(t),o[e.a].push(t),o[e.b].push(t),o[e.c].push(t)}),r.forEach(function(e){e.neighbours=t._buildPolygonNeighbours(e,o)}),{polygons:r,vertices:n}},o._getSharedVerticesInOrder=function(e,t){var r=e.vertexIds,n=r[0],o=r[1],i=r[2],s=t.vertexIds,a=s.includes(n),h=s.includes(o),c=s.includes(i);return a&&h&&c?Array.from(r):a&&h?[n,o]:h&&c?[o,i]:a&&c?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])};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 e,r,n,o=this.portals,i=[],s=0,a=0,h=0;r=o[0].left,n=o[0].right,i.push(e=o[0].left);for(var c=1;c<o.length;c++){var u=o[c].left,p=o[c].right;if(t.triarea2(e,n,p)<=0){if(!(t.vequal(e,n)||t.triarea2(e,r,p)>0)){i.push(r),r=e=r,n=e,a=s=a,h=s,c=s;continue}n=p,h=c}if(t.triarea2(e,r,u)>=0){if(!(t.vequal(e,r)||t.triarea2(e,n,u)<0)){i.push(n),r=e=n,n=e,a=s=h,h=s,c=s;continue}r=u,a=c}}return 0!==i.length&&t.vequal(i[i.length-1],o[o.length-1].left)||i.push(o[o.length-1].left),this.path=i,i};var s,a=function(){this.zones={}};a.createZone=function(t){return t.isGeometry?console.warn("[three-pathfinding]: Use BufferGeometry, not Geometry, to create zone."):t=(new e.Geometry).fromBufferGeometry(t),o.buildZone(t)},a.prototype.setZoneData=function(e,t){this.zones[e]=t},a.prototype.getRandomNode=function(r,n,o,i){if(!this.zones[r])return new e.Vector3;o=o||null,i=i||0;var s=[];return this.zones[r].groups[n].forEach(function(e){o&&i?t.distanceToSquared(o,e.centroid)<i*i&&s.push(e.centroid):s.push(e.centroid)}),t.sample(s)||new e.Vector3},a.prototype.getClosestNode=function(e,r,n,o){void 0===o&&(o=!1);var i=this.zones[r].vertices,s=null,a=Infinity;return this.zones[r].groups[n].forEach(function(r){var n=t.distanceToSquared(r.centroid,e);n<a&&(!o||t.isVectorInPolygon(e,r,i))&&(s=r,a=n)}),s},a.prototype.findPath=function(t,r,o,s){var a=this.zones[o].groups[s],h=this.zones[o].vertices,c=this.getClosestNode(t,o,s,!0),u=this.getClosestNode(r,o,s,!0);if(!c||!u)return null;var p=n.search(a,c,u),l=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},f=new i;f.push(t);for(var d=0;d<p.length;d++){var v=p[d+1];if(v){var g=l(p[d],v);f.push(h[g[0]],h[g[1]])}}f.push(r),f.stringPull();var y=f.path.map(function(t){return new e.Vector3(t.x,t.y,t.z)});return y.shift(),y},a.prototype.getGroup=(s=new e.Plane,function(e,r,n){if(void 0===n&&(n=!1),!this.zones[e])return null;for(var o=null,i=Math.pow(50,2),a=this.zones[e],h=0;h<a.groups.length;h++)for(var c=0,u=a.groups[h];c<u.length;c+=1){var p=u[c];if(n&&(s.setFromCoplanarPoints(a.vertices[p.vertexIds[0]],a.vertices[p.vertexIds[1]],a.vertices[p.vertexIds[2]]),Math.abs(s.distanceToPoint(r))<.01&&t.isPointInPoly([a.vertices[p.vertexIds[0]],a.vertices[p.vertexIds[1]],a.vertices[p.vertexIds[2]]],r)))return h;var l=t.distanceToSquared(p.centroid,r);l<i&&(o=h,i=l)}return o}),a.prototype.clampStep=function(){var t,r,n=new e.Vector3,o=new e.Plane,i=new e.Triangle,s=new e.Vector3,a=new e.Vector3;return function(e,h,c,u,p,l){var f=this.zones[u].vertices,d=this.zones[u].groups[p],v=[c],g={};g[c.id]=0,t=void 0,a.set(0,0,0),r=Infinity,o.setFromCoplanarPoints(f[c.vertexIds[0]],f[c.vertexIds[1]],f[c.vertexIds[2]]),o.projectPoint(h,n),s.copy(n);for(var y=v.pop();y;y=v.pop()){i.set(f[y.vertexIds[0]],f[y.vertexIds[1]],f[y.vertexIds[2]]),i.closestPointToPoint(s,n),n.distanceToSquared(s)<r&&(t=y,a.copy(n),r=n.distanceToSquared(s));var M=g[y.id];if(!(M>2))for(var b=0;b<y.neighbours.length;b++){var m=d[y.neighbours[b]];m.id in g||(v.push(m),g[m.id]=M+1)}}return l.copy(a),t}}();var h={PLAYER:new e.Color(15631215).convertGammaToLinear(2.2).getHex(),TARGET:new e.Color(14469912).convertGammaToLinear(2.2).getHex(),PATH:new e.Color(41903).convertGammaToLinear(2.2).getHex(),WAYPOINT:new e.Color(41903).convertGammaToLinear(2.2).getHex(),CLAMPED_STEP:new e.Color(14472114).convertGammaToLinear(2.2).getHex(),CLOSEST_NODE:new e.Color(4417387).convertGammaToLinear(2.2).getHex()},c=function(t){function r(){var r=this;t.call(this),this._playerMarker=new e.Mesh(new e.SphereGeometry(.25,32,32),new e.MeshBasicMaterial({color:h.PLAYER})),this._targetMarker=new e.Mesh(new e.BoxGeometry(.3,.3,.3),new e.MeshBasicMaterial({color:h.TARGET})),this._nodeMarker=new e.Mesh(new e.BoxGeometry(.1,.8,.1),new e.MeshBasicMaterial({color:h.CLOSEST_NODE})),this._stepMarker=new e.Mesh(new e.BoxGeometry(.1,1,.1),new e.MeshBasicMaterial({color:h.CLAMPED_STEP})),this._pathMarker=new t,this._pathLineMaterial=new e.LineBasicMaterial({color:h.PATH,linewidth:2}),this._pathPointMaterial=new e.MeshBasicMaterial({color:h.WAYPOINT}),this._pathPointGeometry=new e.SphereBufferGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(function(e){e.visible=!1,r.add(e)})}return t&&(r.__proto__=t),(r.prototype=Object.create(t&&t.prototype)).constructor=r,r.prototype.setPath=function(t){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);t=[this._playerMarker.position].concat(t);for(var r=new e.Geometry,n=0;n<t.length;n++)r.vertices.push(t[n].clone().add(new e.Vector3(0,.2,0)));this._pathMarker.add(new e.Line(r,this._pathLineMaterial));for(var o=0;o<t.length-1;o++){var i=new e.Mesh(this._pathPointGeometry,this._pathPointMaterial);i.position.copy(t[o]),i.position.y+=.2,this._pathMarker.add(i)}return this._pathMarker.visible=!0,this},r.prototype.setPlayerPosition=function(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this},r.prototype.setTargetPosition=function(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this},r.prototype.setNodePosition=function(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this},r.prototype.setStepPosition=function(e){return this._stepMarker.position.copy(e),this._stepMarker.visible=!0,this},r.prototype.reset=function(){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);return this._markers.forEach(function(e){e.visible=!1}),this},r}(e.Object3D);exports.Pathfinding=a,exports.PathfindingHelper=c;
var e=require("three"),t=function(){};t.roundNumber=function(e,t){var r=Math.pow(10,t);return Math.round(e*r)/r},t.sample=function(e){return e[Math.floor(Math.random()*e.length)]},t.distanceToSquared=function(e,t){var r=e.x-t.x,n=e.y-t.y,o=e.z-t.z;return r*r+n*n+o*o},t.isPointInPoly=function(e,t){for(var r=!1,n=-1,o=e.length,i=o-1;++n<o;i=n)(e[n].z<=t.z&&t.z<e[i].z||e[i].z<=t.z&&t.z<e[n].z)&&t.x<(e[i].x-e[n].x)*(t.z-e[n].z)/(e[i].z-e[n].z)+e[n].x&&(r=!r);return r},t.isVectorInPolygon=function(e,t,r){var n=1e5,o=-1e5,i=[];return t.vertexIds.forEach(function(e){n=Math.min(r[e].y,n),o=Math.max(r[e].y,o),i.push(r[e])}),!!(e.y<o+.5&&e.y>n-.5&&this.isPointInPoly(i,e))},t.triarea2=function(e,t,r){return(r.x-e.x)*(t.z-e.z)-(t.x-e.x)*(r.z-e.z)},t.vequal=function(e,t){return this.distanceToSquared(e,t)<1e-5};var r=function(e){this.content=[],this.scoreFunction=e};r.prototype.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},r.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},r.prototype.remove=function(e){var t=this.content.indexOf(e),r=this.content.pop();t!==this.content.length-1&&(this.content[t]=r,this.scoreFunction(r)<this.scoreFunction(e)?this.sinkDown(t):this.bubbleUp(t))},r.prototype.size=function(){return this.content.length},r.prototype.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},r.prototype.sinkDown=function(e){for(var t=this.content[e];e>0;){var r=(e+1>>1)-1,n=this.content[r];if(!(this.scoreFunction(t)<this.scoreFunction(n)))break;this.content[r]=t,this.content[e]=n,e=r}},r.prototype.bubbleUp=function(e){for(var t=this.content.length,r=this.content[e],n=this.scoreFunction(r);;){var o=e+1<<1,i=o-1,s=null,a=void 0;if(i<t)(a=this.scoreFunction(this.content[i]))<n&&(s=i);if(o<t)this.scoreFunction(this.content[o])<(null===s?n:a)&&(s=o);if(null===s)break;this.content[e]=this.content[s],this.content[s]=r,e=s}};var n=function(){};n.init=function(e){for(var t=0;t<e.length;t++){var r=e[t];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}},n.cleanUp=function(e){for(var t=0;t<e.length;t++){var r=e[t];delete r.f,delete r.g,delete r.h,delete r.cost,delete r.visited,delete r.closed,delete r.parent}},n.heap=function(){return new r(function(e){return e.f})},n.search=function(e,t,r){this.init(e);var n=this.heap();for(n.push(t);n.size()>0;){var o=n.pop();if(o===r){for(var i=o,s=[];i.parent;)s.push(i),i=i.parent;return this.cleanUp(s),s.reverse()}o.closed=!0;for(var a=this.neighbours(e,o),h=0,c=a.length;h<c;h++){var u=a[h];if(!u.closed){var p=o.g+u.cost,l=u.visited;if(!l||p<u.g){if(u.visited=!0,u.parent=o,!u.centroid||!r.centroid)throw new Error("Unexpected state");u.h=u.h||this.heuristic(u.centroid,r.centroid),u.g=p,u.f=u.g+u.h,l?n.rescoreElement(u):n.push(u)}}}}return[]},n.heuristic=function(e,r){return t.distanceToSquared(e,r)},n.neighbours=function(e,t){for(var r=[],n=0;n<t.neighbours.length;n++)r.push(e[t.neighbours[n]]);return r};var o=function(){};o.buildZone=function(r){var n=this,o=this._buildNavigationMesh(r),i={};o.vertices.forEach(function(e){e.x=t.roundNumber(e.x,2),e.y=t.roundNumber(e.y,2),e.z=t.roundNumber(e.z,2)}),i.vertices=o.vertices;var s=this._buildPolygonGroups(o);return i.groups=new Array(s.length),s.forEach(function(r,o){var s=new Map;r.forEach(function(e,t){s.set(e,t)});var a=new Array(r.length);r.forEach(function(r,o){var h=[];r.neighbours.forEach(function(e){return h.push(s.get(e))});var c=[];r.neighbours.forEach(function(e){return c.push(n._getSharedVerticesInOrder(r,e))});var u=new e.Vector3(0,0,0);u.add(i.vertices[r.vertexIds[0]]),u.add(i.vertices[r.vertexIds[1]]),u.add(i.vertices[r.vertexIds[2]]),u.divideScalar(3),u.x=t.roundNumber(u.x,2),u.y=t.roundNumber(u.y,2),u.z=t.roundNumber(u.z,2),a[o]={id:o,neighbours:h,vertexIds:r.vertexIds,centroid:u,portals:c}}),i.groups[o]=a}),i},o._buildNavigationMesh=function(e){return e.mergeVertices(),this._buildPolygonsFromGeometry(e)},o._buildPolygonGroups=function(e){var t=[],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?t[e.group].push(e):(e.group=t.length,r(e),t.push([e]))}),t},o._buildPolygonNeighbours=function(e,t){var r=new Set,n=t[e.vertexIds[1]],o=t[e.vertexIds[2]];return t[e.vertexIds[0]].forEach(function(t){t!==e&&(n.includes(t)||o.includes(t))&&r.add(t)}),n.forEach(function(t){t!==e&&o.includes(t)&&r.add(t)}),r},o._buildPolygonsFromGeometry=function(e){for(var t=this,r=[],n=e.vertices,o=new Array(n.length),i=0;i<n.length;i++)o[i]=[];return e.faces.forEach(function(e){var t={vertexIds:[e.a,e.b,e.c],neighbours:null};r.push(t),o[e.a].push(t),o[e.b].push(t),o[e.c].push(t)}),r.forEach(function(e){e.neighbours=t._buildPolygonNeighbours(e,o)}),{polygons:r,vertices:n}},o._getSharedVerticesInOrder=function(e,t){var r=e.vertexIds,n=r[0],o=r[1],i=r[2],s=t.vertexIds,a=s.includes(n),h=s.includes(o),c=s.includes(i);return a&&h&&c?Array.from(r):a&&h?[n,o]:h&&c?[o,i]:a&&c?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])};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 e,r,n,o=this.portals,i=[],s=0,a=0,h=0;r=o[0].left,n=o[0].right,i.push(e=o[0].left);for(var c=1;c<o.length;c++){var u=o[c].left,p=o[c].right;if(t.triarea2(e,n,p)<=0){if(!(t.vequal(e,n)||t.triarea2(e,r,p)>0)){i.push(r),r=e=r,n=e,a=s=a,h=s,c=s;continue}n=p,h=c}if(t.triarea2(e,r,u)>=0){if(!(t.vequal(e,r)||t.triarea2(e,n,u)<0)){i.push(n),r=e=n,n=e,a=s=h,h=s,c=s;continue}r=u,a=c}}return 0!==i.length&&t.vequal(i[i.length-1],o[o.length-1].left)||i.push(o[o.length-1].left),this.path=i,i};var s,a=function(){this.zones={}};a.createZone=function(t){return t.isGeometry?console.warn("[three-pathfinding]: Use BufferGeometry, not Geometry, to create zone."):t=(new e.Geometry).fromBufferGeometry(t),o.buildZone(t)},a.prototype.setZoneData=function(e,t){this.zones[e]=t},a.prototype.getRandomNode=function(r,n,o,i){if(!this.zones[r])return new e.Vector3;o=o||null,i=i||0;var s=[];return this.zones[r].groups[n].forEach(function(e){o&&i?t.distanceToSquared(o,e.centroid)<i*i&&s.push(e.centroid):s.push(e.centroid)}),t.sample(s)||new e.Vector3},a.prototype.getClosestNode=function(e,r,n,o){void 0===o&&(o=!1);var i=this.zones[r].vertices,s=null,a=Infinity;return this.zones[r].groups[n].forEach(function(r){var n=t.distanceToSquared(r.centroid,e);n<a&&(!o||t.isVectorInPolygon(e,r,i))&&(s=r,a=n)}),s},a.prototype.findPath=function(t,r,o,s){var a=this.zones[o].groups[s],h=this.zones[o].vertices,c=this.getClosestNode(t,o,s,!0),u=this.getClosestNode(r,o,s,!0);if(!c||!u)return null;var p=n.search(a,c,u),l=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},f=new i;f.push(t);for(var d=0;d<p.length;d++){var v=p[d+1];if(v){var g=l(p[d],v);f.push(h[g[0]],h[g[1]])}}f.push(r),f.stringPull();var y=f.path.map(function(t){return new e.Vector3(t.x,t.y,t.z)});return y.shift(),y},a.prototype.getGroup=(s=new e.Plane,function(e,r,n){if(void 0===n&&(n=!1),!this.zones[e])return null;for(var o=null,i=Math.pow(50,2),a=this.zones[e],h=0;h<a.groups.length;h++)for(var c=0,u=a.groups[h];c<u.length;c+=1){var p=u[c];if(n&&(s.setFromCoplanarPoints(a.vertices[p.vertexIds[0]],a.vertices[p.vertexIds[1]],a.vertices[p.vertexIds[2]]),Math.abs(s.distanceToPoint(r))<.01&&t.isPointInPoly([a.vertices[p.vertexIds[0]],a.vertices[p.vertexIds[1]],a.vertices[p.vertexIds[2]]],r)))return h;var l=t.distanceToSquared(p.centroid,r);l<i&&(o=h,i=l)}return o}),a.prototype.clampStep=function(){var t,r,n=new e.Vector3,o=new e.Plane,i=new e.Triangle,s=new e.Vector3,a=new e.Vector3;return function(e,h,c,u,p,l){var f=this.zones[u].vertices,d=this.zones[u].groups[p],v=[c],g={};g[c.id]=0,t=void 0,a.set(0,0,0),r=Infinity,o.setFromCoplanarPoints(f[c.vertexIds[0]],f[c.vertexIds[1]],f[c.vertexIds[2]]),o.projectPoint(h,n),s.copy(n);for(var y=v.pop();y;y=v.pop()){i.set(f[y.vertexIds[0]],f[y.vertexIds[1]],f[y.vertexIds[2]]),i.closestPointToPoint(s,n),n.distanceToSquared(s)<r&&(t=y,a.copy(n),r=n.distanceToSquared(s));var M=g[y.id];if(!(M>2))for(var b=0;b<y.neighbours.length;b++){var m=d[y.neighbours[b]];m.id in g||(v.push(m),g[m.id]=M+1)}}return l.copy(a),t}}();var h={PLAYER:new e.Color(15631215).convertGammaToLinear(2.2).getHex(),TARGET:new e.Color(14469912).convertGammaToLinear(2.2).getHex(),PATH:new e.Color(41903).convertGammaToLinear(2.2).getHex(),WAYPOINT:new e.Color(41903).convertGammaToLinear(2.2).getHex(),CLAMPED_STEP:new e.Color(14472114).convertGammaToLinear(2.2).getHex(),CLOSEST_NODE:new e.Color(4417387).convertGammaToLinear(2.2).getHex()},c=function(t){function r(){var r=this;t.call(this),this._playerMarker=new e.Mesh(new e.SphereGeometry(.25,32,32),new e.MeshBasicMaterial({color:h.PLAYER})),this._targetMarker=new e.Mesh(new e.BoxGeometry(.3,.3,.3),new e.MeshBasicMaterial({color:h.TARGET})),this._nodeMarker=new e.Mesh(new e.BoxGeometry(.1,.8,.1),new e.MeshBasicMaterial({color:h.CLOSEST_NODE})),this._stepMarker=new e.Mesh(new e.BoxGeometry(.1,1,.1),new e.MeshBasicMaterial({color:h.CLAMPED_STEP})),this._pathMarker=new t,this._pathLineMaterial=new e.LineBasicMaterial({color:h.PATH,linewidth:2}),this._pathPointMaterial=new e.MeshBasicMaterial({color:h.WAYPOINT}),this._pathPointGeometry=new e.SphereBufferGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(function(e){e.visible=!1,r.add(e)})}return t&&(r.__proto__=t),(r.prototype=Object.create(t&&t.prototype)).constructor=r,r.prototype.setPath=function(t){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);t=[this._playerMarker.position].concat(t);for(var r=new e.Geometry,n=0;n<t.length;n++)r.vertices.push(t[n].clone().add(new e.Vector3(0,.2,0)));this._pathMarker.add(new e.Line(r,this._pathLineMaterial));for(var o=0;o<t.length-1;o++){var i=new e.Mesh(this._pathPointGeometry,this._pathPointMaterial);i.position.copy(t[o]),i.position.y+=.2,this._pathMarker.add(i)}return this._pathMarker.visible=!0,this},r.prototype.setPlayerPosition=function(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this},r.prototype.setTargetPosition=function(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this},r.prototype.setNodePosition=function(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this},r.prototype.setStepPosition=function(e){return this._stepMarker.position.copy(e),this._stepMarker.visible=!0,this},r.prototype.reset=function(){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);return this._markers.forEach(function(e){e.visible=!1}),this},r}(e.Object3D);exports.Pathfinding=a,exports.PathfindingHelper=c;
//# sourceMappingURL=three-pathfinding.js.map

2

dist/three-pathfinding.module.js

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

import{Vector3 as t,Plane as e,Geometry as r,Triangle as n,Color as o,Object3D as i,LineBasicMaterial as s,MeshBasicMaterial as a,SphereBufferGeometry as h,BoxGeometry as u,Mesh as c,SphereGeometry as p,Line as l}from"three";var f=function(){};f.roundNumber=function(t,e){var r=Math.pow(10,e);return Math.round(t*r)/r},f.sample=function(t){return t[Math.floor(Math.random()*t.length)]},f.distanceToSquared=function(t,e){var r=t.x-e.x,n=t.y-e.y,o=t.z-e.z;return r*r+n*n+o*o},f.isPointInPoly=function(t,e){for(var r=!1,n=-1,o=t.length,i=o-1;++n<o;i=n)(t[n].z<=e.z&&e.z<t[i].z||t[i].z<=e.z&&e.z<t[n].z)&&e.x<(t[i].x-t[n].x)*(e.z-t[n].z)/(t[i].z-t[n].z)+t[n].x&&(r=!r);return r},f.isVectorInPolygon=function(t,e,r){var n=1e5,o=-1e5,i=[];return e.vertexIds.forEach(function(t){n=Math.min(r[t].y,n),o=Math.max(r[t].y,o),i.push(r[t])}),!!(t.y<o+.5&&t.y>n-.5&&this.isPointInPoly(i,t))},f.triarea2=function(t,e,r){return(r.x-t.x)*(e.z-t.z)-(e.x-t.x)*(r.z-t.z)},f.vequal=function(t,e){return this.distanceToSquared(t,e)<1e-5};var d=function(t){this.content=[],this.scoreFunction=t};d.prototype.push=function(t){this.content.push(t),this.sinkDown(this.content.length-1)},d.prototype.pop=function(){var t=this.content[0],e=this.content.pop();return this.content.length>0&&(this.content[0]=e,this.bubbleUp(0)),t},d.prototype.remove=function(t){var e=this.content.indexOf(t),r=this.content.pop();e!==this.content.length-1&&(this.content[e]=r,this.scoreFunction(r)<this.scoreFunction(t)?this.sinkDown(e):this.bubbleUp(e))},d.prototype.size=function(){return this.content.length},d.prototype.rescoreElement=function(t){this.sinkDown(this.content.indexOf(t))},d.prototype.sinkDown=function(t){for(var e=this.content[t];t>0;){var r=(t+1>>1)-1,n=this.content[r];if(!(this.scoreFunction(e)<this.scoreFunction(n)))break;this.content[r]=e,this.content[t]=n,t=r}},d.prototype.bubbleUp=function(t){for(var e=this.content.length,r=this.content[t],n=this.scoreFunction(r);;){var o=t+1<<1,i=o-1,s=null,a=void 0;if(i<e&&(a=this.scoreFunction(this.content[i]))<n&&(s=i),o<e&&this.scoreFunction(this.content[o])<(null===s?n:a)&&(s=o),null===s)break;this.content[t]=this.content[s],this.content[s]=r,t=s}};var v=function(){};v.init=function(t){for(var e=0;e<t.length;e++){var r=t[e];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}},v.cleanUp=function(t){for(var e=0;e<t.length;e++){var r=t[e];delete r.f,delete r.g,delete r.h,delete r.cost,delete r.visited,delete r.closed,delete r.parent}},v.heap=function(){return new d(function(t){return t.f})},v.search=function(t,e,r){this.init(t);var n=this.heap();for(n.push(e);n.size()>0;){var o=n.pop();if(o===r){for(var i=o,s=[];i.parent;)s.push(i),i=i.parent;return this.cleanUp(s),s.reverse()}o.closed=!0;for(var a=this.neighbours(t,o),h=0,u=a.length;h<u;h++){var c=a[h];if(!c.closed){var p=o.g+c.cost,l=c.visited;if(!l||p<c.g){if(c.visited=!0,c.parent=o,!c.centroid||!r.centroid)throw new Error("Unexpected state");c.h=c.h||this.heuristic(c.centroid,r.centroid),c.g=p,c.f=c.g+c.h,l?n.rescoreElement(c):n.push(c)}}}}return[]},v.heuristic=function(t,e){return f.distanceToSquared(t,e)},v.neighbours=function(t,e){for(var r=[],n=0;n<e.neighbours.length;n++)r.push(t[e.neighbours[n]]);return r};var g=function(){};g.buildZone=function(e){var r=this,n=this._buildNavigationMesh(e),o={};n.vertices.forEach(function(t){t.x=f.roundNumber(t.x,2),t.y=f.roundNumber(t.y,2),t.z=f.roundNumber(t.z,2)}),o.vertices=n.vertices;var i=this._buildPolygonGroups(n);return o.groups=new Array(i.length),i.forEach(function(e,n){var i=new Map;e.forEach(function(t,e){i.set(t,e)});var s=new Array(e.length);e.forEach(function(e,n){var a=[];e.neighbours.forEach(function(t){return a.push(i.get(t))});var h=[];e.neighbours.forEach(function(t){return h.push(r._getSharedVerticesInOrder(e,t))});var u=new t(0,0,0);u.add(o.vertices[e.vertexIds[0]]),u.add(o.vertices[e.vertexIds[1]]),u.add(o.vertices[e.vertexIds[2]]),u.divideScalar(3),u.x=f.roundNumber(u.x,2),u.y=f.roundNumber(u.y,2),u.z=f.roundNumber(u.z,2),s[n]={id:n,neighbours:a,vertexIds:e.vertexIds,centroid:u,portals:h}}),o.groups[n]=s}),o},g._buildNavigationMesh=function(t){return t.mergeVertices(),this._buildPolygonsFromGeometry(t)},g._buildPolygonGroups=function(t){var e=[],r=function(t){t.neighbours.forEach(function(e){void 0===e.group&&(e.group=t.group,r(e))})};return t.polygons.forEach(function(t){void 0!==t.group?e[t.group].push(t):(t.group=e.length,r(t),e.push([t]))}),e},g._buildPolygonNeighbours=function(t,e){var r=new Set,n=e[t.vertexIds[1]],o=e[t.vertexIds[2]];return e[t.vertexIds[0]].forEach(function(e){e!==t&&(n.includes(e)||o.includes(e))&&r.add(e)}),n.forEach(function(e){e!==t&&o.includes(e)&&r.add(e)}),r},g._buildPolygonsFromGeometry=function(t){for(var e=this,r=[],n=t.vertices,o=new Array(n.length),i=0;i<n.length;i++)o[i]=[];return t.faces.forEach(function(t){var e={vertexIds:[t.a,t.b,t.c],neighbours:null};r.push(e),o[t.a].push(e),o[t.b].push(e),o[t.c].push(e)}),r.forEach(function(t){t.neighbours=e._buildPolygonNeighbours(t,o)}),{polygons:r,vertices:n}},g._getSharedVerticesInOrder=function(t,e){var r=t.vertexIds,n=r[0],o=r[1],i=r[2],s=e.vertexIds,a=s.includes(n),h=s.includes(o),u=s.includes(i);return a&&h&&u?Array.from(r):a&&h?[n,o]:h&&u?[o,i]:a&&u?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])};var y=function(){this.portals=[]};y.prototype.push=function(t,e){void 0===e&&(e=t),this.portals.push({left:t,right:e})},y.prototype.stringPull=function(){var t,e,r,n=this.portals,o=[],i=0,s=0,a=0;e=n[0].left,r=n[0].right,o.push(t=n[0].left);for(var h=1;h<n.length;h++){var u=n[h].left,c=n[h].right;if(f.triarea2(t,r,c)<=0){if(!(f.vequal(t,r)||f.triarea2(t,e,c)>0)){o.push(e),e=t=e,r=t,s=i=s,a=i,h=i;continue}r=c,a=h}if(f.triarea2(t,e,u)>=0){if(!(f.vequal(t,e)||f.triarea2(t,r,u)<0)){o.push(r),e=t=r,r=t,s=i=a,a=i,h=i;continue}e=u,s=h}}return 0!==o.length&&f.vequal(o[o.length-1],n[n.length-1].left)||o.push(n[n.length-1].left),this.path=o,o};var b,_=function(){this.zones={}};_.createZone=function(t){return t.isGeometry?console.warn("[three-pathfinding]: Use BufferGeometry, not Geometry, to create zone."):t=(new r).fromBufferGeometry(t),g.buildZone(t)},_.prototype.setZoneData=function(t,e){this.zones[t]=e},_.prototype.getRandomNode=function(e,r,n,o){if(!this.zones[e])return new t;n=n||null,o=o||0;var i=[];return this.zones[e].groups[r].forEach(function(t){n&&o?f.distanceToSquared(n,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),f.sample(i)||new t},_.prototype.getClosestNode=function(t,e,r,n){void 0===n&&(n=!1);var o=this.zones[e].vertices,i=null,s=Infinity;return this.zones[e].groups[r].forEach(function(e){var r=f.distanceToSquared(e.centroid,t);r<s&&(!n||f.isVectorInPolygon(t,e,o))&&(i=e,s=r)}),i},_.prototype.findPath=function(e,r,n,o){var i=this.zones[n].groups[o],s=this.zones[n].vertices,a=this.getClosestNode(e,n,o,!0),h=this.getClosestNode(r,n,o,!0);if(!a||!h)return null;var u=v.search(i,a,h),c=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},p=new y;p.push(e);for(var l=0;l<u.length;l++){var f=u[l+1];if(f){var d=c(u[l],f);p.push(s[d[0]],s[d[1]])}}p.push(r),p.stringPull();var g=p.path.map(function(e){return new t(e.x,e.y,e.z)});return g.shift(),g},_.prototype.getGroup=(b=new e,function(t,e,r){if(void 0===r&&(r=!1),!this.zones[t])return null;for(var n=null,o=Math.pow(50,2),i=this.zones[t],s=0;s<i.groups.length;s++)for(var a=0,h=i.groups[s];a<h.length;a+=1){var u=h[a];if(r&&(b.setFromCoplanarPoints(i.vertices[u.vertexIds[0]],i.vertices[u.vertexIds[1]],i.vertices[u.vertexIds[2]]),Math.abs(b.distanceToPoint(e))<.01&&f.isPointInPoly([i.vertices[u.vertexIds[0]],i.vertices[u.vertexIds[1]],i.vertices[u.vertexIds[2]]],e)))return s;var c=f.distanceToSquared(u.centroid,e);c<o&&(n=s,o=c)}return n}),_.prototype.clampStep=function(){var r,o,i=new t,s=new e,a=new n,h=new t,u=new t;return function(t,e,n,c,p,l){var f=this.zones[c].vertices,d=this.zones[c].groups[p],v=[n],g={};g[n.id]=0,r=void 0,u.set(0,0,0),o=Infinity,s.setFromCoplanarPoints(f[n.vertexIds[0]],f[n.vertexIds[1]],f[n.vertexIds[2]]),s.projectPoint(e,i),h.copy(i);for(var y=v.pop();y;y=v.pop()){a.set(f[y.vertexIds[0]],f[y.vertexIds[1]],f[y.vertexIds[2]]),a.closestPointToPoint(h,i),i.distanceToSquared(h)<o&&(r=y,u.copy(i),o=i.distanceToSquared(h));var b=g[y.id];if(!(b>2))for(var _=0;_<y.neighbours.length;_++){var w=d[y.neighbours[_]];w.id in g||(v.push(w),g[w.id]=b+1)}}return l.copy(u),r}}();var w={PLAYER:new o(15631215).convertGammaToLinear(2.2).getHex(),TARGET:new o(14469912).convertGammaToLinear(2.2).getHex(),PATH:new o(41903).convertGammaToLinear(2.2).getHex(),WAYPOINT:new o(41903).convertGammaToLinear(2.2).getHex(),CLAMPED_STEP:new o(14472114).convertGammaToLinear(2.2).getHex(),CLOSEST_NODE:new o(4417387).convertGammaToLinear(2.2).getHex()},m=function(e){function n(){var t=this;e.call(this),this._playerMarker=new c(new p(.25,32,32),new a({color:w.PLAYER})),this._targetMarker=new c(new u(.3,.3,.3),new a({color:w.TARGET})),this._nodeMarker=new c(new u(.1,.8,.1),new a({color:w.CLOSEST_NODE})),this._stepMarker=new c(new u(.1,1,.1),new a({color:w.CLAMPED_STEP})),this._pathMarker=new e,this._pathLineMaterial=new s({color:w.PATH,linewidth:2}),this._pathPointMaterial=new a({color:w.WAYPOINT}),this._pathPointGeometry=new h(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(function(e){e.visible=!1,t.add(e)})}return e&&(n.__proto__=e),(n.prototype=Object.create(e&&e.prototype)).constructor=n,n.prototype.setPath=function(e){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);e=[this._playerMarker.position].concat(e);for(var n=new r,o=0;o<e.length;o++)n.vertices.push(e[o].clone().add(new t(0,.2,0)));this._pathMarker.add(new l(n,this._pathLineMaterial));for(var i=0;i<e.length-1;i++){var s=new c(this._pathPointGeometry,this._pathPointMaterial);s.position.copy(e[i]),s.position.y+=.2,this._pathMarker.add(s)}return this._pathMarker.visible=!0,this},n.prototype.setPlayerPosition=function(t){return this._playerMarker.position.copy(t),this._playerMarker.visible=!0,this},n.prototype.setTargetPosition=function(t){return this._targetMarker.position.copy(t),this._targetMarker.visible=!0,this},n.prototype.setNodePosition=function(t){return this._nodeMarker.position.copy(t),this._nodeMarker.visible=!0,this},n.prototype.setStepPosition=function(t){return this._stepMarker.position.copy(t),this._stepMarker.visible=!0,this},n.prototype.reset=function(){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);return this._markers.forEach(function(t){t.visible=!1}),this},n}(i);export{_ as Pathfinding,m as PathfindingHelper};
import{Vector3 as t,Plane as e,Geometry as r,Triangle as n,Color as o,Object3D as i,LineBasicMaterial as s,MeshBasicMaterial as a,SphereBufferGeometry as h,BoxGeometry as u,Mesh as c,SphereGeometry as p,Line as l}from"three";var f=function(){};f.roundNumber=function(t,e){var r=Math.pow(10,e);return Math.round(t*r)/r},f.sample=function(t){return t[Math.floor(Math.random()*t.length)]},f.distanceToSquared=function(t,e){var r=t.x-e.x,n=t.y-e.y,o=t.z-e.z;return r*r+n*n+o*o},f.isPointInPoly=function(t,e){for(var r=!1,n=-1,o=t.length,i=o-1;++n<o;i=n)(t[n].z<=e.z&&e.z<t[i].z||t[i].z<=e.z&&e.z<t[n].z)&&e.x<(t[i].x-t[n].x)*(e.z-t[n].z)/(t[i].z-t[n].z)+t[n].x&&(r=!r);return r},f.isVectorInPolygon=function(t,e,r){var n=1e5,o=-1e5,i=[];return e.vertexIds.forEach(function(t){n=Math.min(r[t].y,n),o=Math.max(r[t].y,o),i.push(r[t])}),!!(t.y<o+.5&&t.y>n-.5&&this.isPointInPoly(i,t))},f.triarea2=function(t,e,r){return(r.x-t.x)*(e.z-t.z)-(e.x-t.x)*(r.z-t.z)},f.vequal=function(t,e){return this.distanceToSquared(t,e)<1e-5};var d=function(t){this.content=[],this.scoreFunction=t};d.prototype.push=function(t){this.content.push(t),this.sinkDown(this.content.length-1)},d.prototype.pop=function(){var t=this.content[0],e=this.content.pop();return this.content.length>0&&(this.content[0]=e,this.bubbleUp(0)),t},d.prototype.remove=function(t){var e=this.content.indexOf(t),r=this.content.pop();e!==this.content.length-1&&(this.content[e]=r,this.scoreFunction(r)<this.scoreFunction(t)?this.sinkDown(e):this.bubbleUp(e))},d.prototype.size=function(){return this.content.length},d.prototype.rescoreElement=function(t){this.sinkDown(this.content.indexOf(t))},d.prototype.sinkDown=function(t){for(var e=this.content[t];t>0;){var r=(t+1>>1)-1,n=this.content[r];if(!(this.scoreFunction(e)<this.scoreFunction(n)))break;this.content[r]=e,this.content[t]=n,t=r}},d.prototype.bubbleUp=function(t){for(var e=this.content.length,r=this.content[t],n=this.scoreFunction(r);;){var o=t+1<<1,i=o-1,s=null,a=void 0;if(i<e)(a=this.scoreFunction(this.content[i]))<n&&(s=i);if(o<e)this.scoreFunction(this.content[o])<(null===s?n:a)&&(s=o);if(null===s)break;this.content[t]=this.content[s],this.content[s]=r,t=s}};var v=function(){};v.init=function(t){for(var e=0;e<t.length;e++){var r=t[e];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}},v.cleanUp=function(t){for(var e=0;e<t.length;e++){var r=t[e];delete r.f,delete r.g,delete r.h,delete r.cost,delete r.visited,delete r.closed,delete r.parent}},v.heap=function(){return new d(function(t){return t.f})},v.search=function(t,e,r){this.init(t);var n=this.heap();for(n.push(e);n.size()>0;){var o=n.pop();if(o===r){for(var i=o,s=[];i.parent;)s.push(i),i=i.parent;return this.cleanUp(s),s.reverse()}o.closed=!0;for(var a=this.neighbours(t,o),h=0,u=a.length;h<u;h++){var c=a[h];if(!c.closed){var p=o.g+c.cost,l=c.visited;if(!l||p<c.g){if(c.visited=!0,c.parent=o,!c.centroid||!r.centroid)throw new Error("Unexpected state");c.h=c.h||this.heuristic(c.centroid,r.centroid),c.g=p,c.f=c.g+c.h,l?n.rescoreElement(c):n.push(c)}}}}return[]},v.heuristic=function(t,e){return f.distanceToSquared(t,e)},v.neighbours=function(t,e){for(var r=[],n=0;n<e.neighbours.length;n++)r.push(t[e.neighbours[n]]);return r};var g=function(){};g.buildZone=function(e){var r=this,n=this._buildNavigationMesh(e),o={};n.vertices.forEach(function(t){t.x=f.roundNumber(t.x,2),t.y=f.roundNumber(t.y,2),t.z=f.roundNumber(t.z,2)}),o.vertices=n.vertices;var i=this._buildPolygonGroups(n);return o.groups=new Array(i.length),i.forEach(function(e,n){var i=new Map;e.forEach(function(t,e){i.set(t,e)});var s=new Array(e.length);e.forEach(function(e,n){var a=[];e.neighbours.forEach(function(t){return a.push(i.get(t))});var h=[];e.neighbours.forEach(function(t){return h.push(r._getSharedVerticesInOrder(e,t))});var u=new t(0,0,0);u.add(o.vertices[e.vertexIds[0]]),u.add(o.vertices[e.vertexIds[1]]),u.add(o.vertices[e.vertexIds[2]]),u.divideScalar(3),u.x=f.roundNumber(u.x,2),u.y=f.roundNumber(u.y,2),u.z=f.roundNumber(u.z,2),s[n]={id:n,neighbours:a,vertexIds:e.vertexIds,centroid:u,portals:h}}),o.groups[n]=s}),o},g._buildNavigationMesh=function(t){return t.mergeVertices(),this._buildPolygonsFromGeometry(t)},g._buildPolygonGroups=function(t){var e=[],r=function(t){t.neighbours.forEach(function(e){void 0===e.group&&(e.group=t.group,r(e))})};return t.polygons.forEach(function(t){void 0!==t.group?e[t.group].push(t):(t.group=e.length,r(t),e.push([t]))}),e},g._buildPolygonNeighbours=function(t,e){var r=new Set,n=e[t.vertexIds[1]],o=e[t.vertexIds[2]];return e[t.vertexIds[0]].forEach(function(e){e!==t&&(n.includes(e)||o.includes(e))&&r.add(e)}),n.forEach(function(e){e!==t&&o.includes(e)&&r.add(e)}),r},g._buildPolygonsFromGeometry=function(t){for(var e=this,r=[],n=t.vertices,o=new Array(n.length),i=0;i<n.length;i++)o[i]=[];return t.faces.forEach(function(t){var e={vertexIds:[t.a,t.b,t.c],neighbours:null};r.push(e),o[t.a].push(e),o[t.b].push(e),o[t.c].push(e)}),r.forEach(function(t){t.neighbours=e._buildPolygonNeighbours(t,o)}),{polygons:r,vertices:n}},g._getSharedVerticesInOrder=function(t,e){var r=t.vertexIds,n=r[0],o=r[1],i=r[2],s=e.vertexIds,a=s.includes(n),h=s.includes(o),u=s.includes(i);return a&&h&&u?Array.from(r):a&&h?[n,o]:h&&u?[o,i]:a&&u?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])};var y=function(){this.portals=[]};y.prototype.push=function(t,e){void 0===e&&(e=t),this.portals.push({left:t,right:e})},y.prototype.stringPull=function(){var t,e,r,n=this.portals,o=[],i=0,s=0,a=0;e=n[0].left,r=n[0].right,o.push(t=n[0].left);for(var h=1;h<n.length;h++){var u=n[h].left,c=n[h].right;if(f.triarea2(t,r,c)<=0){if(!(f.vequal(t,r)||f.triarea2(t,e,c)>0)){o.push(e),e=t=e,r=t,s=i=s,a=i,h=i;continue}r=c,a=h}if(f.triarea2(t,e,u)>=0){if(!(f.vequal(t,e)||f.triarea2(t,r,u)<0)){o.push(r),e=t=r,r=t,s=i=a,a=i,h=i;continue}e=u,s=h}}return 0!==o.length&&f.vequal(o[o.length-1],n[n.length-1].left)||o.push(n[n.length-1].left),this.path=o,o};var b,_=function(){this.zones={}};_.createZone=function(t){return t.isGeometry?console.warn("[three-pathfinding]: Use BufferGeometry, not Geometry, to create zone."):t=(new r).fromBufferGeometry(t),g.buildZone(t)},_.prototype.setZoneData=function(t,e){this.zones[t]=e},_.prototype.getRandomNode=function(e,r,n,o){if(!this.zones[e])return new t;n=n||null,o=o||0;var i=[];return this.zones[e].groups[r].forEach(function(t){n&&o?f.distanceToSquared(n,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),f.sample(i)||new t},_.prototype.getClosestNode=function(t,e,r,n){void 0===n&&(n=!1);var o=this.zones[e].vertices,i=null,s=Infinity;return this.zones[e].groups[r].forEach(function(e){var r=f.distanceToSquared(e.centroid,t);r<s&&(!n||f.isVectorInPolygon(t,e,o))&&(i=e,s=r)}),i},_.prototype.findPath=function(e,r,n,o){var i=this.zones[n].groups[o],s=this.zones[n].vertices,a=this.getClosestNode(e,n,o,!0),h=this.getClosestNode(r,n,o,!0);if(!a||!h)return null;var u=v.search(i,a,h),c=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},p=new y;p.push(e);for(var l=0;l<u.length;l++){var f=u[l+1];if(f){var d=c(u[l],f);p.push(s[d[0]],s[d[1]])}}p.push(r),p.stringPull();var g=p.path.map(function(e){return new t(e.x,e.y,e.z)});return g.shift(),g},_.prototype.getGroup=(b=new e,function(t,e,r){if(void 0===r&&(r=!1),!this.zones[t])return null;for(var n=null,o=Math.pow(50,2),i=this.zones[t],s=0;s<i.groups.length;s++)for(var a=0,h=i.groups[s];a<h.length;a+=1){var u=h[a];if(r&&(b.setFromCoplanarPoints(i.vertices[u.vertexIds[0]],i.vertices[u.vertexIds[1]],i.vertices[u.vertexIds[2]]),Math.abs(b.distanceToPoint(e))<.01&&f.isPointInPoly([i.vertices[u.vertexIds[0]],i.vertices[u.vertexIds[1]],i.vertices[u.vertexIds[2]]],e)))return s;var c=f.distanceToSquared(u.centroid,e);c<o&&(n=s,o=c)}return n}),_.prototype.clampStep=function(){var r,o,i=new t,s=new e,a=new n,h=new t,u=new t;return function(t,e,n,c,p,l){var f=this.zones[c].vertices,d=this.zones[c].groups[p],v=[n],g={};g[n.id]=0,r=void 0,u.set(0,0,0),o=Infinity,s.setFromCoplanarPoints(f[n.vertexIds[0]],f[n.vertexIds[1]],f[n.vertexIds[2]]),s.projectPoint(e,i),h.copy(i);for(var y=v.pop();y;y=v.pop()){a.set(f[y.vertexIds[0]],f[y.vertexIds[1]],f[y.vertexIds[2]]),a.closestPointToPoint(h,i),i.distanceToSquared(h)<o&&(r=y,u.copy(i),o=i.distanceToSquared(h));var b=g[y.id];if(!(b>2))for(var _=0;_<y.neighbours.length;_++){var w=d[y.neighbours[_]];w.id in g||(v.push(w),g[w.id]=b+1)}}return l.copy(u),r}}();var w={PLAYER:new o(15631215).convertGammaToLinear(2.2).getHex(),TARGET:new o(14469912).convertGammaToLinear(2.2).getHex(),PATH:new o(41903).convertGammaToLinear(2.2).getHex(),WAYPOINT:new o(41903).convertGammaToLinear(2.2).getHex(),CLAMPED_STEP:new o(14472114).convertGammaToLinear(2.2).getHex(),CLOSEST_NODE:new o(4417387).convertGammaToLinear(2.2).getHex()},m=function(e){function n(){var t=this;e.call(this),this._playerMarker=new c(new p(.25,32,32),new a({color:w.PLAYER})),this._targetMarker=new c(new u(.3,.3,.3),new a({color:w.TARGET})),this._nodeMarker=new c(new u(.1,.8,.1),new a({color:w.CLOSEST_NODE})),this._stepMarker=new c(new u(.1,1,.1),new a({color:w.CLAMPED_STEP})),this._pathMarker=new e,this._pathLineMaterial=new s({color:w.PATH,linewidth:2}),this._pathPointMaterial=new a({color:w.WAYPOINT}),this._pathPointGeometry=new h(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(function(e){e.visible=!1,t.add(e)})}return e&&(n.__proto__=e),(n.prototype=Object.create(e&&e.prototype)).constructor=n,n.prototype.setPath=function(e){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);e=[this._playerMarker.position].concat(e);for(var n=new r,o=0;o<e.length;o++)n.vertices.push(e[o].clone().add(new t(0,.2,0)));this._pathMarker.add(new l(n,this._pathLineMaterial));for(var i=0;i<e.length-1;i++){var s=new c(this._pathPointGeometry,this._pathPointMaterial);s.position.copy(e[i]),s.position.y+=.2,this._pathMarker.add(s)}return this._pathMarker.visible=!0,this},n.prototype.setPlayerPosition=function(t){return this._playerMarker.position.copy(t),this._playerMarker.visible=!0,this},n.prototype.setTargetPosition=function(t){return this._targetMarker.position.copy(t),this._targetMarker.visible=!0,this},n.prototype.setNodePosition=function(t){return this._nodeMarker.position.copy(t),this._nodeMarker.visible=!0,this},n.prototype.setStepPosition=function(t){return this._stepMarker.position.copy(t),this._stepMarker.visible=!0,this},n.prototype.reset=function(){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);return this._markers.forEach(function(t){t.visible=!1}),this},n}(i);export{_ as Pathfinding,m as PathfindingHelper};
//# sourceMappingURL=three-pathfinding.module.js.map

2

dist/three-pathfinding.umd.js

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

!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("three")):"function"==typeof define&&define.amd?define(["exports","three"],t):t(e.threePathfinding={},e.THREE)}(this,function(e,t){var r=function(){};r.roundNumber=function(e,t){var r=Math.pow(10,t);return Math.round(e*r)/r},r.sample=function(e){return e[Math.floor(Math.random()*e.length)]},r.distanceToSquared=function(e,t){var r=e.x-t.x,n=e.y-t.y,o=e.z-t.z;return r*r+n*n+o*o},r.isPointInPoly=function(e,t){for(var r=!1,n=-1,o=e.length,i=o-1;++n<o;i=n)(e[n].z<=t.z&&t.z<e[i].z||e[i].z<=t.z&&t.z<e[n].z)&&t.x<(e[i].x-e[n].x)*(t.z-e[n].z)/(e[i].z-e[n].z)+e[n].x&&(r=!r);return r},r.isVectorInPolygon=function(e,t,r){var n=1e5,o=-1e5,i=[];return t.vertexIds.forEach(function(e){n=Math.min(r[e].y,n),o=Math.max(r[e].y,o),i.push(r[e])}),!!(e.y<o+.5&&e.y>n-.5&&this.isPointInPoly(i,e))},r.triarea2=function(e,t,r){return(r.x-e.x)*(t.z-e.z)-(t.x-e.x)*(r.z-e.z)},r.vequal=function(e,t){return this.distanceToSquared(e,t)<1e-5};var n=function(e){this.content=[],this.scoreFunction=e};n.prototype.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},n.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},n.prototype.remove=function(e){var t=this.content.indexOf(e),r=this.content.pop();t!==this.content.length-1&&(this.content[t]=r,this.scoreFunction(r)<this.scoreFunction(e)?this.sinkDown(t):this.bubbleUp(t))},n.prototype.size=function(){return this.content.length},n.prototype.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},n.prototype.sinkDown=function(e){for(var t=this.content[e];e>0;){var r=(e+1>>1)-1,n=this.content[r];if(!(this.scoreFunction(t)<this.scoreFunction(n)))break;this.content[r]=t,this.content[e]=n,e=r}},n.prototype.bubbleUp=function(e){for(var t=this.content.length,r=this.content[e],n=this.scoreFunction(r);;){var o=e+1<<1,i=o-1,s=null,a=void 0;if(i<t&&(a=this.scoreFunction(this.content[i]))<n&&(s=i),o<t&&this.scoreFunction(this.content[o])<(null===s?n:a)&&(s=o),null===s)break;this.content[e]=this.content[s],this.content[s]=r,e=s}};var o=function(){};o.init=function(e){for(var t=0;t<e.length;t++){var r=e[t];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}},o.cleanUp=function(e){for(var t=0;t<e.length;t++){var r=e[t];delete r.f,delete r.g,delete r.h,delete r.cost,delete r.visited,delete r.closed,delete r.parent}},o.heap=function(){return new n(function(e){return e.f})},o.search=function(e,t,r){this.init(e);var n=this.heap();for(n.push(t);n.size()>0;){var o=n.pop();if(o===r){for(var i=o,s=[];i.parent;)s.push(i),i=i.parent;return this.cleanUp(s),s.reverse()}o.closed=!0;for(var a=this.neighbours(e,o),h=0,c=a.length;h<c;h++){var u=a[h];if(!u.closed){var p=o.g+u.cost,l=u.visited;if(!l||p<u.g){if(u.visited=!0,u.parent=o,!u.centroid||!r.centroid)throw new Error("Unexpected state");u.h=u.h||this.heuristic(u.centroid,r.centroid),u.g=p,u.f=u.g+u.h,l?n.rescoreElement(u):n.push(u)}}}}return[]},o.heuristic=function(e,t){return r.distanceToSquared(e,t)},o.neighbours=function(e,t){for(var r=[],n=0;n<t.neighbours.length;n++)r.push(e[t.neighbours[n]]);return r};var i=function(){};i.buildZone=function(e){var n=this,o=this._buildNavigationMesh(e),i={};o.vertices.forEach(function(e){e.x=r.roundNumber(e.x,2),e.y=r.roundNumber(e.y,2),e.z=r.roundNumber(e.z,2)}),i.vertices=o.vertices;var s=this._buildPolygonGroups(o);return i.groups=new Array(s.length),s.forEach(function(e,o){var s=new Map;e.forEach(function(e,t){s.set(e,t)});var a=new Array(e.length);e.forEach(function(e,o){var h=[];e.neighbours.forEach(function(e){return h.push(s.get(e))});var c=[];e.neighbours.forEach(function(t){return c.push(n._getSharedVerticesInOrder(e,t))});var u=new t.Vector3(0,0,0);u.add(i.vertices[e.vertexIds[0]]),u.add(i.vertices[e.vertexIds[1]]),u.add(i.vertices[e.vertexIds[2]]),u.divideScalar(3),u.x=r.roundNumber(u.x,2),u.y=r.roundNumber(u.y,2),u.z=r.roundNumber(u.z,2),a[o]={id:o,neighbours:h,vertexIds:e.vertexIds,centroid:u,portals:c}}),i.groups[o]=a}),i},i._buildNavigationMesh=function(e){return e.mergeVertices(),this._buildPolygonsFromGeometry(e)},i._buildPolygonGroups=function(e){var t=[],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?t[e.group].push(e):(e.group=t.length,r(e),t.push([e]))}),t},i._buildPolygonNeighbours=function(e,t){var r=new Set,n=t[e.vertexIds[1]],o=t[e.vertexIds[2]];return t[e.vertexIds[0]].forEach(function(t){t!==e&&(n.includes(t)||o.includes(t))&&r.add(t)}),n.forEach(function(t){t!==e&&o.includes(t)&&r.add(t)}),r},i._buildPolygonsFromGeometry=function(e){for(var t=this,r=[],n=e.vertices,o=new Array(n.length),i=0;i<n.length;i++)o[i]=[];return e.faces.forEach(function(e){var t={vertexIds:[e.a,e.b,e.c],neighbours:null};r.push(t),o[e.a].push(t),o[e.b].push(t),o[e.c].push(t)}),r.forEach(function(e){e.neighbours=t._buildPolygonNeighbours(e,o)}),{polygons:r,vertices:n}},i._getSharedVerticesInOrder=function(e,t){var r=e.vertexIds,n=r[0],o=r[1],i=r[2],s=t.vertexIds,a=s.includes(n),h=s.includes(o),c=s.includes(i);return a&&h&&c?Array.from(r):a&&h?[n,o]:h&&c?[o,i]:a&&c?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])};var s=function(){this.portals=[]};s.prototype.push=function(e,t){void 0===t&&(t=e),this.portals.push({left:e,right:t})},s.prototype.stringPull=function(){var e,t,n,o=this.portals,i=[],s=0,a=0,h=0;t=o[0].left,n=o[0].right,i.push(e=o[0].left);for(var c=1;c<o.length;c++){var u=o[c].left,p=o[c].right;if(r.triarea2(e,n,p)<=0){if(!(r.vequal(e,n)||r.triarea2(e,t,p)>0)){i.push(t),t=e=t,n=e,a=s=a,h=s,c=s;continue}n=p,h=c}if(r.triarea2(e,t,u)>=0){if(!(r.vequal(e,t)||r.triarea2(e,n,u)<0)){i.push(n),t=e=n,n=e,a=s=h,h=s,c=s;continue}t=u,a=c}}return 0!==i.length&&r.vequal(i[i.length-1],o[o.length-1].left)||i.push(o[o.length-1].left),this.path=i,i};var a,h=function(){this.zones={}};h.createZone=function(e){return e.isGeometry?console.warn("[three-pathfinding]: Use BufferGeometry, not Geometry, to create zone."):e=(new t.Geometry).fromBufferGeometry(e),i.buildZone(e)},h.prototype.setZoneData=function(e,t){this.zones[e]=t},h.prototype.getRandomNode=function(e,n,o,i){if(!this.zones[e])return new t.Vector3;o=o||null,i=i||0;var s=[];return this.zones[e].groups[n].forEach(function(e){o&&i?r.distanceToSquared(o,e.centroid)<i*i&&s.push(e.centroid):s.push(e.centroid)}),r.sample(s)||new t.Vector3},h.prototype.getClosestNode=function(e,t,n,o){void 0===o&&(o=!1);var i=this.zones[t].vertices,s=null,a=Infinity;return this.zones[t].groups[n].forEach(function(t){var n=r.distanceToSquared(t.centroid,e);n<a&&(!o||r.isVectorInPolygon(e,t,i))&&(s=t,a=n)}),s},h.prototype.findPath=function(e,r,n,i){var a=this.zones[n].groups[i],h=this.zones[n].vertices,c=this.getClosestNode(e,n,i,!0),u=this.getClosestNode(r,n,i,!0);if(!c||!u)return null;var p=o.search(a,c,u),l=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},f=new s;f.push(e);for(var d=0;d<p.length;d++){var v=p[d+1];if(v){var g=l(p[d],v);f.push(h[g[0]],h[g[1]])}}f.push(r),f.stringPull();var y=f.path.map(function(e){return new t.Vector3(e.x,e.y,e.z)});return y.shift(),y},h.prototype.getGroup=(a=new t.Plane,function(e,t,n){if(void 0===n&&(n=!1),!this.zones[e])return null;for(var o=null,i=Math.pow(50,2),s=this.zones[e],h=0;h<s.groups.length;h++)for(var c=0,u=s.groups[h];c<u.length;c+=1){var p=u[c];if(n&&(a.setFromCoplanarPoints(s.vertices[p.vertexIds[0]],s.vertices[p.vertexIds[1]],s.vertices[p.vertexIds[2]]),Math.abs(a.distanceToPoint(t))<.01&&r.isPointInPoly([s.vertices[p.vertexIds[0]],s.vertices[p.vertexIds[1]],s.vertices[p.vertexIds[2]]],t)))return h;var l=r.distanceToSquared(p.centroid,t);l<i&&(o=h,i=l)}return o}),h.prototype.clampStep=function(){var e,r,n=new t.Vector3,o=new t.Plane,i=new t.Triangle,s=new t.Vector3,a=new t.Vector3;return function(t,h,c,u,p,l){var f=this.zones[u].vertices,d=this.zones[u].groups[p],v=[c],g={};g[c.id]=0,e=void 0,a.set(0,0,0),r=Infinity,o.setFromCoplanarPoints(f[c.vertexIds[0]],f[c.vertexIds[1]],f[c.vertexIds[2]]),o.projectPoint(h,n),s.copy(n);for(var y=v.pop();y;y=v.pop()){i.set(f[y.vertexIds[0]],f[y.vertexIds[1]],f[y.vertexIds[2]]),i.closestPointToPoint(s,n),n.distanceToSquared(s)<r&&(e=y,a.copy(n),r=n.distanceToSquared(s));var M=g[y.id];if(!(M>2))for(var b=0;b<y.neighbours.length;b++){var m=d[y.neighbours[b]];m.id in g||(v.push(m),g[m.id]=M+1)}}return l.copy(a),e}}();var c={PLAYER:new t.Color(15631215).convertGammaToLinear(2.2).getHex(),TARGET:new t.Color(14469912).convertGammaToLinear(2.2).getHex(),PATH:new t.Color(41903).convertGammaToLinear(2.2).getHex(),WAYPOINT:new t.Color(41903).convertGammaToLinear(2.2).getHex(),CLAMPED_STEP:new t.Color(14472114).convertGammaToLinear(2.2).getHex(),CLOSEST_NODE:new t.Color(4417387).convertGammaToLinear(2.2).getHex()},u=function(e){function r(){var r=this;e.call(this),this._playerMarker=new t.Mesh(new t.SphereGeometry(.25,32,32),new t.MeshBasicMaterial({color:c.PLAYER})),this._targetMarker=new t.Mesh(new t.BoxGeometry(.3,.3,.3),new t.MeshBasicMaterial({color:c.TARGET})),this._nodeMarker=new t.Mesh(new t.BoxGeometry(.1,.8,.1),new t.MeshBasicMaterial({color:c.CLOSEST_NODE})),this._stepMarker=new t.Mesh(new t.BoxGeometry(.1,1,.1),new t.MeshBasicMaterial({color:c.CLAMPED_STEP})),this._pathMarker=new e,this._pathLineMaterial=new t.LineBasicMaterial({color:c.PATH,linewidth:2}),this._pathPointMaterial=new t.MeshBasicMaterial({color:c.WAYPOINT}),this._pathPointGeometry=new t.SphereBufferGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(function(e){e.visible=!1,r.add(e)})}return e&&(r.__proto__=e),(r.prototype=Object.create(e&&e.prototype)).constructor=r,r.prototype.setPath=function(e){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);e=[this._playerMarker.position].concat(e);for(var r=new t.Geometry,n=0;n<e.length;n++)r.vertices.push(e[n].clone().add(new t.Vector3(0,.2,0)));this._pathMarker.add(new t.Line(r,this._pathLineMaterial));for(var o=0;o<e.length-1;o++){var i=new t.Mesh(this._pathPointGeometry,this._pathPointMaterial);i.position.copy(e[o]),i.position.y+=.2,this._pathMarker.add(i)}return this._pathMarker.visible=!0,this},r.prototype.setPlayerPosition=function(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this},r.prototype.setTargetPosition=function(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this},r.prototype.setNodePosition=function(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this},r.prototype.setStepPosition=function(e){return this._stepMarker.position.copy(e),this._stepMarker.visible=!0,this},r.prototype.reset=function(){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);return this._markers.forEach(function(e){e.visible=!1}),this},r}(t.Object3D);e.Pathfinding=h,e.PathfindingHelper=u});
!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("three")):"function"==typeof define&&define.amd?define(["exports","three"],t):t(e.threePathfinding={},e.three)}(this,function(e,t){var r=function(){};r.roundNumber=function(e,t){var r=Math.pow(10,t);return Math.round(e*r)/r},r.sample=function(e){return e[Math.floor(Math.random()*e.length)]},r.distanceToSquared=function(e,t){var r=e.x-t.x,n=e.y-t.y,o=e.z-t.z;return r*r+n*n+o*o},r.isPointInPoly=function(e,t){for(var r=!1,n=-1,o=e.length,i=o-1;++n<o;i=n)(e[n].z<=t.z&&t.z<e[i].z||e[i].z<=t.z&&t.z<e[n].z)&&t.x<(e[i].x-e[n].x)*(t.z-e[n].z)/(e[i].z-e[n].z)+e[n].x&&(r=!r);return r},r.isVectorInPolygon=function(e,t,r){var n=1e5,o=-1e5,i=[];return t.vertexIds.forEach(function(e){n=Math.min(r[e].y,n),o=Math.max(r[e].y,o),i.push(r[e])}),!!(e.y<o+.5&&e.y>n-.5&&this.isPointInPoly(i,e))},r.triarea2=function(e,t,r){return(r.x-e.x)*(t.z-e.z)-(t.x-e.x)*(r.z-e.z)},r.vequal=function(e,t){return this.distanceToSquared(e,t)<1e-5};var n=function(e){this.content=[],this.scoreFunction=e};n.prototype.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},n.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},n.prototype.remove=function(e){var t=this.content.indexOf(e),r=this.content.pop();t!==this.content.length-1&&(this.content[t]=r,this.scoreFunction(r)<this.scoreFunction(e)?this.sinkDown(t):this.bubbleUp(t))},n.prototype.size=function(){return this.content.length},n.prototype.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},n.prototype.sinkDown=function(e){for(var t=this.content[e];e>0;){var r=(e+1>>1)-1,n=this.content[r];if(!(this.scoreFunction(t)<this.scoreFunction(n)))break;this.content[r]=t,this.content[e]=n,e=r}},n.prototype.bubbleUp=function(e){for(var t=this.content.length,r=this.content[e],n=this.scoreFunction(r);;){var o=e+1<<1,i=o-1,s=null,a=void 0;if(i<t)(a=this.scoreFunction(this.content[i]))<n&&(s=i);if(o<t)this.scoreFunction(this.content[o])<(null===s?n:a)&&(s=o);if(null===s)break;this.content[e]=this.content[s],this.content[s]=r,e=s}};var o=function(){};o.init=function(e){for(var t=0;t<e.length;t++){var r=e[t];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}},o.cleanUp=function(e){for(var t=0;t<e.length;t++){var r=e[t];delete r.f,delete r.g,delete r.h,delete r.cost,delete r.visited,delete r.closed,delete r.parent}},o.heap=function(){return new n(function(e){return e.f})},o.search=function(e,t,r){this.init(e);var n=this.heap();for(n.push(t);n.size()>0;){var o=n.pop();if(o===r){for(var i=o,s=[];i.parent;)s.push(i),i=i.parent;return this.cleanUp(s),s.reverse()}o.closed=!0;for(var a=this.neighbours(e,o),h=0,c=a.length;h<c;h++){var u=a[h];if(!u.closed){var p=o.g+u.cost,l=u.visited;if(!l||p<u.g){if(u.visited=!0,u.parent=o,!u.centroid||!r.centroid)throw new Error("Unexpected state");u.h=u.h||this.heuristic(u.centroid,r.centroid),u.g=p,u.f=u.g+u.h,l?n.rescoreElement(u):n.push(u)}}}}return[]},o.heuristic=function(e,t){return r.distanceToSquared(e,t)},o.neighbours=function(e,t){for(var r=[],n=0;n<t.neighbours.length;n++)r.push(e[t.neighbours[n]]);return r};var i=function(){};i.buildZone=function(e){var n=this,o=this._buildNavigationMesh(e),i={};o.vertices.forEach(function(e){e.x=r.roundNumber(e.x,2),e.y=r.roundNumber(e.y,2),e.z=r.roundNumber(e.z,2)}),i.vertices=o.vertices;var s=this._buildPolygonGroups(o);return i.groups=new Array(s.length),s.forEach(function(e,o){var s=new Map;e.forEach(function(e,t){s.set(e,t)});var a=new Array(e.length);e.forEach(function(e,o){var h=[];e.neighbours.forEach(function(e){return h.push(s.get(e))});var c=[];e.neighbours.forEach(function(t){return c.push(n._getSharedVerticesInOrder(e,t))});var u=new t.Vector3(0,0,0);u.add(i.vertices[e.vertexIds[0]]),u.add(i.vertices[e.vertexIds[1]]),u.add(i.vertices[e.vertexIds[2]]),u.divideScalar(3),u.x=r.roundNumber(u.x,2),u.y=r.roundNumber(u.y,2),u.z=r.roundNumber(u.z,2),a[o]={id:o,neighbours:h,vertexIds:e.vertexIds,centroid:u,portals:c}}),i.groups[o]=a}),i},i._buildNavigationMesh=function(e){return e.mergeVertices(),this._buildPolygonsFromGeometry(e)},i._buildPolygonGroups=function(e){var t=[],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?t[e.group].push(e):(e.group=t.length,r(e),t.push([e]))}),t},i._buildPolygonNeighbours=function(e,t){var r=new Set,n=t[e.vertexIds[1]],o=t[e.vertexIds[2]];return t[e.vertexIds[0]].forEach(function(t){t!==e&&(n.includes(t)||o.includes(t))&&r.add(t)}),n.forEach(function(t){t!==e&&o.includes(t)&&r.add(t)}),r},i._buildPolygonsFromGeometry=function(e){for(var t=this,r=[],n=e.vertices,o=new Array(n.length),i=0;i<n.length;i++)o[i]=[];return e.faces.forEach(function(e){var t={vertexIds:[e.a,e.b,e.c],neighbours:null};r.push(t),o[e.a].push(t),o[e.b].push(t),o[e.c].push(t)}),r.forEach(function(e){e.neighbours=t._buildPolygonNeighbours(e,o)}),{polygons:r,vertices:n}},i._getSharedVerticesInOrder=function(e,t){var r=e.vertexIds,n=r[0],o=r[1],i=r[2],s=t.vertexIds,a=s.includes(n),h=s.includes(o),c=s.includes(i);return a&&h&&c?Array.from(r):a&&h?[n,o]:h&&c?[o,i]:a&&c?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])};var s=function(){this.portals=[]};s.prototype.push=function(e,t){void 0===t&&(t=e),this.portals.push({left:e,right:t})},s.prototype.stringPull=function(){var e,t,n,o=this.portals,i=[],s=0,a=0,h=0;t=o[0].left,n=o[0].right,i.push(e=o[0].left);for(var c=1;c<o.length;c++){var u=o[c].left,p=o[c].right;if(r.triarea2(e,n,p)<=0){if(!(r.vequal(e,n)||r.triarea2(e,t,p)>0)){i.push(t),t=e=t,n=e,a=s=a,h=s,c=s;continue}n=p,h=c}if(r.triarea2(e,t,u)>=0){if(!(r.vequal(e,t)||r.triarea2(e,n,u)<0)){i.push(n),t=e=n,n=e,a=s=h,h=s,c=s;continue}t=u,a=c}}return 0!==i.length&&r.vequal(i[i.length-1],o[o.length-1].left)||i.push(o[o.length-1].left),this.path=i,i};var a,h=function(){this.zones={}};h.createZone=function(e){return e.isGeometry?console.warn("[three-pathfinding]: Use BufferGeometry, not Geometry, to create zone."):e=(new t.Geometry).fromBufferGeometry(e),i.buildZone(e)},h.prototype.setZoneData=function(e,t){this.zones[e]=t},h.prototype.getRandomNode=function(e,n,o,i){if(!this.zones[e])return new t.Vector3;o=o||null,i=i||0;var s=[];return this.zones[e].groups[n].forEach(function(e){o&&i?r.distanceToSquared(o,e.centroid)<i*i&&s.push(e.centroid):s.push(e.centroid)}),r.sample(s)||new t.Vector3},h.prototype.getClosestNode=function(e,t,n,o){void 0===o&&(o=!1);var i=this.zones[t].vertices,s=null,a=Infinity;return this.zones[t].groups[n].forEach(function(t){var n=r.distanceToSquared(t.centroid,e);n<a&&(!o||r.isVectorInPolygon(e,t,i))&&(s=t,a=n)}),s},h.prototype.findPath=function(e,r,n,i){var a=this.zones[n].groups[i],h=this.zones[n].vertices,c=this.getClosestNode(e,n,i,!0),u=this.getClosestNode(r,n,i,!0);if(!c||!u)return null;var p=o.search(a,c,u),l=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},f=new s;f.push(e);for(var d=0;d<p.length;d++){var v=p[d+1];if(v){var g=l(p[d],v);f.push(h[g[0]],h[g[1]])}}f.push(r),f.stringPull();var y=f.path.map(function(e){return new t.Vector3(e.x,e.y,e.z)});return y.shift(),y},h.prototype.getGroup=(a=new t.Plane,function(e,t,n){if(void 0===n&&(n=!1),!this.zones[e])return null;for(var o=null,i=Math.pow(50,2),s=this.zones[e],h=0;h<s.groups.length;h++)for(var c=0,u=s.groups[h];c<u.length;c+=1){var p=u[c];if(n&&(a.setFromCoplanarPoints(s.vertices[p.vertexIds[0]],s.vertices[p.vertexIds[1]],s.vertices[p.vertexIds[2]]),Math.abs(a.distanceToPoint(t))<.01&&r.isPointInPoly([s.vertices[p.vertexIds[0]],s.vertices[p.vertexIds[1]],s.vertices[p.vertexIds[2]]],t)))return h;var l=r.distanceToSquared(p.centroid,t);l<i&&(o=h,i=l)}return o}),h.prototype.clampStep=function(){var e,r,n=new t.Vector3,o=new t.Plane,i=new t.Triangle,s=new t.Vector3,a=new t.Vector3;return function(t,h,c,u,p,l){var f=this.zones[u].vertices,d=this.zones[u].groups[p],v=[c],g={};g[c.id]=0,e=void 0,a.set(0,0,0),r=Infinity,o.setFromCoplanarPoints(f[c.vertexIds[0]],f[c.vertexIds[1]],f[c.vertexIds[2]]),o.projectPoint(h,n),s.copy(n);for(var y=v.pop();y;y=v.pop()){i.set(f[y.vertexIds[0]],f[y.vertexIds[1]],f[y.vertexIds[2]]),i.closestPointToPoint(s,n),n.distanceToSquared(s)<r&&(e=y,a.copy(n),r=n.distanceToSquared(s));var M=g[y.id];if(!(M>2))for(var b=0;b<y.neighbours.length;b++){var m=d[y.neighbours[b]];m.id in g||(v.push(m),g[m.id]=M+1)}}return l.copy(a),e}}();var c={PLAYER:new t.Color(15631215).convertGammaToLinear(2.2).getHex(),TARGET:new t.Color(14469912).convertGammaToLinear(2.2).getHex(),PATH:new t.Color(41903).convertGammaToLinear(2.2).getHex(),WAYPOINT:new t.Color(41903).convertGammaToLinear(2.2).getHex(),CLAMPED_STEP:new t.Color(14472114).convertGammaToLinear(2.2).getHex(),CLOSEST_NODE:new t.Color(4417387).convertGammaToLinear(2.2).getHex()},u=function(e){function r(){var r=this;e.call(this),this._playerMarker=new t.Mesh(new t.SphereGeometry(.25,32,32),new t.MeshBasicMaterial({color:c.PLAYER})),this._targetMarker=new t.Mesh(new t.BoxGeometry(.3,.3,.3),new t.MeshBasicMaterial({color:c.TARGET})),this._nodeMarker=new t.Mesh(new t.BoxGeometry(.1,.8,.1),new t.MeshBasicMaterial({color:c.CLOSEST_NODE})),this._stepMarker=new t.Mesh(new t.BoxGeometry(.1,1,.1),new t.MeshBasicMaterial({color:c.CLAMPED_STEP})),this._pathMarker=new e,this._pathLineMaterial=new t.LineBasicMaterial({color:c.PATH,linewidth:2}),this._pathPointMaterial=new t.MeshBasicMaterial({color:c.WAYPOINT}),this._pathPointGeometry=new t.SphereBufferGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(function(e){e.visible=!1,r.add(e)})}return e&&(r.__proto__=e),(r.prototype=Object.create(e&&e.prototype)).constructor=r,r.prototype.setPath=function(e){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);e=[this._playerMarker.position].concat(e);for(var r=new t.Geometry,n=0;n<e.length;n++)r.vertices.push(e[n].clone().add(new t.Vector3(0,.2,0)));this._pathMarker.add(new t.Line(r,this._pathLineMaterial));for(var o=0;o<e.length-1;o++){var i=new t.Mesh(this._pathPointGeometry,this._pathPointMaterial);i.position.copy(e[o]),i.position.y+=.2,this._pathMarker.add(i)}return this._pathMarker.visible=!0,this},r.prototype.setPlayerPosition=function(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this},r.prototype.setTargetPosition=function(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this},r.prototype.setNodePosition=function(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this},r.prototype.setStepPosition=function(e){return this._stepMarker.position.copy(e),this._stepMarker.visible=!0,this},r.prototype.reset=function(){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);return this._markers.forEach(function(e){e.visible=!1}),this},r}(t.Object3D);e.Pathfinding=h,e.PathfindingHelper=u});
//# sourceMappingURL=three-pathfinding.umd.js.map

14

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

@@ -22,3 +22,3 @@ "author": "Don McCurdy <dm@donmccurdy.com>",

"dist": "microbundle --target web --globals three=THREE --external three",
"version": "npm run dist && npm test && git add -A dist",
"version": "npm run dist && npm test",
"postversion": "git push && git push --tags && npm publish",

@@ -59,3 +59,11 @@ "test": "node tests/index.test.js",

"uglify-js": "^3.3.3"
}
},
"files": [
"dist/",
"src/",
"README.md",
"LICENSE",
"package.json",
"package-lock.json"
]
}

4

README.md

@@ -5,3 +5,3 @@ # three-pathfinding

[![Minzipped size](https://badgen.net/bundlephobia/minzip/three-pathfinding)](https://bundlephobia.com/result?p=three-pathfinding)
[![License](https://img.shields.io/npm/l/three-pathfinding.svg)](https://github.com/donmccurdy/three-pathfinding/blob/master/LICENSE)
[![License](https://img.shields.io/badge/license-MIT-007ec6.svg)](https://github.com/donmccurdy/three-pathfinding/blob/master/LICENSE)
[![Build Status](https://travis-ci.com/donmccurdy/three-pathfinding.svg?branch=master)](https://travis-ci.com/donmccurdy/three-pathfinding)

@@ -35,3 +35,3 @@

Instead, you will need to export the navigation mesh to a 3D model format (like OBJ or glTF) and then load it
with one of the three.js loaders, like THREE.OBJLoader or THREE.GLTFLoader. The library accepts a [THREE.BufferGeometry](https://threejs.org/docs/#api/core/BufferGeometry) instance.
with one of the three.js loaders, like THREE.OBJLoader or THREE.GLTFLoader. The library accepts a [THREE.BufferGeometry](https://threejs.org/docs/#api/core/BufferGeometry) instance, and follows the +Y=Up convention of three.js and glTF.

@@ -38,0 +38,0 @@ ### Example

.travis.yml
benchmark/index.benchmark.js
demo/index.html
demo/meshes/convert_obj_three.py
demo/meshes/level.js
demo/meshes/level.mtl
demo/meshes/level.nav.js
demo/meshes/level.nav.mtl
demo/meshes/level.obj
demo/meshes/navmesh.obj
demo/navmesh.bin
demo/navmesh.gltf
demo/OrbitControls.js
demo/style.css
tests/diagrams/close-adjacent-nodes.png
tests/diagrams/close-groups.png
tests/index.test.js
dist/three-pathfinding.js.map

Sorry, the diff of this file is not supported yet

dist/three-pathfinding.module.js.map

Sorry, the diff of this file is not supported yet

dist/three-pathfinding.umd.js.map

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

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

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc