three-pathfinding - npm Package Compare versions

Comparing version 1.2.0 to 1.3.0

dist/three-pathfinding.js

@@ -1,2 +0,2 @@
-var t=require("three");class e{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(e,r=1e-4){r=Math.max(r,Number.EPSILON);for(var s={},n=e.getIndex(),o=e.getAttribute("position"),i=n?n.count:o.count,h=0,c=[],a=[],u=Math.log10(1/r),l=Math.pow(10,u),d=0;d<i;d++){var p=n?n.getX(d):d,g="";g+=~~(o.getX(p)*l)+",",g+=~~(o.getY(p)*l)+",",(g+=~~(o.getZ(p)*l)+",")in s?c.push(s[g]):(a.push(o.getX(p)),a.push(o.getY(p)),a.push(o.getZ(p)),s[g]=h,c.push(h),h++)}const f=new t.BufferAttribute(new Float32Array(a),o.itemSize,o.normalized),v=new t.BufferGeometry;return v.setAttribute("position",f),v.setIndex(c),v}}class r{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 s{constructor(){this.portals=[]}push(t,e){void 0===e&&(e=t),this.portals.push({left:t,right:e})}stringPull(){const t=this.portals,r=[];let s,n,o,i=0,h=0,c=0;s=t[0].left,n=t[0].left,o=t[0].right,r.push(s);for(let a=1;a<t.length;a++){const u=t[a].left,l=t[a].right;if(e.triarea2(s,o,l)<=0){if(!(e.vequal(s,o)||e.triarea2(s,n,l)>0)){r.push(n),s=n,i=h,n=s,o=s,h=i,c=i,a=i;continue}o=l,c=a}if(e.triarea2(s,n,u)>=0){if(!(e.vequal(s,n)||e.triarea2(s,o,u)<0)){r.push(o),s=o,i=c,n=s,o=s,h=i,c=i,a=i;continue}n=u,h=a}}return 0!==r.length&&e.vequal(r[r.length-1],t[t.length-1].left)||r.push(t[t.length-1].left),this.path=r,r}}class n{constructor(){this.zones={}}static createZone(r,s=1e-4){return class{static buildZone(r,s){const n=this._buildNavigationMesh(r,s),o={};n.vertices.forEach(t=>{t.x=e.roundNumber(t.x,2),t.y=e.roundNumber(t.y,2),t.z=e.roundNumber(t.z,2)}),o.vertices=n.vertices;const i=this._buildPolygonGroups(n);return o.groups=new Array(i.length),i.forEach((r,s)=>{const n=new Map;r.forEach((t,e)=>{n.set(t,e)});const i=new Array(r.length);r.forEach((r,s)=>{const h=[];r.neighbours.forEach(t=>h.push(n.get(t)));const c=[];r.neighbours.forEach(t=>c.push(this._getSharedVerticesInOrder(r,t)));const a=new t.Vector3(0,0,0);a.add(o.vertices[r.vertexIds[0]]),a.add(o.vertices[r.vertexIds[1]]),a.add(o.vertices[r.vertexIds[2]]),a.divideScalar(3),a.x=e.roundNumber(a.x,2),a.y=e.roundNumber(a.y,2),a.z=e.roundNumber(a.z,2),i[s]={id:s,neighbours:h,vertexIds:r.vertexIds,centroid:a,portals:c}}),o.groups[s]=i}),o}static _buildNavigationMesh(t,r){return t=e.mergeVertices(t,r),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(e){const r=[],s=[],n=e.attributes.position,o=e.index,i=[];for(let e=0;e<n.count;e++)s.push((new t.Vector3).fromBufferAttribute(n,e)),i[e]=[];for(let t=0;t<e.index.count;t+=3){const e=o.getX(t),s=o.getX(t+1),n=o.getX(t+2),h={vertexIds:[e,s,n],neighbours:null};r.push(h),i[e].push(h),i[s].push(h),i[n].push(h)}return r.forEach(t=>{t.neighbours=this._buildPolygonNeighbours(t,i)}),{polygons:r,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(r,s)}setZoneData(t,e){this.zones[t]=e}getRandomNode(r,s,n,o){if(!this.zones[r])return new t.Vector3;n=n||null,o=o||0;const i=[];return this.zones[r].groups[s].forEach(t=>{n&&o?e.distanceToSquared(n,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),e.sample(i)||new t.Vector3}getClosestNode(t,r,s,n=!1){const o=this.zones[r].vertices;let i=null,h=Infinity;return this.zones[r].groups[s].forEach(r=>{const s=e.distanceToSquared(r.centroid,t);s<h&&(!n||e.isVectorInPolygon(t,r,o))&&(i=r,h=s)}),i}findPath(n,o,i,h){const c=this.zones[i].groups[h],a=this.zones[i].vertices,u=this.getClosestNode(n,i,h,!0),l=this.getClosestNode(o,i,h,!0);if(!u||!l)return null;const d=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 r(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,r){return e.distanceToSquared(t,r)}static neighbours(t,e){const r=[];for(let s=0;s<e.neighbours.length;s++)r.push(t[e.neighbours[s]]);return r}}.search(c,u,l),p=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},g=new s;g.push(n);for(let t=0;t<d.length;t++){const e=d[t],r=d[t+1];if(r){const t=p(e,r);g.push(a[t[0]],a[t[1]])}}g.push(o),g.stringPull();const f=g.path.map(e=>new t.Vector3(e.x,e.y,e.z));return f.shift(),f}}n.prototype.getGroup=function(){const r=new t.Plane;return function(t,s,n=!1){if(!this.zones[t])return null;let o=null,i=Math.pow(50,2);const h=this.zones[t];for(let t=0;t<h.groups.length;t++){const c=h.groups[t];for(const a of c){if(n&&(r.setFromCoplanarPoints(h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]),Math.abs(r.distanceToPoint(s))<.01)&&e.isPointInPoly([h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]],s))return t;const c=e.distanceToSquared(a.centroid,s);c<i&&(o=t,i=c)}}return o}}(),n.prototype.clampStep=function(){const e=new t.Vector3,r=new t.Plane,s=new t.Triangle,n=new t.Vector3;let o,i,h=new t.Vector3;return function(t,c,a,u,l,d){const p=this.zones[u].vertices,g=this.zones[u].groups[l],f=[a],v={};v[a.id]=0,o=void 0,h.set(0,0,0),i=Infinity,r.setFromCoplanarPoints(p[a.vertexIds[0]],p[a.vertexIds[1]],p[a.vertexIds[2]]),r.projectPoint(c,e),n.copy(e);for(let t=f.pop();t;t=f.pop()){s.set(p[t.vertexIds[0]],p[t.vertexIds[1]],p[t.vertexIds[2]]),s.closestPointToPoint(n,e),e.distanceToSquared(n)<i&&(o=t,h.copy(e),i=e.distanceToSquared(n));const r=v[t.id];if(!(r>2))for(let e=0;e<t.neighbours.length;e++){const s=g[t.neighbours[e]];s.id in v||(f.push(s),v[s.id]=r+1)}}return d.copy(h),o}}();const o={PLAYER:new t.Color(15631215).convertSRGBToLinear().getHex(),TARGET:new t.Color(14469912).convertSRGBToLinear().getHex(),PATH:new t.Color(41903).convertSRGBToLinear().getHex(),WAYPOINT:new t.Color(41903).convertSRGBToLinear().getHex(),CLAMPED_STEP:new t.Color(14472114).convertSRGBToLinear().getHex(),CLOSEST_NODE:new t.Color(4417387).convertSRGBToLinear().getHex()};exports.Pathfinding=n,exports.PathfindingHelper=class extends t.Object3D{constructor(){super(),this._playerMarker=new t.Mesh(new t.SphereGeometry(.25,32,32),new t.MeshBasicMaterial({color:o.PLAYER})),this._targetMarker=new t.Mesh(new t.BoxGeometry(.3,.3,.3),new t.MeshBasicMaterial({color:o.TARGET})),this._nodeMarker=new t.Mesh(new t.BoxGeometry(.1,.8,.1),new t.MeshBasicMaterial({color:o.CLOSEST_NODE})),this._stepMarker=new t.Mesh(new t.BoxGeometry(.1,1,.1),new t.MeshBasicMaterial({color:o.CLAMPED_STEP})),this._pathMarker=new t.Object3D,this._pathLineMaterial=new t.LineBasicMaterial({color:o.PATH,linewidth:2}),this._pathPointMaterial=new t.MeshBasicMaterial({color:o.WAYPOINT}),this._pathPointGeometry=new t.SphereGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(t=>{t.visible=!1,this.add(t)})}setPath(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);const r=new t.BufferGeometry;r.setAttribute("position",new t.BufferAttribute(new Float32Array(3*e.length),3));for(let t=0;t<e.length;t++)r.attributes.position.setXYZ(t,e[t].x,e[t].y+.2,e[t].z);this._pathMarker.add(new t.Line(r,this._pathLineMaterial));for(let r=0;r<e.length-1;r++){const s=new t.Mesh(this._pathPointGeometry,this._pathPointMaterial);s.position.copy(e[r]),s.position.y+=.2,this._pathMarker.add(s)}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}};
+var t=require("three");class e{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(e,r=1e-4){r=Math.max(r,Number.EPSILON);for(var s={},n=e.getIndex(),o=e.getAttribute("position"),i=n?n.count:o.count,h=0,c=[],a=[],u=Math.log10(1/r),l=Math.pow(10,u),d=0;d<i;d++){var p=n?n.getX(d):d,g="";g+=~~(o.getX(p)*l)+",",g+=~~(o.getY(p)*l)+",",(g+=~~(o.getZ(p)*l)+",")in s?c.push(s[g]):(a.push(o.getX(p)),a.push(o.getY(p)),a.push(o.getZ(p)),s[g]=h,c.push(h),h++)}const f=new t.BufferAttribute(new Float32Array(a),o.itemSize,o.normalized),v=new t.BufferGeometry;return v.setAttribute("position",f),v.setIndex(c),v}}class r{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 s{constructor(){this.portals=[]}push(t,e){void 0===e&&(e=t),this.portals.push({left:t,right:e})}stringPull(){const t=this.portals,r=[];let s,n,o,i=0,h=0,c=0;s=t[0].left,n=t[0].left,o=t[0].right,r.push(s);for(let a=1;a<t.length;a++){const u=t[a].left,l=t[a].right;if(e.triarea2(s,o,l)<=0){if(!(e.vequal(s,o)||e.triarea2(s,n,l)>0)){r.push(n),s=n,i=h,n=s,o=s,h=i,c=i,a=i;continue}o=l,c=a}if(e.triarea2(s,n,u)>=0){if(!(e.vequal(s,n)||e.triarea2(s,o,u)<0)){r.push(o),s=o,i=c,n=s,o=s,h=i,c=i,a=i;continue}n=u,h=a}}return 0!==r.length&&e.vequal(r[r.length-1],t[t.length-1].left)||r.push(t[t.length-1].left),this.path=r,r}}class n{constructor(){this.zones={}}static createZone(r,s=1e-4){return class{static buildZone(r,s){const n=this._buildNavigationMesh(r,s),o={};n.vertices.forEach(t=>{t.x=e.roundNumber(t.x,2),t.y=e.roundNumber(t.y,2),t.z=e.roundNumber(t.z,2)}),o.vertices=n.vertices;const i=this._buildPolygonGroups(n);return o.groups=new Array(i.length),i.forEach((r,s)=>{const n=new Map;r.forEach((t,e)=>{n.set(t,e)});const i=new Array(r.length);r.forEach((r,s)=>{const h=[];r.neighbours.forEach(t=>h.push(n.get(t)));const c=[];r.neighbours.forEach(t=>c.push(this._getSharedVerticesInOrder(r,t)));const a=new t.Vector3(0,0,0);a.add(o.vertices[r.vertexIds[0]]),a.add(o.vertices[r.vertexIds[1]]),a.add(o.vertices[r.vertexIds[2]]),a.divideScalar(3),a.x=e.roundNumber(a.x,2),a.y=e.roundNumber(a.y,2),a.z=e.roundNumber(a.z,2),i[s]={id:s,neighbours:h,vertexIds:r.vertexIds,centroid:a,portals:c}}),o.groups[s]=i}),o}static _buildNavigationMesh(t,r){return t=e.mergeVertices(t,r),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(e){const r=[],s=[],n=e.attributes.position,o=e.index,i=[];for(let e=0;e<n.count;e++)s.push((new t.Vector3).fromBufferAttribute(n,e)),i[e]=[];for(let t=0;t<e.index.count;t+=3){const e=o.getX(t),s=o.getX(t+1),n=o.getX(t+2),h={vertexIds:[e,s,n],neighbours:null};r.push(h),i[e].push(h),i[s].push(h),i[n].push(h)}return r.forEach(t=>{t.neighbours=this._buildPolygonNeighbours(t,i)}),{polygons:r,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(r,s)}setZoneData(t,e){this.zones[t]=e}getRandomNode(r,s,n,o){if(!this.zones[r])return new t.Vector3;n=n||null,o=o||0;const i=[];return this.zones[r].groups[s].forEach(t=>{n&&o?e.distanceToSquared(n,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),e.sample(i)||new t.Vector3}getClosestNode(t,r,s,n=!1){const o=this.zones[r].vertices;let i=null,h=Infinity;return this.zones[r].groups[s].forEach(r=>{const s=e.distanceToSquared(r.centroid,t);s<h&&(!n||e.isVectorInPolygon(t,r,o))&&(i=r,h=s)}),i}findPath(n,o,i,h){const c=this.zones[i].groups[h],a=this.zones[i].vertices,u=this.getClosestNode(n,i,h,!0),l=this.getClosestNode(o,i,h,!0);if(!u||!l)return null;const d=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 r(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,r){return e.distanceToSquared(t,r)}static neighbours(t,e){const r=[];for(let s=0;s<e.neighbours.length;s++)r.push(t[e.neighbours[s]]);return r}}.search(c,u,l),p=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},g=new s;g.push(n);for(let t=0;t<d.length;t++){const e=d[t],r=d[t+1];if(r){const t=p(e,r);g.push(a[t[0]],a[t[1]])}}g.push(o),g.stringPull();const f=g.path.map(e=>new t.Vector3(e.x,e.y,e.z));return f.shift(),f}}n.prototype.getGroup=function(){const r=new t.Plane;return function(t,s,n=!1){if(!this.zones[t])return null;let o=null,i=Math.pow(50,2);const h=this.zones[t];for(let t=0;t<h.groups.length;t++){const c=h.groups[t];for(const a of c){if(n&&(r.setFromCoplanarPoints(h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]),Math.abs(r.distanceToPoint(s))<.01)&&e.isPointInPoly([h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]],s))return t;const c=e.distanceToSquared(a.centroid,s);c<i&&(o=t,i=c)}}return o}}(),n.prototype.clampStep=function(){const e=new t.Vector3,r=new t.Plane,s=new t.Triangle,n=new t.Vector3;let o,i,h=new t.Vector3;return function(t,c,a,u,l,d){const p=this.zones[u].vertices,g=this.zones[u].groups[l],f=[a],v={};v[a.id]=0,o=void 0,h.set(0,0,0),i=Infinity,r.setFromCoplanarPoints(p[a.vertexIds[0]],p[a.vertexIds[1]],p[a.vertexIds[2]]),r.projectPoint(c,e),n.copy(e);for(let t=f.pop();t;t=f.pop()){s.set(p[t.vertexIds[0]],p[t.vertexIds[1]],p[t.vertexIds[2]]),s.closestPointToPoint(n,e),e.distanceToSquared(n)<i&&(o=t,h.copy(e),i=e.distanceToSquared(n));const r=v[t.id];if(!(r>2))for(let e=0;e<t.neighbours.length;e++){const s=g[t.neighbours[e]];s.id in v||(f.push(s),v[s.id]=r+1)}}return d.copy(h),o}}(),exports.Pathfinding=n,exports.PathfindingHelper=class extends t.Object3D{constructor(){super(),this._playerMarker=new t.Mesh(new t.SphereGeometry(.25,32,32),new t.MeshBasicMaterial({color:15631215})),this._targetMarker=new t.Mesh(new t.BoxGeometry(.3,.3,.3),new t.MeshBasicMaterial({color:14469912})),this._nodeMarker=new t.Mesh(new t.BoxGeometry(.1,.8,.1),new t.MeshBasicMaterial({color:4417387})),this._stepMarker=new t.Mesh(new t.BoxGeometry(.1,1,.1),new t.MeshBasicMaterial({color:14472114})),this._pathMarker=new t.Object3D,this._pathLineMaterial=new t.LineBasicMaterial({color:41903,linewidth:2}),this._pathPointMaterial=new t.MeshBasicMaterial({color:41903}),this._pathPointGeometry=new t.SphereGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(t=>{t.visible=!1,this.add(t)})}setPath(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);const r=new t.BufferGeometry;r.setAttribute("position",new t.BufferAttribute(new Float32Array(3*e.length),3));for(let t=0;t<e.length;t++)r.attributes.position.setXYZ(t,e[t].x,e[t].y+.2,e[t].z);this._pathMarker.add(new t.Line(r,this._pathLineMaterial));for(let r=0;r<e.length-1;r++){const s=new t.Mesh(this._pathPointGeometry,this._pathPointMaterial);s.position.copy(e[r]),s.position.y+=.2,this._pathMarker.add(s)}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}};
 //# sourceMappingURL=three-pathfinding.js.map

dist/three-pathfinding.module.js

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

dist/three-pathfinding.umd.js

@@ -1,2 +0,2 @@
-!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports,require("three")):"function"==typeof define&&define.amd?define(["exports","three"],e):e((t||self).threePathfinding={},t.THREE)}(this,function(t,e){class r{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(t,r=1e-4){r=Math.max(r,Number.EPSILON);for(var s={},n=t.getIndex(),o=t.getAttribute("position"),i=n?n.count:o.count,h=0,c=[],a=[],u=Math.log10(1/r),l=Math.pow(10,u),d=0;d<i;d++){var p=n?n.getX(d):d,g="";g+=~~(o.getX(p)*l)+",",g+=~~(o.getY(p)*l)+",",(g+=~~(o.getZ(p)*l)+",")in s?c.push(s[g]):(a.push(o.getX(p)),a.push(o.getY(p)),a.push(o.getZ(p)),s[g]=h,c.push(h),h++)}const f=new e.BufferAttribute(new Float32Array(a),o.itemSize,o.normalized),v=new e.BufferGeometry;return v.setAttribute("position",f),v.setIndex(c),v}}class s{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 n{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 s,n,o,i=0,h=0,c=0;s=t[0].left,n=t[0].left,o=t[0].right,e.push(s);for(let a=1;a<t.length;a++){const u=t[a].left,l=t[a].right;if(r.triarea2(s,o,l)<=0){if(!(r.vequal(s,o)||r.triarea2(s,n,l)>0)){e.push(n),s=n,i=h,n=s,o=s,h=i,c=i,a=i;continue}o=l,c=a}if(r.triarea2(s,n,u)>=0){if(!(r.vequal(s,n)||r.triarea2(s,o,u)<0)){e.push(o),s=o,i=c,n=s,o=s,h=i,c=i,a=i;continue}n=u,h=a}}return 0!==e.length&&r.vequal(e[e.length-1],t[t.length-1].left)||e.push(t[t.length-1].left),this.path=e,e}}class o{constructor(){this.zones={}}static createZone(t,s=1e-4){return class{static buildZone(t,s){const n=this._buildNavigationMesh(t,s),o={};n.vertices.forEach(t=>{t.x=r.roundNumber(t.x,2),t.y=r.roundNumber(t.y,2),t.z=r.roundNumber(t.z,2)}),o.vertices=n.vertices;const i=this._buildPolygonGroups(n);return o.groups=new Array(i.length),i.forEach((t,s)=>{const n=new Map;t.forEach((t,e)=>{n.set(t,e)});const i=new Array(t.length);t.forEach((t,s)=>{const h=[];t.neighbours.forEach(t=>h.push(n.get(t)));const c=[];t.neighbours.forEach(e=>c.push(this._getSharedVerticesInOrder(t,e)));const a=new e.Vector3(0,0,0);a.add(o.vertices[t.vertexIds[0]]),a.add(o.vertices[t.vertexIds[1]]),a.add(o.vertices[t.vertexIds[2]]),a.divideScalar(3),a.x=r.roundNumber(a.x,2),a.y=r.roundNumber(a.y,2),a.z=r.roundNumber(a.z,2),i[s]={id:s,neighbours:h,vertexIds:t.vertexIds,centroid:a,portals:c}}),o.groups[s]=i}),o}static _buildNavigationMesh(t,e){return t=r.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 r=[],s=[],n=t.attributes.position,o=t.index,i=[];for(let t=0;t<n.count;t++)s.push((new e.Vector3).fromBufferAttribute(n,t)),i[t]=[];for(let e=0;e<t.index.count;e+=3){const t=o.getX(e),s=o.getX(e+1),n=o.getX(e+2),h={vertexIds:[t,s,n],neighbours:null};r.push(h),i[t].push(h),i[s].push(h),i[n].push(h)}return r.forEach(t=>{t.neighbours=this._buildPolygonNeighbours(t,i)}),{polygons:r,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,s)}setZoneData(t,e){this.zones[t]=e}getRandomNode(t,s,n,o){if(!this.zones[t])return new e.Vector3;n=n||null,o=o||0;const i=[];return this.zones[t].groups[s].forEach(t=>{n&&o?r.distanceToSquared(n,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),r.sample(i)||new e.Vector3}getClosestNode(t,e,s,n=!1){const o=this.zones[e].vertices;let i=null,h=Infinity;return this.zones[e].groups[s].forEach(e=>{const s=r.distanceToSquared(e.centroid,t);s<h&&(!n||r.isVectorInPolygon(t,e,o))&&(i=e,h=s)}),i}findPath(t,o,i,h){const c=this.zones[i].groups[h],a=this.zones[i].vertices,u=this.getClosestNode(t,i,h,!0),l=this.getClosestNode(o,i,h,!0);if(!u||!l)return null;const d=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 s(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 r.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(c,u,l),p=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},g=new n;g.push(t);for(let t=0;t<d.length;t++){const e=d[t],r=d[t+1];if(r){const t=p(e,r);g.push(a[t[0]],a[t[1]])}}g.push(o),g.stringPull();const f=g.path.map(t=>new e.Vector3(t.x,t.y,t.z));return f.shift(),f}}o.prototype.getGroup=function(){const t=new e.Plane;return function(e,s,n=!1){if(!this.zones[e])return null;let o=null,i=Math.pow(50,2);const h=this.zones[e];for(let e=0;e<h.groups.length;e++){const c=h.groups[e];for(const a of c){if(n&&(t.setFromCoplanarPoints(h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]),Math.abs(t.distanceToPoint(s))<.01)&&r.isPointInPoly([h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]],s))return e;const c=r.distanceToSquared(a.centroid,s);c<i&&(o=e,i=c)}}return o}}(),o.prototype.clampStep=function(){const t=new e.Vector3,r=new e.Plane,s=new e.Triangle,n=new e.Vector3;let o,i,h=new e.Vector3;return function(e,c,a,u,l,d){const p=this.zones[u].vertices,g=this.zones[u].groups[l],f=[a],v={};v[a.id]=0,o=void 0,h.set(0,0,0),i=Infinity,r.setFromCoplanarPoints(p[a.vertexIds[0]],p[a.vertexIds[1]],p[a.vertexIds[2]]),r.projectPoint(c,t),n.copy(t);for(let e=f.pop();e;e=f.pop()){s.set(p[e.vertexIds[0]],p[e.vertexIds[1]],p[e.vertexIds[2]]),s.closestPointToPoint(n,t),t.distanceToSquared(n)<i&&(o=e,h.copy(t),i=t.distanceToSquared(n));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(h),o}}();const i={PLAYER:new e.Color(15631215).convertSRGBToLinear().getHex(),TARGET:new e.Color(14469912).convertSRGBToLinear().getHex(),PATH:new e.Color(41903).convertSRGBToLinear().getHex(),WAYPOINT:new e.Color(41903).convertSRGBToLinear().getHex(),CLAMPED_STEP:new e.Color(14472114).convertSRGBToLinear().getHex(),CLOSEST_NODE:new e.Color(4417387).convertSRGBToLinear().getHex()};t.Pathfinding=o,t.PathfindingHelper=class extends e.Object3D{constructor(){super(),this._playerMarker=new e.Mesh(new e.SphereGeometry(.25,32,32),new e.MeshBasicMaterial({color:i.PLAYER})),this._targetMarker=new e.Mesh(new e.BoxGeometry(.3,.3,.3),new e.MeshBasicMaterial({color:i.TARGET})),this._nodeMarker=new e.Mesh(new e.BoxGeometry(.1,.8,.1),new e.MeshBasicMaterial({color:i.CLOSEST_NODE})),this._stepMarker=new e.Mesh(new e.BoxGeometry(.1,1,.1),new e.MeshBasicMaterial({color:i.CLAMPED_STEP})),this._pathMarker=new e.Object3D,this._pathLineMaterial=new e.LineBasicMaterial({color:i.PATH,linewidth:2}),this._pathPointMaterial=new e.MeshBasicMaterial({color:i.WAYPOINT}),this._pathPointGeometry=new e.SphereGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(t=>{t.visible=!1,this.add(t)})}setPath(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);const r=new e.BufferGeometry;r.setAttribute("position",new e.BufferAttribute(new Float32Array(3*t.length),3));for(let e=0;e<t.length;e++)r.attributes.position.setXYZ(e,t[e].x,t[e].y+.2,t[e].z);this._pathMarker.add(new e.Line(r,this._pathLineMaterial));for(let r=0;r<t.length-1;r++){const s=new e.Mesh(this._pathPointGeometry,this._pathPointMaterial);s.position.copy(t[r]),s.position.y+=.2,this._pathMarker.add(s)}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}}});
+!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports,require("three")):"function"==typeof define&&define.amd?define(["exports","three"],e):e((t||self).threePathfinding={},t.THREE)}(this,function(t,e){class r{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(t,r=1e-4){r=Math.max(r,Number.EPSILON);for(var s={},n=t.getIndex(),o=t.getAttribute("position"),i=n?n.count:o.count,h=0,c=[],a=[],u=Math.log10(1/r),l=Math.pow(10,u),d=0;d<i;d++){var p=n?n.getX(d):d,g="";g+=~~(o.getX(p)*l)+",",g+=~~(o.getY(p)*l)+",",(g+=~~(o.getZ(p)*l)+",")in s?c.push(s[g]):(a.push(o.getX(p)),a.push(o.getY(p)),a.push(o.getZ(p)),s[g]=h,c.push(h),h++)}const f=new e.BufferAttribute(new Float32Array(a),o.itemSize,o.normalized),v=new e.BufferGeometry;return v.setAttribute("position",f),v.setIndex(c),v}}class s{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 n{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 s,n,o,i=0,h=0,c=0;s=t[0].left,n=t[0].left,o=t[0].right,e.push(s);for(let a=1;a<t.length;a++){const u=t[a].left,l=t[a].right;if(r.triarea2(s,o,l)<=0){if(!(r.vequal(s,o)||r.triarea2(s,n,l)>0)){e.push(n),s=n,i=h,n=s,o=s,h=i,c=i,a=i;continue}o=l,c=a}if(r.triarea2(s,n,u)>=0){if(!(r.vequal(s,n)||r.triarea2(s,o,u)<0)){e.push(o),s=o,i=c,n=s,o=s,h=i,c=i,a=i;continue}n=u,h=a}}return 0!==e.length&&r.vequal(e[e.length-1],t[t.length-1].left)||e.push(t[t.length-1].left),this.path=e,e}}class o{constructor(){this.zones={}}static createZone(t,s=1e-4){return class{static buildZone(t,s){const n=this._buildNavigationMesh(t,s),o={};n.vertices.forEach(t=>{t.x=r.roundNumber(t.x,2),t.y=r.roundNumber(t.y,2),t.z=r.roundNumber(t.z,2)}),o.vertices=n.vertices;const i=this._buildPolygonGroups(n);return o.groups=new Array(i.length),i.forEach((t,s)=>{const n=new Map;t.forEach((t,e)=>{n.set(t,e)});const i=new Array(t.length);t.forEach((t,s)=>{const h=[];t.neighbours.forEach(t=>h.push(n.get(t)));const c=[];t.neighbours.forEach(e=>c.push(this._getSharedVerticesInOrder(t,e)));const a=new e.Vector3(0,0,0);a.add(o.vertices[t.vertexIds[0]]),a.add(o.vertices[t.vertexIds[1]]),a.add(o.vertices[t.vertexIds[2]]),a.divideScalar(3),a.x=r.roundNumber(a.x,2),a.y=r.roundNumber(a.y,2),a.z=r.roundNumber(a.z,2),i[s]={id:s,neighbours:h,vertexIds:t.vertexIds,centroid:a,portals:c}}),o.groups[s]=i}),o}static _buildNavigationMesh(t,e){return t=r.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 r=[],s=[],n=t.attributes.position,o=t.index,i=[];for(let t=0;t<n.count;t++)s.push((new e.Vector3).fromBufferAttribute(n,t)),i[t]=[];for(let e=0;e<t.index.count;e+=3){const t=o.getX(e),s=o.getX(e+1),n=o.getX(e+2),h={vertexIds:[t,s,n],neighbours:null};r.push(h),i[t].push(h),i[s].push(h),i[n].push(h)}return r.forEach(t=>{t.neighbours=this._buildPolygonNeighbours(t,i)}),{polygons:r,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,s)}setZoneData(t,e){this.zones[t]=e}getRandomNode(t,s,n,o){if(!this.zones[t])return new e.Vector3;n=n||null,o=o||0;const i=[];return this.zones[t].groups[s].forEach(t=>{n&&o?r.distanceToSquared(n,t.centroid)<o*o&&i.push(t.centroid):i.push(t.centroid)}),r.sample(i)||new e.Vector3}getClosestNode(t,e,s,n=!1){const o=this.zones[e].vertices;let i=null,h=Infinity;return this.zones[e].groups[s].forEach(e=>{const s=r.distanceToSquared(e.centroid,t);s<h&&(!n||r.isVectorInPolygon(t,e,o))&&(i=e,h=s)}),i}findPath(t,o,i,h){const c=this.zones[i].groups[h],a=this.zones[i].vertices,u=this.getClosestNode(t,i,h,!0),l=this.getClosestNode(o,i,h,!0);if(!u||!l)return null;const d=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 s(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 r.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(c,u,l),p=function(t,e){for(var r=0;r<t.neighbours.length;r++)if(t.neighbours[r]===e.id)return t.portals[r]},g=new n;g.push(t);for(let t=0;t<d.length;t++){const e=d[t],r=d[t+1];if(r){const t=p(e,r);g.push(a[t[0]],a[t[1]])}}g.push(o),g.stringPull();const f=g.path.map(t=>new e.Vector3(t.x,t.y,t.z));return f.shift(),f}}o.prototype.getGroup=function(){const t=new e.Plane;return function(e,s,n=!1){if(!this.zones[e])return null;let o=null,i=Math.pow(50,2);const h=this.zones[e];for(let e=0;e<h.groups.length;e++){const c=h.groups[e];for(const a of c){if(n&&(t.setFromCoplanarPoints(h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]),Math.abs(t.distanceToPoint(s))<.01)&&r.isPointInPoly([h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]],s))return e;const c=r.distanceToSquared(a.centroid,s);c<i&&(o=e,i=c)}}return o}}(),o.prototype.clampStep=function(){const t=new e.Vector3,r=new e.Plane,s=new e.Triangle,n=new e.Vector3;let o,i,h=new e.Vector3;return function(e,c,a,u,l,d){const p=this.zones[u].vertices,g=this.zones[u].groups[l],f=[a],v={};v[a.id]=0,o=void 0,h.set(0,0,0),i=Infinity,r.setFromCoplanarPoints(p[a.vertexIds[0]],p[a.vertexIds[1]],p[a.vertexIds[2]]),r.projectPoint(c,t),n.copy(t);for(let e=f.pop();e;e=f.pop()){s.set(p[e.vertexIds[0]],p[e.vertexIds[1]],p[e.vertexIds[2]]),s.closestPointToPoint(n,t),t.distanceToSquared(n)<i&&(o=e,h.copy(t),i=t.distanceToSquared(n));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(h),o}}(),t.Pathfinding=o,t.PathfindingHelper=class extends e.Object3D{constructor(){super(),this._playerMarker=new e.Mesh(new e.SphereGeometry(.25,32,32),new e.MeshBasicMaterial({color:15631215})),this._targetMarker=new e.Mesh(new e.BoxGeometry(.3,.3,.3),new e.MeshBasicMaterial({color:14469912})),this._nodeMarker=new e.Mesh(new e.BoxGeometry(.1,.8,.1),new e.MeshBasicMaterial({color:4417387})),this._stepMarker=new e.Mesh(new e.BoxGeometry(.1,1,.1),new e.MeshBasicMaterial({color:14472114})),this._pathMarker=new e.Object3D,this._pathLineMaterial=new e.LineBasicMaterial({color:41903,linewidth:2}),this._pathPointMaterial=new e.MeshBasicMaterial({color:41903}),this._pathPointGeometry=new e.SphereGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(t=>{t.visible=!1,this.add(t)})}setPath(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);const r=new e.BufferGeometry;r.setAttribute("position",new e.BufferAttribute(new Float32Array(3*t.length),3));for(let e=0;e<t.length;e++)r.attributes.position.setXYZ(e,t[e].x,t[e].y+.2,t[e].z);this._pathMarker.add(new e.Line(r,this._pathLineMaterial));for(let r=0;r<t.length-1;r++){const s=new e.Mesh(this._pathPointGeometry,this._pathPointMaterial);s.position.copy(t[r]),s.position.y+=.2,this._pathMarker.add(s)}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}}});
 //# sourceMappingURL=three-pathfinding.umd.js.map

package.json

 {
 	"name": "three-pathfinding",
-	"version": "1.2.0",
+	"version": "1.3.0",
 	"description": "Navigation mesh toolkit for three.js, based on PatrolJS",
@@ -17,2 +17,3 @@ "author": "Don McCurdy <[e-mail]>",
 	"module": "dist/three-pathfinding.module.js",
+	"types": "dist/three-pathfinding.d.ts",
 	"source": "src/index.js",
@@ -25,5 +26,5 @@ "browserslist": [
 		"build": "yarn dist && vite build --config demo/vite.config.js",
-		"dev": "concurrently \"yarn watch\" \"vite --config demo/vite.config.js --port 5000\"",
-		"watch": "microbundle watch --target web --globals three=THREE --external three",
-		"dist": "microbundle --target web --globals three=THREE --external three",
+		"dev": "concurrently \"yarn watch\" \"vite --config demo/vite.config.js --port 3000\"",
+		"watch": "microbundle watch --target web --globals three=THREE --external three --no-generateTypes && node scripts/copy-definition.mjs",
+		"dist": "microbundle --target web --globals three=THREE --external three --no-generateTypes && node scripts/copy-definition.mjs",
 		"version": "npm run dist && yarn test",
@@ -54,10 +55,10 @@ "postversion": "git push && git push --tags && npm publish",
 	"devDependencies": {
-		"concurrently": "7.6.0",
-		"documentation": "14.0.1",
+		"concurrently": "8.2.2",
+		"documentation": "14.0.3",
 		"microbundle": "0.15.1",
 		"replace-between": "0.0.8",
 		"tap-spec": "5.0.0",
-		"tape": "5.6.1",
-		"three": "0.147.0",
-		"vite": "^4.1.1"
+		"tape": "5.7.5",
+		"three": "0.164.1",
+		"vite": "^5.2.11"
 	},
@@ -72,3 +73,3 @@ "files": [
 	],
-	"dependencies": {}
+	"packageManager": "yarn@4.2.2"
 }

README.md

 # three-pathfinding
 
 [![Latest NPM release](https://img.shields.io/npm/v/three-pathfinding.svg)](https://www.npmjs.com/package/three-pathfinding)
-[![Minzipped size](https://badgen.net/bundlephobia/minzip/three-pathfinding)](https://bundlephobia.com/result?p=three-pathfinding)
+[![npm bundle size](https://img.shields.io/bundlephobia/minzip/three-pathfinding)](https://bundlephobia.com/package/three-pathfinding)
 [![License](https://img.shields.io/badge/license-MIT-007ec6.svg)](https://github.com/donmccurdy/three-pathfinding/blob/master/LICENSE)
@@ -90,3 +90,3 @@ [![Build Status](https://github.com/donmccurdy/three-pathfinding/workflows/build/badge.svg?branch=main&event=push)](https://github.com/donmccurdy/three-pathfinding/actions?query=workflow%3Abuild)
 
-The demo will start at http://localhost:5000/.
+The demo will start at http://localhost:3000/.
 
@@ -93,0 +93,0 @@ ## API

src/PathfindingHelper.js

@@ -6,3 +6,2 @@ import {
   BufferGeometry,
-  Color,
   Line,
@@ -17,8 +16,8 @@ LineBasicMaterial,
 const colors = {
-  PLAYER: new Color( 0xee836f ).convertSRGBToLinear().getHex(),
-  TARGET: new Color( 0xdccb18 ).convertSRGBToLinear().getHex(),
-  PATH: new Color( 0x00a3af ).convertSRGBToLinear().getHex(),
-  WAYPOINT: new Color( 0x00a3af ).convertSRGBToLinear().getHex(),
-  CLAMPED_STEP: new Color( 0xdcd3b2 ).convertSRGBToLinear().getHex(),
-  CLOSEST_NODE: new Color( 0x43676b ).convertSRGBToLinear().getHex(),
+  PLAYER: 0xEE836F,
+  TARGET: 0xDCCB18,
+  PATH: 0x00A3AF,
+  WAYPOINT: 0x00A3AF,
+  CLAMPED_STEP: 0xDCD3B2,
+  CLOSEST_NODE: 0x43676B,
 };
@@ -25,0 +24,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

368010

increased by0.67%

Number of package files

24

increased by14.29%

Lines of code

1403

increased by16.82%

No dependency changes