Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

navmesh

Package Overview
Dependencies
Maintainers
1
Versions
10
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

navmesh - npm Package Compare versions

Comparing version 2.0.2 to 2.0.3

LICENSE

1299

dist/navmesh.js

@@ -10,3 +10,3 @@ (function webpackUniversalModuleDefinition(root, factory) {

root["NavMesh"] = factory();
})(window, function() {
})((typeof self !== "undefined" ? self : this), function() {
return /******/ (function(modules) { // webpackBootstrap

@@ -110,3 +110,3 @@ /******/ // The module cache

/* global module, define */
if (typeof module === 'object' && typeof module.exports === 'object') {
if ( true && typeof module.exports === 'object') {
module.exports = definition();

@@ -514,3 +514,3 @@ } else if (true) {

// EXTERNAL MODULE: C:/Users/micha/Documents/GitHub/navmesh/node_modules/javascript-astar/astar.js
// EXTERNAL MODULE: D:/GitHub/navmesh/node_modules/javascript-astar/astar.js
var astar = __webpack_require__(0);

@@ -520,6 +520,2 @@ var astar_default = /*#__PURE__*/__webpack_require__.n(astar);

// CONCATENATED MODULE: ./math/vector-2.js
var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
/**

@@ -531,6 +527,4 @@ * Stripped down version of Phaser's Vector2 with just the functionality needed for navmeshes

*/
var Vector2 = function () {
function Vector2(x, y) {
_classCallCheck(this, Vector2);
class Vector2 {
constructor(x, y) {
this.x = x || 0;

@@ -540,49 +534,33 @@ this.y = y || 0;

_createClass(Vector2, [{
key: "equals",
value: function equals(v) {
return this.x === v.x && this.y === v.y;
}
}, {
key: "angle",
value: function angle(v) {
return Math.atan2(v.y - this.y, v.x - this.x);
}
}, {
key: "distance",
value: function distance(v) {
var dx = v.x - this.x;
var dy = v.y - this.y;
return Math.sqrt(dx * dx + dy * dy);
}
}, {
key: "add",
value: function add(v) {
this.x += v.x;
this.y += v.y;
}
}, {
key: "subtract",
value: function subtract(v) {
this.x -= v.x;
this.y -= v.y;
}
}, {
key: "clone",
value: function clone() {
return new Vector2(this.x, this.y);
}
}]);
equals(v) {
return this.x === v.x && this.y === v.y;
}
return Vector2;
}();
angle(v) {
return Math.atan2(v.y - this.y, v.x - this.x);
}
/* harmony default export */ var vector_2 = (Vector2);
// CONCATENATED MODULE: ./navpoly.js
var navpoly_createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
distance(v) {
const dx = v.x - this.x;
const dy = v.y - this.y;
return Math.sqrt(dx * dx + dy * dy);
}
function navpoly_classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
add(v) {
this.x += v.x;
this.y += v.y;
}
subtract(v) {
this.x -= v.x;
this.y -= v.y;
}
clone() {
return new Vector2(this.x, this.y);
}
}
// CONCATENATED MODULE: ./navpoly.js
/**

@@ -597,3 +575,3 @@ * A class that represents a navigable polygon with a navmesh. It is built on top of a

var navpoly_NavPoly = function () {
class navpoly_NavPoly {
/**

@@ -606,5 +584,3 @@ * Creates an instance of NavPoly.

*/
function NavPoly(id, polygon) {
navpoly_classCallCheck(this, NavPoly);
constructor(id, polygon) {
this.id = id;

@@ -617,6 +593,4 @@ this.polygon = polygon;

this.boundingRadius = this.calculateRadius();
this.weight = 1; // jsastar property
}
/**

@@ -630,168 +604,100 @@ * Returns an array of points that form the polygon.

navpoly_createClass(NavPoly, [{
key: "getPoints",
value: function getPoints() {
return this.polygon.points;
}
getPoints() {
return this.polygon.points;
}
/**
* Check if the given point-like object is within the polygon
*
* @param {object} point Object of the form {x, y}
* @returns {boolean}
* @memberof NavPoly
*/
/**
* Check if the given point-like object is within the polygon
*
* @param {object} point Object of the form {x, y}
* @returns {boolean}
* @memberof NavPoly
*/
}, {
key: "contains",
value: function contains(point) {
// Phaser's polygon check doesn't handle when a point is on one of the edges of the line. Note:
// check numerical stability here. It would also be good to optimize this for different shapes.
return this.polygon.contains(point.x, point.y) || this.isPointOnEdge(point);
}
contains(point) {
// Phaser's polygon check doesn't handle when a point is on one of the edges of the line. Note:
// check numerical stability here. It would also be good to optimize this for different shapes.
return this.polygon.contains(point.x, point.y) || this.isPointOnEdge(point);
}
/**
* Only rectangles are supported, so this calculation works, but this is not actually the centroid
* calculation for a polygon. This is just the average of the vertices - proper centroid of a
* polygon factors in the area.
*
* @returns {Vector2}
* @memberof NavPoly
*/
/**
* Only rectangles are supported, so this calculation works, but this is not actually the centroid
* calculation for a polygon. This is just the average of the vertices - proper centroid of a
* polygon factors in the area.
*
* @returns {Vector2}
* @memberof NavPoly
*/
}, {
key: "calculateCentroid",
value: function calculateCentroid() {
var centroid = new vector_2(0, 0);
var length = this.polygon.points.length;
this.polygon.points.forEach(function (p) {
return centroid.add(p);
});
centroid.x /= length;
centroid.y /= length;
return centroid;
}
calculateCentroid() {
const centroid = new Vector2(0, 0);
const length = this.polygon.points.length;
this.polygon.points.forEach(p => centroid.add(p));
centroid.x /= length;
centroid.y /= length;
return centroid;
}
/**
* Calculate the radius of a circle that circumscribes the polygon.
*
* @returns {number}
* @memberof NavPoly
*/
/**
* Calculate the radius of a circle that circumscribes the polygon.
*
* @returns {number}
* @memberof NavPoly
*/
}, {
key: "calculateRadius",
value: function calculateRadius() {
var boundingRadius = 0;
var _iteratorNormalCompletion = true;
var _didIteratorError = false;
var _iteratorError = undefined;
calculateRadius() {
let boundingRadius = 0;
try {
for (var _iterator = this.polygon.points[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
var point = _step.value;
for (const point of this.polygon.points) {
const d = this.centroid.distance(point);
if (d > boundingRadius) boundingRadius = d;
}
var d = this.centroid.distance(point);
if (d > boundingRadius) boundingRadius = d;
}
} catch (err) {
_didIteratorError = true;
_iteratorError = err;
} finally {
try {
if (!_iteratorNormalCompletion && _iterator.return) {
_iterator.return();
}
} finally {
if (_didIteratorError) {
throw _iteratorError;
}
}
}
return boundingRadius;
}
/**
* Check if the given point-like object is on one of the edges of the polygon.
*
* @param {object} Point-like object in the form { x, y }
* @returns {boolean}
* @memberof NavPoly
*/
return boundingRadius;
isPointOnEdge({
x,
y
}) {
for (const edge of this.edges) {
if (edge.pointOnSegment(x, y)) return true;
}
/**
* Check if the given point-like object is on one of the edges of the polygon.
*
* @param {object} Point-like object in the form { x, y }
* @returns {boolean}
* @memberof NavPoly
*/
return false;
}
}, {
key: "isPointOnEdge",
value: function isPointOnEdge(_ref) {
var x = _ref.x,
y = _ref.y;
var _iteratorNormalCompletion2 = true;
var _didIteratorError2 = false;
var _iteratorError2 = undefined;
destroy() {
this.neighbors = [];
this.portals = [];
} // jsastar methods
try {
for (var _iterator2 = this.edges[Symbol.iterator](), _step2; !(_iteratorNormalCompletion2 = (_step2 = _iterator2.next()).done); _iteratorNormalCompletion2 = true) {
var edge = _step2.value;
if (edge.pointOnSegment(x, y)) return true;
}
} catch (err) {
_didIteratorError2 = true;
_iteratorError2 = err;
} finally {
try {
if (!_iteratorNormalCompletion2 && _iterator2.return) {
_iterator2.return();
}
} finally {
if (_didIteratorError2) {
throw _iteratorError2;
}
}
}
toString() {
return `NavPoly(id: ${this.id} at: ${this.centroid})`;
}
return false;
}
}, {
key: "destroy",
value: function destroy() {
this.neighbors = [];
this.portals = [];
}
isWall() {
return this.weight === 0;
}
// jsastar methods
centroidDistance(navPolygon) {
return this.centroid.distance(navPolygon.centroid);
}
}, {
key: "toString",
value: function toString() {
return "NavPoly(id: " + this.id + " at: " + this.centroid + ")";
}
}, {
key: "isWall",
value: function isWall() {
return this.weight === 0;
}
}, {
key: "centroidDistance",
value: function centroidDistance(navPolygon) {
return this.centroid.distance(navPolygon.centroid);
}
}, {
key: "getCost",
value: function getCost(navPolygon) {
return this.centroidDistance(navPolygon);
}
}]);
getCost(navPolygon) {
return this.centroidDistance(navPolygon);
}
return NavPoly;
}();
/* harmony default export */ var navpoly = (navpoly_NavPoly);
}
// CONCATENATED MODULE: ./navgraph.js
var navgraph_createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
function navgraph_classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
/**

@@ -805,6 +711,4 @@ * Graph for javascript-astar. It implements the functionality for astar. See GPS test from astar

var NavGraph = function () {
function NavGraph(navPolygons) {
navgraph_classCallCheck(this, NavGraph);
class NavGraph {
constructor(navPolygons) {
this.nodes = navPolygons;

@@ -814,27 +718,20 @@ this.init();

navgraph_createClass(NavGraph, [{
key: "neighbors",
value: function neighbors(navPolygon) {
return navPolygon.neighbors;
}
}, {
key: "navHeuristic",
value: function navHeuristic(navPolygon1, navPolygon2) {
return navPolygon1.centroidDistance(navPolygon2);
}
}, {
key: "destroy",
value: function destroy() {
this.cleanDirty();
this.nodes = [];
}
}]);
neighbors(navPolygon) {
return navPolygon.neighbors;
}
return NavGraph;
}();
navHeuristic(navPolygon1, navPolygon2) {
return navPolygon1.centroidDistance(navPolygon2);
}
destroy() {
this.cleanDirty();
this.nodes = [];
}
}
NavGraph.prototype.init = astar_default.a.Graph.prototype.init;
NavGraph.prototype.cleanDirty = astar_default.a.Graph.prototype.cleanDirty;
NavGraph.prototype.markDirty = astar_default.a.Graph.prototype.markDirty;
/* harmony default export */ var navgraph = (NavGraph);

@@ -848,9 +745,8 @@ // CONCATENATED MODULE: ./utils.js

function triarea2(a, b, c) {
var ax = b.x - a.x;
var ay = b.y - a.y;
var bx = c.x - a.x;
var by = c.y - a.y;
const ax = b.x - a.x;
const ay = b.y - a.y;
const bx = c.x - a.x;
const by = c.y - a.y;
return bx * ay - ax * by;
}
/**

@@ -861,2 +757,3 @@ * Clamp value between min and max

*/
function clamp(value, min, max) {

@@ -867,3 +764,2 @@ if (value < min) value = min;

}
/**

@@ -874,8 +770,6 @@ * Check if two values within a small margin of one another

*/
function almostEqual(value1, value2) {
var errorMargin = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 0.0001;
function almostEqual(value1, value2, errorMargin = 0.0001) {
if (Math.abs(value1 - value2) <= errorMargin) return true;else return false;
}
/**

@@ -887,11 +781,12 @@ * Find the smallest angle difference between two angles

*/
function angleDifference(x, y) {
var a = x - y;
var i = a + Math.PI;
var j = Math.PI * 2;
let a = x - y;
const i = a + Math.PI;
const j = Math.PI * 2;
a = i - Math.floor(i / j) * j; // (a+180) % 360; this ensures the correct sign
a -= Math.PI;
return a;
}
/**

@@ -902,9 +797,9 @@ * Check if two lines are collinear (within a marign)

*/
function areCollinear(line1, line2) {
var errorMargin = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 0.0001;
function areCollinear(line1, line2, errorMargin = 0.0001) {
// Figure out if the two lines are equal by looking at the area of the triangle formed
// by their points
var area1 = triarea2(line1.start, line1.end, line2.start);
var area2 = triarea2(line1.start, line1.end, line2.end);
const area1 = triarea2(line1.start, line1.end, line2.start);
const area2 = triarea2(line1.start, line1.end, line2.end);
if (almostEqual(area1, 0, errorMargin) && almostEqual(area2, 0, errorMargin)) {

@@ -915,11 +810,5 @@ return true;

// CONCATENATED MODULE: ./channel.js
var channel_createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
function channel_classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
// Mostly sourced from PatrolJS at the moment. TODO: come back and reimplement this as an incomplete
// funnel algorithm so astar checks can be more accurate.
/**

@@ -929,119 +818,98 @@ * @private

var channel_Channel = function () {
function Channel() {
channel_classCallCheck(this, Channel);
class channel_Channel {
constructor() {
this.portals = [];
}
channel_createClass(Channel, [{
key: "push",
value: function push(p1) {
var p2 = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : null;
push(p1, p2 = null) {
if (p2 === null) p2 = p1;
this.portals.push({
left: p1,
right: p2
});
}
if (p2 === null) p2 = p1;
this.portals.push({
left: p1,
right: p2
});
}
}, {
key: "stringPull",
value: function stringPull() {
var portals = this.portals;
var pts = [];
// Init scan state
var portalApex, portalLeft, portalRight;
var apexIndex = 0,
leftIndex = 0,
rightIndex = 0;
stringPull() {
var portals = this.portals;
var pts = []; // Init scan state
portalApex = portals[0].left;
portalLeft = portals[0].left;
portalRight = portals[0].right;
var portalApex, portalLeft, portalRight;
var apexIndex = 0,
leftIndex = 0,
rightIndex = 0;
portalApex = portals[0].left;
portalLeft = portals[0].left;
portalRight = portals[0].right; // Add start point.
// Add start point.
pts.push(portalApex);
pts.push(portalApex);
for (var i = 1; i < portals.length; i++) {
// Find the next portal vertices
var left = portals[i].left;
var right = portals[i].right;
for (var i = 1; i < portals.length; i++) {
// Find the next portal vertices
var left = portals[i].left;
var right = portals[i].right; // Update right vertex.
// Update right vertex.
if (triarea2(portalApex, portalRight, right) <= 0.0) {
if (portalApex.equals(portalRight) || triarea2(portalApex, portalLeft, right) > 0.0) {
// Tighten the funnel.
portalRight = right;
rightIndex = i;
} else {
// Right vertex just crossed over the left vertex, so the left vertex should
// now be part of the path.
pts.push(portalLeft);
if (triarea2(portalApex, portalRight, right) <= 0.0) {
if (portalApex.equals(portalRight) || triarea2(portalApex, portalLeft, right) > 0.0) {
// Tighten the funnel.
portalRight = right;
rightIndex = i;
} else {
// Right vertex just crossed over the left vertex, so the left vertex should
// now be part of the path.
pts.push(portalLeft); // Restart scan from portal left point.
// Make current left the new apex.
// Restart scan from portal left point.
portalApex = portalLeft;
apexIndex = leftIndex; // Reset portal
// Make current left the new apex.
portalApex = portalLeft;
apexIndex = leftIndex;
// Reset portal
portalLeft = portalApex;
portalRight = portalApex;
leftIndex = apexIndex;
rightIndex = apexIndex;
// Restart scan
i = apexIndex;
continue;
}
portalLeft = portalApex;
portalRight = portalApex;
leftIndex = apexIndex;
rightIndex = apexIndex; // Restart scan
i = apexIndex;
continue;
}
} // Update left vertex.
// Update left vertex.
if (triarea2(portalApex, portalLeft, left) >= 0.0) {
if (portalApex.equals(portalLeft) || triarea2(portalApex, portalRight, left) < 0.0) {
// Tighten the funnel.
portalLeft = left;
leftIndex = i;
} else {
// Left vertex just crossed over the right vertex, so the right vertex should
// now be part of the path
pts.push(portalRight);
// Restart scan from portal right point.
if (triarea2(portalApex, portalLeft, left) >= 0.0) {
if (portalApex.equals(portalLeft) || triarea2(portalApex, portalRight, left) < 0.0) {
// Tighten the funnel.
portalLeft = left;
leftIndex = i;
} else {
// Left vertex just crossed over the right vertex, so the right vertex should
// now be part of the path
pts.push(portalRight); // Restart scan from portal right point.
// Make current right the new apex.
// Make current right the new apex.
portalApex = portalRight;
apexIndex = rightIndex;
// Reset portal
portalLeft = portalApex;
portalRight = portalApex;
leftIndex = apexIndex;
rightIndex = apexIndex;
// Restart scan
i = apexIndex;
continue;
}
portalApex = portalRight;
apexIndex = rightIndex; // Reset portal
portalLeft = portalApex;
portalRight = portalApex;
leftIndex = apexIndex;
rightIndex = apexIndex; // Restart scan
i = apexIndex;
continue;
}
}
}
if (pts.length === 0 || !pts[pts.length - 1].equals(portals[portals.length - 1].left)) {
// Append last point to path.
pts.push(portals[portals.length - 1].left);
}
this.path = pts;
return pts;
if (pts.length === 0 || !pts[pts.length - 1].equals(portals[portals.length - 1].left)) {
// Append last point to path.
pts.push(portals[portals.length - 1].left);
}
}]);
return Channel;
}();
this.path = pts;
return pts;
}
}
/* harmony default export */ var channel_0 = (channel_Channel);
// CONCATENATED MODULE: ./math/line.js
var line_createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
function line_classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
/**

@@ -1054,9 +922,6 @@ * Stripped down version of Phaser's Line with just the functionality needed for navmeshes

var line_Line = function () {
function Line(x1, y1, x2, y2) {
line_classCallCheck(this, Line);
this.start = new vector_2(x1, y1);
this.end = new vector_2(x2, y2);
class line_Line {
constructor(x1, y1, x2, y2) {
this.start = new Vector2(x1, y1);
this.end = new Vector2(x2, y2);
this.left = Math.min(x1, x2);

@@ -1068,26 +933,14 @@ this.right = Math.max(x1, x2);

line_createClass(Line, [{
key: "pointOnSegment",
value: function pointOnSegment(x, y) {
return x >= this.left && x <= this.right && y >= this.top && y <= this.bottom && this.pointOnLine(x, y);
}
}, {
key: "pointOnLine",
value: function pointOnLine(x, y) {
// Compare slope of line start -> xy to line start -> line end
return (x - this.left) * (this.bottom - this.top) === (this.right - this.left) * (y - this.top);
}
}]);
pointOnSegment(x, y) {
return x >= this.left && x <= this.right && y >= this.top && y <= this.bottom && this.pointOnLine(x, y);
}
return Line;
}();
pointOnLine(x, y) {
// Compare slope of line start -> xy to line start -> line end
return (x - this.left) * (this.bottom - this.top) === (this.right - this.left) * (y - this.top);
}
/* harmony default export */ var math_line = (line_Line);
}
// CONCATENATED MODULE: ./math/polygon.js
var polygon_createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
function polygon_classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
/**

@@ -1100,54 +953,41 @@ * Stripped down version of Phaser's Polygon with just the functionality needed for navmeshes

var polygon_Polygon = function () {
function Polygon(points) {
var closed = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : true;
polygon_classCallCheck(this, Polygon);
class polygon_Polygon {
constructor(points, closed = true) {
this.points = points;
this.edges = [];
for (var i = 1; i < points.length; i++) {
var p1 = points[i - 1];
var p2 = points[i];
this.edges.push(new math_line(p1.x, p1.y, p2.x, p2.y));
for (let i = 1; i < points.length; i++) {
const p1 = points[i - 1];
const p2 = points[i];
this.edges.push(new line_Line(p1.x, p1.y, p2.x, p2.y));
}
if (closed) {
var first = points[0];
var last = points[points.length - 1];
this.edges.push(new math_line(first.x, first.y, last.x, last.y));
const first = points[0];
const last = points[points.length - 1];
this.edges.push(new line_Line(first.x, first.y, last.x, last.y));
}
}
polygon_createClass(Polygon, [{
key: "contains",
value: function contains(x, y) {
var inside = false;
contains(x, y) {
let inside = false;
for (var i = -1, j = this.points.length - 1; ++i < this.points.length; j = i) {
var ix = this.points[i].x;
var iy = this.points[i].y;
for (let i = -1, j = this.points.length - 1; ++i < this.points.length; j = i) {
const ix = this.points[i].x;
const iy = this.points[i].y;
const jx = this.points[j].x;
const jy = this.points[j].y;
var jx = this.points[j].x;
var jy = this.points[j].y;
if ((iy <= y && y < jy || jy <= y && y < iy) && x < (jx - ix) * (y - iy) / (jy - iy) + ix) {
inside = !inside;
}
if ((iy <= y && y < jy || jy <= y && y < iy) && x < (jx - ix) * (y - iy) / (jy - iy) + ix) {
inside = !inside;
}
return inside;
}
}]);
return Polygon;
}();
return inside;
}
/* harmony default export */ var math_polygon = (polygon_Polygon);
}
// CONCATENATED MODULE: ./navmesh.js
var _slicedToArray = function () { function sliceIterator(arr, i) { var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"]) _i["return"](); } finally { if (_d) throw _e; } } return _arr; } return function (arr, i) { if (Array.isArray(arr)) { return arr; } else if (Symbol.iterator in Object(arr)) { return sliceIterator(arr, i); } else { throw new TypeError("Invalid attempt to destructure non-iterable instance"); } }; }();
var navmesh_createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
function navmesh_classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }

@@ -1159,6 +999,2 @@

/**

@@ -1176,3 +1012,3 @@ * The workhorse that represents a navigation mesh built from a series of polygons. Once built, the

var navmesh_NavMesh = function () {
class navmesh_NavMesh {
/**

@@ -1186,26 +1022,15 @@ * Creates an instance of NavMesh.

*/
function NavMesh(meshPolygonPoints) {
var meshShrinkAmount = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : 0;
navmesh_classCallCheck(this, NavMesh);
constructor(meshPolygonPoints, meshShrinkAmount = 0) {
this._meshShrinkAmount = meshShrinkAmount;
var newPolys = meshPolygonPoints.map(function (polyPoints) {
var vectors = polyPoints.map(function (p) {
return new vector_2(p.x, p.y);
});
return new math_polygon(vectors);
const newPolys = meshPolygonPoints.map(polyPoints => {
const vectors = polyPoints.map(p => new Vector2(p.x, p.y));
return new polygon_Polygon(vectors);
});
this._navPolygons = newPolys.map((polygon, i) => new navpoly_NavPoly(i, polygon));
this._navPolygons = newPolys.map(function (polygon, i) {
return new navpoly(i, polygon);
});
this._calculateNeighbors(); // Astar graph of connections between polygons
this._calculateNeighbors();
// Astar graph of connections between polygons
this._graph = new navgraph(this._navPolygons);
}
/**

@@ -1219,359 +1044,198 @@ * Get the NavPolys that are in this navmesh.

navmesh_createClass(NavMesh, [{
key: "getPolygons",
value: function getPolygons() {
return this._navPolygons;
}
getPolygons() {
return this._navPolygons;
}
/**
* Cleanup method to remove references.
*
* @memberof NavMesh
*/
/**
* Cleanup method to remove references.
*
* @memberof NavMesh
*/
}, {
key: "destroy",
value: function destroy() {
this._graph.destroy();
var _iteratorNormalCompletion = true;
var _didIteratorError = false;
var _iteratorError = undefined;
destroy() {
this._graph.destroy();
try {
for (var _iterator = this._navPolygons[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
var poly = _step.value;
poly.destroy();
}
} catch (err) {
_didIteratorError = true;
_iteratorError = err;
} finally {
try {
if (!_iteratorNormalCompletion && _iterator.return) {
_iterator.return();
}
} finally {
if (_didIteratorError) {
throw _iteratorError;
}
}
}
for (const poly of this._navPolygons) poly.destroy();
this._navPolygons = [];
}
this._navPolygons = [];
}
/**
* Find a path from the start point to the end point using this nav mesh.
*
* @param {object} startPoint A point-like object in the form {x, y}
* @param {object} endPoint A point-like object in the form {x, y}
* @returns {Vector2[]|null} An array of points if a path is found, or null if no path
*
* @memberof NavMesh
*/
/**
* Find a path from the start point to the end point using this nav mesh.
*
* @param {object} startPoint A point-like object in the form {x, y}
* @param {object} endPoint A point-like object in the form {x, y}
* @returns {Vector2[]|null} An array of points if a path is found, or null if no path
*
* @memberof NavMesh
*/
}, {
key: "findPath",
value: function findPath(startPoint, endPoint) {
var startPoly = null;
var endPoly = null;
var startDistance = Number.MAX_VALUE;
var endDistance = Number.MAX_VALUE;
var d = void 0,
r = void 0;
var startVector = new vector_2(startPoint.x, startPoint.y);
var endVector = new vector_2(endPoint.x, endPoint.y);
findPath(startPoint, endPoint) {
let startPoly = null;
let endPoly = null;
let startDistance = Number.MAX_VALUE;
let endDistance = Number.MAX_VALUE;
let d, r;
const startVector = new Vector2(startPoint.x, startPoint.y);
const endVector = new Vector2(endPoint.x, endPoint.y); // Find the closest poly for the starting and ending point
// Find the closest poly for the starting and ending point
var _iteratorNormalCompletion2 = true;
var _didIteratorError2 = false;
var _iteratorError2 = undefined;
for (const navPoly of this._navPolygons) {
r = navPoly.boundingRadius; // Start
try {
for (var _iterator2 = this._navPolygons[Symbol.iterator](), _step2; !(_iteratorNormalCompletion2 = (_step2 = _iterator2.next()).done); _iteratorNormalCompletion2 = true) {
var navPoly = _step2.value;
d = navPoly.centroid.distance(startVector);
r = navPoly.boundingRadius;
// Start
d = navPoly.centroid.distance(startVector);
if (d <= startDistance && d <= r && navPoly.contains(startVector)) {
startPoly = navPoly;
startDistance = d;
}
// End
d = navPoly.centroid.distance(endVector);
if (d <= endDistance && d <= r && navPoly.contains(endVector)) {
endPoly = navPoly;
endDistance = d;
}
}
if (d <= startDistance && d <= r && navPoly.contains(startVector)) {
startPoly = navPoly;
startDistance = d;
} // End
// If the start point wasn't inside a polygon, run a more liberal check that allows a point
// to be within meshShrinkAmount radius of a polygon
} catch (err) {
_didIteratorError2 = true;
_iteratorError2 = err;
} finally {
try {
if (!_iteratorNormalCompletion2 && _iterator2.return) {
_iterator2.return();
}
} finally {
if (_didIteratorError2) {
throw _iteratorError2;
}
}
d = navPoly.centroid.distance(endVector);
if (d <= endDistance && d <= r && navPoly.contains(endVector)) {
endPoly = navPoly;
endDistance = d;
}
} // If the start point wasn't inside a polygon, run a more liberal check that allows a point
// to be within meshShrinkAmount radius of a polygon
if (!startPoly && this._meshShrinkAmount > 0) {
var _iteratorNormalCompletion3 = true;
var _didIteratorError3 = false;
var _iteratorError3 = undefined;
try {
for (var _iterator3 = this._navPolygons[Symbol.iterator](), _step3; !(_iteratorNormalCompletion3 = (_step3 = _iterator3.next()).done); _iteratorNormalCompletion3 = true) {
var _navPoly = _step3.value;
if (!startPoly && this._meshShrinkAmount > 0) {
for (const navPoly of this._navPolygons) {
// Check if point is within bounding circle to avoid extra projection calculations
r = navPoly.boundingRadius + this._meshShrinkAmount;
d = navPoly.centroid.distance(startVector);
// Check if point is within bounding circle to avoid extra projection calculations
r = _navPoly.boundingRadius + this._meshShrinkAmount;
d = _navPoly.centroid.distance(startVector);
if (d <= r) {
// Check if projected point is within range of a polgyon and is closer than the
// previous point
var _projectPointToPolygo = this._projectPointToPolygon(startVector, _navPoly),
distance = _projectPointToPolygo.distance;
if (d <= r) {
// Check if projected point is within range of a polgyon and is closer than the
// previous point
const {
distance
} = this._projectPointToPolygon(startVector, navPoly);
if (distance <= this._meshShrinkAmount && distance < startDistance) {
startPoly = _navPoly;
startDistance = distance;
}
}
if (distance <= this._meshShrinkAmount && distance < startDistance) {
startPoly = navPoly;
startDistance = distance;
}
} catch (err) {
_didIteratorError3 = true;
_iteratorError3 = err;
} finally {
try {
if (!_iteratorNormalCompletion3 && _iterator3.return) {
_iterator3.return();
}
} finally {
if (_didIteratorError3) {
throw _iteratorError3;
}
}
}
}
} // Same check as above, but for the end point
// Same check as above, but for the end point
if (!endPoly && this._meshShrinkAmount > 0) {
var _iteratorNormalCompletion4 = true;
var _didIteratorError4 = false;
var _iteratorError4 = undefined;
try {
for (var _iterator4 = this._navPolygons[Symbol.iterator](), _step4; !(_iteratorNormalCompletion4 = (_step4 = _iterator4.next()).done); _iteratorNormalCompletion4 = true) {
var _navPoly2 = _step4.value;
if (!endPoly && this._meshShrinkAmount > 0) {
for (const navPoly of this._navPolygons) {
r = navPoly.boundingRadius + this._meshShrinkAmount;
d = navPoly.centroid.distance(endVector);
r = _navPoly2.boundingRadius + this._meshShrinkAmount;
d = _navPoly2.centroid.distance(endVector);
if (d <= r) {
var _projectPointToPolygo2 = this._projectPointToPolygon(endVector, _navPoly2),
_distance = _projectPointToPolygo2.distance;
if (d <= r) {
const {
distance
} = this._projectPointToPolygon(endVector, navPoly);
if (_distance <= this._meshShrinkAmount && _distance < endDistance) {
endPoly = _navPoly2;
endDistance = _distance;
}
}
if (distance <= this._meshShrinkAmount && distance < endDistance) {
endPoly = navPoly;
endDistance = distance;
}
} catch (err) {
_didIteratorError4 = true;
_iteratorError4 = err;
} finally {
try {
if (!_iteratorNormalCompletion4 && _iterator4.return) {
_iterator4.return();
}
} finally {
if (_didIteratorError4) {
throw _iteratorError4;
}
}
}
}
} // No matching polygons locations for the start or end, so no path found
// No matching polygons locations for the start or end, so no path found
if (!startPoly || !endPoly) return null;
// If the start and end polygons are the same, return a direct path
if (startPoly === endPoly) return [startVector, endVector];
if (!startPoly || !endPoly) return null; // If the start and end polygons are the same, return a direct path
// Search!
var astarPath = astar_default.a.astar.search(this._graph, startPoly, endPoly, {
heuristic: this._graph.navHeuristic
});
if (startPoly === endPoly) return [startVector, endVector]; // Search!
// While the start and end polygons may be valid, no path between them
if (astarPath.length === 0) return null;
const astarPath = astar_default.a.astar.search(this._graph, startPoly, endPoly, {
heuristic: this._graph.navHeuristic
}); // While the start and end polygons may be valid, no path between them
// jsastar drops the first point from the path, but the funnel algorithm needs it
astarPath.unshift(startPoly);
if (astarPath.length === 0) return null; // jsastar drops the first point from the path, but the funnel algorithm needs it
// We have a path, so now time for the funnel algorithm
var channel = new channel_0();
channel.push(startVector);
for (var i = 0; i < astarPath.length - 1; i++) {
var navPolygon = astarPath[i];
var nextNavPolygon = astarPath[i + 1];
astarPath.unshift(startPoly); // We have a path, so now time for the funnel algorithm
// Find the portal
var portal = null;
for (var _i = 0; _i < navPolygon.neighbors.length; _i++) {
if (navPolygon.neighbors[_i].id === nextNavPolygon.id) {
portal = navPolygon.portals[_i];
}
const channel = new channel_0();
channel.push(startVector);
for (let i = 0; i < astarPath.length - 1; i++) {
const navPolygon = astarPath[i];
const nextNavPolygon = astarPath[i + 1]; // Find the portal
let portal = null;
for (let i = 0; i < navPolygon.neighbors.length; i++) {
if (navPolygon.neighbors[i].id === nextNavPolygon.id) {
portal = navPolygon.portals[i];
}
} // Push the portal vertices into the channel
// Push the portal vertices into the channel
channel.push(portal.start, portal.end);
}
channel.push(endVector);
// Pull a string along the channel to run the funnel
channel.stringPull();
channel.push(portal.start, portal.end);
}
// Clone path, excluding duplicates
var lastPoint = null;
var phaserPath = [];
var _iteratorNormalCompletion5 = true;
var _didIteratorError5 = false;
var _iteratorError5 = undefined;
channel.push(endVector); // Pull a string along the channel to run the funnel
try {
for (var _iterator5 = channel.path[Symbol.iterator](), _step5; !(_iteratorNormalCompletion5 = (_step5 = _iterator5.next()).done); _iteratorNormalCompletion5 = true) {
var p = _step5.value;
channel.stringPull(); // Clone path, excluding duplicates
var newPoint = p.clone();
if (!lastPoint || !newPoint.equals(lastPoint)) phaserPath.push(newPoint);
lastPoint = newPoint;
}
} catch (err) {
_didIteratorError5 = true;
_iteratorError5 = err;
} finally {
try {
if (!_iteratorNormalCompletion5 && _iterator5.return) {
_iterator5.return();
}
} finally {
if (_didIteratorError5) {
throw _iteratorError5;
}
}
}
let lastPoint = null;
const phaserPath = [];
return phaserPath;
for (const p of channel.path) {
const newPoint = p.clone();
if (!lastPoint || !newPoint.equals(lastPoint)) phaserPath.push(newPoint);
lastPoint = newPoint;
}
}, {
key: "_calculateNeighbors",
value: function _calculateNeighbors() {
// Fill out the neighbor information for each navpoly
for (var i = 0; i < this._navPolygons.length; i++) {
var navPoly = this._navPolygons[i];
for (var j = i + 1; j < this._navPolygons.length; j++) {
var otherNavPoly = this._navPolygons[j];
return phaserPath;
}
// Check if the other navpoly is within range to touch
var d = navPoly.centroid.distance(otherNavPoly.centroid);
if (d > navPoly.boundingRadius + otherNavPoly.boundingRadius) continue;
_calculateNeighbors() {
// Fill out the neighbor information for each navpoly
for (let i = 0; i < this._navPolygons.length; i++) {
const navPoly = this._navPolygons[i];
// The are in range, so check each edge pairing
var _iteratorNormalCompletion6 = true;
var _didIteratorError6 = false;
var _iteratorError6 = undefined;
for (let j = i + 1; j < this._navPolygons.length; j++) {
const otherNavPoly = this._navPolygons[j]; // Check if the other navpoly is within range to touch
try {
for (var _iterator6 = navPoly.edges[Symbol.iterator](), _step6; !(_iteratorNormalCompletion6 = (_step6 = _iterator6.next()).done); _iteratorNormalCompletion6 = true) {
var edge = _step6.value;
var _iteratorNormalCompletion7 = true;
var _didIteratorError7 = false;
var _iteratorError7 = undefined;
const d = navPoly.centroid.distance(otherNavPoly.centroid);
if (d > navPoly.boundingRadius + otherNavPoly.boundingRadius) continue; // The are in range, so check each edge pairing
try {
for (var _iterator7 = otherNavPoly.edges[Symbol.iterator](), _step7; !(_iteratorNormalCompletion7 = (_step7 = _iterator7.next()).done); _iteratorNormalCompletion7 = true) {
var otherEdge = _step7.value;
for (const edge of navPoly.edges) {
for (const otherEdge of otherNavPoly.edges) {
// If edges aren't collinear, not an option for connecting navpolys
if (!areCollinear(edge, otherEdge)) continue; // If they are collinear, check if they overlap
// If edges aren't collinear, not an option for connecting navpolys
if (!areCollinear(edge, otherEdge)) continue;
const overlap = this._getSegmentOverlap(edge, otherEdge);
// If they are collinear, check if they overlap
var overlap = this._getSegmentOverlap(edge, otherEdge);
if (!overlap) continue;
if (!overlap) continue; // Connections are symmetric!
// Connections are symmetric!
navPoly.neighbors.push(otherNavPoly);
otherNavPoly.neighbors.push(navPoly);
navPoly.neighbors.push(otherNavPoly);
otherNavPoly.neighbors.push(navPoly); // Calculate the portal between the two polygons - this needs to be in
// counter-clockwise order, relative to each polygon
// Calculate the portal between the two polygons - this needs to be in
// counter-clockwise order, relative to each polygon
const [p1, p2] = overlap;
let edgeStartAngle = navPoly.centroid.angle(edge.start);
let a1 = navPoly.centroid.angle(overlap[0]);
let a2 = navPoly.centroid.angle(overlap[1]);
let d1 = angleDifference(edgeStartAngle, a1);
let d2 = angleDifference(edgeStartAngle, a2);
var _overlap = _slicedToArray(overlap, 2),
p1 = _overlap[0],
p2 = _overlap[1];
if (d1 < d2) {
navPoly.portals.push(new line_Line(p1.x, p1.y, p2.x, p2.y));
} else {
navPoly.portals.push(new line_Line(p2.x, p2.y, p1.x, p1.y));
}
var edgeStartAngle = navPoly.centroid.angle(edge.start);
var a1 = navPoly.centroid.angle(overlap[0]);
var a2 = navPoly.centroid.angle(overlap[1]);
var d1 = angleDifference(edgeStartAngle, a1);
var d2 = angleDifference(edgeStartAngle, a2);
if (d1 < d2) {
navPoly.portals.push(new math_line(p1.x, p1.y, p2.x, p2.y));
} else {
navPoly.portals.push(new math_line(p2.x, p2.y, p1.x, p1.y));
}
edgeStartAngle = otherNavPoly.centroid.angle(otherEdge.start);
a1 = otherNavPoly.centroid.angle(overlap[0]);
a2 = otherNavPoly.centroid.angle(overlap[1]);
d1 = angleDifference(edgeStartAngle, a1);
d2 = angleDifference(edgeStartAngle, a2);
edgeStartAngle = otherNavPoly.centroid.angle(otherEdge.start);
a1 = otherNavPoly.centroid.angle(overlap[0]);
a2 = otherNavPoly.centroid.angle(overlap[1]);
d1 = angleDifference(edgeStartAngle, a1);
d2 = angleDifference(edgeStartAngle, a2);
if (d1 < d2) {
otherNavPoly.portals.push(new math_line(p1.x, p1.y, p2.x, p2.y));
} else {
otherNavPoly.portals.push(new math_line(p2.x, p2.y, p1.x, p1.y));
}
if (d1 < d2) {
otherNavPoly.portals.push(new line_Line(p1.x, p1.y, p2.x, p2.y));
} else {
otherNavPoly.portals.push(new line_Line(p2.x, p2.y, p1.x, p1.y));
} // Two convex polygons shouldn't be connected more than once! (Unless
// there are unnecessary vertices...)
// Two convex polygons shouldn't be connected more than once! (Unless
// there are unnecessary vertices...)
}
} catch (err) {
_didIteratorError7 = true;
_iteratorError7 = err;
} finally {
try {
if (!_iteratorNormalCompletion7 && _iterator7.return) {
_iterator7.return();
}
} finally {
if (_didIteratorError7) {
throw _iteratorError7;
}
}
}
}
} catch (err) {
_didIteratorError6 = true;
_iteratorError6 = err;
} finally {
try {
if (!_iteratorNormalCompletion6 && _iterator6.return) {
_iterator6.return();
}
} finally {
if (_didIteratorError6) {
throw _iteratorError6;
}
}
}

@@ -1581,109 +1245,94 @@ }

}
} // Check two collinear line segments to see if they overlap by sorting the points.
// Algorithm source: http://stackoverflow.com/a/17152247
// Check two collinear line segments to see if they overlap by sorting the points.
// Algorithm source: http://stackoverflow.com/a/17152247
}, {
key: "_getSegmentOverlap",
value: function _getSegmentOverlap(line1, line2) {
var points = [{ line: line1, point: line1.start }, { line: line1, point: line1.end }, { line: line2, point: line2.start }, { line: line2, point: line2.end }];
points.sort(function (a, b) {
if (a.point.x < b.point.x) return -1;else if (a.point.x > b.point.x) return 1;else {
if (a.point.y < b.point.y) return -1;else if (a.point.y > b.point.y) return 1;else return 0;
}
});
// If the first two points in the array come from the same line, no overlap
var noOverlap = points[0].line === points[1].line;
// If the two middle points in the array are the same coordinates, then there is a
// single point of overlap.
var singlePointOverlap = points[1].point.equals(points[2].point);
if (noOverlap || singlePointOverlap) return null;else return [points[1].point, points[2].point];
}
_getSegmentOverlap(line1, line2) {
const points = [{
line: line1,
point: line1.start
}, {
line: line1,
point: line1.end
}, {
line: line2,
point: line2.start
}, {
line: line2,
point: line2.end
}];
points.sort(function (a, b) {
if (a.point.x < b.point.x) return -1;else if (a.point.x > b.point.x) return 1;else {
if (a.point.y < b.point.y) return -1;else if (a.point.y > b.point.y) return 1;else return 0;
}
}); // If the first two points in the array come from the same line, no overlap
/**
* Project a point onto a polygon in the shortest distance possible.
*
* @param {Phaser.Point} point The point to project
* @param {NavPoly} navPoly The navigation polygon to test against
* @returns {{point: Phaser.Point, distance: number}}
*
* @private
* @memberof NavMesh
*/
const noOverlap = points[0].line === points[1].line; // If the two middle points in the array are the same coordinates, then there is a
// single point of overlap.
}, {
key: "_projectPointToPolygon",
value: function _projectPointToPolygon(point, navPoly) {
var closestProjection = null;
var closestDistance = Number.MAX_VALUE;
var _iteratorNormalCompletion8 = true;
var _didIteratorError8 = false;
var _iteratorError8 = undefined;
const singlePointOverlap = points[1].point.equals(points[2].point);
if (noOverlap || singlePointOverlap) return null;else return [points[1].point, points[2].point];
}
/**
* Project a point onto a polygon in the shortest distance possible.
*
* @param {Phaser.Point} point The point to project
* @param {NavPoly} navPoly The navigation polygon to test against
* @returns {{point: Phaser.Point, distance: number}}
*
* @private
* @memberof NavMesh
*/
try {
for (var _iterator8 = navPoly.edges[Symbol.iterator](), _step8; !(_iteratorNormalCompletion8 = (_step8 = _iterator8.next()).done); _iteratorNormalCompletion8 = true) {
var edge = _step8.value;
var projectedPoint = this._projectPointToEdge(point, edge);
var d = point.distance(projectedPoint);
if (closestProjection === null || d < closestDistance) {
closestDistance = d;
closestProjection = projectedPoint;
}
}
} catch (err) {
_didIteratorError8 = true;
_iteratorError8 = err;
} finally {
try {
if (!_iteratorNormalCompletion8 && _iterator8.return) {
_iterator8.return();
}
} finally {
if (_didIteratorError8) {
throw _iteratorError8;
}
}
}
_projectPointToPolygon(point, navPoly) {
let closestProjection = null;
let closestDistance = Number.MAX_VALUE;
return { point: closestProjection, distance: closestDistance };
}
}, {
key: "_distanceSquared",
value: function _distanceSquared(a, b) {
var dx = b.x - a.x;
var dy = b.y - a.y;
return dx * dx + dy * dy;
}
for (const edge of navPoly.edges) {
const projectedPoint = this._projectPointToEdge(point, edge);
// Project a point onto a line segment
// JS Source: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
const d = point.distance(projectedPoint);
}, {
key: "_projectPointToEdge",
value: function _projectPointToEdge(point, line) {
var a = line.start;
var b = line.end;
// Consider the parametric equation for the edge's line, p = a + t (b - a). We want to find
// where our point lies on the line by solving for t:
// t = [(p-a) . (b-a)] / |b-a|^2
var l2 = this._distanceSquared(a, b);
var t = ((point.x - a.x) * (b.x - a.x) + (point.y - a.y) * (b.y - a.y)) / l2;
// We clamp t from [0,1] to handle points outside the segment vw.
t = clamp(t, 0, 1);
// Project onto the segment
var p = new vector_2(a.x + t * (b.x - a.x), a.y + t * (b.y - a.y));
return p;
if (closestProjection === null || d < closestDistance) {
closestDistance = d;
closestProjection = projectedPoint;
}
}
}]);
return NavMesh;
}();
return {
point: closestProjection,
distance: closestDistance
};
}
/* harmony default export */ var navmesh = (navmesh_NavMesh);
_distanceSquared(a, b) {
const dx = b.x - a.x;
const dy = b.y - a.y;
return dx * dx + dy * dy;
} // Project a point onto a line segment
// JS Source: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
_projectPointToEdge(point, line) {
const a = line.start;
const b = line.end; // Consider the parametric equation for the edge's line, p = a + t (b - a). We want to find
// where our point lies on the line by solving for t:
// t = [(p-a) . (b-a)] / |b-a|^2
const l2 = this._distanceSquared(a, b);
let t = ((point.x - a.x) * (b.x - a.x) + (point.y - a.y) * (b.y - a.y)) / l2; // We clamp t from [0,1] to handle points outside the segment vw.
t = clamp(t, 0, 1); // Project onto the segment
const p = new Vector2(a.x + t * (b.x - a.x), a.y + t * (b.y - a.y));
return p;
}
}
// CONCATENATED MODULE: ./index.js
/* harmony default export */ var index = __webpack_exports__["default"] = (navmesh_NavMesh);
/* harmony default export */ var index = __webpack_exports__["default"] = (navmesh);
/***/ })

@@ -1690,0 +1339,0 @@ /******/ ])["default"];

2

dist/navmesh.min.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()}(window,function(){return function(t){var n={};function e(r){if(n[r])return n[r].exports;var i=n[r]={i:r,l:!1,exports:{}};return t[r].call(i.exports,i,i.exports,e),i.l=!0,i.exports}return e.m=t,e.c=n,e.d=function(t,n,r){e.o(t,n)||Object.defineProperty(t,n,{enumerable:!0,get:r})},e.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},e.t=function(t,n){if(1&n&&(t=e(t)),8&n)return t;if(4&n&&"object"==typeof t&&t&&t.__esModule)return t;var r=Object.create(null);if(e.r(r),Object.defineProperty(r,"default",{enumerable:!0,value:t}),2&n&&"string"!=typeof t)for(var i in t)e.d(r,i,function(n){return t[n]}.bind(null,i));return r},e.n=function(t){var n=t&&t.__esModule?function(){return t.default}:function(){return t};return e.d(n,"a",n),n},e.o=function(t,n){return Object.prototype.hasOwnProperty.call(t,n)},e.p="",e(e.s=1)}([function(t,n,e){var r,i,o;!function(n){"object"==typeof t&&"object"==typeof t.exports?t.exports=n():(i=[],void 0===(o="function"==typeof(r=n)?r.apply(void 0,i):r)||(t.exports=o))}(function(){function t(t){for(var n=t,e=[];n.parent;)e.unshift(n),n=n.parent;return e}var n={search:function(e,r,o,a){e.cleanDirty();var u=(a=a||{}).heuristic||n.heuristics.manhattan,s=a.closest||!1,h=new i(function(t){return t.f}),l=r;for(r.h=u(r,o),e.markDirty(r),h.push(r);h.size()>0;){var c=h.pop();if(c===o)return t(c);c.closed=!0;for(var f=e.neighbors(c),y=0,p=f.length;y<p;++y){var v=f[y];if(!v.closed&&!v.isWall()){var d=c.g+v.getCost(c),g=v.visited;(!g||d<v.g)&&(v.visited=!0,v.parent=c,v.h=v.h||u(v,o),v.g=d,v.f=v.g+v.h,e.markDirty(v),s&&(v.h<l.h||v.h===l.h&&v.g<l.g)&&(l=v),g?h.rescoreElement(v):h.push(v))}}}return s?t(l):[]},heuristics:{manhattan:function(t,n){return Math.abs(n.x-t.x)+Math.abs(n.y-t.y)},diagonal:function(t,n){var e=Math.sqrt(2),r=Math.abs(n.x-t.x),i=Math.abs(n.y-t.y);return 1*(r+i)+(e-2)*Math.min(r,i)}},cleanNode:function(t){t.f=0,t.g=0,t.h=0,t.visited=!1,t.closed=!1,t.parent=null}};function e(t,n){n=n||{},this.nodes=[],this.diagonal=!!n.diagonal,this.grid=[];for(var e=0;e<t.length;e++){this.grid[e]=[];for(var i=0,o=t[e];i<o.length;i++){var a=new r(e,i,o[i]);this.grid[e][i]=a,this.nodes.push(a)}}this.init()}function r(t,n,e){this.x=t,this.y=n,this.weight=e}function i(t){this.content=[],this.scoreFunction=t}return e.prototype.init=function(){this.dirtyNodes=[];for(var t=0;t<this.nodes.length;t++)n.cleanNode(this.nodes[t])},e.prototype.cleanDirty=function(){for(var t=0;t<this.dirtyNodes.length;t++)n.cleanNode(this.dirtyNodes[t]);this.dirtyNodes=[]},e.prototype.markDirty=function(t){this.dirtyNodes.push(t)},e.prototype.neighbors=function(t){var n=[],e=t.x,r=t.y,i=this.grid;return i[e-1]&&i[e-1][r]&&n.push(i[e-1][r]),i[e+1]&&i[e+1][r]&&n.push(i[e+1][r]),i[e]&&i[e][r-1]&&n.push(i[e][r-1]),i[e]&&i[e][r+1]&&n.push(i[e][r+1]),this.diagonal&&(i[e-1]&&i[e-1][r-1]&&n.push(i[e-1][r-1]),i[e+1]&&i[e+1][r-1]&&n.push(i[e+1][r-1]),i[e-1]&&i[e-1][r+1]&&n.push(i[e-1][r+1]),i[e+1]&&i[e+1][r+1]&&n.push(i[e+1][r+1])),n},e.prototype.toString=function(){for(var t=[],n=this.grid,e=0;e<n.length;e++){for(var r=[],i=n[e],o=0;o<i.length;o++)r.push(i[o].weight);t.push(r.join(" "))}return t.join("\n")},r.prototype.toString=function(){return"["+this.x+" "+this.y+"]"},r.prototype.getCost=function(t){return t&&t.x!=this.x&&t.y!=this.y?1.41421*this.weight:this.weight},r.prototype.isWall=function(){return 0===this.weight},i.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),e=this.content.pop();n!==this.content.length-1&&(this.content[n]=e,this.scoreFunction(e)<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 e=(t+1>>1)-1,r=this.content[e];if(!(this.scoreFunction(n)<this.scoreFunction(r)))break;this.content[e]=n,this.content[t]=r,t=e}},bubbleUp:function(t){for(var n=this.content.length,e=this.content[t],r=this.scoreFunction(e);;){var i,o=t+1<<1,a=o-1,u=null;if(a<n){var s=this.content[a];(i=this.scoreFunction(s))<r&&(u=a)}if(o<n){var h=this.content[o];this.scoreFunction(h)<(null===u?r:i)&&(u=o)}if(null===u)break;this.content[t]=this.content[u],this.content[u]=e,t=u}}},{astar:n,Graph:e}})},function(t,n,e){"use strict";e.r(n);var r=e(0),i=e.n(r),o=function(){function t(t,n){for(var e=0;e<n.length;e++){var r=n[e];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(t,r.key,r)}}return function(n,e,r){return e&&t(n.prototype,e),r&&t(n,r),n}}();var a=function(){function t(n,e){!function(t,n){if(!(t instanceof n))throw new TypeError("Cannot call a class as a function")}(this,t),this.x=n||0,this.y=e||0}return o(t,[{key:"equals",value:function(t){return this.x===t.x&&this.y===t.y}},{key:"angle",value:function(t){return Math.atan2(t.y-this.y,t.x-this.x)}},{key:"distance",value:function(t){var n=t.x-this.x,e=t.y-this.y;return Math.sqrt(n*n+e*e)}},{key:"add",value:function(t){this.x+=t.x,this.y+=t.y}},{key:"subtract",value:function(t){this.x-=t.x,this.y-=t.y}},{key:"clone",value:function(){return new t(this.x,this.y)}}]),t}(),u=function(){function t(t,n){for(var e=0;e<n.length;e++){var r=n[e];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(t,r.key,r)}}return function(n,e,r){return e&&t(n.prototype,e),r&&t(n,r),n}}();var s=function(){function t(n,e){!function(t,n){if(!(t instanceof n))throw new TypeError("Cannot call a class as a function")}(this,t),this.id=n,this.polygon=e,this.edges=e.edges,this.neighbors=[],this.portals=[],this.centroid=this.calculateCentroid(),this.boundingRadius=this.calculateRadius(),this.weight=1}return u(t,[{key:"getPoints",value:function(){return this.polygon.points}},{key:"contains",value:function(t){return this.polygon.contains(t.x,t.y)||this.isPointOnEdge(t)}},{key:"calculateCentroid",value:function(){var t=new a(0,0),n=this.polygon.points.length;return this.polygon.points.forEach(function(n){return t.add(n)}),t.x/=n,t.y/=n,t}},{key:"calculateRadius",value:function(){var t=0,n=!0,e=!1,r=void 0;try{for(var i,o=this.polygon.points[Symbol.iterator]();!(n=(i=o.next()).done);n=!0){var a=i.value,u=this.centroid.distance(a);u>t&&(t=u)}}catch(t){e=!0,r=t}finally{try{!n&&o.return&&o.return()}finally{if(e)throw r}}return t}},{key:"isPointOnEdge",value:function(t){var n=t.x,e=t.y,r=!0,i=!1,o=void 0;try{for(var a,u=this.edges[Symbol.iterator]();!(r=(a=u.next()).done);r=!0){if(a.value.pointOnSegment(n,e))return!0}}catch(t){i=!0,o=t}finally{try{!r&&u.return&&u.return()}finally{if(i)throw o}}return!1}},{key:"destroy",value:function(){this.neighbors=[],this.portals=[]}},{key:"toString",value:function(){return"NavPoly(id: "+this.id+" at: "+this.centroid+")"}},{key:"isWall",value:function(){return 0===this.weight}},{key:"centroidDistance",value:function(t){return this.centroid.distance(t.centroid)}},{key:"getCost",value:function(t){return this.centroidDistance(t)}}]),t}(),h=function(){function t(t,n){for(var e=0;e<n.length;e++){var r=n[e];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(t,r.key,r)}}return function(n,e,r){return e&&t(n.prototype,e),r&&t(n,r),n}}();var l=function(){function t(n){!function(t,n){if(!(t instanceof n))throw new TypeError("Cannot call a class as a function")}(this,t),this.nodes=n,this.init()}return h(t,[{key:"neighbors",value:function(t){return t.neighbors}},{key:"navHeuristic",value:function(t,n){return t.centroidDistance(n)}},{key:"destroy",value:function(){this.cleanDirty(),this.nodes=[]}}]),t}();l.prototype.init=i.a.Graph.prototype.init,l.prototype.cleanDirty=i.a.Graph.prototype.cleanDirty,l.prototype.markDirty=i.a.Graph.prototype.markDirty;var c=l;function f(t,n,e){var r=n.x-t.x,i=n.y-t.y;return(e.x-t.x)*i-r*(e.y-t.y)}function y(t,n){var e=arguments.length>2&&void 0!==arguments[2]?arguments[2]:1e-4;return Math.abs(t-n)<=e}function p(t,n){var e=t-n,r=e+Math.PI,i=2*Math.PI;return e=r-Math.floor(r/i)*i,e-=Math.PI}function v(t,n){var e=arguments.length>2&&void 0!==arguments[2]?arguments[2]:1e-4,r=f(t.start,t.end,n.start),i=f(t.start,t.end,n.end);return!(!y(r,0,e)||!y(i,0,e))}var d=function(){function t(t,n){for(var e=0;e<n.length;e++){var r=n[e];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(t,r.key,r)}}return function(n,e,r){return e&&t(n.prototype,e),r&&t(n,r),n}}();var g=function(){function t(){!function(t,n){if(!(t instanceof n))throw new TypeError("Cannot call a class as a function")}(this,t),this.portals=[]}return d(t,[{key:"push",value:function(t){var n=arguments.length>1&&void 0!==arguments[1]?arguments[1]:null;null===n&&(n=t),this.portals.push({left:t,right:n})}},{key:"stringPull",value:function(){var t,n,e,r=this.portals,i=[],o=0,a=0,u=0;t=r[0].left,n=r[0].left,e=r[0].right,i.push(t);for(var s=1;s<r.length;s++){var h=r[s].left,l=r[s].right;if(f(t,e,l)<=0){if(!(t.equals(e)||f(t,n,l)>0)){i.push(n),n=t=n,e=t,a=o=a,u=o,s=o;continue}e=l,u=s}if(f(t,n,h)>=0){if(!(t.equals(n)||f(t,e,h)<0)){i.push(e),n=t=e,e=t,a=o=u,u=o,s=o;continue}n=h,a=s}}return 0!==i.length&&i[i.length-1].equals(r[r.length-1].left)||i.push(r[r.length-1].left),this.path=i,i}}]),t}(),b=function(){function t(t,n){for(var e=0;e<n.length;e++){var r=n[e];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(t,r.key,r)}}return function(n,e,r){return e&&t(n.prototype,e),r&&t(n,r),n}}();var x=function(){function t(n,e,r,i){!function(t,n){if(!(t instanceof n))throw new TypeError("Cannot call a class as a function")}(this,t),this.start=new a(n,e),this.end=new a(r,i),this.left=Math.min(n,r),this.right=Math.max(n,r),this.top=Math.min(e,i),this.bottom=Math.max(e,i)}return b(t,[{key:"pointOnSegment",value:function(t,n){return t>=this.left&&t<=this.right&&n>=this.top&&n<=this.bottom&&this.pointOnLine(t,n)}},{key:"pointOnLine",value:function(t,n){return(t-this.left)*(this.bottom-this.top)==(this.right-this.left)*(n-this.top)}}]),t}(),m=function(){function t(t,n){for(var e=0;e<n.length;e++){var r=n[e];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(t,r.key,r)}}return function(n,e,r){return e&&t(n.prototype,e),r&&t(n,r),n}}();var w=function(){function t(n){var e=!(arguments.length>1&&void 0!==arguments[1])||arguments[1];!function(t,n){if(!(t instanceof n))throw new TypeError("Cannot call a class as a function")}(this,t),this.points=n,this.edges=[];for(var r=1;r<n.length;r++){var i=n[r-1],o=n[r];this.edges.push(new x(i.x,i.y,o.x,o.y))}if(e){var a=n[0],u=n[n.length-1];this.edges.push(new x(a.x,a.y,u.x,u.y))}}return m(t,[{key:"contains",value:function(t,n){for(var e=!1,r=-1,i=this.points.length-1;++r<this.points.length;i=r){var o=this.points[r].x,a=this.points[r].y,u=this.points[i].x,s=this.points[i].y;(a<=n&&n<s||s<=n&&n<a)&&t<(u-o)*(n-a)/(s-a)+o&&(e=!e)}return e}}]),t}(),k=function(){return function(t,n){if(Array.isArray(t))return t;if(Symbol.iterator in Object(t))return function(t,n){var e=[],r=!0,i=!1,o=void 0;try{for(var a,u=t[Symbol.iterator]();!(r=(a=u.next()).done)&&(e.push(a.value),!n||e.length!==n);r=!0);}catch(t){i=!0,o=t}finally{try{!r&&u.return&&u.return()}finally{if(i)throw o}}return e}(t,n);throw new TypeError("Invalid attempt to destructure non-iterable instance")}}(),P=function(){function t(t,n){for(var e=0;e<n.length;e++){var r=n[e];r.enumerable=r.enumerable||!1,r.configurable=!0,"value"in r&&(r.writable=!0),Object.defineProperty(t,r.key,r)}}return function(n,e,r){return e&&t(n.prototype,e),r&&t(n,r),n}}();var _=function(){function t(n){var e=arguments.length>1&&void 0!==arguments[1]?arguments[1]:0;!function(t,n){if(!(t instanceof n))throw new TypeError("Cannot call a class as a function")}(this,t),this._meshShrinkAmount=e;var r=n.map(function(t){var n=t.map(function(t){return new a(t.x,t.y)});return new w(n)});this._navPolygons=r.map(function(t,n){return new s(n,t)}),this._calculateNeighbors(),this._graph=new c(this._navPolygons)}return P(t,[{key:"getPolygons",value:function(){return this._navPolygons}},{key:"destroy",value:function(){this._graph.destroy();var t=!0,n=!1,e=void 0;try{for(var r,i=this._navPolygons[Symbol.iterator]();!(t=(r=i.next()).done);t=!0){r.value.destroy()}}catch(t){n=!0,e=t}finally{try{!t&&i.return&&i.return()}finally{if(n)throw e}}this._navPolygons=[]}},{key:"findPath",value:function(t,n){var e=null,r=null,o=Number.MAX_VALUE,u=Number.MAX_VALUE,s=void 0,h=void 0,l=new a(t.x,t.y),c=new a(n.x,n.y),f=!0,y=!1,p=void 0;try{for(var v,d=this._navPolygons[Symbol.iterator]();!(f=(v=d.next()).done);f=!0){var b=v.value;h=b.boundingRadius,(s=b.centroid.distance(l))<=o&&s<=h&&b.contains(l)&&(e=b,o=s),(s=b.centroid.distance(c))<=u&&s<=h&&b.contains(c)&&(r=b,u=s)}}catch(t){y=!0,p=t}finally{try{!f&&d.return&&d.return()}finally{if(y)throw p}}if(!e&&this._meshShrinkAmount>0){var x=!0,m=!1,w=void 0;try{for(var k,P=this._navPolygons[Symbol.iterator]();!(x=(k=P.next()).done);x=!0){var _=k.value;if(h=_.boundingRadius+this._meshShrinkAmount,(s=_.centroid.distance(l))<=h){var S=this._projectPointToPolygon(l,_).distance;S<=this._meshShrinkAmount&&S<o&&(e=_,o=S)}}}catch(t){m=!0,w=t}finally{try{!x&&P.return&&P.return()}finally{if(m)throw w}}}if(!r&&this._meshShrinkAmount>0){var j=!0,M=!1,O=void 0;try{for(var E,D=this._navPolygons[Symbol.iterator]();!(j=(E=D.next()).done);j=!0){var N=E.value;if(h=N.boundingRadius+this._meshShrinkAmount,(s=N.centroid.distance(c))<=h){var A=this._projectPointToPolygon(c,N).distance;A<=this._meshShrinkAmount&&A<u&&(r=N,u=A)}}}catch(t){M=!0,O=t}finally{try{!j&&D.return&&D.return()}finally{if(M)throw O}}}if(!e||!r)return null;if(e===r)return[l,c];var T=i.a.astar.search(this._graph,e,r,{heuristic:this._graph.navHeuristic});if(0===T.length)return null;T.unshift(e);var C=new g;C.push(l);for(var q=0;q<T.length-1;q++){for(var F=T[q],R=T[q+1],U=null,L=0;L<F.neighbors.length;L++)F.neighbors[L].id===R.id&&(U=F.portals[L]);C.push(U.start,U.end)}C.push(c),C.stringPull();var G=null,I=[],V=!0,W=!1,X=void 0;try{for(var z,H=C.path[Symbol.iterator]();!(V=(z=H.next()).done);V=!0){var B=z.value.clone();G&&B.equals(G)||I.push(B),G=B}}catch(t){W=!0,X=t}finally{try{!V&&H.return&&H.return()}finally{if(W)throw X}}return I}},{key:"_calculateNeighbors",value:function(){for(var t=0;t<this._navPolygons.length;t++)for(var n=this._navPolygons[t],e=t+1;e<this._navPolygons.length;e++){var r=this._navPolygons[e];if(!(n.centroid.distance(r.centroid)>n.boundingRadius+r.boundingRadius)){var i=!0,o=!1,a=void 0;try{for(var u,s=n.edges[Symbol.iterator]();!(i=(u=s.next()).done);i=!0){var h=u.value,l=!0,c=!1,f=void 0;try{for(var y,d=r.edges[Symbol.iterator]();!(l=(y=d.next()).done);l=!0){var g=y.value;if(v(h,g)){var b=this._getSegmentOverlap(h,g);if(b){n.neighbors.push(r),r.neighbors.push(n);var m=k(b,2),w=m[0],P=m[1],_=n.centroid.angle(h.start),S=n.centroid.angle(b[0]),j=n.centroid.angle(b[1]),M=p(_,S),O=p(_,j);M<O?n.portals.push(new x(w.x,w.y,P.x,P.y)):n.portals.push(new x(P.x,P.y,w.x,w.y)),_=r.centroid.angle(g.start),S=r.centroid.angle(b[0]),j=r.centroid.angle(b[1]),(M=p(_,S))<(O=p(_,j))?r.portals.push(new x(w.x,w.y,P.x,P.y)):r.portals.push(new x(P.x,P.y,w.x,w.y))}}}}catch(t){c=!0,f=t}finally{try{!l&&d.return&&d.return()}finally{if(c)throw f}}}}catch(t){o=!0,a=t}finally{try{!i&&s.return&&s.return()}finally{if(o)throw a}}}}}},{key:"_getSegmentOverlap",value:function(t,n){var e=[{line:t,point:t.start},{line:t,point:t.end},{line:n,point:n.start},{line:n,point:n.end}];e.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});var r=e[0].line===e[1].line,i=e[1].point.equals(e[2].point);return r||i?null:[e[1].point,e[2].point]}},{key:"_projectPointToPolygon",value:function(t,n){var e=null,r=Number.MAX_VALUE,i=!0,o=!1,a=void 0;try{for(var u,s=n.edges[Symbol.iterator]();!(i=(u=s.next()).done);i=!0){var h=u.value,l=this._projectPointToEdge(t,h),c=t.distance(l);(null===e||c<r)&&(r=c,e=l)}}catch(t){o=!0,a=t}finally{try{!i&&s.return&&s.return()}finally{if(o)throw a}}return{point:e,distance:r}}},{key:"_distanceSquared",value:function(t,n){var e=n.x-t.x,r=n.y-t.y;return e*e+r*r}},{key:"_projectPointToEdge",value:function(t,n){var e=n.start,r=n.end,i=this._distanceSquared(e,r),o=((t.x-e.x)*(r.x-e.x)+(t.y-e.y)*(r.y-e.y))/i;return o=function(t,n,e){return t<n&&(t=n),t>e&&(t=e),t}(o,0,1),new a(e.x+o*(r.x-e.x),e.y+o*(r.y-e.y))}}]),t}();n.default=_}]).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 function(t){var n={};function i(e){if(n[e])return n[e].exports;var o=n[e]={i:e,l:!1,exports:{}};return t[e].call(o.exports,o,o.exports,i),o.l=!0,o.exports}return i.m=t,i.c=n,i.d=function(t,n,e){i.o(t,n)||Object.defineProperty(t,n,{enumerable:!0,get:e})},i.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},i.t=function(t,n){if(1&n&&(t=i(t)),8&n)return t;if(4&n&&"object"==typeof t&&t&&t.__esModule)return t;var e=Object.create(null);if(i.r(e),Object.defineProperty(e,"default",{enumerable:!0,value:t}),2&n&&"string"!=typeof t)for(var o in t)i.d(e,o,function(n){return t[n]}.bind(null,o));return e},i.n=function(t){var n=t&&t.__esModule?function(){return t.default}:function(){return t};return i.d(n,"a",n),n},i.o=function(t,n){return Object.prototype.hasOwnProperty.call(t,n)},i.p="",i(i.s=1)}([function(t,n,i){var e,o,s;!function(n){"object"==typeof t.exports?t.exports=n():(o=[],void 0===(s="function"==typeof(e=n)?e.apply(void 0,o):e)||(t.exports=s))}(function(){function t(t){for(var n=t,i=[];n.parent;)i.unshift(n),n=n.parent;return i}var n={search:function(i,e,s,r){i.cleanDirty();var h=(r=r||{}).heuristic||n.heuristics.manhattan,c=r.closest||!1,u=new o(function(t){return t.f}),a=e;for(e.h=h(e,s),i.markDirty(e),u.push(e);u.size()>0;){var l=u.pop();if(l===s)return t(l);l.closed=!0;for(var p=i.neighbors(l),f=0,d=p.length;f<d;++f){var g=p[f];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,s),g.g=y,g.f=g.g+g.h,i.markDirty(g),c&&(g.h<a.h||g.h===a.h&&g.g<a.g)&&(a=g),x?u.rescoreElement(g):u.push(g))}}}return c?t(a):[]},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),e=Math.abs(n.x-t.x),o=Math.abs(n.y-t.y);return 1*(e+o)+(i-2)*Math.min(e,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,s=t[i];o<s.length;o++){var r=new e(i,o,s[o]);this.grid[i][o]=r,this.nodes.push(r)}}this.init()}function e(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,e=t.y,o=this.grid;return o[i-1]&&o[i-1][e]&&n.push(o[i-1][e]),o[i+1]&&o[i+1][e]&&n.push(o[i+1][e]),o[i]&&o[i][e-1]&&n.push(o[i][e-1]),o[i]&&o[i][e+1]&&n.push(o[i][e+1]),this.diagonal&&(o[i-1]&&o[i-1][e-1]&&n.push(o[i-1][e-1]),o[i+1]&&o[i+1][e-1]&&n.push(o[i+1][e-1]),o[i-1]&&o[i-1][e+1]&&n.push(o[i-1][e+1]),o[i+1]&&o[i+1][e+1]&&n.push(o[i+1][e+1])),n},i.prototype.toString=function(){for(var t=[],n=this.grid,i=0;i<n.length;i++){for(var e=[],o=n[i],s=0;s<o.length;s++)e.push(o[s].weight);t.push(e.join(" "))}return t.join("\n")},e.prototype.toString=function(){return"["+this.x+" "+this.y+"]"},e.prototype.getCost=function(t){return t&&t.x!=this.x&&t.y!=this.y?1.41421*this.weight:this.weight},e.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,e=this.content[i];if(!(this.scoreFunction(n)<this.scoreFunction(e)))break;this.content[i]=n,this.content[t]=e,t=i}},bubbleUp:function(t){for(var n=this.content.length,i=this.content[t],e=this.scoreFunction(i);;){var o,s=t+1<<1,r=s-1,h=null;if(r<n){var c=this.content[r];(o=this.scoreFunction(c))<e&&(h=r)}if(s<n){var u=this.content[s];this.scoreFunction(u)<(null===h?e:o)&&(h=s)}if(null===h)break;this.content[t]=this.content[h],this.content[h]=i,t=h}}},{astar:n,Graph:i}})},function(t,n,i){"use strict";i.r(n);var e=i(0),o=i.n(e);class s{constructor(t,n){this.x=t||0,this.y=n||0}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 s(this.x,this.y)}}class r{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(),this.weight=1}getPoints(){return this.polygon.points}contains(t){return this.polygon.contains(t.x,t.y)||this.isPointOnEdge(t)}calculateCentroid(){const t=new s(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)}}class h{constructor(t){this.nodes=t,this.init()}neighbors(t){return t.neighbors}navHeuristic(t,n){return t.centroidDistance(n)}destroy(){this.cleanDirty(),this.nodes=[]}}h.prototype.init=o.a.Graph.prototype.init,h.prototype.cleanDirty=o.a.Graph.prototype.cleanDirty,h.prototype.markDirty=o.a.Graph.prototype.markDirty;var c=h;function u(t,n,i){const e=n.x-t.x,o=n.y-t.y;return(i.x-t.x)*o-e*(i.y-t.y)}function a(t,n,i=1e-4){return Math.abs(t-n)<=i}function l(t,n){let i=t-n;const e=i+Math.PI,o=2*Math.PI;return i=e-Math.floor(e/o)*o,i-=Math.PI}function p(t,n,i=1e-4){const e=u(t.start,t.end,n.start),o=u(t.start,t.end,n.end);return!(!a(e,0,i)||!a(o,0,i))}var f=class{constructor(){this.portals=[]}push(t,n=null){null===n&&(n=t),this.portals.push({left:t,right:n})}stringPull(){var t,n,i,e=this.portals,o=[],s=0,r=0,h=0;t=e[0].left,n=e[0].left,i=e[0].right,o.push(t);for(var c=1;c<e.length;c++){var a=e[c].left,l=e[c].right;if(u(t,i,l)<=0){if(!(t.equals(i)||u(t,n,l)>0)){o.push(n),n=t=n,i=t,r=s=r,h=s,c=s;continue}i=l,h=c}if(u(t,n,a)>=0){if(!(t.equals(n)||u(t,i,a)<0)){o.push(i),n=t=i,i=t,r=s=h,h=s,c=s;continue}n=a,r=c}}return 0!==o.length&&o[o.length-1].equals(e[e.length-1].left)||o.push(e[e.length-1].left),this.path=o,o}};class d{constructor(t,n,i,e){this.start=new s(t,n),this.end=new s(i,e),this.left=Math.min(t,i),this.right=Math.max(t,i),this.top=Math.min(n,e),this.bottom=Math.max(n,e)}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 g{constructor(t,n=!0){this.points=t,this.edges=[];for(let n=1;n<t.length;n++){const i=t[n-1],e=t[n];this.edges.push(new d(i.x,i.y,e.x,e.y))}if(n){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 e=-1,o=this.points.length-1;++e<this.points.length;o=e){const s=this.points[e].x,r=this.points[e].y,h=this.points[o].x,c=this.points[o].y;(r<=n&&n<c||c<=n&&n<r)&&t<(h-s)*(n-r)/(c-r)+s&&(i=!i)}return i}}n.default=class{constructor(t,n=0){this._meshShrinkAmount=n;const i=t.map(t=>{const n=t.map(t=>new s(t.x,t.y));return new g(n)});this._navPolygons=i.map((t,n)=>new r(n,t)),this._calculateNeighbors(),this._graph=new c(this._navPolygons)}getPolygons(){return this._navPolygons}destroy(){this._graph.destroy();for(const t of this._navPolygons)t.destroy();this._navPolygons=[]}findPath(t,n){let i,e,r=null,h=null,c=Number.MAX_VALUE,u=Number.MAX_VALUE;const a=new s(t.x,t.y),l=new s(n.x,n.y);for(const t of this._navPolygons)e=t.boundingRadius,(i=t.centroid.distance(a))<=c&&i<=e&&t.contains(a)&&(r=t,c=i),(i=t.centroid.distance(l))<=u&&i<=e&&t.contains(l)&&(h=t,u=i);if(!r&&this._meshShrinkAmount>0)for(const t of this._navPolygons)if(e=t.boundingRadius+this._meshShrinkAmount,(i=t.centroid.distance(a))<=e){const{distance:n}=this._projectPointToPolygon(a,t);n<=this._meshShrinkAmount&&n<c&&(r=t,c=n)}if(!h&&this._meshShrinkAmount>0)for(const t of this._navPolygons)if(e=t.boundingRadius+this._meshShrinkAmount,(i=t.centroid.distance(l))<=e){const{distance:n}=this._projectPointToPolygon(l,t);n<=this._meshShrinkAmount&&n<u&&(h=t,u=n)}if(!r||!h)return null;if(r===h)return[a,l];const p=o.a.astar.search(this._graph,r,h,{heuristic:this._graph.navHeuristic});if(0===p.length)return null;p.unshift(r);const d=new f;d.push(a);for(let t=0;t<p.length-1;t++){const n=p[t],i=p[t+1];let e=null;for(let t=0;t<n.neighbors.length;t++)n.neighbors[t].id===i.id&&(e=n.portals[t]);d.push(e.start,e.end)}d.push(l),d.stringPull();let g=null;const y=[];for(const t of d.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 e of t.edges){if(!p(i,e))continue;const o=this._getSegmentOverlap(i,e);if(!o)continue;n.neighbors.push(t),t.neighbors.push(n);const[s,r]=o;let h=n.centroid.angle(i.start),c=n.centroid.angle(o[0]),u=n.centroid.angle(o[1]),a=l(h,c),f=l(h,u);a<f?n.portals.push(new d(s.x,s.y,r.x,r.y)):n.portals.push(new d(r.x,r.y,s.x,s.y)),h=t.centroid.angle(e.start),c=t.centroid.angle(o[0]),u=t.centroid.angle(o[1]),(a=l(h,c))<(f=l(h,u))?t.portals.push(new d(s.x,s.y,r.x,r.y)):t.portals.push(new d(r.x,r.y,s.x,s.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 e=i[0].line===i[1].line,o=i[1].point.equals(i[2].point);return e||o?null:[i[1].point,i[2].point]}_projectPointToPolygon(t,n){let i=null,e=Number.MAX_VALUE;for(const o of n.edges){const n=this._projectPointToEdge(t,o),s=t.distance(n);(null===i||s<e)&&(e=s,i=n)}return{point:i,distance:e}}_distanceSquared(t,n){const i=n.x-t.x,e=n.y-t.y;return i*i+e*e}_projectPointToEdge(t,n){const i=n.start,e=n.end,o=this._distanceSquared(i,e);let r=((t.x-i.x)*(e.x-i.x)+(t.y-i.y)*(e.y-i.y))/o;return r=function(t,n,i){return t<n&&(t=n),t>i&&(t=i),t}(r,0,1),new s(i.x+r*(e.x-i.x),i.y+r*(e.y-i.y))}}}]).default});
//# sourceMappingURL=navmesh.min.js.map

11

package.json
{
"name": "navmesh",
"version": "2.0.2",
"version": "2.0.3",
"description": "A library for fast pathfinding using navigation meshes in JS",

@@ -16,6 +16,6 @@ "main": "dist/navmesh.min.js",

"devDependencies": {
"babel-core": "^6.26.3",
"@babel/core": "^7.5.5",
"@babel/preset-env": "^7.5.5",
"babel-jest": "^23.2.0",
"babel-loader": "^7.1.4",
"babel-preset-env": "^1.7.0",
"babel-loader": "^8.0.6",
"jest": "^23.2.0",

@@ -43,3 +43,4 @@ "uglifyjs-webpack-plugin": "^1.2.7",

},
"homepage": "https://github.com/mikewesthad/phaser-navmesh-plugin#readme"
"homepage": "https://github.com/mikewesthad/phaser-navmesh-plugin#readme",
"gitHead": "f5fdc676b88a7ac85cf2c169428efb7851de7f5d"
}

4

README.md

@@ -9,4 +9,8 @@ # NavMesh

Version 2.0.3 - 2019-08-04
- Bug: fixed webpack config so that it applied babel transform and so that it worked under node environments, thanks to [@will-hart](https://github.com/will-hart)
Version 2.0.2 - 2018-01-03
- Initial publish of changelog

5

webpack.config.js

@@ -21,3 +21,4 @@ /* eslint-env node */

libraryTarget: "umd",
libraryExport: "default"
libraryExport: "default",
globalObject: '(typeof self !== "undefined" ? self : this)'
},

@@ -32,3 +33,3 @@ optimization: {

exclude: /node_modules/,
use: ["babel-loader"]
use: { loader: "babel-loader", options: { root: "../../" } }
}

@@ -35,0 +36,0 @@ ]

dist/navmesh.js.map

Sorry, the diff of this file is not supported yet

dist/navmesh.min.js.map

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc