three-pathfinding - npm Package Compare versions

Comparing version 1.1.0 to 1.2.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.SphereBufferGeometry(.25,32,32),new t.MeshBasicMaterial({color:o.PLAYER})),this._targetMarker=new t.Mesh(new t.BoxBufferGeometry(.3,.3,.3),new t.MeshBasicMaterial({color:o.TARGET})),this._nodeMarker=new t.Mesh(new t.BoxBufferGeometry(.1,.8,.1),new t.MeshBasicMaterial({color:o.CLOSEST_NODE})),this._stepMarker=new t.Mesh(new t.BoxBufferGeometry(.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.SphereBufferGeometry(.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}}();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}};
 //# sourceMappingURL=three-pathfinding.js.map

dist/three-pathfinding.modern.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,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).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 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};
 //# sourceMappingURL=three-pathfinding.modern.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,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).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 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};
 //# sourceMappingURL=three-pathfinding.module.js.map

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){class r{static roundNumber(e,t){const r=Math.pow(10,t);return Math.round(e*r)/r}static sample(e){return e[Math.floor(Math.random()*e.length)]}static distanceToSquared(e,t){var r=e.x-t.x,s=e.y-t.y,n=e.z-t.z;return r*r+s*s+n*n}static isPointInPoly(e,t){for(var r=!1,s=-1,n=e.length,o=n-1;++s<n;o=s)(e[s].z<=t.z&&t.z<e[o].z||e[o].z<=t.z&&t.z<e[s].z)&&t.x<(e[o].x-e[s].x)*(t.z-e[s].z)/(e[o].z-e[s].z)+e[s].x&&(r=!r);return r}static isVectorInPolygon(e,t,r){var s=1e5,n=-1e5,o=[];return t.vertexIds.forEach(e=>{s=Math.min(r[e].y,s),n=Math.max(r[e].y,n),o.push(r[e])}),!!(e.y<n+.5&&e.y>s-.5&&this.isPointInPoly(o,e))}static triarea2(e,t,r){return(r.x-e.x)*(t.z-e.z)-(t.x-e.x)*(r.z-e.z)}static vequal(e,t){return this.distanceToSquared(e,t)<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 s{constructor(e){this.content=[],this.scoreFunction=e}push(e){this.content.push(e),this.sinkDown(this.content.length-1)}pop(){const e=this.content[0],t=this.content.pop();return this.content.length>0&&(this.content[0]=t,this.bubbleUp(0)),e}remove(e){const 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))}size(){return this.content.length}rescoreElement(e){this.sinkDown(this.content.indexOf(e))}sinkDown(e){const t=this.content[e];for(;e>0;){const r=(e+1>>1)-1,s=this.content[r];if(!(this.scoreFunction(t)<this.scoreFunction(s)))break;this.content[r]=t,this.content[e]=s,e=r}}bubbleUp(e){const t=this.content.length,r=this.content[e],s=this.scoreFunction(r);for(;;){const n=e+1<<1,o=n-1;let i,h=null;if(o<t&&(i=this.scoreFunction(this.content[o]),i<s&&(h=o)),n<t&&this.scoreFunction(this.content[n])<(null===h?s:i)&&(h=n),null===h)break;this.content[e]=this.content[h],this.content[h]=r,e=h}}}class n{constructor(){this.portals=[]}push(e,t){void 0===t&&(t=e),this.portals.push({left:e,right:t})}stringPull(){const e=this.portals,t=[];let s,n,o,i=0,h=0,c=0;s=e[0].left,n=e[0].left,o=e[0].right,t.push(s);for(let a=1;a<e.length;a++){const u=e[a].left,l=e[a].right;if(r.triarea2(s,o,l)<=0){if(!(r.vequal(s,o)||r.triarea2(s,n,l)>0)){t.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)){t.push(o),s=o,i=c,n=s,o=s,h=i,c=i,a=i;continue}n=u,h=a}}return 0!==t.length&&r.vequal(t[t.length-1],e[e.length-1].left)||t.push(e[e.length-1].left),this.path=t,t}}class o{constructor(){this.zones={}}static createZone(e,s=1e-4){return class{static buildZone(e,s){const n=this._buildNavigationMesh(e,s),o={};n.vertices.forEach(e=>{e.x=r.roundNumber(e.x,2),e.y=r.roundNumber(e.y,2),e.z=r.roundNumber(e.z,2)}),o.vertices=n.vertices;const i=this._buildPolygonGroups(n);return o.groups=new Array(i.length),i.forEach((e,s)=>{const n=new Map;e.forEach((e,t)=>{n.set(e,t)});const i=new Array(e.length);e.forEach((e,s)=>{const h=[];e.neighbours.forEach(e=>h.push(n.get(e)));const c=[];e.neighbours.forEach(t=>c.push(this._getSharedVerticesInOrder(e,t)));const a=new t.Vector3(0,0,0);a.add(o.vertices[e.vertexIds[0]]),a.add(o.vertices[e.vertexIds[1]]),a.add(o.vertices[e.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:e.vertexIds,centroid:a,portals:c}}),o.groups[s]=i}),o}static _buildNavigationMesh(e,t){return e=r.mergeVertices(e,t),this._buildPolygonsFromGeometry(e)}static _spreadGroupId(e){let t=new Set([e]);for(;t.size>0;){const r=t;t=new Set,r.forEach(r=>{r.group=e.group,r.neighbours.forEach(e=>{void 0===e.group&&t.add(e)})})}}static _buildPolygonGroups(e){const t=[];return e.polygons.forEach(e=>{void 0!==e.group?t[e.group].push(e):(e.group=t.length,this._spreadGroupId(e),t.push([e]))}),t}static _buildPolygonNeighbours(e,t){const r=new Set,s=t[e.vertexIds[1]],n=t[e.vertexIds[2]];return t[e.vertexIds[0]].forEach(t=>{t!==e&&(s.includes(t)||n.includes(t))&&r.add(t)}),s.forEach(t=>{t!==e&&n.includes(t)&&r.add(t)}),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(e=>{e.neighbours=this._buildPolygonNeighbours(e,i)}),{polygons:r,vertices:s}}static _getSharedVerticesInOrder(e,t){const r=e.vertexIds,s=r[0],n=r[1],o=r[2],i=t.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(e,s)}setZoneData(e,t){this.zones[e]=t}getRandomNode(e,s,n,o){if(!this.zones[e])return new t.Vector3;n=n||null,o=o||0;const i=[];return this.zones[e].groups[s].forEach(e=>{n&&o?r.distanceToSquared(n,e.centroid)<o*o&&i.push(e.centroid):i.push(e.centroid)}),r.sample(i)||new t.Vector3}getClosestNode(e,t,s,n=!1){const o=this.zones[t].vertices;let i=null,h=Infinity;return this.zones[t].groups[s].forEach(t=>{const s=r.distanceToSquared(t.centroid,e);s<h&&(!n||r.isVectorInPolygon(e,t,o))&&(i=t,h=s)}),i}findPath(e,o,i,h){const c=this.zones[i].groups[h],a=this.zones[i].vertices,u=this.getClosestNode(e,i,h,!0),l=this.getClosestNode(o,i,h,!0);if(!u||!l)return null;const d=class{static init(e){for(let t=0;t<e.length;t++){const r=e[t];r.f=0,r.g=0,r.h=0,r.cost=1,r.visited=!1,r.closed=!1,r.parent=null}}static cleanUp(e){for(let t=0;t<e.length;t++){const r=e[t];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(e){return e.f})}static search(e,t,r){this.init(e);const s=this.heap();for(s.push(t);s.size()>0;){const t=s.pop();if(t===r){let e=t;const r=[];for(;e.parent;)r.push(e),e=e.parent;return this.cleanUp(r),r.reverse()}t.closed=!0;const n=this.neighbours(e,t);for(let e=0,o=n.length;e<o;e++){const o=n[e];if(o.closed)continue;const i=t.g+o.cost,h=o.visited;if(!h||i<o.g){if(o.visited=!0,o.parent=t,!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(e,t){return r.distanceToSquared(e,t)}static neighbours(e,t){const r=[];for(let s=0;s<t.neighbours.length;s++)r.push(e[t.neighbours[s]]);return r}}.search(c,u,l),p=function(e,t){for(var r=0;r<e.neighbours.length;r++)if(e.neighbours[r]===t.id)return e.portals[r]},g=new n;g.push(e);for(let e=0;e<d.length;e++){const t=d[e],r=d[e+1];if(r){const e=p(t,r);g.push(a[e[0]],a[e[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}}o.prototype.getGroup=function(){const e=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&&(e.setFromCoplanarPoints(h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]),Math.abs(e.distanceToPoint(s))<.01)&&r.isPointInPoly([h.vertices[a.vertexIds[0]],h.vertices[a.vertexIds[1]],h.vertices[a.vertexIds[2]]],s))return t;const c=r.distanceToSquared(a.centroid,s);c<i&&(o=t,i=c)}}return o}}(),o.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 i={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()};e.Pathfinding=o,e.PathfindingHelper=class extends t.Object3D{constructor(){super(),this._playerMarker=new t.Mesh(new t.SphereBufferGeometry(.25,32,32),new t.MeshBasicMaterial({color:i.PLAYER})),this._targetMarker=new t.Mesh(new t.BoxBufferGeometry(.3,.3,.3),new t.MeshBasicMaterial({color:i.TARGET})),this._nodeMarker=new t.Mesh(new t.BoxBufferGeometry(.1,.8,.1),new t.MeshBasicMaterial({color:i.CLOSEST_NODE})),this._stepMarker=new t.Mesh(new t.BoxBufferGeometry(.1,1,.1),new t.MeshBasicMaterial({color:i.CLAMPED_STEP})),this._pathMarker=new t.Object3D,this._pathLineMaterial=new t.LineBasicMaterial({color:i.PATH,linewidth:2}),this._pathPointMaterial=new t.MeshBasicMaterial({color:i.WAYPOINT}),this._pathPointGeometry=new t.SphereBufferGeometry(.08),this._markers=[this._playerMarker,this._targetMarker,this._nodeMarker,this._stepMarker,this._pathMarker],this._markers.forEach(e=>{e.visible=!1,this.add(e)})}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(e){return this._playerMarker.position.copy(e),this._playerMarker.visible=!0,this}setTargetPosition(e){return this._targetMarker.position.copy(e),this._targetMarker.visible=!0,this}setNodePosition(e){return this._nodeMarker.position.copy(e),this._nodeMarker.visible=!0,this}setStepPosition(e){return this._stepMarker.position.copy(e),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(e=>{e.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}}();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}}});
 //# sourceMappingURL=three-pathfinding.umd.js.map

package.json

 {
 	"name": "three-pathfinding",
-	"version": "1.1.0",
+	"version": "1.2.0",
 	"description": "Navigation mesh toolkit for three.js, based on PatrolJS",
@@ -23,10 +23,12 @@ "author": "Don McCurdy <[e-mail]>",
 	"scripts": {
-		"dev": "concurrently \"microbundle watch --target web --globals three=THREE --external three\" \"serve --listen 5000\"",
-		"docs": "documentation build src/Pathfinding.js src/PathfindingHelper.js --shallow -f md | replace-between --target README.md --token API",
+		"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",
-		"version": "npm run dist && npm test",
+		"version": "npm run dist && yarn test",
 		"postversion": "git push && git push --tags && npm publish",
+		"docs": "documentation build src/Pathfinding.js src/PathfindingHelper.js --shallow -f md | replace-between --target README.md --token API",
 		"test": "node tests/index.test.js | tap-spec",
 		"benchmark": "node benchmark/index.benchmark.js",
-		"deploy": "npm run dist && npm test && vercel --prod"
+		"deploy": "yarn build && yarn test && vercel --prod"
 	},
@@ -51,11 +53,10 @@ "keywords": [
 	"devDependencies": {
-		"concurrently": "7.0.0",
-		"documentation": "13.2.5",
-		"microbundle": "0.14.2",
+		"concurrently": "7.6.0",
+		"documentation": "14.0.1",
+		"microbundle": "0.15.1",
 		"replace-between": "0.0.8",
-		"serve": "13.0.2",
 		"tap-spec": "5.0.0",
-		"tape": "5.5.0",
-		"three": "0.137.5",
-		"uglify-js": "3.15.0"
+		"tape": "5.6.1",
+		"three": "0.147.0",
+		"vite": "^4.1.1"
 	},
@@ -69,3 +70,4 @@ "files": [
 		"package-lock.json"
-	]
+	],
+	"dependencies": {}
 }

README.md

@@ -6,3 +6,3 @@ # three-pathfinding
 [![License](https://img.shields.io/badge/license-MIT-007ec6.svg)](https://github.com/donmccurdy/three-pathfinding/blob/master/LICENSE)
-[![Build Status](https://github.com/donmccurdy/three-pathfinding/workflows/build/badge.svg?branch=master&event=push)](https://github.com/donmccurdy/three-pathfinding/actions?query=workflow%3Abuild)
+[![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)
 
@@ -91,3 +91,3 @@ Navigation mesh toolkit for ThreeJS, based on [PatrolJS](https://github.com/nickjanssen/PatrolJS). Computes paths between points on a 3D nav mesh, supports multiple zones, and clamps movement vectors for FPS controls. To learn how to create a navigation mesh using Blender, see [Creating a Nav Mesh](https://www.donmccurdy.com/2017/08/20/creating-a-nav-mesh-for-a-webvr-scene/).
 
-The demo will start at http://localhost:5000/demo/.
+The demo will start at http://localhost:5000/.
 
@@ -94,0 +94,0 @@ ## API

src/PathfindingHelper.js

 import {
-  BoxBufferGeometry,
+  BoxGeometry,
+  SphereGeometry,
   BufferAttribute,
@@ -11,3 +12,2 @@ BufferGeometry,
   Object3D,
-  SphereBufferGeometry,
   Vector3,
@@ -35,3 +35,3 @@ } from 'three';
     this._playerMarker = new Mesh(
-      new SphereBufferGeometry( 0.25, 32, 32 ),
+      new SphereGeometry( 0.25, 32, 32 ),
       new MeshBasicMaterial( { color: colors.PLAYER } )
@@ -41,3 +41,3 @@ );
     this._targetMarker = new Mesh(
-      new BoxBufferGeometry( 0.3, 0.3, 0.3 ),
+      new BoxGeometry( 0.3, 0.3, 0.3 ),
       new MeshBasicMaterial( { color: colors.TARGET } )
@@ -48,3 +48,3 @@ );
     this._nodeMarker = new Mesh(
-      new BoxBufferGeometry( 0.1, 0.8, 0.1 ),
+      new BoxGeometry( 0.1, 0.8, 0.1 ),
       new MeshBasicMaterial( { color: colors.CLOSEST_NODE } )
@@ -55,3 +55,3 @@ );
     this._stepMarker = new Mesh(
-      new BoxBufferGeometry( 0.1, 1, 0.1 ),
+      new BoxGeometry( 0.1, 1, 0.1 ),
       new MeshBasicMaterial( { color: colors.CLAMPED_STEP } )
@@ -64,3 +64,3 @@ );
     this._pathPointMaterial = new MeshBasicMaterial( { color: colors.WAYPOINT } );
-    this._pathPointGeometry = new SphereBufferGeometry( 0.08 );
+    this._pathPointGeometry = new SphereGeometry( 0.08 );
 
@@ -67,0 +67,0 @@ this._markers = [

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

365549

increased by21.74%

Dev dependency count

8

decreased by-11.11%

Number of package files

21

increased by10.53%

Lines of code

1201

increased by3.71%

No dependency changes