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.14.1 to 0.15.0

2

dist/three-pathfinding.js

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

var e=require("three");function t(e,r){return(t=Object.setPrototypeOf||function(e,t){return e.__proto__=t,e})(e,r)}function r(e,t){(null==t||t>e.length)&&(t=e.length);for(var r=0,n=new Array(t);r<t;r++)n[r]=e[r];return n}function n(e,t){var n;if("undefined"==typeof Symbol||null==e[Symbol.iterator]){if(Array.isArray(e)||(n=function(e,t){if(e){if("string"==typeof e)return r(e,t);var n=Object.prototype.toString.call(e).slice(8,-1);return"Object"===n&&e.constructor&&(n=e.constructor.name),"Map"===n||"Set"===n?Array.from(e):"Arguments"===n||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)?r(e,t):void 0}}(e))||t&&e&&"number"==typeof e.length){n&&(e=n);var o=0;return function(){return o>=e.length?{done:!0}:{done:!1,value:e[o++]}}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}return(n=e[Symbol.iterator]()).next.bind(n)}var o,i=function(){function t(){}return 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},t.mergeVertices=function(t,r){void 0===r&&(r=1e-4),r=Math.max(r,Number.EPSILON);for(var n={},o=t.getIndex(),i=t.getAttribute("position"),s=o?o.count:i.count,a=0,u=[],h=[],c=Math.log10(1/r),l=Math.pow(10,c),f=0;f<s;f++){var p=o?o.getX(f):f,d="";d+=~~(i.getX(p)*l)+",",d+=~~(i.getY(p)*l)+",",(d+=~~(i.getZ(p)*l)+",")in n?u.push(n[d]):(h.push(i.getX(p)),h.push(i.getY(p)),h.push(i.getZ(p)),n[d]=a,u.push(a),a++)}var v=new e.BufferAttribute(new Float32Array(h),i.itemSize,i.normalized),g=new e.BufferGeometry;return g.setAttribute("position",v),g.setIndex(u),g},t}(),s=function(){function e(e){this.content=[],this.scoreFunction=e}var t=e.prototype;return t.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},t.pop=function(){var e=this.content[0],t=this.content.pop();return this.content.length>0&&(this.content[0]=t,this.bubbleUp(0)),e},t.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))},t.size=function(){return this.content.length},t.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},t.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}},t.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}},e}(),a=function(){function e(){}return e.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}},e.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}},e.heap=function(){return new s(function(e){return e.f})},e.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),u=0,h=a.length;u<h;u++){var c=a[u];if(!c.closed){var l=o.g+c.cost,f=c.visited;if(!f||l<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=l,c.f=c.g+c.h,f?n.rescoreElement(c):n.push(c)}}}}return[]},e.heuristic=function(e,t){return i.distanceToSquared(e,t)},e.neighbours=function(e,t){for(var r=[],n=0;n<t.neighbours.length;n++)r.push(e[t.neighbours[n]]);return r},e}(),u=function(){function t(){}return t.buildZone=function(t,r){var n=this,o=this._buildNavigationMesh(t,r),s={};o.vertices.forEach(function(e){e.x=i.roundNumber(e.x,2),e.y=i.roundNumber(e.y,2),e.z=i.roundNumber(e.z,2)}),s.vertices=o.vertices;var a=this._buildPolygonGroups(o);return s.groups=new Array(a.length),a.forEach(function(t,r){var o=new Map;t.forEach(function(e,t){o.set(e,t)});var a=new Array(t.length);t.forEach(function(t,r){var u=[];t.neighbours.forEach(function(e){return u.push(o.get(e))});var h=[];t.neighbours.forEach(function(e){return h.push(n._getSharedVerticesInOrder(t,e))});var c=new e.Vector3(0,0,0);c.add(s.vertices[t.vertexIds[0]]),c.add(s.vertices[t.vertexIds[1]]),c.add(s.vertices[t.vertexIds[2]]),c.divideScalar(3),c.x=i.roundNumber(c.x,2),c.y=i.roundNumber(c.y,2),c.z=i.roundNumber(c.z,2),a[r]={id:r,neighbours:u,vertexIds:t.vertexIds,centroid:c,portals:h}}),s.groups[r]=a}),s},t._buildNavigationMesh=function(e,t){return e=i.mergeVertices(e,t),this._buildPolygonsFromGeometry(e)},t._buildPolygonGroups=function(e){var t=[],r=function e(t){t.neighbours.forEach(function(r){void 0===r.group&&(r.group=t.group,e(r))})};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},t._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},t._buildPolygonsFromGeometry=function(t){for(var r=this,n=[],o=[],i=t.attributes.position,s=t.index,a=[],u=0;u<i.count;u++)o.push((new e.Vector3).fromBufferAttribute(i,u)),a[u]=[];for(var h=0;h<t.index.count;h+=3){var c=s.getX(h),l=s.getX(h+1),f=s.getX(h+2),p={vertexIds:[c,l,f],neighbours:null};n.push(p),a[c].push(p),a[l].push(p),a[f].push(p)}return n.forEach(function(e){e.neighbours=r._buildPolygonNeighbours(e,a)}),{polygons:n,vertices:o}},t._getSharedVerticesInOrder=function(e,t){var r=e.vertexIds,n=r[0],o=r[1],i=r[2],s=t.vertexIds,a=s.includes(n),u=s.includes(o),h=s.includes(i);return a&&u&&h?Array.from(r):a&&u?[n,o]:u&&h?[o,i]:a&&h?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])},t}(),h=function(){function e(){this.portals=[]}var t=e.prototype;return t.push=function(e,t){void 0===t&&(t=e),this.portals.push({left:e,right:t})},t.stringPull=function(){var e,t,r,n=this.portals,o=[],s=0,a=0,u=0;t=n[0].left,r=n[0].right,o.push(e=n[0].left);for(var h=1;h<n.length;h++){var c=n[h].left,l=n[h].right;if(i.triarea2(e,r,l)<=0){if(!(i.vequal(e,r)||i.triarea2(e,t,l)>0)){o.push(t),t=e=t,r=e,a=s=a,u=s,h=s;continue}r=l,u=h}if(i.triarea2(e,t,c)>=0){if(!(i.vequal(e,t)||i.triarea2(e,r,c)<0)){o.push(r),t=e=r,r=e,a=s=u,u=s,h=s;continue}t=c,a=h}}return 0!==o.length&&i.vequal(o[o.length-1],n[n.length-1].left)||o.push(n[n.length-1].left),this.path=o,o},e}(),c=function(){function t(){this.zones={}}t.createZone=function(e,t){return void 0===t&&(t=1e-4),u.buildZone(e,t)};var r=t.prototype;return r.setZoneData=function(e,t){this.zones[e]=t},r.getRandomNode=function(t,r,n,o){if(!this.zones[t])return new e.Vector3;n=n||null,o=o||0;var s=[];return this.zones[t].groups[r].forEach(function(e){n&&o?i.distanceToSquared(n,e.centroid)<o*o&&s.push(e.centroid):s.push(e.centroid)}),i.sample(s)||new e.Vector3},r.getClosestNode=function(e,t,r,n){void 0===n&&(n=!1);var o=this.zones[t].vertices,s=null,a=Infinity;return this.zones[t].groups[r].forEach(function(t){var r=i.distanceToSquared(t.centroid,e);r<a&&(!n||i.isVectorInPolygon(e,t,o))&&(s=t,a=r)}),s},r.findPath=function(t,r,n,o){var i=this.zones[n].groups[o],s=this.zones[n].vertices,u=this.getClosestNode(t,n,o,!0),c=this.getClosestNode(r,n,o,!0);if(!u||!c)return null;var l=a.search(i,u,c),f=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},p=new h;p.push(t);for(var d=0;d<l.length;d++){var v=l[d+1];if(v){var g=f(l[d],v);p.push(s[g[0]],s[g[1]])}}p.push(r),p.stringPull();var y=p.path.map(function(t){return new e.Vector3(t.x,t.y,t.z)});return y.shift(),y},t}();c.prototype.getGroup=(o=new e.Plane,function(e,t,r){if(void 0===r&&(r=!1),!this.zones[e])return null;for(var s=null,a=Math.pow(50,2),u=this.zones[e],h=0;h<u.groups.length;h++)for(var c,l=n(u.groups[h]);!(c=l()).done;){var f=c.value;if(r&&(o.setFromCoplanarPoints(u.vertices[f.vertexIds[0]],u.vertices[f.vertexIds[1]],u.vertices[f.vertexIds[2]]),Math.abs(o.distanceToPoint(t))<.01&&i.isPointInPoly([u.vertices[f.vertexIds[0]],u.vertices[f.vertexIds[1]],u.vertices[f.vertexIds[2]]],t)))return h;var p=i.distanceToSquared(f.centroid,t);p<a&&(s=h,a=p)}return s}),c.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,u,h,c,l,f){var p=this.zones[c].vertices,d=this.zones[c].groups[l],v=[h],g={};g[h.id]=0,t=void 0,a.set(0,0,0),r=Infinity,o.setFromCoplanarPoints(p[h.vertexIds[0]],p[h.vertexIds[1]],p[h.vertexIds[2]]),o.projectPoint(u,n),s.copy(n);for(var y=v.pop();y;y=v.pop()){i.set(p[y.vertexIds[0]],p[y.vertexIds[1]],p[y.vertexIds[2]]),i.closestPointToPoint(s,n),n.distanceToSquared(s)<r&&(t=y,a.copy(n),r=n.distanceToSquared(s));var b=g[y.id];if(!(b>2))for(var m=0;m<y.neighbours.length;m++){var M=d[y.neighbours[m]];M.id in g||(v.push(M),g[M.id]=b+1)}}return f.copy(a),t}}();var l={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()},f=function(r){var n,o;function i(){var t;return(t=r.call(this)||this)._playerMarker=new e.Mesh(new e.SphereBufferGeometry(.25,32,32),new e.MeshBasicMaterial({color:l.PLAYER})),t._targetMarker=new e.Mesh(new e.BoxBufferGeometry(.3,.3,.3),new e.MeshBasicMaterial({color:l.TARGET})),t._nodeMarker=new e.Mesh(new e.BoxBufferGeometry(.1,.8,.1),new e.MeshBasicMaterial({color:l.CLOSEST_NODE})),t._stepMarker=new e.Mesh(new e.BoxBufferGeometry(.1,1,.1),new e.MeshBasicMaterial({color:l.CLAMPED_STEP})),t._pathMarker=new e.Object3D,t._pathLineMaterial=new e.LineBasicMaterial({color:l.PATH,linewidth:2}),t._pathPointMaterial=new e.MeshBasicMaterial({color:l.WAYPOINT}),t._pathPointGeometry=new e.SphereBufferGeometry(.08),t._markers=[t._playerMarker,t._targetMarker,t._nodeMarker,t._stepMarker,t._pathMarker],t._markers.forEach(function(e){e.visible=!1,t.add(e)}),t}o=r,(n=i).prototype=Object.create(o.prototype),n.prototype.constructor=n,t(n,o);var s=i.prototype;return s.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);var r=new e.BufferGeometry;r.setAttribute("position",new e.BufferAttribute(new Float32Array(3*t.length),3));for(var n=0;n<t.length;n++)r.attributes.position.setXYZ(n,t[n].x,t[n].y+.2,t[n].z);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},s.setPlayerPosition=function(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this},s.setTargetPosition=function(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this},s.setNodePosition=function(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this},s.setStepPosition=function(e){return this._stepMarker.position.copy(e),this._stepMarker.visible=!0,this},s.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},i}(e.Object3D);exports.Pathfinding=c,exports.PathfindingHelper=f;
var e=require("three");function t(e,t){(null==t||t>e.length)&&(t=e.length);for(var r=0,n=new Array(t);r<t;r++)n[r]=e[r];return n}function r(e,r){var n;if("undefined"==typeof Symbol||null==e[Symbol.iterator]){if(Array.isArray(e)||(n=function(e,r){if(e){if("string"==typeof e)return t(e,r);var n=Object.prototype.toString.call(e).slice(8,-1);return"Object"===n&&e.constructor&&(n=e.constructor.name),"Map"===n||"Set"===n?Array.from(e):"Arguments"===n||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)?t(e,r):void 0}}(e))||r&&e&&"number"==typeof e.length){n&&(e=n);var o=0;return function(){return o>=e.length?{done:!0}:{done:!1,value:e[o++]}}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}return(n=e[Symbol.iterator]()).next.bind(n)}var n,o=function(){function t(){}return 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},t.mergeVertices=function(t,r){void 0===r&&(r=1e-4),r=Math.max(r,Number.EPSILON);for(var n={},o=t.getIndex(),i=t.getAttribute("position"),s=o?o.count:i.count,a=0,u=[],h=[],c=Math.log10(1/r),l=Math.pow(10,c),f=0;f<s;f++){var p=o?o.getX(f):f,d="";d+=~~(i.getX(p)*l)+",",d+=~~(i.getY(p)*l)+",",(d+=~~(i.getZ(p)*l)+",")in n?u.push(n[d]):(h.push(i.getX(p)),h.push(i.getY(p)),h.push(i.getZ(p)),n[d]=a,u.push(a),a++)}var v=new e.BufferAttribute(new Float32Array(h),i.itemSize,i.normalized),g=new e.BufferGeometry;return g.setAttribute("position",v),g.setIndex(u),g},t}(),i=function(){function e(e){this.content=[],this.scoreFunction=e}var t=e.prototype;return t.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},t.pop=function(){var e=this.content[0],t=this.content.pop();return this.content.length>0&&(this.content[0]=t,this.bubbleUp(0)),e},t.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))},t.size=function(){return this.content.length},t.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},t.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}},t.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}},e}(),s=function(){function e(){}return e.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}},e.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}},e.heap=function(){return new i(function(e){return e.f})},e.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),u=0,h=a.length;u<h;u++){var c=a[u];if(!c.closed){var l=o.g+c.cost,f=c.visited;if(!f||l<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=l,c.f=c.g+c.h,f?n.rescoreElement(c):n.push(c)}}}}return[]},e.heuristic=function(e,t){return o.distanceToSquared(e,t)},e.neighbours=function(e,t){for(var r=[],n=0;n<t.neighbours.length;n++)r.push(e[t.neighbours[n]]);return r},e}(),a=function(){function t(){}return t.buildZone=function(t,r){var n=this,i=this._buildNavigationMesh(t,r),s={};i.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)}),s.vertices=i.vertices;var a=this._buildPolygonGroups(i);return s.groups=new Array(a.length),a.forEach(function(t,r){var i=new Map;t.forEach(function(e,t){i.set(e,t)});var a=new Array(t.length);t.forEach(function(t,r){var u=[];t.neighbours.forEach(function(e){return u.push(i.get(e))});var h=[];t.neighbours.forEach(function(e){return h.push(n._getSharedVerticesInOrder(t,e))});var c=new e.Vector3(0,0,0);c.add(s.vertices[t.vertexIds[0]]),c.add(s.vertices[t.vertexIds[1]]),c.add(s.vertices[t.vertexIds[2]]),c.divideScalar(3),c.x=o.roundNumber(c.x,2),c.y=o.roundNumber(c.y,2),c.z=o.roundNumber(c.z,2),a[r]={id:r,neighbours:u,vertexIds:t.vertexIds,centroid:c,portals:h}}),s.groups[r]=a}),s},t._buildNavigationMesh=function(e,t){return e=o.mergeVertices(e,t),this._buildPolygonsFromGeometry(e)},t._spreadGroupId=function(e){for(var t=new Set([e]);t.size>0;){var r=t;t=new Set,r.forEach(function(r){r.group=e.group,r.neighbours.forEach(function(e){void 0===e.group&&t.add(e)})})}},t._buildPolygonGroups=function(e){var t=this,r=[];return e.polygons.forEach(function(e){void 0!==e.group?r[e.group].push(e):(e.group=r.length,t._spreadGroupId(e),r.push([e]))}),r},t._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},t._buildPolygonsFromGeometry=function(t){for(var r=this,n=[],o=[],i=t.attributes.position,s=t.index,a=[],u=0;u<i.count;u++)o.push((new e.Vector3).fromBufferAttribute(i,u)),a[u]=[];for(var h=0;h<t.index.count;h+=3){var c=s.getX(h),l=s.getX(h+1),f=s.getX(h+2),p={vertexIds:[c,l,f],neighbours:null};n.push(p),a[c].push(p),a[l].push(p),a[f].push(p)}return n.forEach(function(e){e.neighbours=r._buildPolygonNeighbours(e,a)}),{polygons:n,vertices:o}},t._getSharedVerticesInOrder=function(e,t){var r=e.vertexIds,n=r[0],o=r[1],i=r[2],s=t.vertexIds,a=s.includes(n),u=s.includes(o),h=s.includes(i);return a&&u&&h?Array.from(r):a&&u?[n,o]:u&&h?[o,i]:a&&h?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])},t}(),u=function(){function e(){this.portals=[]}var t=e.prototype;return t.push=function(e,t){void 0===t&&(t=e),this.portals.push({left:e,right:t})},t.stringPull=function(){var e,t,r,n=this.portals,i=[],s=0,a=0,u=0;t=n[0].left,r=n[0].right,i.push(e=n[0].left);for(var h=1;h<n.length;h++){var c=n[h].left,l=n[h].right;if(o.triarea2(e,r,l)<=0){if(!(o.vequal(e,r)||o.triarea2(e,t,l)>0)){i.push(t),t=e=t,r=e,a=s=a,u=s,h=s;continue}r=l,u=h}if(o.triarea2(e,t,c)>=0){if(!(o.vequal(e,t)||o.triarea2(e,r,c)<0)){i.push(r),t=e=r,r=e,a=s=u,u=s,h=s;continue}t=c,a=h}}return 0!==i.length&&o.vequal(i[i.length-1],n[n.length-1].left)||i.push(n[n.length-1].left),this.path=i,i},e}(),h=function(){function t(){this.zones={}}t.createZone=function(e,t){return void 0===t&&(t=1e-4),a.buildZone(e,t)};var r=t.prototype;return r.setZoneData=function(e,t){this.zones[e]=t},r.getRandomNode=function(t,r,n,i){if(!this.zones[t])return new e.Vector3;n=n||null,i=i||0;var s=[];return this.zones[t].groups[r].forEach(function(e){n&&i?o.distanceToSquared(n,e.centroid)<i*i&&s.push(e.centroid):s.push(e.centroid)}),o.sample(s)||new e.Vector3},r.getClosestNode=function(e,t,r,n){void 0===n&&(n=!1);var i=this.zones[t].vertices,s=null,a=Infinity;return this.zones[t].groups[r].forEach(function(t){var r=o.distanceToSquared(t.centroid,e);r<a&&(!n||o.isVectorInPolygon(e,t,i))&&(s=t,a=r)}),s},r.findPath=function(t,r,n,o){var i=this.zones[n].groups[o],a=this.zones[n].vertices,h=this.getClosestNode(t,n,o,!0),c=this.getClosestNode(r,n,o,!0);if(!h||!c)return null;var l=s.search(i,h,c),f=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},p=new u;p.push(t);for(var d=0;d<l.length;d++){var v=l[d+1];if(v){var g=f(l[d],v);p.push(a[g[0]],a[g[1]])}}p.push(r),p.stringPull();var y=p.path.map(function(t){return new e.Vector3(t.x,t.y,t.z)});return y.shift(),y},t}();h.prototype.getGroup=(n=new e.Plane,function(e,t,i){if(void 0===i&&(i=!1),!this.zones[e])return null;for(var s=null,a=Math.pow(50,2),u=this.zones[e],h=0;h<u.groups.length;h++)for(var c,l=r(u.groups[h]);!(c=l()).done;){var f=c.value;if(i&&(n.setFromCoplanarPoints(u.vertices[f.vertexIds[0]],u.vertices[f.vertexIds[1]],u.vertices[f.vertexIds[2]]),Math.abs(n.distanceToPoint(t))<.01&&o.isPointInPoly([u.vertices[f.vertexIds[0]],u.vertices[f.vertexIds[1]],u.vertices[f.vertexIds[2]]],t)))return h;var p=o.distanceToSquared(f.centroid,t);p<a&&(s=h,a=p)}return s}),h.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,u,h,c,l,f){var p=this.zones[c].vertices,d=this.zones[c].groups[l],v=[h],g={};g[h.id]=0,t=void 0,a.set(0,0,0),r=Infinity,o.setFromCoplanarPoints(p[h.vertexIds[0]],p[h.vertexIds[1]],p[h.vertexIds[2]]),o.projectPoint(u,n),s.copy(n);for(var y=v.pop();y;y=v.pop()){i.set(p[y.vertexIds[0]],p[y.vertexIds[1]],p[y.vertexIds[2]]),i.closestPointToPoint(s,n),n.distanceToSquared(s)<r&&(t=y,a.copy(n),r=n.distanceToSquared(s));var b=g[y.id];if(!(b>2))for(var m=0;m<y.neighbours.length;m++){var M=d[y.neighbours[m]];M.id in g||(v.push(M),g[M.id]=b+1)}}return f.copy(a),t}}();var c={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()},l=function(t){var r,n;function o(){var r;return(r=t.call(this)||this)._playerMarker=new e.Mesh(new e.SphereBufferGeometry(.25,32,32),new e.MeshBasicMaterial({color:c.PLAYER})),r._targetMarker=new e.Mesh(new e.BoxBufferGeometry(.3,.3,.3),new e.MeshBasicMaterial({color:c.TARGET})),r._nodeMarker=new e.Mesh(new e.BoxBufferGeometry(.1,.8,.1),new e.MeshBasicMaterial({color:c.CLOSEST_NODE})),r._stepMarker=new e.Mesh(new e.BoxBufferGeometry(.1,1,.1),new e.MeshBasicMaterial({color:c.CLAMPED_STEP})),r._pathMarker=new e.Object3D,r._pathLineMaterial=new e.LineBasicMaterial({color:c.PATH,linewidth:2}),r._pathPointMaterial=new e.MeshBasicMaterial({color:c.WAYPOINT}),r._pathPointGeometry=new e.SphereBufferGeometry(.08),r._markers=[r._playerMarker,r._targetMarker,r._nodeMarker,r._stepMarker,r._pathMarker],r._markers.forEach(function(e){e.visible=!1,r.add(e)}),r}n=t,(r=o).prototype=Object.create(n.prototype),r.prototype.constructor=r,r.__proto__=n;var i=o.prototype;return i.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);var r=new e.BufferGeometry;r.setAttribute("position",new e.BufferAttribute(new Float32Array(3*t.length),3));for(var n=0;n<t.length;n++)r.attributes.position.setXYZ(n,t[n].x,t[n].y+.2,t[n].z);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},i.setPlayerPosition=function(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this},i.setTargetPosition=function(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this},i.setNodePosition=function(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this},i.setStepPosition=function(e){return this._stepMarker.position.copy(e),this._stepMarker.visible=!0,this},i.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},o}(e.Object3D);exports.Pathfinding=h,exports.PathfindingHelper=l;
//# sourceMappingURL=three-pathfinding.js.map

