navmesh - npm Package Compare versions

Comparing version 2.2.1 to 2.3.0

dist/navmesh.js

		@@ -1,2 +0,2 @@
		!function(t,n){"object"==typeof exports&&"object"==typeof module?module.exports=n():"function"==typeof define&&define.amd?define([],n):"object"==typeof exports?exports.NavMesh=n():t.NavMesh=n()}("undefined"!=typeof self?self:this,(function(){return(()=>{var t={774:(t,n)=>{var i,s,o,e;e=function(){function t(t){for(var n=t,i=[];n.parent;)i.unshift(n),n=n.parent;return i}var n={search:function(i,s,e,r){i.cleanDirty();var h=(r=r\|\|{}).heuristic\|\|n.heuristics.manhattan,a=r.closest\|\|!1,c=new o((function(t){return t.f})),u=s;for(s.h=h(s,e),i.markDirty(s),c.push(s);c.size()>0;){var l=c.pop();if(l===e)return t(l);l.closed=!0;for(var p=i.neighbors(l),d=0,g=p.length;d<g;++d){var f=p[d];if(!f.closed&&!f.isWall()){var y=l.g+f.getCost(l),x=f.visited;(!x\|\|y<f.g)&&(f.visited=!0,f.parent=l,f.h=f.h\|\|h(f,e),f.g=y,f.f=f.g+f.h,i.markDirty(f),a&&(f.h<u.h\|\|f.h===u.h&&f.g<u.g)&&(u=f),x?c.rescoreElement(f):c.push(f))}}}return a?t(u):[]},heuristics:{manhattan:function(t,n){return Math.abs(n.x-t.x)+Math.abs(n.y-t.y)},diagonal:function(t,n){var i=Math.sqrt(2),s=Math.abs(n.x-t.x),o=Math.abs(n.y-t.y);return 1(s+o)+(i-2)Math.min(s,o)}},cleanNode:function(t){t.f=0,t.g=0,t.h=0,t.visited=!1,t.closed=!1,t.parent=null}};function i(t,n){n=n\|\|{},this.nodes=[],this.diagonal=!!n.diagonal,this.grid=[];for(var i=0;i<t.length;i++){this.grid[i]=[];for(var o=0,e=t[i];o<e.length;o++){var r=new s(i,o,e[o]);this.grid[i][o]=r,this.nodes.push(r)}}this.init()}function s(t,n,i){this.x=t,this.y=n,this.weight=i}function o(t){this.content=[],this.scoreFunction=t}return i.prototype.init=function(){this.dirtyNodes=[];for(var t=0;t<this.nodes.length;t++)n.cleanNode(this.nodes[t])},i.prototype.cleanDirty=function(){for(var t=0;t<this.dirtyNodes.length;t++)n.cleanNode(this.dirtyNodes[t]);this.dirtyNodes=[]},i.prototype.markDirty=function(t){this.dirtyNodes.push(t)},i.prototype.neighbors=function(t){var n=[],i=t.x,s=t.y,o=this.grid;return o[i-1]&&o[i-1][s]&&n.push(o[i-1][s]),o[i+1]&&o[i+1][s]&&n.push(o[i+1][s]),o[i]&&o[i][s-1]&&n.push(o[i][s-1]),o[i]&&o[i][s+1]&&n.push(o[i][s+1]),this.diagonal&&(o[i-1]&&o[i-1][s-1]&&n.push(o[i-1][s-1]),o[i+1]&&o[i+1][s-1]&&n.push(o[i+1][s-1]),o[i-1]&&o[i-1][s+1]&&n.push(o[i-1][s+1]),o[i+1]&&o[i+1][s+1]&&n.push(o[i+1][s+1])),n},i.prototype.toString=function(){for(var t=[],n=this.grid,i=0;i<n.length;i++){for(var s=[],o=n[i],e=0;e<o.length;e++)s.push(o[e].weight);t.push(s.join(" "))}return t.join("\n")},s.prototype.toString=function(){return"["+this.x+" "+this.y+"]"},s.prototype.getCost=function(t){return t&&t.x!=this.x&&t.y!=this.y?1.41421this.weight:this.weight},s.prototype.isWall=function(){return 0===this.weight},o.prototype={push:function(t){this.content.push(t),this.sinkDown(this.content.length-1)},pop:function(){var t=this.content[0],n=this.content.pop();return this.content.length>0&&(this.content[0]=n,this.bubbleUp(0)),t},remove:function(t){var n=this.content.indexOf(t),i=this.content.pop();n!==this.content.length-1&&(this.content[n]=i,this.scoreFunction(i)<this.scoreFunction(t)?this.sinkDown(n):this.bubbleUp(n))},size:function(){return this.content.length},rescoreElement:function(t){this.sinkDown(this.content.indexOf(t))},sinkDown:function(t){for(var n=this.content[t];t>0;){var i=(t+1>>1)-1,s=this.content[i];if(!(this.scoreFunction(n)<this.scoreFunction(s)))break;this.content[i]=n,this.content[t]=s,t=i}},bubbleUp:function(t){for(var n=this.content.length,i=this.content[t],s=this.scoreFunction(i);;){var o,e=t+1<<1,r=e-1,h=null;if(r<n){var a=this.content[r];(o=this.scoreFunction(a))<s&&(h=r)}if(e<n){var c=this.content[e];this.scoreFunction(c)<(null===h?s:o)&&(h=e)}if(null===h)break;this.content[t]=this.content[h],this.content[h]=i,t=h}}},{astar:n,Graph:i}},"object"==typeof t.exports?t.exports=e():(s=[],void 0===(o="function"==typeof(i=e)?i.apply(void 0,s):i)\|\|(t.exports=o))}},n={};function i(s){var o=n[s];if(void 0!==o)return o.exports;var e=n[s]={exports:{}};return t[s](e,e.exports,i),e.exports}i.n=t=>{var n=t&&t.__esModule?()=>t.default:()=>t;return i.d(n,{a:n}),n},i.d=(t,n)=>{for(var s in n)i.o(n,s)&&!i.o(t,s)&&Object.defineProperty(t,s,{enumerable:!0,get:n[s]})},i.o=(t,n)=>Object.prototype.hasOwnProperty.call(t,n);var s={};return(()=>{"use strict";i.d(s,{default:()=>g});var t=i(774),n=i.n(t);class o{x;y;constructor(t=0,n=0){this.x=t,this.y=n}equals(t){return this.x===t.x&&this.y===t.y}angle(t){return Math.atan2(t.y-this.y,t.x-this.x)}distance(t){const n=t.x-this.x,i=t.y-this.y;return Math.sqrt(nn+ii)}add(t){this.x+=t.x,this.y+=t.y}subtract(t){this.x-=t.x,this.y-=t.y}clone(){return new o(this.x,this.y)}}class e{id;polygon;edges;neighbors;portals;centroid;boundingRadius;weight=1;x=0;y=0;constructor(t,n){this.id=t,this.polygon=n,this.edges=n.edges,this.neighbors=[],this.portals=[],this.centroid=this.calculateCentroid(),this.boundingRadius=this.calculateRadius()}getPoints(){return this.polygon.points}contains(t){return this.polygon.contains(t.x,t.y)\|\|this.isPointOnEdge(t)}calculateCentroid(){const t=new o(0,0),n=this.polygon.points.length;return this.polygon.points.forEach((n=>t.add(n))),t.x/=n,t.y/=n,t}calculateRadius(){let t=0;for(const n of this.polygon.points){const i=this.centroid.distance(n);i>t&&(t=i)}return t}isPointOnEdge({x:t,y:n}){for(const i of this.edges)if(i.pointOnSegment(t,n))return!0;return!1}destroy(){this.neighbors=[],this.portals=[]}toString(){return`NavPoly(id: ${this.id} at: ${this.centroid})`}isWall(){return 0===this.weight}centroidDistance(t){return this.centroid.distance(t.centroid)}getCost(t){return this.centroidDistance(t)}}function r(t,n){const i=n.start,s=n.end,e=function(t,n){const i=n.x-t.x,s=n.y-t.y;return ii+ss}(i,s);let r=((t.x-i.x)(s.x-i.x)+(t.y-i.y)(s.y-i.y))/e;var h;return(h=r)<0&&(h=0),h>1&&(h=1),r=h,new o(i.x+r(s.x-i.x),i.y+r(s.y-i.y))}function h(t,n,i){const s=n.x-t.x,o=n.y-t.y;return(i.x-t.x)o-s(i.y-t.y)}function a(t,n,i=1e-4){return Math.abs(t-n)<=i}function c(t,n){let i=t-n;const s=i+Math.PI,o=2Math.PI;return i=s-Math.floor(s/o)o,i-=Math.PI,i}function u(t,n,i=1e-4){const s=h(t.start,t.end,n.start),o=h(t.start,t.end,n.end);return!(!a(s,0,i)\|\|!a(o,0,i))}class l{path;portals;constructor(){this.portals=[],this.path=[]}push(t,n){void 0===n&&(n=t),this.portals.push({left:t,right:n})}stringPull(){const t=this.portals,n=[];let i=0,s=0,o=0,e=t[0].left,r=t[0].left,a=t[0].right;n.push(e);for(var c=1;c<t.length;c++){const u=t[c].left,l=t[c].right;if(h(e,a,l)<=0){if(!(e.equals(a)\|\|h(e,r,l)>0)){n.push(r),e=r,i=s,r=e,a=e,s=i,o=i,c=i;continue}a=l,o=c}if(h(e,r,u)>=0){if(!(e.equals(r)\|\|h(e,a,u)<0)){n.push(a),e=a,i=o,r=e,a=e,s=i,o=i,c=i;continue}r=u,s=c}}return 0!==n.length&&n[n.length-1].equals(t[t.length-1].left)\|\|n.push(t[t.length-1].left),this.path=n,n}}class p{start;end;left;right;top;bottom;constructor(t,n,i,s){this.start=new o(t,n),this.end=new o(i,s),this.left=Math.min(t,i),this.right=Math.max(t,i),this.top=Math.min(n,s),this.bottom=Math.max(n,s)}pointOnSegment(t,n){return t>=this.left&&t<=this.right&&n>=this.top&&n<=this.bottom&&this.pointOnLine(t,n)}pointOnLine(t,n){return(t-this.left)(this.bottom-this.top)==(this.right-this.left)(n-this.top)}}class d{edges;points;isClosed;constructor(t,n=!0){this.isClosed=n,this.points=t,this.edges=[];for(let n=1;n<t.length;n++){const i=t[n-1],s=t[n];this.edges.push(new p(i.x,i.y,s.x,s.y))}if(this.isClosed){const n=t[0],i=t[t.length-1];this.edges.push(new p(n.x,n.y,i.x,i.y))}}contains(t,n){let i=!1;for(let s=-1,o=this.points.length-1;++s<this.points.length;o=s){const e=this.points[s].x,r=this.points[s].y,h=this.points[o].x,a=this.points[o].y;(r<=n&&n<a\|\|a<=n&&n<r)&&t<(h-e)(n-r)/(a-r)+e&&(i=!i)}return i}}const g=class{meshShrinkAmount;navPolygons;graph;constructor(t,i=0){this.meshShrinkAmount=i;const s=t.map((t=>{const n=t.map((t=>new o(t.x,t.y)));return new d(n)}));this.navPolygons=s.map(((t,n)=>new e(n,t))),this.calculateNeighbors(),this.graph=new class{nodes;grid=[];constructor(t){this.nodes=t,this.init()}neighbors(t){return t.neighbors}navHeuristic(t,n){return t.centroidDistance(n)}destroy(){this.cleanDirty(),this.nodes=[]}init=n().Graph.prototype.init.bind(this);cleanDirty=n().Graph.prototype.cleanDirty.bind(this);markDirty=n().Graph.prototype.markDirty.bind(this);toString=n().Graph.prototype.toString.bind(this)}(this.navPolygons)}getPolygons(){return this.navPolygons}destroy(){this.graph.destroy();for(const t of this.navPolygons)t.destroy();this.navPolygons=[]}isPointInMesh(t){return this.navPolygons.some((n=>n.contains(t)))}findClosestMeshPoint(t,n=Number.POSITIVE_INFINITY){let i=n,s=null,o=null;for(const n of this.navPolygons){if(n.contains(t)){i=0,s=n,o=t;break}const e=n.boundingRadius;if(n.centroid.distance(t)-e<i){const e=this.projectPointToPolygon(t,n);e.distance<i&&(i=e.distance,s=n,o=e.point)}}return{distance:i,polygon:s,point:o}}findPath(t,i){let s,e,r=null,h=null,a=Number.MAX_VALUE,c=Number.MAX_VALUE;const u=new o(t.x,t.y),p=new o(i.x,i.y);for(const t of this.navPolygons)e=t.boundingRadius,s=t.centroid.distance(u),s<=a&&s<=e&&t.contains(u)&&(r=t,a=s),s=t.centroid.distance(p),s<=c&&s<=e&&t.contains(p)&&(h=t,c=s);if(!h&&this.meshShrinkAmount>0)for(const t of this.navPolygons)if(e=t.boundingRadius+this.meshShrinkAmount,s=t.centroid.distance(p),s<=e){const{distance:n}=this.projectPointToPolygon(p,t);n<=this.meshShrinkAmount&&n<c&&(h=t,c=n)}if(!h)return null;if(!r&&this.meshShrinkAmount>0)for(const t of this.navPolygons)if(e=t.boundingRadius+this.meshShrinkAmount,s=t.centroid.distance(u),s<=e){const{distance:n}=this.projectPointToPolygon(u,t);n<=this.meshShrinkAmount&&n<a&&(r=t,a=n)}if(!r)return null;if(r===h)return[u,p];const d=n().astar.search(this.graph,r,h,{heuristic:this.graph.navHeuristic});if(0===d.length)return null;d.unshift(r);const g=new l;g.push(u);for(let t=0;t<d.length-1;t++){const n=d[t],i=d[t+1];let s=null;for(let t=0;t<n.neighbors.length;t++)n.neighbors[t].id===i.id&&(s=n.portals[t]);if(!s)throw new Error("Path was supposed to be found, but portal is missing!");g.push(s.start,s.end)}g.push(p),g.stringPull();let f=null;const y=[];for(const t of g.path){const n=t.clone();f&&n.equals(f)\|\|y.push(n),f=n}return y}calculateNeighbors(){for(let t=0;t<this.navPolygons.length;t++){const n=this.navPolygons[t];for(let i=t+1;i<this.navPolygons.length;i++){const t=this.navPolygons[i];if(!(n.centroid.distance(t.centroid)>n.boundingRadius+t.boundingRadius))for(const i of n.edges)for(const s of t.edges){if(!u(i,s))continue;const o=this.getSegmentOverlap(i,s);if(!o)continue;n.neighbors.push(t),t.neighbors.push(n);const[e,r]=o;let h=n.centroid.angle(i.start),a=n.centroid.angle(o[0]),l=n.centroid.angle(o[1]),d=c(h,a),g=c(h,l);d<g?n.portals.push(new p(e.x,e.y,r.x,r.y)):n.portals.push(new p(r.x,r.y,e.x,e.y)),h=t.centroid.angle(s.start),a=t.centroid.angle(o[0]),l=t.centroid.angle(o[1]),d=c(h,a),g=c(h,l),d<g?t.portals.push(new p(e.x,e.y,r.x,r.y)):t.portals.push(new p(r.x,r.y,e.x,e.y))}}}}getSegmentOverlap(t,n){const i=[{line:t,point:t.start},{line:t,point:t.end},{line:n,point:n.start},{line:n,point:n.end}];i.sort((function(t,n){return t.point.x<n.point.x?-1:t.point.x>n.point.x?1:t.point.y<n.point.y?-1:t.point.y>n.point.y?1:0}));const s=i[0].line===i[1].line,o=i[1].point.equals(i[2].point);return s\|\|o?null:[i[1].point,i[2].point]}projectPointToPolygon(t,n){let i=null,s=Number.MAX_VALUE;for(const o of n.edges){const n=r(t,o),e=t.distance(n);(null===i\|\|e<s)&&(s=e,i=n)}return{point:i,distance:s}}}})(),s.default})()}));
		!function(t,i){"object"==typeof exports&&"object"==typeof module?module.exports=i():"function"==typeof define&&define.amd?define([],i):"object"==typeof exports?exports.NavMesh=i():t.NavMesh=i()}("undefined"!=typeof self?self:this,(function(){return(()=>{var t={774:(t,i)=>{var n,o,e,s;s=function(){function t(t){for(var i=t,n=[];i.parent;)n.unshift(i),i=i.parent;return n}var i={search:function(n,o,s,r){n.cleanDirty();var h=(r=r\|\|{}).heuristic\|\|i.heuristics.manhattan,l=r.closest\|\|!1,a=new e((function(t){return t.f})),c=o;for(o.h=h(o,s),n.markDirty(o),a.push(o);a.size()>0;){var u=a.pop();if(u===s)return t(u);u.closed=!0;for(var d=n.neighbors(u),g=0,p=d.length;g<p;++g){var f=d[g];if(!f.closed&&!f.isWall()){var y=u.g+f.getCost(u),x=f.visited;(!x\|\|y<f.g)&&(f.visited=!0,f.parent=u,f.h=f.h\|\|h(f,s),f.g=y,f.f=f.g+f.h,n.markDirty(f),l&&(f.h<c.h\|\|f.h===c.h&&f.g<c.g)&&(c=f),x?a.rescoreElement(f):a.push(f))}}}return l?t(c):[]},heuristics:{manhattan:function(t,i){return Math.abs(i.x-t.x)+Math.abs(i.y-t.y)},diagonal:function(t,i){var n=Math.sqrt(2),o=Math.abs(i.x-t.x),e=Math.abs(i.y-t.y);return 1(o+e)+(n-2)Math.min(o,e)}},cleanNode:function(t){t.f=0,t.g=0,t.h=0,t.visited=!1,t.closed=!1,t.parent=null}};function n(t,i){i=i\|\|{},this.nodes=[],this.diagonal=!!i.diagonal,this.grid=[];for(var n=0;n<t.length;n++){this.grid[n]=[];for(var e=0,s=t[n];e<s.length;e++){var r=new o(n,e,s[e]);this.grid[n][e]=r,this.nodes.push(r)}}this.init()}function o(t,i,n){this.x=t,this.y=i,this.weight=n}function e(t){this.content=[],this.scoreFunction=t}return n.prototype.init=function(){this.dirtyNodes=[];for(var t=0;t<this.nodes.length;t++)i.cleanNode(this.nodes[t])},n.prototype.cleanDirty=function(){for(var t=0;t<this.dirtyNodes.length;t++)i.cleanNode(this.dirtyNodes[t]);this.dirtyNodes=[]},n.prototype.markDirty=function(t){this.dirtyNodes.push(t)},n.prototype.neighbors=function(t){var i=[],n=t.x,o=t.y,e=this.grid;return e[n-1]&&e[n-1][o]&&i.push(e[n-1][o]),e[n+1]&&e[n+1][o]&&i.push(e[n+1][o]),e[n]&&e[n][o-1]&&i.push(e[n][o-1]),e[n]&&e[n][o+1]&&i.push(e[n][o+1]),this.diagonal&&(e[n-1]&&e[n-1][o-1]&&i.push(e[n-1][o-1]),e[n+1]&&e[n+1][o-1]&&i.push(e[n+1][o-1]),e[n-1]&&e[n-1][o+1]&&i.push(e[n-1][o+1]),e[n+1]&&e[n+1][o+1]&&i.push(e[n+1][o+1])),i},n.prototype.toString=function(){for(var t=[],i=this.grid,n=0;n<i.length;n++){for(var o=[],e=i[n],s=0;s<e.length;s++)o.push(e[s].weight);t.push(o.join(" "))}return t.join("\n")},o.prototype.toString=function(){return"["+this.x+" "+this.y+"]"},o.prototype.getCost=function(t){return t&&t.x!=this.x&&t.y!=this.y?1.41421this.weight:this.weight},o.prototype.isWall=function(){return 0===this.weight},e.prototype={push:function(t){this.content.push(t),this.sinkDown(this.content.length-1)},pop:function(){var t=this.content[0],i=this.content.pop();return this.content.length>0&&(this.content[0]=i,this.bubbleUp(0)),t},remove:function(t){var i=this.content.indexOf(t),n=this.content.pop();i!==this.content.length-1&&(this.content[i]=n,this.scoreFunction(n)<this.scoreFunction(t)?this.sinkDown(i):this.bubbleUp(i))},size:function(){return this.content.length},rescoreElement:function(t){this.sinkDown(this.content.indexOf(t))},sinkDown:function(t){for(var i=this.content[t];t>0;){var n=(t+1>>1)-1,o=this.content[n];if(!(this.scoreFunction(i)<this.scoreFunction(o)))break;this.content[n]=i,this.content[t]=o,t=n}},bubbleUp:function(t){for(var i=this.content.length,n=this.content[t],o=this.scoreFunction(n);;){var e,s=t+1<<1,r=s-1,h=null;if(r<i){var l=this.content[r];(e=this.scoreFunction(l))<o&&(h=r)}if(s<i){var a=this.content[s];this.scoreFunction(a)<(null===h?o:e)&&(h=s)}if(null===h)break;this.content[t]=this.content[h],this.content[h]=n,t=h}}},{astar:i,Graph:n}},"object"==typeof t.exports?t.exports=s():(o=[],void 0===(e="function"==typeof(n=s)?n.apply(void 0,o):n)\|\|(t.exports=e))}},i={};function n(o){var e=i[o];if(void 0!==e)return e.exports;var s=i[o]={exports:{}};return t[o](s,s.exports,n),s.exports}n.n=t=>{var i=t&&t.__esModule?()=>t.default:()=>t;return n.d(i,{a:i}),i},n.d=(t,i)=>{for(var o in i)n.o(i,o)&&!n.o(t,o)&&Object.defineProperty(t,o,{enumerable:!0,get:i[o]})},n.o=(t,i)=>Object.prototype.hasOwnProperty.call(t,i),n.r=t=>{"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})};var o={};return(()=>{"use strict";n.r(o),n.d(o,{NavMesh:()=>f,PointQueue:()=>x,RectangleHull:()=>b,buildPolysFromGridMap:()=>m,default:()=>w});var t=n(774),i=n.n(t);class e{x;y;constructor(t=0,i=0){this.x=t,this.y=i}equals(t){return this.x===t.x&&this.y===t.y}angle(t){return Math.atan2(t.y-this.y,t.x-this.x)}distance(t){const i=t.x-this.x,n=t.y-this.y;return Math.sqrt(ii+nn)}add(t){this.x+=t.x,this.y+=t.y}subtract(t){this.x-=t.x,this.y-=t.y}clone(){return new e(this.x,this.y)}}class s{id;polygon;edges;neighbors;portals;centroid;boundingRadius;weight=1;x=0;y=0;constructor(t,i){this.id=t,this.polygon=i,this.edges=i.edges,this.neighbors=[],this.portals=[],this.centroid=this.calculateCentroid(),this.boundingRadius=this.calculateRadius()}getPoints(){return this.polygon.points}contains(t){return this.polygon.contains(t.x,t.y)\|\|this.isPointOnEdge(t)}calculateCentroid(){const t=new e(0,0),i=this.polygon.points.length;return this.polygon.points.forEach((i=>t.add(i))),t.x/=i,t.y/=i,t}calculateRadius(){let t=0;for(const i of this.polygon.points){const n=this.centroid.distance(i);n>t&&(t=n)}return t}isPointOnEdge({x:t,y:i}){for(const n of this.edges)if(n.pointOnSegment(t,i))return!0;return!1}destroy(){this.neighbors=[],this.portals=[]}toString(){return`NavPoly(id: ${this.id} at: ${this.centroid})`}isWall(){return 0===this.weight}centroidDistance(t){return this.centroid.distance(t.centroid)}getCost(t){return this.centroidDistance(t)}}function r(t,i){const n=i.start,o=i.end,s=function(t,i){const n=i.x-t.x,o=i.y-t.y;return nn+oo}(n,o);let r=((t.x-n.x)(o.x-n.x)+(t.y-n.y)(o.y-n.y))/s;var h;return(h=r)<0&&(h=0),h>1&&(h=1),r=h,new e(n.x+r(o.x-n.x),n.y+r(o.y-n.y))}function h(t,i,n){const o=i.x-t.x,e=i.y-t.y;return(n.x-t.x)e-o(n.y-t.y)}function l(t,i,n=1e-4){return Math.abs(t-i)<=n}function a(t,i){let n=t-i;const o=n+Math.PI,e=2Math.PI;return n=o-Math.floor(o/e)e,n-=Math.PI,n}function c(t,i,n=1e-4){const o=h(t.start,t.end,i.start),e=h(t.start,t.end,i.end);return!(!l(o,0,n)\|\|!l(e,0,n))}function u(t){return Boolean(t)}class d{path;portals;constructor(){this.portals=[],this.path=[]}push(t,i){void 0===i&&(i=t),this.portals.push({left:t,right:i})}stringPull(){const t=this.portals,i=[];let n=0,o=0,e=0,s=t[0].left,r=t[0].left,l=t[0].right;i.push(s);for(var a=1;a<t.length;a++){const c=t[a].left,u=t[a].right;if(h(s,l,u)<=0){if(!(s.equals(l)\|\|h(s,r,u)>0)){i.push(r),s=r,n=o,r=s,l=s,o=n,e=n,a=n;continue}l=u,e=a}if(h(s,r,c)>=0){if(!(s.equals(r)\|\|h(s,l,c)<0)){i.push(l),s=l,n=e,r=s,l=s,o=n,e=n,a=n;continue}r=c,o=a}}return 0!==i.length&&i[i.length-1].equals(t[t.length-1].left)\|\|i.push(t[t.length-1].left),this.path=i,i}}class g{start;end;left;right;top;bottom;constructor(t,i,n,o){this.start=new e(t,i),this.end=new e(n,o),this.left=Math.min(t,n),this.right=Math.max(t,n),this.top=Math.min(i,o),this.bottom=Math.max(i,o)}pointOnSegment(t,i){return t>=this.left&&t<=this.right&&i>=this.top&&i<=this.bottom&&this.pointOnLine(t,i)}pointOnLine(t,i){return(t-this.left)(this.bottom-this.top)==(this.right-this.left)(i-this.top)}}class p{edges;points;isClosed;constructor(t,i=!0){this.isClosed=i,this.points=t,this.edges=[];for(let i=1;i<t.length;i++){const n=t[i-1],o=t[i];this.edges.push(new g(n.x,n.y,o.x,o.y))}if(this.isClosed){const i=t[0],n=t[t.length-1];this.edges.push(new g(i.x,i.y,n.x,n.y))}}contains(t,i){let n=!1;for(let o=-1,e=this.points.length-1;++o<this.points.length;e=o){const s=this.points[o].x,r=this.points[o].y,h=this.points[e].x,l=this.points[e].y;(r<=i&&i<l\|\|l<=i&&i<r)&&t<(h-s)(i-r)/(l-r)+s&&(n=!n)}return n}}class f{meshShrinkAmount;navPolygons;graph;constructor(t,n=0){this.meshShrinkAmount=n;const o=t.map((t=>{const i=t.map((t=>new e(t.x,t.y)));return new p(i)}));this.navPolygons=o.map(((t,i)=>new s(i,t))),this.calculateNeighbors(),this.graph=new class{nodes;grid=[];constructor(t){this.nodes=t,this.init()}neighbors(t){return t.neighbors}navHeuristic(t,i){return t.centroidDistance(i)}destroy(){this.cleanDirty(),this.nodes=[]}init=i().Graph.prototype.init.bind(this);cleanDirty=i().Graph.prototype.cleanDirty.bind(this);markDirty=i().Graph.prototype.markDirty.bind(this);toString=i().Graph.prototype.toString.bind(this)}(this.navPolygons)}getPolygons(){return this.navPolygons}destroy(){this.graph.destroy();for(const t of this.navPolygons)t.destroy();this.navPolygons=[]}isPointInMesh(t){return this.navPolygons.some((i=>i.contains(t)))}findClosestMeshPoint(t,i=Number.POSITIVE_INFINITY){let n=i,o=null,e=null;for(const i of this.navPolygons){if(i.contains(t)){n=0,o=i,e=t;break}const s=i.boundingRadius;if(i.centroid.distance(t)-s<n){const s=this.projectPointToPolygon(t,i);s.distance<n&&(n=s.distance,o=i,e=s.point)}}return{distance:n,polygon:o,point:e}}findPath(t,n){let o,s,r=null,h=null,l=Number.MAX_VALUE,a=Number.MAX_VALUE;const c=new e(t.x,t.y),u=new e(n.x,n.y);for(const t of this.navPolygons)s=t.boundingRadius,o=t.centroid.distance(c),o<=l&&o<=s&&t.contains(c)&&(r=t,l=o),o=t.centroid.distance(u),o<=a&&o<=s&&t.contains(u)&&(h=t,a=o);if(!h&&this.meshShrinkAmount>0)for(const t of this.navPolygons)if(s=t.boundingRadius+this.meshShrinkAmount,o=t.centroid.distance(u),o<=s){const{distance:i}=this.projectPointToPolygon(u,t);i<=this.meshShrinkAmount&&i<a&&(h=t,a=i)}if(!h)return null;if(!r&&this.meshShrinkAmount>0)for(const t of this.navPolygons)if(s=t.boundingRadius+this.meshShrinkAmount,o=t.centroid.distance(c),o<=s){const{distance:i}=this.projectPointToPolygon(c,t);i<=this.meshShrinkAmount&&i<l&&(r=t,l=i)}if(!r)return null;if(r===h)return[c,u];const g=i().astar.search(this.graph,r,h,{heuristic:this.graph.navHeuristic});if(0===g.length)return null;g.unshift(r);const p=new d;p.push(c);for(let t=0;t<g.length-1;t++){const i=g[t],n=g[t+1];let o=null;for(let t=0;t<i.neighbors.length;t++)i.neighbors[t].id===n.id&&(o=i.portals[t]);if(!o)throw new Error("Path was supposed to be found, but portal is missing!");p.push(o.start,o.end)}p.push(u),p.stringPull();let f=null;const y=[];for(const t of p.path){const i=t.clone();f&&i.equals(f)\|\|y.push(i),f=i}return y}calculateNeighbors(){for(let t=0;t<this.navPolygons.length;t++){const i=this.navPolygons[t];for(let n=t+1;n<this.navPolygons.length;n++){const t=this.navPolygons[n];if(!(i.centroid.distance(t.centroid)>i.boundingRadius+t.boundingRadius))for(const n of i.edges)for(const o of t.edges){if(!c(n,o))continue;const e=this.getSegmentOverlap(n,o);if(!e)continue;i.neighbors.push(t),t.neighbors.push(i);const[s,r]=e;let h=i.centroid.angle(n.start),l=i.centroid.angle(e[0]),u=i.centroid.angle(e[1]),d=a(h,l),p=a(h,u);d<p?i.portals.push(new g(s.x,s.y,r.x,r.y)):i.portals.push(new g(r.x,r.y,s.x,s.y)),h=t.centroid.angle(o.start),l=t.centroid.angle(e[0]),u=t.centroid.angle(e[1]),d=a(h,l),p=a(h,u),d<p?t.portals.push(new g(s.x,s.y,r.x,r.y)):t.portals.push(new g(r.x,r.y,s.x,s.y))}}}}getSegmentOverlap(t,i){const n=[{line:t,point:t.start},{line:t,point:t.end},{line:i,point:i.start},{line:i,point:i.end}];n.sort((function(t,i){return t.point.x<i.point.x?-1:t.point.x>i.point.x?1:t.point.y<i.point.y?-1:t.point.y>i.point.y?1:0}));const o=n[0].line===n[1].line,e=n[1].point.equals(n[2].point);return o\|\|e?null:[n[1].point,n[2].point]}projectPointToPolygon(t,i){let n=null,o=Number.MAX_VALUE;for(const e of i.edges){const i=r(t,e),s=t.distance(i);(null===n\|\|s<o)&&(o=s,n=i)}return{point:n,distance:o}}}class y{width;height;tileWidth;tileHeight;map;isWalkableTest;constructor(t,i,n,o){this.map=t,this.isWalkableTest=i,this.height=t.length,this.width=t[0].length,this.tileWidth=n,this.tileHeight=o}forEach(t){this.map.forEach(((i,n)=>{i.forEach(((i,o)=>{t(o,n,this.map[n][o])}))}))}isInGrid(t,i){return t>=0&&t<this.width&&i>=0&&i<this.height}isWalkable(t,i){return this.isInGrid(t,i)&&this.isWalkableTest(this.map[i][t],t,i)}isBlocked(t,i){return this.isInGrid(t,i)&&!this.isWalkableTest(this.map[i][t],t,i)}isBlockedAtWorld(t,i){return this.isBlocked(this.getGridX(t),this.getGridY(i))}getGridX(t){return Math.floor(t/this.tileWidth)}getGridY(t){return Math.floor(t/this.tileHeight)}getGridXY(t,i){return{x:this.getGridX(t),y:this.getGridY(i)}}getWorldX(t){return tthis.tileWidth}getWorldY(t){return tthis.tileHeight}getWorldXY(t,i){return{x:this.getWorldX(t),y:this.getWorldY(i)}}}class x{data=[];add(t){this.data.push(t)}shift(){return this.data.shift()}isEmpty(){return 0===this.data.length}containsPoint(t){return void 0!==this.data.find((i=>i.x===t.x&&i.y===t.y))}containsAllPoints(t){return t.every((t=>this.containsPoint(t)))}getIndexOfPoint(t){return this.data.findIndex((i=>i.x==t.x&&i.y==t.y))}removePoint(t){const i=this.getIndexOfPoint(t);-1!==i&&this.data.splice(i,1)}removePoints(t){t.forEach((t=>this.removePoint(t)))}}class b{x;y;width;height;constructor(t,i,n,o){this.x=t,this.y=i,this.width=n,this.height=o}setPosition(t,i){this.x=t,this.y=i}setSize(t,i){this.width=t,this.height=i}set(t,i,n,o){this.setPosition(t,i),this.setSize(n,o)}get left(){return this.x}set left(t){this.x=t}get top(){return this.y}set top(t){this.y=t}get right(){return this.x+this.width}set right(t){this.width=t-this.x}get bottom(){return this.y+this.height}set bottom(t){this.height=t-this.top}get center(){return{x:(this.x+this.right)/2,y:(this.y+this.bottom)/2}}doesOverlap(t){return!(this.right<t.x\|\|this.x>t.right\|\|this.y>t.bottom\|\|this.bottom<t.y)}attemptMergeIn(t){const i=this.x===t.x&&this.width===t.width,n=this.y===t.y&&this.height===t.height;return i&&this.top===t.bottom?(this.height+=t.height,this.y=t.y,!0):i&&this.bottom===t.top?(this.bottom=t.bottom,!0):n&&this.left===t.right?(this.width+=t.width,this.x=t.x,!0):!(!n\|\|this.right!==t.left\|\|(this.right=t.right,0))}toPoints(){const{left:t,right:i,top:n,bottom:o}=this;return[{x:t,y:n},{x:i,y:n},{x:i,y:o},{x:t,y:o}]}}function m(t,i=1,n=1,o=u,e=0){const s=new y(t,o,i,n);if(e>=i\|\|e>=n)throw new Error(`navmesh: Unsupported shrink amount ${e}. Must be less than tile width and height.`);let r=function(t){const i=new x,{tileWidth:n,tileHeight:o}=t,e=[];let s;t.forEach(((n,o)=>{t.isWalkable(n,o)&&i.add({x:n,y:o})}));const r=(t,n)=>{const o=((t,i)=>{const{top:n,left:o,right:e,bottom:s}=t;let r=[];if("top"===i)for(let t=o;t<=e-1;t++)r.push({x:t,y:n});else if("bottom"===i)for(let t=o;t<=e-1;t++)r.push({x:t,y:s});else if("left"===i)for(let t=n;t<=s-1;t++)r.push({x:o,y:t});else{if("right"!==i)throw new Error(`Invalid dir "${i}" for extend`);for(let t=n;t<=s-1;t++)r.push({x:e,y:t})}return r})(t,n),e=i.containsAllPoints(o);return e&&(((t,i)=>{if("top"===i)t.y-=1;else if("bottom"===i)t.bottom+=1;else if("left"===i)t.x-=1;else{if("right"!==i)throw new Error(`Invalid dir "${i}" for extend`);t.right+=1}})(t,n),i.removePoints(o)),e};for(;!i.isEmpty();){const t=i.shift();if(void 0===t)break;s=new b(t.x,t.y,1,1);let h=!0;for(;h;){const t=r(s,"top"),i=r(s,"right"),n=r(s,"left"),o=r(s,"bottom");h=t\|\|o\|\|n\|\|i}s.setPosition(s.xn,s.yo),s.setSize(s.widthn,s.heighto),e.push(s)}return e}(s);return e>0&&(r=function(t,i,n){const{tileHeight:o,tileWidth:e}=i,s=[],r=[];t.forEach(((t,h)=>{const l=o,a=e,c=i.getGridX(t.x),u=i.getGridY(t.y),d=i.getGridY(t.bottom),g=i.getGridX(t.right),p=v(t,i,n,e,o);if(t.left>=t.right\|\|t.top>=t.bottom)return;r.push(t);const f=[],y=[],x=(t,i,n,o)=>{const e=new b(t,i,n,o);n>o?y.push(e):f.push(e)};if(p.left){const o=t.left-n;let e=u,s=e-1;for(let t=u;t<d;t++)i.isBlocked(c-1,t)?(e<=s&&x(o,el,n,(s-e+1)l),e=t+1):s=t;e<=s&&x(o,el,n,(s-e+1)l)}if(p.right){const o=t.right;let e=u,s=e-1;for(let t=u;t<d;t++)i.isBlocked(g,t)?(e<=s&&x(o,el,n,(s-e+1)l),e=t+1):s=t;e<=s&&x(o,el,n,(s-e+1)l)}if(p.top){const o=t.top-n;let e=c,s=e-1;for(let t=c;t<g;t++)i.isBlocked(t,u-1)?(e<=s&&x(ea,o,(s-e+1)l,n),e=t+1):s=t;e<=s&&x(ea,o,(s-e+1)l,n)}if(p.bottom){const o=t.bottom;let e=c,s=e-1;for(let t=c;t<g;t++)i.isBlocked(t,d)?(e<=s&&x(ea,o,(s-e+1)l,n),e=t+1):s=t;e<=s&&x(ea,o,(s-e+1)l,n)}y.forEach((t=>{f.forEach((i=>{t.doesOverlap(i)&&(t.y>i.y?i.height-=n:i.top+=n)}))})),[...y,...f].forEach((t=>{v(t,i,n,e,o),t.left>=t.right\|\|t.top>=t.bottom\|\|s.push(t)}))}));for(let i=0;i<s.length;i++){let n=!1;for(const o of t)if(n=o.attemptMergeIn(s[i]),n)break;if(!n){for(let t=i+1;t<s.length&&(n=s[t].attemptMergeIn(s[i]),!n);t++);n\|\|r.push(s[i])}}return r}(r,s,e)),r.map((t=>t.toPoints()))}function v(t,i,n,o,e){const s=n,r=o/2,h=e/2,{left:l,top:a,right:c,bottom:u}=t,d={left:!1,right:!1,top:!1,bottom:!1,topLeft:i.isBlockedAtWorld(l-s,a-s),topRight:i.isBlockedAtWorld(c+s,a-s),bottomLeft:i.isBlockedAtWorld(l-s,u+s),bottomRight:i.isBlockedAtWorld(c+s,u+s)};for(let t=a+h;t<u;t+=h)if(i.isBlockedAtWorld(l-s,t)){d.left=!0;break}for(let t=a+h;t<u;t+=h)if(i.isBlockedAtWorld(c+s,t)){d.right=!0;break}for(let t=l+r;t<c;t+=r)if(i.isBlockedAtWorld(t,a-n)){d.top=!0;break}for(let t=l+r;t<c;t+=r)if(i.isBlockedAtWorld(t,u+n)){d.bottom=!0;break}const g={left:d.left,right:d.right,top:d.top,bottom:d.bottom};return!d.topLeft\|\|d.left\|\|d.top\|\|(t.width>t.height?g.left=!0:g.top=!0),!d.topRight\|\|d.right\|\|d.top\|\|(t.width>t.height?g.right=!0:g.top=!0),!d.bottomLeft\|\|d.bottom\|\|d.left\|\|(t.width>t.height?g.left=!0:g.bottom=!0),!d.bottomRight\|\|d.bottom\|\|d.right\|\|(t.width>t.height?g.right=!0:g.bottom=!0),g.left&&(t.x+=n,t.width-=n),g.top&&(t.y+=n,t.height-=n),g.right&&(t.width-=n),g.bottom&&(t.height-=n),g}const w=f})(),o})()}));
		//# sourceMappingURL=navmesh.js.map

package.json

		{
		"name": "navmesh",
		"version": "2.2.1",
		"version": "2.3.0",
		"description": "A library for fast pathfinding using navigation meshes in JS",
		@@ -55,3 +55,3 @@ "main": "dist/navmesh.js",
		"homepage": "https://github.com/mikewesthad/phaser-navmesh-plugin#readme",
		"gitHead": "9a4066ae12d68e9d3f1ff1d359097153730b2258"
		"gitHead": "3a3d21e259e67480fab9ec76c674d849855fa81f"
		}

README.md

		@@ -9,2 +9,6 @@ # NavMesh

		Version 2.3.0

		- Fix: webpack misconfiguration that caused [issue 37](https://github.com/mikewesthad/navmesh/issues/37). The build was only picking up the "default" export, but now it properly picks up all library exports. Thanks to[@Wenish](https://github.com/Wenish).

		Version 2.2.1
		@@ -11,0 +15,0 @@

dist/navmesh.js.map

Sorry, the diff of this file is not supported yet

navmesh - npm Package Compare versions

New alerts

Fixed alerts

Improved metrics