navmesh - npm Package Compare versions

Comparing version 2.2.0 to 2.2.1

dist/channel.d.ts

@@ -0,0 +0,0 @@ import Vector2 from "./math/vector-2";

dist/common-types.d.ts

@@ -0,0 +0,0 @@ export interface Point {

dist/index.d.ts

@@ -0,0 +0,0 @@ /**

dist/map-parsers/build-polys-from-grid-map.d.ts

 import { PolyPoints } from "../common-types";
+import { TileWalkableTest } from "./grid-map";
 /**
@@ -21,3 +22,3 @@ * This parses a world that is a uniform grid into convex polygons (specifically rectangles) that
  */
-export default function buildPolysFromGridMap<TileType>(map: TileType[][], tileWidth?: number, tileHeight?: number, isWalkable?: (tile: TileType, x: number, y: number) => boolean): PolyPoints[];
+export default function buildPolysFromGridMap<TileType>(map: TileType[][], tileWidth?: number, tileHeight?: number, isWalkable?: TileWalkableTest<TileType>, shrinkAmount?: number): PolyPoints[];
 //# sourceMappingURL=build-polys-from-grid-map.d.ts.map

dist/map-parsers/index.d.ts

@@ -0,0 +0,0 @@ /**

dist/map-parsers/point-queue.d.ts

@@ -0,0 +0,0 @@ import { Point } from "../common-types";

dist/map-parsers/rectangle-hull.d.ts

@@ -6,13 +6,31 @@ import { Point } from "../common-types";
 export declare class RectangleHull {
-    left: number;
-    right: number;
-    top: number;
-    bottom: number;
-    tiles: Point[];
-    constructor(left: number, top: number, right: number, bottom: number);
-    forEachTopPoint(fn: (x: number, y: number) => void): void;
-    forEachBottomPoint(fn: (x: number, y: number) => void): void;
-    forEachLeftPoint(fn: (x: number, y: number) => void): void;
-    forEachRightPoint(fn: (x: number, y: number) => void): void;
+    x: number;
+    y: number;
+    width: number;
+    height: number;
+    constructor(x: number, y: number, width: number, height: number);
+    setPosition(x: number, y: number): void;
+    setSize(width: number, height: number): void;
+    set(left: number, top: number, width: number, height: number): void;
+    get left(): number;
+    set left(val: number);
+    get top(): number;
+    set top(val: number);
+    get right(): number;
+    set right(val: number);
+    get bottom(): number;
+    set bottom(val: number);
+    get center(): Point;
+    doesOverlap(otherHull: RectangleHull): boolean;
+    /**
+     * Attempt to merge another hull into this one. If they share an edge, `this` will be extended to
+     * contain `otherHull`.
+     * @param otherHull
+     */
+    attemptMergeIn(otherHull: RectangleHull): boolean;
+    toPoints(): {
+        x: number;
+        y: number;
+    }[];
 }
 //# sourceMappingURL=rectangle-hull.d.ts.map

dist/math/line.d.ts

@@ -0,0 +0,0 @@ import Vector2 from "./vector-2";

dist/math/polygon.d.ts

@@ -0,0 +0,0 @@ import { Point } from "../common-types";

dist/math/vector-2.d.ts

@@ -0,0 +0,0 @@ import { Point } from "../common-types";

dist/navgraph.d.ts

@@ -0,0 +0,0 @@ import jsastar from "javascript-astar";

dist/navmesh.d.ts