2

dist/three-pathfinding.modern.js

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

import{BufferAttribute as t,BufferGeometry as e,Vector3 as r,Plane as n,Triangle as s,Color as o,Object3D as i,Mesh as h,SphereBufferGeometry as c,MeshBasicMaterial as a,BoxBufferGeometry as u,LineBasicMaterial as l,Line as p}from"three";class d{static roundNumber(t,e){const r=Math.pow(10,e);return Math.round(t*r)/r}static sample(t){return t[Math.floor(Math.random()*t.length)]}static distanceToSquared(t,e){var r=t.x-e.x,n=t.y-e.y,s=t.z-e.z;return r*r+n*n+s*s}static isPointInPoly(t,e){for(var r=!1,n=-1,s=t.length,o=s-1;++n<s;o=n)(t[n].z<=e.z&&e.z<t[o].z||t[o].z<=e.z&&e.z<t[n].z)&&e.x<(t[o].x-t[n].x)*(e.z-t[n].z)/(t[o].z-t[n].z)+t[n].x&&(r=!r);return r}static isVectorInPolygon(t,e,r){var n=1e5,s=-1e5,o=[];return e.vertexIds.forEach(t=>{n=Math.min(r[t].y,n),s=Math.max(r[t].y,s),o.push(r[t])}),!!(t.y<s+.5&&t.y>n-.5&&this.isPointInPoly(o,t))}static triarea2(t,e,r){return(r.x-t.x)*(e.z-t.z)-(e.x-t.x)*(r.z-t.z)}static vequal(t,e){return this.distanceToSquared(t,e)<1e-5}static mergeVertices(r,n=1e-4){n=Math.max(n,Number.EPSILON);for(var s={},o=r.getIndex(),i=r.getAttribute("position"),h=o?o.count:i.count,c=0,a=[],u=[],l=Math.log10(1/n),p=Math.pow(10,l),d=0;d<h;d++){var g=o?o.getX(d):d,f="";f+=~~(i.getX(g)*p)+",",f+=~~(i.getY(g)*p)+",",(f+=~~(i.getZ(g)*p)+",")in s?a.push(s[f]):(u.push(i.getX(g)),u.push(i.getY(g)),u.push(i.getZ(g)),s[f]=c,a.push(c),c++)}const v=new t(new Float32Array(u),i.itemSize,i.normalized),b=new e;return b.setAttribute("position",v),b.setIndex(a),b}}class g{constructor(t){this.content=[],this.scoreFunction=t}push(t){this.content.push(t),this.sinkDown(this.content.length-1)}pop(){const t=this.content[0],e=this.content.pop();return this.content.length>0&&(this.content[0]=e,this.bubbleUp(0)),t}remove(t){const 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))}size(){return this.content.length}rescoreElement(t){this.sinkDown(this.content.indexOf(t))}sinkDown(t){const e=this.content[t];for(;t>0;){const 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}}bubbleUp(t){const e=this.content.length,r=this.content[t],n=this.scoreFunction(r);for(;;){const s=t+1<<1,o=s-1;let i,h=null;if(o<e&&(i=this.scoreFunction(this.content[o]),i<n&&(h=o)),s<e&&this.scoreFunction(this.content[s])<(null===h?n:i)&&(h=s),null===h)break;this.content[t]=this.content[h],this.content[h]=r,t=h}}}class f{constructor(){this.portals=[]}push(t,e){void 0===e&&(e=t),this.portals.push({left:t,right:e})}stringPull(){const t=this.portals,e=[];let r,n,s,o=0,i=0,h=0;r=t[0].left,n=t[0].left,s=t[0].right,e.push(r);for(let c=1;c<t.length;c++){const a=t[c].left,u=t[c].right;if(d.triarea2(r,s,u)<=0){if(!(d.vequal(r,s)||d.triarea2(r,n,u)>0)){e.push(n),r=n,o=i,n=r,s=r,i=o,h=o,c=o;continue}s=u,h=c}if(d.triarea2(r,n,a)>=0){if(!(d.vequal(r,n)||d.triarea2(r,s,a)<0)){e.push(s),r=s,o=h,n=r,s=r,i=o,h=o,c=o;continue}n=a,i=c}}return 0!==e.length&&d.vequal(e[e.length-1],t[t.length-1].left)||e.push(t[t.length-1].left),this.path=e,e}}class v{constructor(){this.zones={}}static createZone(t,e=1e-4){return class{static buildZone(t,e){const n=this._buildNavigationMesh(t,e),s={};n.vertices.forEach(t=>{t.x=d.roundNumber(t.x,2),t.y=d.roundNumber(t.y,2),t.z=d.roundNumber(t.z,2)}),s.vertices=n.vertices;const o=this._buildPolygonGroups(n);return s.groups=new Array(o.length),o.forEach((t,e)=>{const n=new Map;t.forEach((t,e)=>{n.set(t,e)});const o=new Array(t.length);t.forEach((t,e)=>{const i=[];t.neighbours.forEach(t=>i.push(n.get(t)));const h=[];t.neighbours.forEach(e=>h.push(this._getSharedVerticesInOrder(t,e)));const c=new r(0,0,0);c.add(s.vertices[t.vertexIds[0]]),c.add(s.vertices[t.vertexIds[1]]),c.add(s.vertices[t.vertexIds[2]]),c.divideScalar(3),c.x=d.roundNumber(c.x,2),c.y=d.roundNumber(c.y,2),c.z=d.roundNumber(c.z,2),o[e]={id:e,neighbours:i,vertexIds:t.vertexIds,centroid:c,portals:h}}),s.groups[e]=o}),s}static _buildNavigationMesh(t,e){return t=d.mergeVertices(t,e),this._buildPolygonsFromGeometry(t)}static _buildPolygonGroups(t){const e=[],r=function t(e){e.neighbours.forEach(r=>{void 0===r.group&&(r.group=e.group,t(r))})};return t.polygons.forEach(t=>{void 0!==t.group?e[t.group].push(t):(t.group=e.length,r(t),e.push([t]))}),e}static _buildPolygonNeighbours(t,e){const r=new Set,n=e[t.vertexIds[1]],s=e[t.vertexIds[2]];return e[t.vertexIds[0]].forEach(e=>{e!==t&&(n.includes(e)||s.includes(e))&&r.add(e)}),n.forEach(e=>{e!==t&&s.includes(e)&&r.add(e)}),r}static _buildPolygonsFromGeometry(t){const e=[],n=[],s=t.attributes.position,o=t.index,i=[];for(let t=0;t<s.count;t++)n.push((new r).fromBufferAttribute(s,t)),i[t]=[];for(let r=0;r<t.index.count;r+=3){const t=o.getX(r),n=o.getX(r+1),s=o.getX(r+2),h={vertexIds:[t,n,s],neighbours:null};e.push(h),i[t].push(h),i[n].push(h),i[s].push(h)}return e.forEach(t=>{t.neighbours=this._buildPolygonNeighbours(t,i)}),{polygons:e,vertices:n}}static _getSharedVerticesInOrder(t,e){const r=t.vertexIds,n=r[0],s=r[1],o=r[2],i=e.vertexIds,h=i.includes(n),c=i.includes(s),a=i.includes(o);return h&&c&&a?Array.from(r):h&&c?[n,s]:c&&a?[s,o]:h&&a?[o,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])}}.buildZone(t,e)}setZoneData(t,e){this.zones[t]=e}getRandomNode(t,e,n,s){if(!this.zones[t])return new r;n=n||null,s=s||0;const o=[];return this.zones[t].groups[e].forEach(t=>{n&&s?d.distanceToSquared(n,t.centroid)<s*s&&o.push(t.centroid):o.push(t.centroid)}),d.sample(o)||new r}getClosestNode(t,e,r,n=!1){const s=this.zones[e].vertices;let o=null,i=Infinity;return this.zones[e].groups[r].forEach(e=>{const r=d.distanceToSquared(e.centroid,t);r<i&&(!n||d.isVectorInPolygon(t,e,s))&&(o=e,i=r)}),o}findPath(t,e,n,s){const o=this.zones[n].groups[s],i=this.zones[n].vertices,h=this.getClosestNode(t,n,s,!0),c=this.getClosestNode(e,n,s,!0);if(!h||!c)return null;const a=class{static init(t){for(let e=0;e<t.length;e++){const r=t[e];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}}static cleanUp(t){for(let e=0;e<t.length;e++){const r=t[e];delete r.f,delete r.g,delete r.h,delete r.cost,delete r.visited,delete r.closed,delete r.parent}}static heap(){return new g(function(t){return t.f})}static search(t,e,r){this.init(t);const n=this.heap();for(n.push(e);n.size()>0;){const e=n.pop();if(e===r){let t=e;const r=[];for(;t.parent;)r.push(t),t=t.parent;return this.cleanUp(r),r.reverse()}e.closed=!0;const s=this.neighbours(t,e);for(let t=0,o=s.length;t<o;t++){const o=s[t];if(o.closed)continue;const i=e.g+o.cost,h=o.visited;if(!h||i<o.g){if(o.visited=!0,o.parent=e,!o.centroid||!r.centroid)throw new Error("Unexpected state");o.h=o.h||this.heuristic(o.centroid,r.centroid),o.g=i,o.f=o.g+o.h,h?n.rescoreElement(o):n.push(o)}}}return[]}static heuristic(t,e){return d.distanceToSquared(t,e)}static neighbours(t,e){const r=[];for(let n=0;n<e.neighbours.length;n++)r.push(t[e.neighbours[n]]);return r}}.search(o,h,c),u=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},l=new f;l.push(t);for(let t=0;t<a.length;t++){const e=a[t],r=a[t+1];if(r){const t=u(e,r);l.push(i[t[0]],i[t[1]])}}l.push(e),l.stringPull();const p=l.path.map(t=>new r(t.x,t.y,t.z));return p.shift(),p}}v.prototype.getGroup=function(){const t=new n;return function(e,r,n=!1){if(!this.zones[e])return null;let s=null,o=Math.pow(50,2);const i=this.zones[e];for(let e=0;e<i.groups.length;e++){const h=i.groups[e];for(const c of h){if(n&&(t.setFromCoplanarPoints(i.vertices[c.vertexIds[0]],i.vertices[c.vertexIds[1]],i.vertices[c.vertexIds[2]]),Math.abs(t.distanceToPoint(r))<.01)&&d.isPointInPoly([i.vertices[c.vertexIds[0]],i.vertices[c.vertexIds[1]],i.vertices[c.vertexIds[2]]],r))return e;const h=d.distanceToSquared(c.centroid,r);h<o&&(s=e,o=h)}}return s}}(),v.prototype.clampStep=function(){const t=new r,e=new n,o=new s,i=new r;let h,c,a=new r;return function(r,n,s,u,l,p){const d=this.zones[u].vertices,g=this.zones[u].groups[l],f=[s],v={};v[s.id]=0,h=void 0,a.set(0,0,0),c=Infinity,e.setFromCoplanarPoints(d[s.vertexIds[0]],d[s.vertexIds[1]],d[s.vertexIds[2]]),e.projectPoint(n,t),i.copy(t);for(let e=f.pop();e;e=f.pop()){o.set(d[e.vertexIds[0]],d[e.vertexIds[1]],d[e.vertexIds[2]]),o.closestPointToPoint(i,t),t.distanceToSquared(i)<c&&(h=e,a.copy(t),c=t.distanceToSquared(i));const r=v[e.id];if(!(r>2))for(let t=0;t<e.neighbours.length;t++){const n=g[e.neighbours[t]];n.id in v||(f.push(n),v[n.id]=r+1)}}return p.copy(a),h}}();const b={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()};class w extends i{constructor(){super(),this._playerMarker=new h(new c(.25,32,32),new a({color:b.PLAYER})),this._targetMarker=new h(new u(.3,.3,.3),new a({color:b.TARGET})),this._nodeMarker=new h(new u(.1,.8,.1),new a({color:b.CLOSEST_NODE})),this._stepMarker=new h(new u(.1,1,.1),new a({color:b.CLAMPED_STEP})),this._pathMarker=new i,this._pathLineMaterial=new l({color:b.PATH,linewidth:2}),this._pathPointMaterial=new a({color:b.WAYPOINT}),this._pathPointGeometry=new c(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(t=>{t.visible=!1,this.add(t)})}setPath(r){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);r=[this._playerMarker.position].concat(r);const n=new e;n.setAttribute("position",new t(new Float32Array(3*r.length),3));for(let t=0;t<r.length;t++)n.attributes.position.setXYZ(t,r[t].x,r[t].y+.2,r[t].z);this._pathMarker.add(new p(n,this._pathLineMaterial));for(let t=0;t<r.length-1;t++){const e=new h(this._pathPointGeometry,this._pathPointMaterial);e.position.copy(r[t]),e.position.y+=.2,this._pathMarker.add(e)}return this._pathMarker.visible=!0,this}setPlayerPosition(t){return this._playerMarker.position.copy(t),this._playerMarker.visible=!0,this}setTargetPosition(t){return this._targetMarker.position.copy(t),this._targetMarker.visible=!0,this}setNodePosition(t){return this._nodeMarker.position.copy(t),this._nodeMarker.visible=!0,this}setStepPosition(t){return this._stepMarker.position.copy(t),this._stepMarker.visible=!0,this}reset(){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);return this._markers.forEach(t=>{t.visible=!1}),this}}export{v as Pathfinding,w as PathfindingHelper};
import{BufferAttribute as t,BufferGeometry as e,Vector3 as r,Plane as s,Triangle as n,Color as o,Object3D as i,Mesh as h,SphereBufferGeometry as c,MeshBasicMaterial as a,BoxBufferGeometry as u,LineBasicMaterial as l,Line as d}from"three";class p{static roundNumber(t,e){const r=Math.pow(10,e);return Math.round(t*r)/r}static sample(t){return t[Math.floor(Math.random()*t.length)]}static distanceToSquared(t,e){var r=t.x-e.x,s=t.y-e.y,n=t.z-e.z;return r*r+s*s+n*n}static isPointInPoly(t,e){for(var r=!1,s=-1,n=t.length,o=n-1;++s<n;o=s)(t[s].z<=e.z&&e.z<t[o].z||t[o].z<=e.z&&e.z<t[s].z)&&e.x<(t[o].x-t[s].x)*(e.z-t[s].z)/(t[o].z-t[s].z)+t[s].x&&(r=!r);return r}static isVectorInPolygon(t,e,r){var s=1e5,n=-1e5,o=[];return e.vertexIds.forEach(t=>{s=Math.min(r[t].y,s),n=Math.max(r[t].y,n),o.push(r[t])}),!!(t.y<n+.5&&t.y>s-.5&&this.isPointInPoly(o,t))}static triarea2(t,e,r){return(r.x-t.x)*(e.z-t.z)-(e.x-t.x)*(r.z-t.z)}static vequal(t,e){return this.distanceToSquared(t,e)<1e-5}static mergeVertices(r,s=1e-4){s=Math.max(s,Number.EPSILON);for(var n={},o=r.getIndex(),i=r.getAttribute("position"),h=o?o.count:i.count,c=0,a=[],u=[],l=Math.log10(1/s),d=Math.pow(10,l),p=0;p<h;p++){var g=o?o.getX(p):p,f="";f+=~~(i.getX(g)*d)+",",f+=~~(i.getY(g)*d)+",",(f+=~~(i.getZ(g)*d)+",")in n?a.push(n[f]):(u.push(i.getX(g)),u.push(i.getY(g)),u.push(i.getZ(g)),n[f]=c,a.push(c),c++)}const v=new t(new Float32Array(u),i.itemSize,i.normalized),b=new e;return b.setAttribute("position",v),b.setIndex(a),b}}class g{constructor(t){this.content=[],this.scoreFunction=t}push(t){this.content.push(t),this.sinkDown(this.content.length-1)}pop(){const t=this.content[0],e=this.content.pop();return this.content.length>0&&(this.content[0]=e,this.bubbleUp(0)),t}remove(t){const 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))}size(){return this.content.length}rescoreElement(t){this.sinkDown(this.content.indexOf(t))}sinkDown(t){const e=this.content[t];for(;t>0;){const r=(t+1>>1)-1,s=this.content[r];if(!(this.scoreFunction(e)<this.scoreFunction(s)))break;this.content[r]=e,this.content[t]=s,t=r}}bubbleUp(t){const e=this.content.length,r=this.content[t],s=this.scoreFunction(r);for(;;){const n=t+1<<1,o=n-1;let i,h=null;if(o<e&&(i=this.scoreFunction(this.content[o]),i<s&&(h=o)),n<e&&this.scoreFunction(this.content[n])<(null===h?s:i)&&(h=n),null===h)break;this.content[t]=this.content[h],this.content[h]=r,t=h}}}class f{constructor(){this.portals=[]}push(t,e){void 0===e&&(e=t),this.portals.push({left:t,right:e})}stringPull(){const t=this.portals,e=[];let r,s,n,o=0,i=0,h=0;r=t[0].left,s=t[0].left,n=t[0].right,e.push(r);for(let c=1;c<t.length;c++){const a=t[c].left,u=t[c].right;if(p.triarea2(r,n,u)<=0){if(!(p.vequal(r,n)||p.triarea2(r,s,u)>0)){e.push(s),r=s,o=i,s=r,n=r,i=o,h=o,c=o;continue}n=u,h=c}if(p.triarea2(r,s,a)>=0){if(!(p.vequal(r,s)||p.triarea2(r,n,a)<0)){e.push(n),r=n,o=h,s=r,n=r,i=o,h=o,c=o;continue}s=a,i=c}}return 0!==e.length&&p.vequal(e[e.length-1],t[t.length-1].left)||e.push(t[t.length-1].left),this.path=e,e}}class v{constructor(){this.zones={}}static createZone(t,e=1e-4){return class{static buildZone(t,e){const s=this._buildNavigationMesh(t,e),n={};s.vertices.forEach(t=>{t.x=p.roundNumber(t.x,2),t.y=p.roundNumber(t.y,2),t.z=p.roundNumber(t.z,2)}),n.vertices=s.vertices;const o=this._buildPolygonGroups(s);return n.groups=new Array(o.length),o.forEach((t,e)=>{const s=new Map;t.forEach((t,e)=>{s.set(t,e)});const o=new Array(t.length);t.forEach((t,e)=>{const i=[];t.neighbours.forEach(t=>i.push(s.get(t)));const h=[];t.neighbours.forEach(e=>h.push(this._getSharedVerticesInOrder(t,e)));const c=new r(0,0,0);c.add(n.vertices[t.vertexIds[0]]),c.add(n.vertices[t.vertexIds[1]]),c.add(n.vertices[t.vertexIds[2]]),c.divideScalar(3),c.x=p.roundNumber(c.x,2),c.y=p.roundNumber(c.y,2),c.z=p.roundNumber(c.z,2),o[e]={id:e,neighbours:i,vertexIds:t.vertexIds,centroid:c,portals:h}}),n.groups[e]=o}),n}static _buildNavigationMesh(t,e){return t=p.mergeVertices(t,e),this._buildPolygonsFromGeometry(t)}static _spreadGroupId(t){let e=new Set([t]);for(;e.size>0;){const r=e;e=new Set,r.forEach(r=>{r.group=t.group,r.neighbours.forEach(t=>{void 0===t.group&&e.add(t)})})}}static _buildPolygonGroups(t){const e=[];return t.polygons.forEach(t=>{void 0!==t.group?e[t.group].push(t):(t.group=e.length,this._spreadGroupId(t),e.push([t]))}),e}static _buildPolygonNeighbours(t,e){const r=new Set,s=e[t.vertexIds[1]],n=e[t.vertexIds[2]];return e[t.vertexIds[0]].forEach(e=>{e!==t&&(s.includes(e)||n.includes(e))&&r.add(e)}),s.forEach(e=>{e!==t&&n.includes(e)&&r.add(e)}),r}static _buildPolygonsFromGeometry(t){const e=[],s=[],n=t.attributes.position,o=t.index,i=[];for(let t=0;t<n.count;t++)s.push((new r).fromBufferAttribute(n,t)),i[t]=[];for(let r=0;r<t.index.count;r+=3){const t=o.getX(r),s=o.getX(r+1),n=o.getX(r+2),h={vertexIds:[t,s,n],neighbours:null};e.push(h),i[t].push(h),i[s].push(h),i[n].push(h)}return e.forEach(t=>{t.neighbours=this._buildPolygonNeighbours(t,i)}),{polygons:e,vertices:s}}static _getSharedVerticesInOrder(t,e){const r=t.vertexIds,s=r[0],n=r[1],o=r[2],i=e.vertexIds,h=i.includes(s),c=i.includes(n),a=i.includes(o);return h&&c&&a?Array.from(r):h&&c?[s,n]:c&&a?[n,o]:h&&a?[o,s]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])}}.buildZone(t,e)}setZoneData(t,e){this.zones[t]=e}getRandomNode(t,e,s,n){if(!this.zones[t])return new r;s=s||null,n=n||0;const o=[];return this.zones[t].groups[e].forEach(t=>{s&&n?p.distanceToSquared(s,t.centroid)<n*n&&o.push(t.centroid):o.push(t.centroid)}),p.sample(o)||new r}getClosestNode(t,e,r,s=!1){const n=this.zones[e].vertices;let o=null,i=Infinity;return this.zones[e].groups[r].forEach(e=>{const r=p.distanceToSquared(e.centroid,t);r<i&&(!s||p.isVectorInPolygon(t,e,n))&&(o=e,i=r)}),o}findPath(t,e,s,n){const o=this.zones[s].groups[n],i=this.zones[s].vertices,h=this.getClosestNode(t,s,n,!0),c=this.getClosestNode(e,s,n,!0);if(!h||!c)return null;const a=class{static init(t){for(let e=0;e<t.length;e++){const r=t[e];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}}static cleanUp(t){for(let e=0;e<t.length;e++){const r=t[e];delete r.f,delete r.g,delete r.h,delete r.cost,delete r.visited,delete r.closed,delete r.parent}}static heap(){return new g(function(t){return t.f})}static search(t,e,r){this.init(t);const s=this.heap();for(s.push(e);s.size()>0;){const e=s.pop();if(e===r){let t=e;const r=[];for(;t.parent;)r.push(t),t=t.parent;return this.cleanUp(r),r.reverse()}e.closed=!0;const n=this.neighbours(t,e);for(let t=0,o=n.length;t<o;t++){const o=n[t];if(o.closed)continue;const i=e.g+o.cost,h=o.visited;if(!h||i<o.g){if(o.visited=!0,o.parent=e,!o.centroid||!r.centroid)throw new Error("Unexpected state");o.h=o.h||this.heuristic(o.centroid,r.centroid),o.g=i,o.f=o.g+o.h,h?s.rescoreElement(o):s.push(o)}}}return[]}static heuristic(t,e){return p.distanceToSquared(t,e)}static neighbours(t,e){const r=[];for(let s=0;s<e.neighbours.length;s++)r.push(t[e.neighbours[s]]);return r}}.search(o,h,c),u=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},l=new f;l.push(t);for(let t=0;t<a.length;t++){const e=a[t],r=a[t+1];if(r){const t=u(e,r);l.push(i[t[0]],i[t[1]])}}l.push(e),l.stringPull();const d=l.path.map(t=>new r(t.x,t.y,t.z));return d.shift(),d}}v.prototype.getGroup=function(){const t=new s;return function(e,r,s=!1){if(!this.zones[e])return null;let n=null,o=Math.pow(50,2);const i=this.zones[e];for(let e=0;e<i.groups.length;e++){const h=i.groups[e];for(const c of h){if(s&&(t.setFromCoplanarPoints(i.vertices[c.vertexIds[0]],i.vertices[c.vertexIds[1]],i.vertices[c.vertexIds[2]]),Math.abs(t.distanceToPoint(r))<.01)&&p.isPointInPoly([i.vertices[c.vertexIds[0]],i.vertices[c.vertexIds[1]],i.vertices[c.vertexIds[2]]],r))return e;const h=p.distanceToSquared(c.centroid,r);h<o&&(n=e,o=h)}}return n}}(),v.prototype.clampStep=function(){const t=new r,e=new s,o=new n,i=new r;let h,c,a=new r;return function(r,s,n,u,l,d){const p=this.zones[u].vertices,g=this.zones[u].groups[l],f=[n],v={};v[n.id]=0,h=void 0,a.set(0,0,0),c=Infinity,e.setFromCoplanarPoints(p[n.vertexIds[0]],p[n.vertexIds[1]],p[n.vertexIds[2]]),e.projectPoint(s,t),i.copy(t);for(let e=f.pop();e;e=f.pop()){o.set(p[e.vertexIds[0]],p[e.vertexIds[1]],p[e.vertexIds[2]]),o.closestPointToPoint(i,t),t.distanceToSquared(i)<c&&(h=e,a.copy(t),c=t.distanceToSquared(i));const r=v[e.id];if(!(r>2))for(let t=0;t<e.neighbours.length;t++){const s=g[e.neighbours[t]];s.id in v||(f.push(s),v[s.id]=r+1)}}return d.copy(a),h}}();const b={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()};class w extends i{constructor(){super(),this._playerMarker=new h(new c(.25,32,32),new a({color:b.PLAYER})),this._targetMarker=new h(new u(.3,.3,.3),new a({color:b.TARGET})),this._nodeMarker=new h(new u(.1,.8,.1),new a({color:b.CLOSEST_NODE})),this._stepMarker=new h(new u(.1,1,.1),new a({color:b.CLAMPED_STEP})),this._pathMarker=new i,this._pathLineMaterial=new l({color:b.PATH,linewidth:2}),this._pathPointMaterial=new a({color:b.WAYPOINT}),this._pathPointGeometry=new c(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(t=>{t.visible=!1,this.add(t)})}setPath(r){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);r=[this._playerMarker.position].concat(r);const s=new e;s.setAttribute("position",new t(new Float32Array(3*r.length),3));for(let t=0;t<r.length;t++)s.attributes.position.setXYZ(t,r[t].x,r[t].y+.2,r[t].z);this._pathMarker.add(new d(s,this._pathLineMaterial));for(let t=0;t<r.length-1;t++){const e=new h(this._pathPointGeometry,this._pathPointMaterial);e.position.copy(r[t]),e.position.y+=.2,this._pathMarker.add(e)}return this._pathMarker.visible=!0,this}setPlayerPosition(t){return this._playerMarker.position.copy(t),this._playerMarker.visible=!0,this}setTargetPosition(t){return this._targetMarker.position.copy(t),this._targetMarker.visible=!0,this}setNodePosition(t){return this._nodeMarker.position.copy(t),this._nodeMarker.visible=!0,this}setStepPosition(t){return this._stepMarker.position.copy(t),this._stepMarker.visible=!0,this}reset(){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);return this._markers.forEach(t=>{t.visible=!1}),this}}export{v as Pathfinding,w as PathfindingHelper};
//# sourceMappingURL=three-pathfinding.modern.js.map

2

dist/three-pathfinding.module.js

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

import{BufferAttribute as t,BufferGeometry as e,Vector3 as r,Plane as n,Triangle as o,Color as i,Line as s,Mesh as a,SphereBufferGeometry as u,MeshBasicMaterial as h,BoxBufferGeometry as c,Object3D as l,LineBasicMaterial as p}from"three";function f(t,e){return(f=Object.setPrototypeOf||function(t,e){return t.__proto__=e,t})(t,e)}function d(t,e){(null==e||e>t.length)&&(e=t.length);for(var r=0,n=new Array(e);r<e;r++)n[r]=t[r];return n}function v(t,e){var r;if("undefined"==typeof Symbol||null==t[Symbol.iterator]){if(Array.isArray(t)||(r=function(t,e){if(t){if("string"==typeof t)return d(t,e);var r=Object.prototype.toString.call(t).slice(8,-1);return"Object"===r&&t.constructor&&(r=t.constructor.name),"Map"===r||"Set"===r?Array.from(t):"Arguments"===r||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(r)?d(t,e):void 0}}(t))||e&&t&&"number"==typeof t.length){r&&(t=r);var n=0;return function(){return n>=t.length?{done:!0}:{done:!1,value:t[n++]}}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}return(r=t[Symbol.iterator]()).next.bind(r)}var g,b=function(){function r(){}return r.roundNumber=function(t,e){var r=Math.pow(10,e);return Math.round(t*r)/r},r.sample=function(t){return t[Math.floor(Math.random()*t.length)]},r.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},r.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},r.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))},r.triarea2=function(t,e,r){return(r.x-t.x)*(e.z-t.z)-(e.x-t.x)*(r.z-t.z)},r.vequal=function(t,e){return this.distanceToSquared(t,e)<1e-5},r.mergeVertices=function(r,n){void 0===n&&(n=1e-4),n=Math.max(n,Number.EPSILON);for(var o={},i=r.getIndex(),s=r.getAttribute("position"),a=i?i.count:s.count,u=0,h=[],c=[],l=Math.log10(1/n),p=Math.pow(10,l),f=0;f<a;f++){var d=i?i.getX(f):f,v="";v+=~~(s.getX(d)*p)+",",v+=~~(s.getY(d)*p)+",",(v+=~~(s.getZ(d)*p)+",")in o?h.push(o[v]):(c.push(s.getX(d)),c.push(s.getY(d)),c.push(s.getZ(d)),o[v]=u,h.push(u),u++)}var g=new t(new Float32Array(c),s.itemSize,s.normalized),b=new e;return b.setAttribute("position",g),b.setIndex(h),b},r}(),y=function(){function t(t){this.content=[],this.scoreFunction=t}var e=t.prototype;return e.push=function(t){this.content.push(t),this.sinkDown(this.content.length-1)},e.pop=function(){var t=this.content[0],e=this.content.pop();return this.content.length>0&&(this.content[0]=e,this.bubbleUp(0)),t},e.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))},e.size=function(){return this.content.length},e.rescoreElement=function(t){this.sinkDown(this.content.indexOf(t))},e.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}},e.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}},t}(),m=function(){function t(){}return t.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}},t.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}},t.heap=function(){return new y(function(t){return t.f})},t.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),u=0,h=a.length;u<h;u++){var c=a[u];if(!c.closed){var l=o.g+c.cost,p=c.visited;if(!p||l<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=l,c.f=c.g+c.h,p?n.rescoreElement(c):n.push(c)}}}}return[]},t.heuristic=function(t,e){return b.distanceToSquared(t,e)},t.neighbours=function(t,e){for(var r=[],n=0;n<e.neighbours.length;n++)r.push(t[e.neighbours[n]]);return r},t}(),w=function(){function t(){}return t.buildZone=function(t,e){var n=this,o=this._buildNavigationMesh(t,e),i={};o.vertices.forEach(function(t){t.x=b.roundNumber(t.x,2),t.y=b.roundNumber(t.y,2),t.z=b.roundNumber(t.z,2)}),i.vertices=o.vertices;var s=this._buildPolygonGroups(o);return i.groups=new Array(s.length),s.forEach(function(t,e){var o=new Map;t.forEach(function(t,e){o.set(t,e)});var s=new Array(t.length);t.forEach(function(t,e){var a=[];t.neighbours.forEach(function(t){return a.push(o.get(t))});var u=[];t.neighbours.forEach(function(e){return u.push(n._getSharedVerticesInOrder(t,e))});var h=new r(0,0,0);h.add(i.vertices[t.vertexIds[0]]),h.add(i.vertices[t.vertexIds[1]]),h.add(i.vertices[t.vertexIds[2]]),h.divideScalar(3),h.x=b.roundNumber(h.x,2),h.y=b.roundNumber(h.y,2),h.z=b.roundNumber(h.z,2),s[e]={id:e,neighbours:a,vertexIds:t.vertexIds,centroid:h,portals:u}}),i.groups[e]=s}),i},t._buildNavigationMesh=function(t,e){return t=b.mergeVertices(t,e),this._buildPolygonsFromGeometry(t)},t._buildPolygonGroups=function(t){var e=[],r=function t(e){e.neighbours.forEach(function(r){void 0===r.group&&(r.group=e.group,t(r))})};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},t._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},t._buildPolygonsFromGeometry=function(t){for(var e=this,n=[],o=[],i=t.attributes.position,s=t.index,a=[],u=0;u<i.count;u++)o.push((new r).fromBufferAttribute(i,u)),a[u]=[];for(var h=0;h<t.index.count;h+=3){var c=s.getX(h),l=s.getX(h+1),p=s.getX(h+2),f={vertexIds:[c,l,p],neighbours:null};n.push(f),a[c].push(f),a[l].push(f),a[p].push(f)}return n.forEach(function(t){t.neighbours=e._buildPolygonNeighbours(t,a)}),{polygons:n,vertices:o}},t._getSharedVerticesInOrder=function(t,e){var r=t.vertexIds,n=r[0],o=r[1],i=r[2],s=e.vertexIds,a=s.includes(n),u=s.includes(o),h=s.includes(i);return a&&u&&h?Array.from(r):a&&u?[n,o]:u&&h?[o,i]:a&&h?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])},t}(),x=function(){function t(){this.portals=[]}var e=t.prototype;return e.push=function(t,e){void 0===e&&(e=t),this.portals.push({left:t,right:e})},e.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 u=1;u<n.length;u++){var h=n[u].left,c=n[u].right;if(b.triarea2(t,r,c)<=0){if(!(b.vequal(t,r)||b.triarea2(t,e,c)>0)){o.push(e),e=t=e,r=t,s=i=s,a=i,u=i;continue}r=c,a=u}if(b.triarea2(t,e,h)>=0){if(!(b.vequal(t,e)||b.triarea2(t,r,h)<0)){o.push(r),e=t=r,r=t,s=i=a,a=i,u=i;continue}e=h,s=u}}return 0!==o.length&&b.vequal(o[o.length-1],n[n.length-1].left)||o.push(n[n.length-1].left),this.path=o,o},t}(),_=function(){function t(){this.zones={}}t.createZone=function(t,e){return void 0===e&&(e=1e-4),w.buildZone(t,e)};var e=t.prototype;return e.setZoneData=function(t,e){this.zones[t]=e},e.getRandomNode=function(t,e,n,o){if(!this.zones[t])return new r;n=n||null,o=o||0;var i=[];return this.zones[t].groups[e].forEach(function(t){n&&o?b.distanceToSquared(n,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),b.sample(i)||new r},e.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=b.distanceToSquared(e.centroid,t);r<s&&(!n||b.isVectorInPolygon(t,e,o))&&(i=e,s=r)}),i},e.findPath=function(t,e,n,o){var i=this.zones[n].groups[o],s=this.zones[n].vertices,a=this.getClosestNode(t,n,o,!0),u=this.getClosestNode(e,n,o,!0);if(!a||!u)return null;var h=m.search(i,a,u),c=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},l=new x;l.push(t);for(var p=0;p<h.length;p++){var f=h[p+1];if(f){var d=c(h[p],f);l.push(s[d[0]],s[d[1]])}}l.push(e),l.stringPull();var v=l.path.map(function(t){return new r(t.x,t.y,t.z)});return v.shift(),v},t}();_.prototype.getGroup=(g=new n,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,u=v(i.groups[s]);!(a=u()).done;){var h=a.value;if(r&&(g.setFromCoplanarPoints(i.vertices[h.vertexIds[0]],i.vertices[h.vertexIds[1]],i.vertices[h.vertexIds[2]]),Math.abs(g.distanceToPoint(e))<.01&&b.isPointInPoly([i.vertices[h.vertexIds[0]],i.vertices[h.vertexIds[1]],i.vertices[h.vertexIds[2]]],e)))return s;var c=b.distanceToSquared(h.centroid,e);c<o&&(n=s,o=c)}return n}),_.prototype.clampStep=function(){var t,e,i=new r,s=new n,a=new o,u=new r,h=new r;return function(r,n,o,c,l,p){var f=this.zones[c].vertices,d=this.zones[c].groups[l],v=[o],g={};g[o.id]=0,t=void 0,h.set(0,0,0),e=Infinity,s.setFromCoplanarPoints(f[o.vertexIds[0]],f[o.vertexIds[1]],f[o.vertexIds[2]]),s.projectPoint(n,i),u.copy(i);for(var b=v.pop();b;b=v.pop()){a.set(f[b.vertexIds[0]],f[b.vertexIds[1]],f[b.vertexIds[2]]),a.closestPointToPoint(u,i),i.distanceToSquared(u)<e&&(t=b,h.copy(i),e=i.distanceToSquared(u));var y=g[b.id];if(!(y>2))for(var m=0;m<b.neighbours.length;m++){var w=d[b.neighbours[m]];w.id in g||(v.push(w),g[w.id]=y+1)}}return p.copy(h),t}}();var M={PLAYER:new i(15631215).convertGammaToLinear(2.2).getHex(),TARGET:new i(14469912).convertGammaToLinear(2.2).getHex(),PATH:new i(41903).convertGammaToLinear(2.2).getHex(),WAYPOINT:new i(41903).convertGammaToLinear(2.2).getHex(),CLAMPED_STEP:new i(14472114).convertGammaToLinear(2.2).getHex(),CLOSEST_NODE:new i(4417387).convertGammaToLinear(2.2).getHex()},P=function(r){var n,o;function i(){var t;return(t=r.call(this)||this)._playerMarker=new a(new u(.25,32,32),new h({color:M.PLAYER})),t._targetMarker=new a(new c(.3,.3,.3),new h({color:M.TARGET})),t._nodeMarker=new a(new c(.1,.8,.1),new h({color:M.CLOSEST_NODE})),t._stepMarker=new a(new c(.1,1,.1),new h({color:M.CLAMPED_STEP})),t._pathMarker=new l,t._pathLineMaterial=new p({color:M.PATH,linewidth:2}),t._pathPointMaterial=new h({color:M.WAYPOINT}),t._pathPointGeometry=new u(.08),t._markers=[t._playerMarker,t._targetMarker,t._nodeMarker,t._stepMarker,t._pathMarker],t._markers.forEach(function(e){e.visible=!1,t.add(e)}),t}o=r,(n=i).prototype=Object.create(o.prototype),n.prototype.constructor=n,f(n,o);var d=i.prototype;return d.setPath=function(r){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);r=[this._playerMarker.position].concat(r);var n=new e;n.setAttribute("position",new t(new Float32Array(3*r.length),3));for(var o=0;o<r.length;o++)n.attributes.position.setXYZ(o,r[o].x,r[o].y+.2,r[o].z);this._pathMarker.add(new s(n,this._pathLineMaterial));for(var i=0;i<r.length-1;i++){var u=new a(this._pathPointGeometry,this._pathPointMaterial);u.position.copy(r[i]),u.position.y+=.2,this._pathMarker.add(u)}return this._pathMarker.visible=!0,this},d.setPlayerPosition=function(t){return this._playerMarker.position.copy(t),this._playerMarker.visible=!0,this},d.setTargetPosition=function(t){return this._targetMarker.position.copy(t),this._targetMarker.visible=!0,this},d.setNodePosition=function(t){return this._nodeMarker.position.copy(t),this._nodeMarker.visible=!0,this},d.setStepPosition=function(t){return this._stepMarker.position.copy(t),this._stepMarker.visible=!0,this},d.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},i}(l);export{_ as Pathfinding,P as PathfindingHelper};
import{BufferAttribute as t,BufferGeometry as e,Vector3 as r,Plane as n,Triangle as o,Color as i,Line as s,Mesh as a,SphereBufferGeometry as u,MeshBasicMaterial as h,BoxBufferGeometry as c,Object3D as l,LineBasicMaterial as p}from"three";function d(t,e){(null==e||e>t.length)&&(e=t.length);for(var r=0,n=new Array(e);r<e;r++)n[r]=t[r];return n}function f(t,e){var r;if("undefined"==typeof Symbol||null==t[Symbol.iterator]){if(Array.isArray(t)||(r=function(t,e){if(t){if("string"==typeof t)return d(t,e);var r=Object.prototype.toString.call(t).slice(8,-1);return"Object"===r&&t.constructor&&(r=t.constructor.name),"Map"===r||"Set"===r?Array.from(t):"Arguments"===r||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(r)?d(t,e):void 0}}(t))||e&&t&&"number"==typeof t.length){r&&(t=r);var n=0;return function(){return n>=t.length?{done:!0}:{done:!1,value:t[n++]}}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}return(r=t[Symbol.iterator]()).next.bind(r)}var v,g=function(){function r(){}return r.roundNumber=function(t,e){var r=Math.pow(10,e);return Math.round(t*r)/r},r.sample=function(t){return t[Math.floor(Math.random()*t.length)]},r.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},r.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},r.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))},r.triarea2=function(t,e,r){return(r.x-t.x)*(e.z-t.z)-(e.x-t.x)*(r.z-t.z)},r.vequal=function(t,e){return this.distanceToSquared(t,e)<1e-5},r.mergeVertices=function(r,n){void 0===n&&(n=1e-4),n=Math.max(n,Number.EPSILON);for(var o={},i=r.getIndex(),s=r.getAttribute("position"),a=i?i.count:s.count,u=0,h=[],c=[],l=Math.log10(1/n),p=Math.pow(10,l),d=0;d<a;d++){var f=i?i.getX(d):d,v="";v+=~~(s.getX(f)*p)+",",v+=~~(s.getY(f)*p)+",",(v+=~~(s.getZ(f)*p)+",")in o?h.push(o[v]):(c.push(s.getX(f)),c.push(s.getY(f)),c.push(s.getZ(f)),o[v]=u,h.push(u),u++)}var g=new t(new Float32Array(c),s.itemSize,s.normalized),b=new e;return b.setAttribute("position",g),b.setIndex(h),b},r}(),b=function(){function t(t){this.content=[],this.scoreFunction=t}var e=t.prototype;return e.push=function(t){this.content.push(t),this.sinkDown(this.content.length-1)},e.pop=function(){var t=this.content[0],e=this.content.pop();return this.content.length>0&&(this.content[0]=e,this.bubbleUp(0)),t},e.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))},e.size=function(){return this.content.length},e.rescoreElement=function(t){this.sinkDown(this.content.indexOf(t))},e.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}},e.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}},t}(),y=function(){function t(){}return t.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}},t.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}},t.heap=function(){return new b(function(t){return t.f})},t.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),u=0,h=a.length;u<h;u++){var c=a[u];if(!c.closed){var l=o.g+c.cost,p=c.visited;if(!p||l<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=l,c.f=c.g+c.h,p?n.rescoreElement(c):n.push(c)}}}}return[]},t.heuristic=function(t,e){return g.distanceToSquared(t,e)},t.neighbours=function(t,e){for(var r=[],n=0;n<e.neighbours.length;n++)r.push(t[e.neighbours[n]]);return r},t}(),m=function(){function t(){}return t.buildZone=function(t,e){var n=this,o=this._buildNavigationMesh(t,e),i={};o.vertices.forEach(function(t){t.x=g.roundNumber(t.x,2),t.y=g.roundNumber(t.y,2),t.z=g.roundNumber(t.z,2)}),i.vertices=o.vertices;var s=this._buildPolygonGroups(o);return i.groups=new Array(s.length),s.forEach(function(t,e){var o=new Map;t.forEach(function(t,e){o.set(t,e)});var s=new Array(t.length);t.forEach(function(t,e){var a=[];t.neighbours.forEach(function(t){return a.push(o.get(t))});var u=[];t.neighbours.forEach(function(e){return u.push(n._getSharedVerticesInOrder(t,e))});var h=new r(0,0,0);h.add(i.vertices[t.vertexIds[0]]),h.add(i.vertices[t.vertexIds[1]]),h.add(i.vertices[t.vertexIds[2]]),h.divideScalar(3),h.x=g.roundNumber(h.x,2),h.y=g.roundNumber(h.y,2),h.z=g.roundNumber(h.z,2),s[e]={id:e,neighbours:a,vertexIds:t.vertexIds,centroid:h,portals:u}}),i.groups[e]=s}),i},t._buildNavigationMesh=function(t,e){return t=g.mergeVertices(t,e),this._buildPolygonsFromGeometry(t)},t._spreadGroupId=function(t){for(var e=new Set([t]);e.size>0;){var r=e;e=new Set,r.forEach(function(r){r.group=t.group,r.neighbours.forEach(function(t){void 0===t.group&&e.add(t)})})}},t._buildPolygonGroups=function(t){var e=this,r=[];return t.polygons.forEach(function(t){void 0!==t.group?r[t.group].push(t):(t.group=r.length,e._spreadGroupId(t),r.push([t]))}),r},t._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},t._buildPolygonsFromGeometry=function(t){for(var e=this,n=[],o=[],i=t.attributes.position,s=t.index,a=[],u=0;u<i.count;u++)o.push((new r).fromBufferAttribute(i,u)),a[u]=[];for(var h=0;h<t.index.count;h+=3){var c=s.getX(h),l=s.getX(h+1),p=s.getX(h+2),d={vertexIds:[c,l,p],neighbours:null};n.push(d),a[c].push(d),a[l].push(d),a[p].push(d)}return n.forEach(function(t){t.neighbours=e._buildPolygonNeighbours(t,a)}),{polygons:n,vertices:o}},t._getSharedVerticesInOrder=function(t,e){var r=t.vertexIds,n=r[0],o=r[1],i=r[2],s=e.vertexIds,a=s.includes(n),u=s.includes(o),h=s.includes(i);return a&&u&&h?Array.from(r):a&&u?[n,o]:u&&h?[o,i]:a&&h?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])},t}(),w=function(){function t(){this.portals=[]}var e=t.prototype;return e.push=function(t,e){void 0===e&&(e=t),this.portals.push({left:t,right:e})},e.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 u=1;u<n.length;u++){var h=n[u].left,c=n[u].right;if(g.triarea2(t,r,c)<=0){if(!(g.vequal(t,r)||g.triarea2(t,e,c)>0)){o.push(e),e=t=e,r=t,s=i=s,a=i,u=i;continue}r=c,a=u}if(g.triarea2(t,e,h)>=0){if(!(g.vequal(t,e)||g.triarea2(t,r,h)<0)){o.push(r),e=t=r,r=t,s=i=a,a=i,u=i;continue}e=h,s=u}}return 0!==o.length&&g.vequal(o[o.length-1],n[n.length-1].left)||o.push(n[n.length-1].left),this.path=o,o},t}(),_=function(){function t(){this.zones={}}t.createZone=function(t,e){return void 0===e&&(e=1e-4),m.buildZone(t,e)};var e=t.prototype;return e.setZoneData=function(t,e){this.zones[t]=e},e.getRandomNode=function(t,e,n,o){if(!this.zones[t])return new r;n=n||null,o=o||0;var i=[];return this.zones[t].groups[e].forEach(function(t){n&&o?g.distanceToSquared(n,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),g.sample(i)||new r},e.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=g.distanceToSquared(e.centroid,t);r<s&&(!n||g.isVectorInPolygon(t,e,o))&&(i=e,s=r)}),i},e.findPath=function(t,e,n,o){var i=this.zones[n].groups[o],s=this.zones[n].vertices,a=this.getClosestNode(t,n,o,!0),u=this.getClosestNode(e,n,o,!0);if(!a||!u)return null;var h=y.search(i,a,u),c=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},l=new w;l.push(t);for(var p=0;p<h.length;p++){var d=h[p+1];if(d){var f=c(h[p],d);l.push(s[f[0]],s[f[1]])}}l.push(e),l.stringPull();var v=l.path.map(function(t){return new r(t.x,t.y,t.z)});return v.shift(),v},t}();_.prototype.getGroup=(v=new n,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,u=f(i.groups[s]);!(a=u()).done;){var h=a.value;if(r&&(v.setFromCoplanarPoints(i.vertices[h.vertexIds[0]],i.vertices[h.vertexIds[1]],i.vertices[h.vertexIds[2]]),Math.abs(v.distanceToPoint(e))<.01&&g.isPointInPoly([i.vertices[h.vertexIds[0]],i.vertices[h.vertexIds[1]],i.vertices[h.vertexIds[2]]],e)))return s;var c=g.distanceToSquared(h.centroid,e);c<o&&(n=s,o=c)}return n}),_.prototype.clampStep=function(){var t,e,i=new r,s=new n,a=new o,u=new r,h=new r;return function(r,n,o,c,l,p){var d=this.zones[c].vertices,f=this.zones[c].groups[l],v=[o],g={};g[o.id]=0,t=void 0,h.set(0,0,0),e=Infinity,s.setFromCoplanarPoints(d[o.vertexIds[0]],d[o.vertexIds[1]],d[o.vertexIds[2]]),s.projectPoint(n,i),u.copy(i);for(var b=v.pop();b;b=v.pop()){a.set(d[b.vertexIds[0]],d[b.vertexIds[1]],d[b.vertexIds[2]]),a.closestPointToPoint(u,i),i.distanceToSquared(u)<e&&(t=b,h.copy(i),e=i.distanceToSquared(u));var y=g[b.id];if(!(y>2))for(var m=0;m<b.neighbours.length;m++){var w=f[b.neighbours[m]];w.id in g||(v.push(w),g[w.id]=y+1)}}return p.copy(h),t}}();var x={PLAYER:new i(15631215).convertGammaToLinear(2.2).getHex(),TARGET:new i(14469912).convertGammaToLinear(2.2).getHex(),PATH:new i(41903).convertGammaToLinear(2.2).getHex(),WAYPOINT:new i(41903).convertGammaToLinear(2.2).getHex(),CLAMPED_STEP:new i(14472114).convertGammaToLinear(2.2).getHex(),CLOSEST_NODE:new i(4417387).convertGammaToLinear(2.2).getHex()},M=function(r){var n,o;function i(){var t;return(t=r.call(this)||this)._playerMarker=new a(new u(.25,32,32),new h({color:x.PLAYER})),t._targetMarker=new a(new c(.3,.3,.3),new h({color:x.TARGET})),t._nodeMarker=new a(new c(.1,.8,.1),new h({color:x.CLOSEST_NODE})),t._stepMarker=new a(new c(.1,1,.1),new h({color:x.CLAMPED_STEP})),t._pathMarker=new l,t._pathLineMaterial=new p({color:x.PATH,linewidth:2}),t._pathPointMaterial=new h({color:x.WAYPOINT}),t._pathPointGeometry=new u(.08),t._markers=[t._playerMarker,t._targetMarker,t._nodeMarker,t._stepMarker,t._pathMarker],t._markers.forEach(function(e){e.visible=!1,t.add(e)}),t}o=r,(n=i).prototype=Object.create(o.prototype),n.prototype.constructor=n,n.__proto__=o;var d=i.prototype;return d.setPath=function(r){for(;this._pathMarker.children.length;)this._pathMarker.children[0].visible=!1,this._pathMarker.remove(this._pathMarker.children[0]);r=[this._playerMarker.position].concat(r);var n=new e;n.setAttribute("position",new t(new Float32Array(3*r.length),3));for(var o=0;o<r.length;o++)n.attributes.position.setXYZ(o,r[o].x,r[o].y+.2,r[o].z);this._pathMarker.add(new s(n,this._pathLineMaterial));for(var i=0;i<r.length-1;i++){var u=new a(this._pathPointGeometry,this._pathPointMaterial);u.position.copy(r[i]),u.position.y+=.2,this._pathMarker.add(u)}return this._pathMarker.visible=!0,this},d.setPlayerPosition=function(t){return this._playerMarker.position.copy(t),this._playerMarker.visible=!0,this},d.setTargetPosition=function(t){return this._targetMarker.position.copy(t),this._targetMarker.visible=!0,this},d.setNodePosition=function(t){return this._nodeMarker.position.copy(t),this._nodeMarker.visible=!0,this},d.setStepPosition=function(t){return this._stepMarker.position.copy(t),this._stepMarker.visible=!0,this},d.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},i}(l);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||self).threePathfinding={},e.THREE)}(this,function(e,t){function r(e,t){return(r=Object.setPrototypeOf||function(e,t){return e.__proto__=t,e})(e,t)}function n(e,t){(null==t||t>e.length)&&(t=e.length);for(var r=0,n=new Array(t);r<t;r++)n[r]=e[r];return n}function o(e,t){var r;if("undefined"==typeof Symbol||null==e[Symbol.iterator]){if(Array.isArray(e)||(r=function(e,t){if(e){if("string"==typeof e)return n(e,t);var r=Object.prototype.toString.call(e).slice(8,-1);return"Object"===r&&e.constructor&&(r=e.constructor.name),"Map"===r||"Set"===r?Array.from(e):"Arguments"===r||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(r)?n(e,t):void 0}}(e))||t&&e&&"number"==typeof e.length){r&&(e=r);var o=0;return function(){return o>=e.length?{done:!0}:{done:!1,value:e[o++]}}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}return(r=e[Symbol.iterator]()).next.bind(r)}var i,s=function(){function e(){}return e.roundNumber=function(e,t){var r=Math.pow(10,t);return Math.round(e*r)/r},e.sample=function(e){return e[Math.floor(Math.random()*e.length)]},e.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},e.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},e.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))},e.triarea2=function(e,t,r){return(r.x-e.x)*(t.z-e.z)-(t.x-e.x)*(r.z-e.z)},e.vequal=function(e,t){return this.distanceToSquared(e,t)<1e-5},e.mergeVertices=function(e,r){void 0===r&&(r=1e-4),r=Math.max(r,Number.EPSILON);for(var n={},o=e.getIndex(),i=e.getAttribute("position"),s=o?o.count:i.count,a=0,u=[],h=[],c=Math.log10(1/r),l=Math.pow(10,c),f=0;f<s;f++){var p=o?o.getX(f):f,d="";d+=~~(i.getX(p)*l)+",",d+=~~(i.getY(p)*l)+",",(d+=~~(i.getZ(p)*l)+",")in n?u.push(n[d]):(h.push(i.getX(p)),h.push(i.getY(p)),h.push(i.getZ(p)),n[d]=a,u.push(a),a++)}var v=new t.BufferAttribute(new Float32Array(h),i.itemSize,i.normalized),g=new t.BufferGeometry;return g.setAttribute("position",v),g.setIndex(u),g},e}(),a=function(){function e(e){this.content=[],this.scoreFunction=e}var t=e.prototype;return t.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},t.pop=function(){var e=this.content[0],t=this.content.pop();return this.content.length>0&&(this.content[0]=t,this.bubbleUp(0)),e},t.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))},t.size=function(){return this.content.length},t.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},t.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}},t.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}},e}(),u=function(){function e(){}return e.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}},e.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}},e.heap=function(){return new a(function(e){return e.f})},e.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),u=0,h=a.length;u<h;u++){var c=a[u];if(!c.closed){var l=o.g+c.cost,f=c.visited;if(!f||l<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=l,c.f=c.g+c.h,f?n.rescoreElement(c):n.push(c)}}}}return[]},e.heuristic=function(e,t){return s.distanceToSquared(e,t)},e.neighbours=function(e,t){for(var r=[],n=0;n<t.neighbours.length;n++)r.push(e[t.neighbours[n]]);return r},e}(),h=function(){function e(){}return e.buildZone=function(e,r){var n=this,o=this._buildNavigationMesh(e,r),i={};o.vertices.forEach(function(e){e.x=s.roundNumber(e.x,2),e.y=s.roundNumber(e.y,2),e.z=s.roundNumber(e.z,2)}),i.vertices=o.vertices;var a=this._buildPolygonGroups(o);return i.groups=new Array(a.length),a.forEach(function(e,r){var o=new Map;e.forEach(function(e,t){o.set(e,t)});var a=new Array(e.length);e.forEach(function(e,r){var u=[];e.neighbours.forEach(function(e){return u.push(o.get(e))});var h=[];e.neighbours.forEach(function(t){return h.push(n._getSharedVerticesInOrder(e,t))});var c=new t.Vector3(0,0,0);c.add(i.vertices[e.vertexIds[0]]),c.add(i.vertices[e.vertexIds[1]]),c.add(i.vertices[e.vertexIds[2]]),c.divideScalar(3),c.x=s.roundNumber(c.x,2),c.y=s.roundNumber(c.y,2),c.z=s.roundNumber(c.z,2),a[r]={id:r,neighbours:u,vertexIds:e.vertexIds,centroid:c,portals:h}}),i.groups[r]=a}),i},e._buildNavigationMesh=function(e,t){return e=s.mergeVertices(e,t),this._buildPolygonsFromGeometry(e)},e._buildPolygonGroups=function(e){var t=[],r=function e(t){t.neighbours.forEach(function(r){void 0===r.group&&(r.group=t.group,e(r))})};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},e._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},e._buildPolygonsFromGeometry=function(e){for(var r=this,n=[],o=[],i=e.attributes.position,s=e.index,a=[],u=0;u<i.count;u++)o.push((new t.Vector3).fromBufferAttribute(i,u)),a[u]=[];for(var h=0;h<e.index.count;h+=3){var c=s.getX(h),l=s.getX(h+1),f=s.getX(h+2),p={vertexIds:[c,l,f],neighbours:null};n.push(p),a[c].push(p),a[l].push(p),a[f].push(p)}return n.forEach(function(e){e.neighbours=r._buildPolygonNeighbours(e,a)}),{polygons:n,vertices:o}},e._getSharedVerticesInOrder=function(e,t){var r=e.vertexIds,n=r[0],o=r[1],i=r[2],s=t.vertexIds,a=s.includes(n),u=s.includes(o),h=s.includes(i);return a&&u&&h?Array.from(r):a&&u?[n,o]:u&&h?[o,i]:a&&h?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])},e}(),c=function(){function e(){this.portals=[]}var t=e.prototype;return t.push=function(e,t){void 0===t&&(t=e),this.portals.push({left:e,right:t})},t.stringPull=function(){var e,t,r,n=this.portals,o=[],i=0,a=0,u=0;t=n[0].left,r=n[0].right,o.push(e=n[0].left);for(var h=1;h<n.length;h++){var c=n[h].left,l=n[h].right;if(s.triarea2(e,r,l)<=0){if(!(s.vequal(e,r)||s.triarea2(e,t,l)>0)){o.push(t),t=e=t,r=e,a=i=a,u=i,h=i;continue}r=l,u=h}if(s.triarea2(e,t,c)>=0){if(!(s.vequal(e,t)||s.triarea2(e,r,c)<0)){o.push(r),t=e=r,r=e,a=i=u,u=i,h=i;continue}t=c,a=h}}return 0!==o.length&&s.vequal(o[o.length-1],n[n.length-1].left)||o.push(n[n.length-1].left),this.path=o,o},e}(),l=function(){function e(){this.zones={}}e.createZone=function(e,t){return void 0===t&&(t=1e-4),h.buildZone(e,t)};var r=e.prototype;return r.setZoneData=function(e,t){this.zones[e]=t},r.getRandomNode=function(e,r,n,o){if(!this.zones[e])return new t.Vector3;n=n||null,o=o||0;var i=[];return this.zones[e].groups[r].forEach(function(e){n&&o?s.distanceToSquared(n,e.centroid)<o*o&&i.push(e.centroid):i.push(e.centroid)}),s.sample(i)||new t.Vector3},r.getClosestNode=function(e,t,r,n){void 0===n&&(n=!1);var o=this.zones[t].vertices,i=null,a=Infinity;return this.zones[t].groups[r].forEach(function(t){var r=s.distanceToSquared(t.centroid,e);r<a&&(!n||s.isVectorInPolygon(e,t,o))&&(i=t,a=r)}),i},r.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 l=u.search(i,a,h),f=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},p=new c;p.push(e);for(var d=0;d<l.length;d++){var v=l[d+1];if(v){var g=f(l[d],v);p.push(s[g[0]],s[g[1]])}}p.push(r),p.stringPull();var y=p.path.map(function(e){return new t.Vector3(e.x,e.y,e.z)});return y.shift(),y},e}();l.prototype.getGroup=(i=new t.Plane,function(e,t,r){if(void 0===r&&(r=!1),!this.zones[e])return null;for(var n=null,a=Math.pow(50,2),u=this.zones[e],h=0;h<u.groups.length;h++)for(var c,l=o(u.groups[h]);!(c=l()).done;){var f=c.value;if(r&&(i.setFromCoplanarPoints(u.vertices[f.vertexIds[0]],u.vertices[f.vertexIds[1]],u.vertices[f.vertexIds[2]]),Math.abs(i.distanceToPoint(t))<.01&&s.isPointInPoly([u.vertices[f.vertexIds[0]],u.vertices[f.vertexIds[1]],u.vertices[f.vertexIds[2]]],t)))return h;var p=s.distanceToSquared(f.centroid,t);p<a&&(n=h,a=p)}return n}),l.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,u,h,c,l,f){var p=this.zones[c].vertices,d=this.zones[c].groups[l],v=[h],g={};g[h.id]=0,e=void 0,a.set(0,0,0),r=Infinity,o.setFromCoplanarPoints(p[h.vertexIds[0]],p[h.vertexIds[1]],p[h.vertexIds[2]]),o.projectPoint(u,n),s.copy(n);for(var y=v.pop();y;y=v.pop()){i.set(p[y.vertexIds[0]],p[y.vertexIds[1]],p[y.vertexIds[2]]),i.closestPointToPoint(s,n),n.distanceToSquared(s)<r&&(e=y,a.copy(n),r=n.distanceToSquared(s));var b=g[y.id];if(!(b>2))for(var m=0;m<y.neighbours.length;m++){var M=d[y.neighbours[m]];M.id in g||(v.push(M),g[M.id]=b+1)}}return f.copy(a),e}}();var f={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()},p=function(e){var n,o;function i(){var r;return(r=e.call(this)||this)._playerMarker=new t.Mesh(new t.SphereBufferGeometry(.25,32,32),new t.MeshBasicMaterial({color:f.PLAYER})),r._targetMarker=new t.Mesh(new t.BoxBufferGeometry(.3,.3,.3),new t.MeshBasicMaterial({color:f.TARGET})),r._nodeMarker=new t.Mesh(new t.BoxBufferGeometry(.1,.8,.1),new t.MeshBasicMaterial({color:f.CLOSEST_NODE})),r._stepMarker=new t.Mesh(new t.BoxBufferGeometry(.1,1,.1),new t.MeshBasicMaterial({color:f.CLAMPED_STEP})),r._pathMarker=new t.Object3D,r._pathLineMaterial=new t.LineBasicMaterial({color:f.PATH,linewidth:2}),r._pathPointMaterial=new t.MeshBasicMaterial({color:f.WAYPOINT}),r._pathPointGeometry=new t.SphereBufferGeometry(.08),r._markers=[r._playerMarker,r._targetMarker,r._nodeMarker,r._stepMarker,r._pathMarker],r._markers.forEach(function(e){e.visible=!1,r.add(e)}),r}o=e,(n=i).prototype=Object.create(o.prototype),n.prototype.constructor=n,r(n,o);var s=i.prototype;return s.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);var r=new t.BufferGeometry;r.setAttribute("position",new t.BufferAttribute(new Float32Array(3*e.length),3));for(var n=0;n<e.length;n++)r.attributes.position.setXYZ(n,e[n].x,e[n].y+.2,e[n].z);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},s.setPlayerPosition=function(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this},s.setTargetPosition=function(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this},s.setNodePosition=function(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this},s.setStepPosition=function(e){return this._stepMarker.position.copy(e),this._stepMarker.visible=!0,this},s.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},i}(t.Object3D);e.Pathfinding=l,e.PathfindingHelper=p});
!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("three")):"function"==typeof define&&define.amd?define(["exports","three"],t):t((e||self).threePathfinding={},e.THREE)}(this,function(e,t){function r(e,t){(null==t||t>e.length)&&(t=e.length);for(var r=0,n=new Array(t);r<t;r++)n[r]=e[r];return n}function n(e,t){var n;if("undefined"==typeof Symbol||null==e[Symbol.iterator]){if(Array.isArray(e)||(n=function(e,t){if(e){if("string"==typeof e)return r(e,t);var n=Object.prototype.toString.call(e).slice(8,-1);return"Object"===n&&e.constructor&&(n=e.constructor.name),"Map"===n||"Set"===n?Array.from(e):"Arguments"===n||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)?r(e,t):void 0}}(e))||t&&e&&"number"==typeof e.length){n&&(e=n);var o=0;return function(){return o>=e.length?{done:!0}:{done:!1,value:e[o++]}}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}return(n=e[Symbol.iterator]()).next.bind(n)}var o,i=function(){function e(){}return e.roundNumber=function(e,t){var r=Math.pow(10,t);return Math.round(e*r)/r},e.sample=function(e){return e[Math.floor(Math.random()*e.length)]},e.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},e.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},e.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))},e.triarea2=function(e,t,r){return(r.x-e.x)*(t.z-e.z)-(t.x-e.x)*(r.z-e.z)},e.vequal=function(e,t){return this.distanceToSquared(e,t)<1e-5},e.mergeVertices=function(e,r){void 0===r&&(r=1e-4),r=Math.max(r,Number.EPSILON);for(var n={},o=e.getIndex(),i=e.getAttribute("position"),s=o?o.count:i.count,a=0,u=[],h=[],c=Math.log10(1/r),l=Math.pow(10,c),f=0;f<s;f++){var p=o?o.getX(f):f,d="";d+=~~(i.getX(p)*l)+",",d+=~~(i.getY(p)*l)+",",(d+=~~(i.getZ(p)*l)+",")in n?u.push(n[d]):(h.push(i.getX(p)),h.push(i.getY(p)),h.push(i.getZ(p)),n[d]=a,u.push(a),a++)}var v=new t.BufferAttribute(new Float32Array(h),i.itemSize,i.normalized),g=new t.BufferGeometry;return g.setAttribute("position",v),g.setIndex(u),g},e}(),s=function(){function e(e){this.content=[],this.scoreFunction=e}var t=e.prototype;return t.push=function(e){this.content.push(e),this.sinkDown(this.content.length-1)},t.pop=function(){var e=this.content[0],t=this.content.pop();return this.content.length>0&&(this.content[0]=t,this.bubbleUp(0)),e},t.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))},t.size=function(){return this.content.length},t.rescoreElement=function(e){this.sinkDown(this.content.indexOf(e))},t.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}},t.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}},e}(),a=function(){function e(){}return e.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}},e.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}},e.heap=function(){return new s(function(e){return e.f})},e.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),u=0,h=a.length;u<h;u++){var c=a[u];if(!c.closed){var l=o.g+c.cost,f=c.visited;if(!f||l<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=l,c.f=c.g+c.h,f?n.rescoreElement(c):n.push(c)}}}}return[]},e.heuristic=function(e,t){return i.distanceToSquared(e,t)},e.neighbours=function(e,t){for(var r=[],n=0;n<t.neighbours.length;n++)r.push(e[t.neighbours[n]]);return r},e}(),u=function(){function e(){}return e.buildZone=function(e,r){var n=this,o=this._buildNavigationMesh(e,r),s={};o.vertices.forEach(function(e){e.x=i.roundNumber(e.x,2),e.y=i.roundNumber(e.y,2),e.z=i.roundNumber(e.z,2)}),s.vertices=o.vertices;var a=this._buildPolygonGroups(o);return s.groups=new Array(a.length),a.forEach(function(e,r){var o=new Map;e.forEach(function(e,t){o.set(e,t)});var a=new Array(e.length);e.forEach(function(e,r){var u=[];e.neighbours.forEach(function(e){return u.push(o.get(e))});var h=[];e.neighbours.forEach(function(t){return h.push(n._getSharedVerticesInOrder(e,t))});var c=new t.Vector3(0,0,0);c.add(s.vertices[e.vertexIds[0]]),c.add(s.vertices[e.vertexIds[1]]),c.add(s.vertices[e.vertexIds[2]]),c.divideScalar(3),c.x=i.roundNumber(c.x,2),c.y=i.roundNumber(c.y,2),c.z=i.roundNumber(c.z,2),a[r]={id:r,neighbours:u,vertexIds:e.vertexIds,centroid:c,portals:h}}),s.groups[r]=a}),s},e._buildNavigationMesh=function(e,t){return e=i.mergeVertices(e,t),this._buildPolygonsFromGeometry(e)},e._spreadGroupId=function(e){for(var t=new Set([e]);t.size>0;){var r=t;t=new Set,r.forEach(function(r){r.group=e.group,r.neighbours.forEach(function(e){void 0===e.group&&t.add(e)})})}},e._buildPolygonGroups=function(e){var t=this,r=[];return e.polygons.forEach(function(e){void 0!==e.group?r[e.group].push(e):(e.group=r.length,t._spreadGroupId(e),r.push([e]))}),r},e._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},e._buildPolygonsFromGeometry=function(e){for(var r=this,n=[],o=[],i=e.attributes.position,s=e.index,a=[],u=0;u<i.count;u++)o.push((new t.Vector3).fromBufferAttribute(i,u)),a[u]=[];for(var h=0;h<e.index.count;h+=3){var c=s.getX(h),l=s.getX(h+1),f=s.getX(h+2),p={vertexIds:[c,l,f],neighbours:null};n.push(p),a[c].push(p),a[l].push(p),a[f].push(p)}return n.forEach(function(e){e.neighbours=r._buildPolygonNeighbours(e,a)}),{polygons:n,vertices:o}},e._getSharedVerticesInOrder=function(e,t){var r=e.vertexIds,n=r[0],o=r[1],i=r[2],s=t.vertexIds,a=s.includes(n),u=s.includes(o),h=s.includes(i);return a&&u&&h?Array.from(r):a&&u?[n,o]:u&&h?[o,i]:a&&h?[i,n]:(console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found."),[])},e}(),h=function(){function e(){this.portals=[]}var t=e.prototype;return t.push=function(e,t){void 0===t&&(t=e),this.portals.push({left:e,right:t})},t.stringPull=function(){var e,t,r,n=this.portals,o=[],s=0,a=0,u=0;t=n[0].left,r=n[0].right,o.push(e=n[0].left);for(var h=1;h<n.length;h++){var c=n[h].left,l=n[h].right;if(i.triarea2(e,r,l)<=0){if(!(i.vequal(e,r)||i.triarea2(e,t,l)>0)){o.push(t),t=e=t,r=e,a=s=a,u=s,h=s;continue}r=l,u=h}if(i.triarea2(e,t,c)>=0){if(!(i.vequal(e,t)||i.triarea2(e,r,c)<0)){o.push(r),t=e=r,r=e,a=s=u,u=s,h=s;continue}t=c,a=h}}return 0!==o.length&&i.vequal(o[o.length-1],n[n.length-1].left)||o.push(n[n.length-1].left),this.path=o,o},e}(),c=function(){function e(){this.zones={}}e.createZone=function(e,t){return void 0===t&&(t=1e-4),u.buildZone(e,t)};var r=e.prototype;return r.setZoneData=function(e,t){this.zones[e]=t},r.getRandomNode=function(e,r,n,o){if(!this.zones[e])return new t.Vector3;n=n||null,o=o||0;var s=[];return this.zones[e].groups[r].forEach(function(e){n&&o?i.distanceToSquared(n,e.centroid)<o*o&&s.push(e.centroid):s.push(e.centroid)}),i.sample(s)||new t.Vector3},r.getClosestNode=function(e,t,r,n){void 0===n&&(n=!1);var o=this.zones[t].vertices,s=null,a=Infinity;return this.zones[t].groups[r].forEach(function(t){var r=i.distanceToSquared(t.centroid,e);r<a&&(!n||i.isVectorInPolygon(e,t,o))&&(s=t,a=r)}),s},r.findPath=function(e,r,n,o){var i=this.zones[n].groups[o],s=this.zones[n].vertices,u=this.getClosestNode(e,n,o,!0),c=this.getClosestNode(r,n,o,!0);if(!u||!c)return null;var l=a.search(i,u,c),f=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},p=new h;p.push(e);for(var d=0;d<l.length;d++){var v=l[d+1];if(v){var g=f(l[d],v);p.push(s[g[0]],s[g[1]])}}p.push(r),p.stringPull();var y=p.path.map(function(e){return new t.Vector3(e.x,e.y,e.z)});return y.shift(),y},e}();c.prototype.getGroup=(o=new t.Plane,function(e,t,r){if(void 0===r&&(r=!1),!this.zones[e])return null;for(var s=null,a=Math.pow(50,2),u=this.zones[e],h=0;h<u.groups.length;h++)for(var c,l=n(u.groups[h]);!(c=l()).done;){var f=c.value;if(r&&(o.setFromCoplanarPoints(u.vertices[f.vertexIds[0]],u.vertices[f.vertexIds[1]],u.vertices[f.vertexIds[2]]),Math.abs(o.distanceToPoint(t))<.01&&i.isPointInPoly([u.vertices[f.vertexIds[0]],u.vertices[f.vertexIds[1]],u.vertices[f.vertexIds[2]]],t)))return h;var p=i.distanceToSquared(f.centroid,t);p<a&&(s=h,a=p)}return s}),c.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,u,h,c,l,f){var p=this.zones[c].vertices,d=this.zones[c].groups[l],v=[h],g={};g[h.id]=0,e=void 0,a.set(0,0,0),r=Infinity,o.setFromCoplanarPoints(p[h.vertexIds[0]],p[h.vertexIds[1]],p[h.vertexIds[2]]),o.projectPoint(u,n),s.copy(n);for(var y=v.pop();y;y=v.pop()){i.set(p[y.vertexIds[0]],p[y.vertexIds[1]],p[y.vertexIds[2]]),i.closestPointToPoint(s,n),n.distanceToSquared(s)<r&&(e=y,a.copy(n),r=n.distanceToSquared(s));var b=g[y.id];if(!(b>2))for(var m=0;m<y.neighbours.length;m++){var M=d[y.neighbours[m]];M.id in g||(v.push(M),g[M.id]=b+1)}}return f.copy(a),e}}();var l={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()},f=function(e){var r,n;function o(){var r;return(r=e.call(this)||this)._playerMarker=new t.Mesh(new t.SphereBufferGeometry(.25,32,32),new t.MeshBasicMaterial({color:l.PLAYER})),r._targetMarker=new t.Mesh(new t.BoxBufferGeometry(.3,.3,.3),new t.MeshBasicMaterial({color:l.TARGET})),r._nodeMarker=new t.Mesh(new t.BoxBufferGeometry(.1,.8,.1),new t.MeshBasicMaterial({color:l.CLOSEST_NODE})),r._stepMarker=new t.Mesh(new t.BoxBufferGeometry(.1,1,.1),new t.MeshBasicMaterial({color:l.CLAMPED_STEP})),r._pathMarker=new t.Object3D,r._pathLineMaterial=new t.LineBasicMaterial({color:l.PATH,linewidth:2}),r._pathPointMaterial=new t.MeshBasicMaterial({color:l.WAYPOINT}),r._pathPointGeometry=new t.SphereBufferGeometry(.08),r._markers=[r._playerMarker,r._targetMarker,r._nodeMarker,r._stepMarker,r._pathMarker],r._markers.forEach(function(e){e.visible=!1,r.add(e)}),r}n=e,(r=o).prototype=Object.create(n.prototype),r.prototype.constructor=r,r.__proto__=n;var i=o.prototype;return i.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);var r=new t.BufferGeometry;r.setAttribute("position",new t.BufferAttribute(new Float32Array(3*e.length),3));for(var n=0;n<e.length;n++)r.attributes.position.setXYZ(n,e[n].x,e[n].y+.2,e[n].z);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},i.setPlayerPosition=function(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this},i.setTargetPosition=function(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this},i.setNodePosition=function(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this},i.setStepPosition=function(e){return this._stepMarker.position.copy(e),this._stepMarker.visible=!0,this},i.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},o}(t.Object3D);e.Pathfinding=c,e.PathfindingHelper=f});
//# sourceMappingURL=three-pathfinding.umd.js.map

24

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

@@ -26,8 +26,4 @@ "author": "Don McCurdy <dm@donmccurdy.com>",

"benchmark": "node benchmark/index.benchmark.js",
"deploy": "npm run dist && npm test && now --static && now alias"
"deploy": "npm run dist && npm test && vercel --prod"
},
"now": {
"alias": "three-pathfinding.donmccurdy.com",
"public": true
},
"keywords": [

@@ -51,11 +47,11 @@ "patrol",

"devDependencies": {
"concurrently": "^6.0.0",
"documentation": "^13.1.1",
"microbundle": "^0.13.0",
"concurrently": "6.2.1",
"documentation": "13.2.5",
"microbundle": "0.13.3",
"replace-between": "0.0.8",
"serve": "^11.3.2",
"tap-spec": "^5.0.0",
"tape": "^5.2.2",
"three": "^0.126.1",
"uglify-js": "^3.3.3"
"serve": "12.0.0",
"tap-spec": "5.0.0",
"tape": "5.3.1",
"three": "0.131.3",
"uglify-js": "3.14.1"
},

@@ -62,0 +58,0 @@ "files": [

229

README.md

@@ -102,18 +102,18 @@ # three-pathfinding

- [setZoneData][2]
- [getRandomNode][3]
- [getClosestNode][4]
- [findPath][5]
- [getGroup][6]
- [clampStep][7]
- [createZone][8]
- [PathfindingHelper][9]
- [setPath][10]
- [setPlayerPosition][11]
- [setTargetPosition][12]
- [setNodePosition][13]
- [setStepPosition][14]
- [reset][15]
- [Zone][16]
- [Group][17]
- [Node][18]
- [getRandomNode][4]
- [getClosestNode][6]
- [findPath][8]
- [getGroup][10]
- [clampStep][12]
- [createZone][14]
- [PathfindingHelper][16]
- [setPath][17]
- [setPlayerPosition][19]
- [setTargetPosition][21]
- [setNodePosition][23]
- [setStepPosition][25]
- [reset][27]
- [Zone][28]
- [Group][30]
- [Node][31]

@@ -128,6 +128,6 @@ ## Pathfinding

**Parameters**
#### Parameters
- `zoneID` **[string][19]**
- `zone` **[Zone][20]**
- `zoneID` **[string][33]**
- `zone` **[Zone][34]**

@@ -138,10 +138,10 @@ ### getRandomNode

**Parameters**
#### Parameters
- `zoneID` **[string][19]**
- `groupID` **[number][21]**
- `nearPosition` **THREE.Vector3**
- `nearRange` **[number][21]**
- `zoneID` **[string][33]**
- `groupID` **[number][35]**
- `nearPosition` **Vector3**
- `nearRange` **[number][35]**
Returns **[Node][22]**
Returns **[Node][36]**

@@ -152,10 +152,10 @@ ### getClosestNode

**Parameters**
#### Parameters
- `position` **THREE.Vector3**
- `zoneID` **[string][19]**
- `groupID` **[number][21]**
- `checkPolygon` **[boolean][23]** (optional, default `false`)
- `position` **Vector3**
- `zoneID` **[string][33]**
- `groupID` **[number][35]**
- `checkPolygon` **[boolean][37]** (optional, default `false`)
Returns **[Node][22]**
Returns **[Node][36]**

@@ -167,10 +167,10 @@ ### findPath

**Parameters**
#### Parameters
- `startPosition` **THREE.Vector3** Start position.
- `targetPosition` **THREE.Vector3** Destination.
- `zoneID` **[string][19]** ID of current zone.
- `groupID` **[number][21]** Current group ID.
- `startPosition` **Vector3** Start position.
- `targetPosition` **Vector3** Destination.
- `zoneID` **[string][33]** ID of current zone.
- `groupID` **[number][35]** Current group ID.
Returns **[Array][24]&lt;THREE.Vector3>** Array of points defining the path.
Returns **[Array][38]&lt;Vector3>** Array of points defining the path.

@@ -181,8 +181,8 @@ ### getGroup

**Parameters**
#### Parameters
- `zoneID` **[string][19]**
- `position` **THREE.Vector3**
- `zoneID` **[string][33]**
- `position` **Vector3**
Returns **[number][21]**
Returns **[number][35]**

@@ -194,12 +194,12 @@ ### clampStep

**Parameters**
#### Parameters
- `start` **THREE.Vector3**
- `end` **THREE.Vector3** Desired endpoint.
- `node` **[Node][22]**
- `zoneID` **[string][19]**
- `groupID` **[number][21]**
- `endTarget` **THREE.Vector3** Updated endpoint.
- `start` **Vector3**
- `end` **Vector3** Desired endpoint.
- `node` **[Node][36]**
- `zoneID` **[string][33]**
- `groupID` **[number][35]**
- `endTarget` **Vector3** Updated endpoint.
Returns **[Node][22]** Updated node.
Returns **[Node][36]** Updated node.

@@ -210,11 +210,12 @@ ### createZone

**Parameters**
#### Parameters
- `geometry` **THREE.BufferGeometry**
- `geometry` **BufferGeometry**
- `tolerance` **[number][35]** Vertex welding tolerance. (optional, default `1e-4`)
Returns **[Zone][20]**
Returns **[Zone][34]**
## PathfindingHelper
**Extends THREE.Object3D**
**Extends Object3D**

@@ -225,5 +226,5 @@ Helper for debugging pathfinding behavior.

**Parameters**
#### Parameters
- `path`
- `path` **[Array][38]&lt;Vector3>**

@@ -234,5 +235,5 @@ Returns **this**

**Parameters**
#### Parameters
- `position` **THREE.Vector3**
- `position` **Vector3**

@@ -243,5 +244,5 @@ Returns **this**

**Parameters**
#### Parameters
- `position` **THREE.Vector3**
- `position` **Vector3**

@@ -252,5 +253,5 @@ Returns **this**

**Parameters**
#### Parameters
- `position` **THREE.Vector3**
- `position` **Vector3**

@@ -261,5 +262,5 @@ Returns **this**

**Parameters**
#### Parameters
- `position` **THREE.Vector3**
- `position` **Vector3**

@@ -278,6 +279,9 @@ Returns **this**

**Properties**
Type: [Object][39]
- `groups` **[Array][24]&lt;[Group][25]>**
### Properties
- `groups` **[Array][38]&lt;[Group][40]>**
- `vertices` **[Array][38]&lt;Vector3>**
## Group

@@ -287,2 +291,4 @@

Type: [Object][39]
## Node

@@ -292,11 +298,14 @@

**Properties**
Type: [Object][39]
- `id` **[number][21]**
- `neighbours` **[Array][24]&lt;[number][21]>** IDs of neighboring nodes.
- `centroid` **THREE.Vector3**
- `portals` **[Array][24]&lt;[Array][24]&lt;[number][21]>>** Array of portals, each defined by two vertex IDs.
- `closed` **[boolean][23]**
- `cost` **[number][21]**
### Properties
- `id` **[number][35]**
- `neighbours` **[Array][38]&lt;[number][35]>** IDs of neighboring nodes.
- `vertexIds` **[Array][38]&lt;[number][35]>**
- `centroid` **Vector3**
- `portals` **[Array][38]&lt;[Array][38]&lt;[number][35]>>** Array of portals, each defined by two vertex IDs.
- `closed` **[boolean][37]**
- `cost` **[number][35]**
[1]: #pathfinding

@@ -306,47 +315,77 @@

[3]: #getrandomnode
[3]: #parameters
[4]: #getclosestnode
[4]: #getrandomnode
[5]: #findpath
[5]: #parameters-1
[6]: #getgroup
[6]: #getclosestnode
[7]: #clampstep
[7]: #parameters-2
[8]: #createzone
[8]: #findpath
[9]: #pathfindinghelper
[9]: #parameters-3
[10]: #setpath
[10]: #getgroup
[11]: #setplayerposition
[11]: #parameters-4
[12]: #settargetposition
[12]: #clampstep
[13]: #setnodeposition
[13]: #parameters-5
[14]: #setstepposition
[14]: #createzone
[15]: #reset
[15]: #parameters-6
[16]: #zone
[16]: #pathfindinghelper
[17]: #group
[17]: #setpath
[18]: #node
[18]: #parameters-7
[19]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/String
[19]: #setplayerposition
[20]: #zone
[20]: #parameters-8
[21]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Number
[21]: #settargetposition
[22]: #node
[22]: #parameters-9
[23]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Boolean
[23]: #setnodeposition
[24]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Array
[24]: #parameters-10
[25]: #group
[25]: #setstepposition
[26]: #parameters-11
[27]: #reset
[28]: #zone
[29]: #properties
[30]: #group
[31]: #node
[32]: #properties-1
[33]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/String
[34]: #zone
[35]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Number
[36]: #node
[37]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Boolean
[38]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Array
[39]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Object
[40]: #group
<!--- API END --->

@@ -353,0 +392,0 @@

33

src/Builder.js

@@ -81,2 +81,24 @@ import { Vector3 } from 'three';

/**
* Spreads the group ID of the given polygon to all connected polygons
* @param {Object} seed
*/
static _spreadGroupId (seed) {
let nextBatch = new Set([seed]);
while(nextBatch.size > 0) {
const batch = nextBatch;
nextBatch = new Set();
batch.forEach((polygon) => {
polygon.group = seed.group;
polygon.neighbours.forEach((neighbour) => {
if(neighbour.group === undefined) {
nextBatch.add(neighbour);
}
});
});
}
}
static _buildPolygonGroups (navigationMesh) {

@@ -88,11 +110,2 @@

const spreadGroupId = function (polygon) {
polygon.neighbours.forEach((neighbour) => {
if (neighbour.group === undefined) {
neighbour.group = polygon.group;
spreadGroupId(neighbour);
}
});
};
polygons.forEach((polygon) => {

@@ -105,3 +118,3 @@ if (polygon.group !== undefined) {

polygon.group = polygonGroups.length;
spreadGroupId(polygon);
this._spreadGroupId(polygon);
polygonGroups.push([polygon]);

@@ -108,0 +121,0 @@ }

dist/three-pathfinding.js.map

Sorry, the diff of this file is not supported yet

dist/three-pathfinding.modern.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