@@ -0,0 +0,0 @@ import NavPoly from "./navpoly";

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,c=r.closest||!1,a=new o((function(t){return t.f})),u=s;for(s.h=h(s,e),i.markDirty(s),a.push(s);a.size()>0;){var l=a.pop();if(l===e)return t(l);l.closed=!0;for(var p=i.neighbors(l),d=0,f=p.length;d<f;++d){var g=p[d];if(!g.closed&&!g.isWall()){var y=l.g+g.getCost(l),x=g.visited;(!x||y<g.g)&&(g.visited=!0,g.parent=l,g.h=g.h||h(g,e),g.g=y,g.f=g.g+g.h,i.markDirty(g),c&&(g.h<u.h||g.h===u.h&&g.g<u.g)&&(u=g),x?a.rescoreElement(g):a.push(g))}}}return c?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.41421*this.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 c=this.content[r];(o=this.scoreFunction(c))<s&&(h=r)}if(e<n){var a=this.content[e];this.scoreFunction(a)<(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))},636:(t,n,i)=>{"use strict";i.d(n,{default:()=>g});var s=i(774),o=i.n(s);class e{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(n*n+i*i)}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 r{constructor(t,n){this.weight=1,this.x=0,this.y=0,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 e(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 h(t,n){const i=n.start,s=n.end,o=function(t,n){const i=n.x-t.x,s=n.y-t.y;return i*i+s*s}(i,s);let r=((t.x-i.x)*(s.x-i.x)+(t.y-i.y)*(s.y-i.y))/o;var h;return(h=r)<0&&(h=0),h>1&&(h=1),r=h,new e(i.x+r*(s.x-i.x),i.y+r*(s.y-i.y))}function c(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 u(t,n){let i=t-n;const s=i+Math.PI,o=2*Math.PI;return i=s-Math.floor(s/o)*o,i-=Math.PI,i}function l(t,n,i=1e-4){const s=c(t.start,t.end,n.start),o=c(t.start,t.end,n.end);return!(!a(s,0,i)||!a(o,0,i))}class p{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,h=t[0].right;n.push(e);for(var a=1;a<t.length;a++){const u=t[a].left,l=t[a].right;if(c(e,h,l)<=0){if(!(e.equals(h)||c(e,r,l)>0)){n.push(r),e=r,i=s,r=e,h=e,s=i,o=i,a=i;continue}h=l,o=a}if(c(e,r,u)>=0){if(!(e.equals(r)||c(e,h,u)<0)){n.push(h),e=h,i=o,r=e,h=e,s=i,o=i,a=i;continue}r=u,s=a}}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 d{constructor(t,n,i,s){this.start=new e(t,n),this.end=new e(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 f{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 d(i.x,i.y,s.x,s.y))}if(this.isClosed){const n=t[0],i=t[t.length-1];this.edges.push(new d(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,c=this.points[o].y;(r<=n&&n<c||c<=n&&n<r)&&t<(h-e)*(n-r)/(c-r)+e&&(i=!i)}return i}}const g=class{constructor(t,n=0){this.meshShrinkAmount=n;const i=t.map((t=>{const n=t.map((t=>new e(t.x,t.y)));return new f(n)}));this.navPolygons=i.map(((t,n)=>new r(n,t))),this.calculateNeighbors(),this.graph=new class{constructor(t){this.grid=[],this.init=o().Graph.prototype.init.bind(this),this.cleanDirty=o().Graph.prototype.cleanDirty.bind(this),this.markDirty=o().Graph.prototype.markDirty.bind(this),this.toString=o().Graph.prototype.toString.bind(this),this.nodes=t,this.init()}neighbors(t){return t.neighbors}navHeuristic(t,n){return t.centroidDistance(n)}destroy(){this.cleanDirty(),this.nodes=[]}}(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,n){let i,s,r=null,h=null,c=Number.MAX_VALUE,a=Number.MAX_VALUE;const u=new e(t.x,t.y),l=new e(n.x,n.y);for(const t of this.navPolygons)s=t.boundingRadius,i=t.centroid.distance(u),i<=c&&i<=s&&t.contains(u)&&(r=t,c=i),i=t.centroid.distance(l),i<=a&&i<=s&&t.contains(l)&&(h=t,a=i);if(!h&&this.meshShrinkAmount>0)for(const t of this.navPolygons)if(s=t.boundingRadius+this.meshShrinkAmount,i=t.centroid.distance(l),i<=s){const{distance:n}=this.projectPointToPolygon(l,t);n<=this.meshShrinkAmount&&n<a&&(h=t,a=n)}if(!h)return null;if(!r&&this.meshShrinkAmount>0)for(const t of this.navPolygons)if(s=t.boundingRadius+this.meshShrinkAmount,i=t.centroid.distance(u),i<=s){const{distance:n}=this.projectPointToPolygon(u,t);n<=this.meshShrinkAmount&&n<c&&(r=t,c=n)}if(!r)return null;if(r===h)return[u,l];const d=o().astar.search(this.graph,r,h,{heuristic:this.graph.navHeuristic});if(0===d.length)return null;d.unshift(r);const f=new p;f.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!");f.push(s.start,s.end)}f.push(l),f.stringPull();let g=null;const y=[];for(const t of f.path){const n=t.clone();g&&n.equals(g)||y.push(n),g=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(!l(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),c=n.centroid.angle(o[0]),a=n.centroid.angle(o[1]),p=u(h,c),f=u(h,a);p<f?n.portals.push(new d(e.x,e.y,r.x,r.y)):n.portals.push(new d(r.x,r.y,e.x,e.y)),h=t.centroid.angle(s.start),c=t.centroid.angle(o[0]),a=t.centroid.angle(o[1]),p=u(h,c),f=u(h,a),p<f?t.portals.push(new d(e.x,e.y,r.x,r.y)):t.portals.push(new d(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=h(t,o),e=t.distance(n);(null===i||e<s)&&(s=e,i=n)}return{point:i,distance:s}}}}},n={};function i(s){if(n[s])return n[s].exports;var o=n[s]={exports:{}};return t[s](o,o.exports,i),o.exports}return 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),i(636)})().default}));
+!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.41421*this.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(n*n+i*i)}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 i*i+s*s}(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=2*Math.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})()}));
 //# sourceMappingURL=navmesh.js.map

dist/navpoly.d.ts

@@ -0,0 +0,0 @@ import Line from "./math/line";

dist/utils.d.ts

@@ -0,0 +0,0 @@ import { Point } from "./common-types";

package.json

 {
   "name": "navmesh",
-  "version": "2.2.0",
+  "version": "2.2.1",
   "description": "A library for fast pathfinding using navigation meshes in JS",
@@ -23,14 +23,15 @@ "main": "dist/navmesh.js",
   "devDependencies": {
-    "@babel/core": "^7.12.13",
-    "@babel/preset-env": "^7.12.13",
-    "@types/jest": "^26.0.20",
-    "babel-jest": "^26.6.3",
+    "@babel/core": "^7.14.6",
+    "@babel/preset-env": "^7.14.5",
+    "@types/jest": "^26.0.23",
+    "babel-jest": "^27.0.2",
     "babel-loader": "^8.2.2",
     "clean-webpack-plugin": "^3.0.0",
-    "eslint": "^7.19.0",
-    "jest": "^26.6.3",
-    "ts-jest": "^26.5.1",
-    "ts-loader": "^8.0.17",
-    "typescript": "^4.1.5",
-    "webpack-cli": "^4.5.0"
+    "eslint": "^7.29.0",
+    "jest": "^27.0.4",
+    "ts-jest": "^27.0.3",
+    "ts-loader": "^9.2.3",
+    "typescript": "^4.3.4",
+    "webpack": "^5.40.0",
+    "webpack-cli": "^4.7.2"
   },
@@ -55,3 +56,3 @@ "repository": {
   "homepage": "https://github.com/mikewesthad/phaser-navmesh-plugin#readme",
-  "gitHead": "d4a4676c6bf2798eb69ff8aabdf5a6483591b136"
+  "gitHead": "9a4066ae12d68e9d3f1ff1d359097153730b2258"
 }

README.md

@@ -9,2 +9,6 @@ # NavMesh
 
+Version 2.2.1
+
+- Update all dependencies to the latest versions.
+
 Version 2.2.0
@@ -11,0 +15,0 @@

src/map-parsers/build-polys-from-grid-map.ts

 import { Point, PolyPoints } from "../common-types";
 import { isTruthy } from "../utils";
+import { GridMap, TileWalkableTest } from "./grid-map";
 import { PointQueue } from "./point-queue";
@@ -31,22 +32,52 @@ import { RectangleHull } from "./rectangle-hull";
   tileHeight: number = 1,
-  isWalkable: (tile: TileType, x: number, y: number) => boolean = isTruthy
-) {
+  isWalkable: TileWalkableTest<TileType> = isTruthy,
+  shrinkAmount: number = 0
+): PolyPoints[] {
+  const gridMap = new GridMap(map, isWalkable, tileWidth, tileHeight);
+
+  if (shrinkAmount >= tileWidth || shrinkAmount >= tileHeight) {
+    throw new Error(
+      `navmesh: Unsupported shrink amount ${shrinkAmount}. Must be less than tile width and height.`
+    );
+  }
+
+  let hulls: RectangleHull[] = buildInitialHulls(gridMap);
+
+  if (shrinkAmount > 0) {
+    hulls = shrinkHulls(hulls, gridMap, shrinkAmount);
+  }
+
+  return hulls.map((hull) => hull.toPoints());
+}
+
+/**
+ * Build up rectangular hulls from the walkable areas of a GridMap. This starts with a walkable tile
+ * and attempts to "grow" each of its edges to engulf its neighbors. This process repeats until the
+ * current hull can't engulf any neighbors.
+ * @param gridMap
+ */
+function buildInitialHulls<TileType>(gridMap: GridMap<TileType>) {
   const walkableQueue = new PointQueue();
+  const { tileWidth, tileHeight } = gridMap;
   const hulls: RectangleHull[] = [];
   let currentHull;
 
-  // Build up the queue of walkable tiles.
-  map.forEach((row, y) => {
-    row.forEach((col, x) => {
-      if (isWalkable(col, x, y)) walkableQueue.add({ x, y });
-    });
+  gridMap.forEach((x, y) => {
+    if (gridMap.isWalkable(x, y)) walkableQueue.add({ x, y });
   });
 
   const getExtensionPoints = (hull: RectangleHull, dir: CardinalDirection) => {
-    const points: Point[] = [];
-    if (dir === "top") hull.forEachTopPoint((x, y) => points.push({ x, y: y - 1 }));
-    else if (dir === "bottom") hull.forEachBottomPoint((x, y) => points.push({ x, y: y + 1 }));
-    else if (dir === "left") hull.forEachLeftPoint((x, y) => points.push({ x: x - 1, y }));
-    else if (dir === "right") hull.forEachRightPoint((x, y) => points.push({ x: x + 1, y }));
-    else throw new Error(`Invalid dir "${dir}" for extend`);
+    const { top, left, right, bottom } = hull;
+    let points: Point[] = [];
+    if (dir === "top") {
+      for (let x = left; x <= right - 1; x++) points.push({ x, y: top });
+    } else if (dir === "bottom") {
+      for (let x = left; x <= right - 1; x++) points.push({ x, y: bottom });
+    } else if (dir === "left") {
+      for (let y = top; y <= bottom - 1; y++) points.push({ x: left, y });
+    } else if (dir === "right") {
+      for (let y = top; y <= bottom - 1; y++) points.push({ x: right, y });
+    } else {
+      throw new Error(`Invalid dir "${dir}" for extend`);
+    }
     return points;
@@ -56,5 +87,5 @@ };
   const extendHullInDirection = (hull: RectangleHull, dir: CardinalDirection) => {
-    if (dir === "top") hull.top -= 1;
+    if (dir === "top") hull.y -= 1;
     else if (dir === "bottom") hull.bottom += 1;
-    else if (dir === "left") hull.left -= 1;
+    else if (dir === "left") hull.x -= 1;
     else if (dir === "right") hull.right += 1;
@@ -69,3 +100,2 @@ else throw new Error(`Invalid dir "${dir}" for extend`);
       extendHullInDirection(hull, dir);
-      hull.tiles.push(...neighborPoints);
       walkableQueue.removePoints(neighborPoints);
@@ -81,8 +111,4 @@ }
 
-    currentHull = new RectangleHull(0, 0, 0, 0);
-    currentHull.left = tile.x;
-    currentHull.right = tile.x;
-    currentHull.top = tile.y;
-    currentHull.bottom = tile.y;
-    currentHull.tiles.push(tile);
+    // Use tile dimensions (i.e. 1 tile wide, 1 tile tall) to simplify the checks.
+    currentHull = new RectangleHull(tile.x, tile.y, 1, 1);
 
@@ -93,25 +119,249 @@ // Check edges of bounding box to see if they can be extended.
       const extendedTop = attemptExtension(currentHull, "top");
+      const extendedRight = attemptExtension(currentHull, "right");
+      const extendedLeft = attemptExtension(currentHull, "left");
       const extendedBottom = attemptExtension(currentHull, "bottom");
-      const extendedLeft = attemptExtension(currentHull, "left");
-      const extendedRight = attemptExtension(currentHull, "right");
       needsExtensionCheck = extendedTop || extendedBottom || extendedLeft || extendedRight;
     }
 
+    // Scale the hull up from grid dimensions to real world dimensions.
+    currentHull.setPosition(currentHull.x * tileWidth, currentHull.y * tileHeight);
+    currentHull.setSize(currentHull.width * tileWidth, currentHull.height * tileHeight);
     hulls.push(currentHull);
   }
 
-  const polygons: PolyPoints[] = hulls.map((hull) => {
-    const left = hull.left * tileWidth;
-    const top = hull.top * tileHeight;
-    const right = (hull.right + 1) * tileWidth;
-    const bottom = (hull.bottom + 1) * tileHeight;
-    return [
-      { x: left, y: top },
-      { x: left, y: bottom },
-      { x: right, y: bottom },
-      { x: right, y: top },
-    ];
+  return hulls;
+}
+// TODO: check larger than tile size. Assumes shrink <= 1 tile.
+function shrinkHull<TileType>(
+  hull: RectangleHull,
+  gridMap: GridMap<TileType>,
+  shrinkAmount: number,
+  tileWidth: number,
+  tileHeight: number
+) {
+  const s = shrinkAmount;
+  const halfWidth = tileWidth / 2;
+  const halfHeight = tileHeight / 2;
+  const { left, top, right, bottom } = hull;
+
+  const info = {
+    left: false,
+    right: false,
+    top: false,
+    bottom: false,
+    topLeft: gridMap.isBlockedAtWorld(left - s, top - s),
+    topRight: gridMap.isBlockedAtWorld(right + s, top - s),
+    bottomLeft: gridMap.isBlockedAtWorld(left - s, bottom + s),
+    bottomRight: gridMap.isBlockedAtWorld(right + s, bottom + s),
+  };
+
+  for (let y = top + halfHeight; y < bottom; y += halfHeight) {
+    if (gridMap.isBlockedAtWorld(left - s, y)) {
+      info.left = true;
+      break;
+    }
+  }
+  for (let y = top + halfHeight; y < bottom; y += halfHeight) {
+    if (gridMap.isBlockedAtWorld(right + s, y)) {
+      info.right = true;
+      break;
+    }
+  }
+  for (let x = left + halfWidth; x < right; x += halfWidth) {
+    if (gridMap.isBlockedAtWorld(x, top - shrinkAmount)) {
+      info.top = true;
+      break;
+    }
+  }
+  for (let x = left + halfWidth; x < right; x += halfWidth) {
+    if (gridMap.isBlockedAtWorld(x, bottom + shrinkAmount)) {
+      info.bottom = true;
+      break;
+    }
+  }
+
+  const shrink = {
+    left: info.left,
+    right: info.right,
+    top: info.top,
+    bottom: info.bottom,
+  };
+
+  if (info.topLeft && !info.left && !info.top) {
+    if (hull.width > hull.height) shrink.left = true;
+    else shrink.top = true;
+  }
+  if (info.topRight && !info.right && !info.top) {
+    if (hull.width > hull.height) shrink.right = true;
+    else shrink.top = true;
+  }
+  if (info.bottomLeft && !info.bottom && !info.left) {
+    if (hull.width > hull.height) shrink.left = true;
+    else shrink.bottom = true;
+  }
+  if (info.bottomRight && !info.bottom && !info.right) {
+    if (hull.width > hull.height) shrink.right = true;
+    else shrink.bottom = true;
+  }
+
+  if (shrink.left) {
+    hull.x += shrinkAmount;
+    hull.width -= shrinkAmount;
+  }
+  if (shrink.top) {
+    hull.y += shrinkAmount;
+    hull.height -= shrinkAmount;
+  }
+  if (shrink.right) {
+    hull.width -= shrinkAmount;
+  }
+  if (shrink.bottom) {
+    hull.height -= shrinkAmount;
+  }
+
+  return shrink;
+}
+
+function shrinkHulls<TileType>(
+  hulls: RectangleHull[],
+  gridMap: GridMap<TileType>,
+  shrinkAmount: number
+) {
+  const { tileHeight, tileWidth } = gridMap;
+  const newHulls: RectangleHull[] = [];
+  const finalHulls: RectangleHull[] = [];
+
+  hulls.forEach((hull, hullIndex) => {
+    const th = tileHeight;
+    const tw = tileWidth;
+    const tLeft = gridMap.getGridX(hull.x);
+    const tTop = gridMap.getGridY(hull.y);
+    const tBottom = gridMap.getGridY(hull.bottom);
+    const tRight = gridMap.getGridX(hull.right);
+    const shrink = shrinkHull(hull, gridMap, shrinkAmount, tileWidth, tileHeight);
+
+    if (hull.left >= hull.right || hull.top >= hull.bottom) return;
+
+    finalHulls.push(hull);
+
+    const newVerticalHulls: RectangleHull[] = [];
+    const newHorizontalHulls: RectangleHull[] = [];
+    const addHull = (x: number, y: number, w: number, h: number) => {
+      const hull = new RectangleHull(x, y, w, h);
+      if (w > h) newHorizontalHulls.push(hull);
+      else newVerticalHulls.push(hull);
+    };
+
+    if (shrink.left) {
+      const x = hull.left - shrinkAmount;
+      let startY = tTop;
+      let endY = startY - 1;
+      for (let y = tTop; y < tBottom; y++) {
+        if (gridMap.isBlocked(tLeft - 1, y)) {
+          if (startY <= endY) {
+            addHull(x, startY * th, shrinkAmount, (endY - startY + 1) * th);
+          }
+          startY = y + 1;
+        } else {
+          endY = y;
+        }
+      }
+      if (startY <= endY) {
+        addHull(x, startY * th, shrinkAmount, (endY - startY + 1) * th);
+      }
+    }
+
+    if (shrink.right) {
+      const x = hull.right;
+      let startY = tTop;
+      let endY = startY - 1;
+      for (let y = tTop; y < tBottom; y++) {
+        if (gridMap.isBlocked(tRight, y)) {
+          if (startY <= endY) {
+            addHull(x, startY * th, shrinkAmount, (endY - startY + 1) * th);
+          }
+          startY = y + 1;
+        } else {
+          endY = y;
+        }
+      }
+      if (startY <= endY) {
+        addHull(x, startY * th, shrinkAmount, (endY - startY + 1) * th);
+      }
+    }
+
+    if (shrink.top) {
+      const y = hull.top - shrinkAmount;
+      let startX = tLeft;
+      let endX = startX - 1;
+      for (let x = tLeft; x < tRight; x++) {
+        if (gridMap.isBlocked(x, tTop - 1)) {
+          if (startX <= endX) {
+            addHull(startX * tw, y, (endX - startX + 1) * th, shrinkAmount);
+          }
+          startX = x + 1;
+        } else {
+          endX = x;
+        }
+      }
+      if (startX <= endX) {
+        addHull(startX * tw, y, (endX - startX + 1) * th, shrinkAmount);
+      }
+    }
+
+    if (shrink.bottom) {
+      const y = hull.bottom;
+      let startX = tLeft;
+      let endX = startX - 1;
+      for (let x = tLeft; x < tRight; x++) {
+        if (gridMap.isBlocked(x, tBottom)) {
+          if (startX <= endX) {
+            addHull(startX * tw, y, (endX - startX + 1) * th, shrinkAmount);
+          }
+          startX = x + 1;
+        } else {
+          endX = x;
+        }
+      }
+      if (startX <= endX) {
+        addHull(startX * tw, y, (endX - startX + 1) * th, shrinkAmount);
+      }
+    }
+
+    // Shrunk at corners when the new hulls overlap.
+    newHorizontalHulls.forEach((hh) => {
+      newVerticalHulls.forEach((vh) => {
+        if (hh.doesOverlap(vh)) {
+          const isBottomSide = hh.y > vh.y;
+          if (isBottomSide) vh.height -= shrinkAmount;
+          else vh.top += shrinkAmount;
+        }
+      });
+    });
+
+    [...newHorizontalHulls, ...newVerticalHulls].forEach((hull) => {
+      shrinkHull(hull, gridMap, shrinkAmount, tileWidth, tileHeight);
+      if (hull.left >= hull.right || hull.top >= hull.bottom) return;
+      newHulls.push(hull);
+    });
   });
 
-  return polygons;
+  // Attempt to merge new hulls into existing hulls if possible.
+  for (let i = 0; i < newHulls.length; i++) {
+    let wasMerged = false;
+    // Attempt to merge into the main (shrunken) hulls first.
+    for (const mainHull of hulls) {
+      wasMerged = mainHull.attemptMergeIn(newHulls[i]);
+      if (wasMerged) break;
+    }
+    if (wasMerged) continue;
+    // Then check to see if we can merge into a later hull in newHulls.
+    for (let j = i + 1; j < newHulls.length; j++) {
+      wasMerged = newHulls[j].attemptMergeIn(newHulls[i]);
+      if (wasMerged) break;
+    }
+    if (!wasMerged) finalHulls.push(newHulls[i]);
+  }
+
+  return finalHulls;
 }

src/map-parsers/rectangle-hull.ts

@@ -7,31 +7,113 @@ import { Point } from "../common-types";
 export class RectangleHull {
-  public left: number;
-  public right: number;
-  public top: number;
-  public bottom: number;
-  public tiles: Point[];
+  public x: number;
+  public y: number;
+  public width: number;
+  public height: number;
 
-  public constructor(left: number, top: number, right: number, bottom: number) {
-    this.left = left;
-    this.right = right;
-    this.top = top;
-    this.bottom = bottom;
-    this.tiles = [];
+  public constructor(x: number, y: number, width: number, height: number) {
+    this.x = x;
+    this.y = y;
+    this.width = width;
+    this.height = height;
   }
 
-  public forEachTopPoint(fn: (x: number, y: number) => void) {
-    for (let x = this.left; x <= this.right; x++) fn(x, this.top);
+  public setPosition(x: number, y: number) {
+    this.x = x;
+    this.y = y;
   }
 
-  public forEachBottomPoint(fn: (x: number, y: number) => void) {
-    for (let x = this.left; x <= this.right; x++) fn(x, this.bottom);
+  public setSize(width: number, height: number) {
+    this.width = width;
+    this.height = height;
   }
 
-  public forEachLeftPoint(fn: (x: number, y: number) => void) {
-    for (let y = this.top; y <= this.bottom; y++) fn(this.left, y);
+  public set(left: number, top: number, width: number, height: number) {
+    this.setPosition(left, top);
+    this.setSize(width, height);
   }
 
-  public forEachRightPoint(fn: (x: number, y: number) => void) {
-    for (let y = this.top; y <= this.bottom; y++) fn(this.right, y);
+  public get left() {
+    return this.x;
   }
+
+  public set left(val) {
+    this.x = val;
+  }
+
+  public get top() {
+    return this.y;
+  }
+
+  public set top(val) {
+    this.y = val;
+  }
+
+  // TODO: make consistent. Either left/right should both resize or they should both just reposition
+  public get right() {
+    return this.x + this.width;
+  }
+
+  public set right(val) {
+    this.width = val - this.x;
+  }
+
+  public get bottom() {
+    return this.y + this.height;
+  }
+
+  public set bottom(val) {
+    this.height = val - this.top;
+  }
+
+  public get center(): Point {
+    return { x: (this.x + this.right) / 2, y: (this.y + this.bottom) / 2 };
+  }
+
+  public doesOverlap(otherHull: RectangleHull) {
+    return !(
+      this.right < otherHull.x ||
+      this.x > otherHull.right ||
+      this.y > otherHull.bottom ||
+      this.bottom < otherHull.y
+    );
+  }
+
+  /**
+   * Attempt to merge another hull into this one. If they share an edge, `this` will be extended to
+   * contain `otherHull`.
+   * @param otherHull
+   */
+  public attemptMergeIn(otherHull: RectangleHull): boolean {
+    const horizontalMatch = this.x === otherHull.x && this.width === otherHull.width;
+    const verticalMatch = this.y === otherHull.y && this.height === otherHull.height;
+    if (horizontalMatch && this.top === otherHull.bottom) {
+      this.height += otherHull.height;
+      this.y = otherHull.y;
+      return true;
+    }
+    if (horizontalMatch && this.bottom === otherHull.top) {
+      this.bottom = otherHull.bottom;
+      return true;
+    }
+    if (verticalMatch && this.left === otherHull.right) {
+      this.width += otherHull.width;
+      this.x = otherHull.x;
+      return true;
+    }
+    if (verticalMatch && this.right === otherHull.left) {
+      this.right = otherHull.right;
+      return true;
+    }
+    return false;
+  }
+
+  public toPoints() {
+    const { left, right, top, bottom } = this;
+    return [
+      { x: left, y: top },
+      { x: right, y: top },
+      { x: right, y: bottom },
+      { x: left, y: bottom },
+    ];
+  }
 }

src/nav-mesh.test.ts

@@ -160,4 +160,4 @@ import NavMesh from "./navmesh";
     const result = navMesh.findClosestMeshPoint(v2(5, 5));
-    expect(result.polygon.id).toBe(0);
-    expect(result.point).toEqual({ x: 5, y: 5 });
+    expect(result?.polygon?.id).toBe(0);
+    expect(result?.point).toEqual({ x: 5, y: 5 });
   });
@@ -167,4 +167,4 @@
     const result = navMesh.findClosestMeshPoint(v2(10, 5));
-    expect(result.polygon.id).toBeGreaterThanOrEqual(0);
-    expect(result.polygon.id).toBeLessThanOrEqual(1);
+    expect(result?.polygon?.id).toBeGreaterThanOrEqual(0);
+    expect(result?.polygon?.id).toBeLessThanOrEqual(1);
   });
@@ -174,3 +174,3 @@
     const result = navMesh.findClosestMeshPoint(v2(-10, -10));
-    expect(result.point).toEqual({ x: 0, y: 0 });
+    expect(result?.point).toEqual({ x: 0, y: 0 });
   });
@@ -180,3 +180,3 @@
     const result = navMesh.findClosestMeshPoint(v2(-10, 5));
-    expect(result.point).toEqual({ x: 0, y: 5 });
+    expect(result?.point).toEqual({ x: 0, y: 5 });
   });
@@ -186,6 +186,5 @@
     const result = navMesh.findClosestMeshPoint(v2(25, 5));
-    const isPoly2or4 = result.polygon.id === 1 || result.polygon.id === 3;
-    console.log(result.point, result.distance);
+    const isPoly2or4 = result?.polygon?.id === 1 || result?.polygon?.id === 3;
     expect(isPoly2or4).toBe(true);
   });
 });

src/navgraph.ts

@@ -0,0 +0,0 @@ import jsastar from "javascript-astar";

src/navmesh.ts

@@ -0,0 +0,0 @@ import jsastar from "javascript-astar";

src/navpoly.ts

@@ -0,0 +0,0 @@ import Line from "./math/line";

No alert changes

Improved metrics

Total package byte prevSize

156568

8.64%

Number of package files

54

5.88%

Lines of code

1993

25.27%

Number of lines in readme file

34

13.33%

Worsened metrics

Dev dependency count

13

8.33%

No dependency changes