mirror of
https://github.com/JulianGro/overte.git
synced 2025-04-06 01:22:55 +02:00
743 lines
No EOL
27 KiB
JavaScript
743 lines
No EOL
27 KiB
JavaScript
// The MIT License (MIT)
|
|
|
|
// Copyright (c) 2012-2015 Bryce Neal
|
|
|
|
// Permission is hereby granted, free of charge, to any person obtaining a copy
|
|
// of this software and associated documentation files (the "Software"), to deal
|
|
// in the Software without restriction, including without limitation the rights
|
|
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
|
// copies of the Software, and to permit persons to whom the Software is
|
|
// furnished to do so, subject to the following conditions:
|
|
|
|
// The above copyright notice and this permission notice shall be included in
|
|
// all copies or substantial portions of the Software.
|
|
|
|
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
|
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
|
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
|
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
|
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
|
|
// THE SOFTWARE.
|
|
|
|
// Adapted for High Fidelity by James B. Pollack on 11/6/2015
|
|
|
|
loadEasyStar = function() {
|
|
var ezStar = eStar();
|
|
return new ezStar.js()
|
|
}
|
|
|
|
var eStar = function() {
|
|
|
|
var EasyStar = EasyStar || {};
|
|
|
|
|
|
/**
|
|
* A simple Node that represents a single tile on the grid.
|
|
* @param {Object} parent The parent node.
|
|
* @param {Number} x The x position on the grid.
|
|
* @param {Number} y The y position on the grid.
|
|
* @param {Number} costSoFar How far this node is in moves*cost from the start.
|
|
* @param {Number} simpleDistanceToTarget Manhatten distance to the end point.
|
|
**/
|
|
EasyStar.Node = function(parent, x, y, costSoFar, simpleDistanceToTarget) {
|
|
this.parent = parent;
|
|
this.x = x;
|
|
this.y = y;
|
|
this.costSoFar = costSoFar;
|
|
this.simpleDistanceToTarget = simpleDistanceToTarget;
|
|
|
|
/**
|
|
* @return {Number} Best guess distance of a cost using this node.
|
|
**/
|
|
this.bestGuessDistance = function() {
|
|
return this.costSoFar + this.simpleDistanceToTarget;
|
|
}
|
|
};
|
|
|
|
// Constants
|
|
EasyStar.Node.OPEN_LIST = 0;
|
|
EasyStar.Node.CLOSED_LIST = 1;
|
|
/**
|
|
* This is an improved Priority Queue data type implementation that can be used to sort any object type.
|
|
* It uses a technique called a binary heap.
|
|
*
|
|
* For more on binary heaps see: http://en.wikipedia.org/wiki/Binary_heap
|
|
*
|
|
* @param {String} criteria The criteria by which to sort the objects.
|
|
* This should be a property of the objects you're sorting.
|
|
*
|
|
* @param {Number} heapType either PriorityQueue.MAX_HEAP or PriorityQueue.MIN_HEAP.
|
|
**/
|
|
EasyStar.PriorityQueue = function(criteria, heapType) {
|
|
this.length = 0; //The current length of heap.
|
|
var queue = [];
|
|
var isMax = false;
|
|
|
|
//Constructor
|
|
if (heapType == EasyStar.PriorityQueue.MAX_HEAP) {
|
|
isMax = true;
|
|
} else if (heapType == EasyStar.PriorityQueue.MIN_HEAP) {
|
|
isMax = false;
|
|
} else {
|
|
throw heapType + " not supported.";
|
|
}
|
|
|
|
/**
|
|
* Inserts the value into the heap and sorts it.
|
|
*
|
|
* @param value The object to insert into the heap.
|
|
**/
|
|
this.insert = function(value) {
|
|
if (!value.hasOwnProperty(criteria)) {
|
|
throw "Cannot insert " + value + " because it does not have a property by the name of " + criteria + ".";
|
|
}
|
|
queue.push(value);
|
|
this.length++;
|
|
bubbleUp(this.length - 1);
|
|
}
|
|
|
|
/**
|
|
* Peeks at the highest priority element.
|
|
*
|
|
* @return the highest priority element
|
|
**/
|
|
this.getHighestPriorityElement = function() {
|
|
return queue[0];
|
|
}
|
|
|
|
/**
|
|
* Removes and returns the highest priority element from the queue.
|
|
*
|
|
* @return the highest priority element
|
|
**/
|
|
this.shiftHighestPriorityElement = function() {
|
|
if (this.length === 0) {
|
|
throw ("There are no more elements in your priority queue.");
|
|
} else if (this.length === 1) {
|
|
var onlyValue = queue[0];
|
|
queue = [];
|
|
this.length = 0;
|
|
return onlyValue;
|
|
}
|
|
var oldRoot = queue[0];
|
|
var newRoot = queue.pop();
|
|
this.length--;
|
|
queue[0] = newRoot;
|
|
swapUntilQueueIsCorrect(0);
|
|
return oldRoot;
|
|
}
|
|
|
|
var bubbleUp = function(index) {
|
|
if (index === 0) {
|
|
return;
|
|
}
|
|
var parent = getParentOf(index);
|
|
if (evaluate(index, parent)) {
|
|
swap(index, parent);
|
|
bubbleUp(parent);
|
|
} else {
|
|
return;
|
|
}
|
|
}
|
|
|
|
var swapUntilQueueIsCorrect = function(value) {
|
|
var left = getLeftOf(value);
|
|
var right = getRightOf(value);
|
|
if (evaluate(left, value)) {
|
|
swap(value, left);
|
|
swapUntilQueueIsCorrect(left);
|
|
} else if (evaluate(right, value)) {
|
|
swap(value, right);
|
|
swapUntilQueueIsCorrect(right);
|
|
} else if (value == 0) {
|
|
return;
|
|
} else {
|
|
swapUntilQueueIsCorrect(0);
|
|
}
|
|
}
|
|
|
|
var swap = function(self, target) {
|
|
var placeHolder = queue[self];
|
|
queue[self] = queue[target];
|
|
queue[target] = placeHolder;
|
|
}
|
|
|
|
var evaluate = function(self, target) {
|
|
if (queue[target] === undefined || queue[self] === undefined) {
|
|
return false;
|
|
}
|
|
|
|
var selfValue;
|
|
var targetValue;
|
|
|
|
// Check if the criteria should be the result of a function call.
|
|
if (typeof queue[self][criteria] === 'function') {
|
|
selfValue = queue[self][criteria]();
|
|
targetValue = queue[target][criteria]();
|
|
} else {
|
|
selfValue = queue[self][criteria];
|
|
targetValue = queue[target][criteria];
|
|
}
|
|
|
|
if (isMax) {
|
|
if (selfValue > targetValue) {
|
|
return true;
|
|
} else {
|
|
return false;
|
|
}
|
|
} else {
|
|
if (selfValue < targetValue) {
|
|
return true;
|
|
} else {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
|
|
var getParentOf = function(index) {
|
|
return Math.floor((index - 1) / 2);
|
|
}
|
|
|
|
var getLeftOf = function(index) {
|
|
return index * 2 + 1;
|
|
}
|
|
|
|
var getRightOf = function(index) {
|
|
return index * 2 + 2;
|
|
}
|
|
};
|
|
|
|
// Constants
|
|
EasyStar.PriorityQueue.MAX_HEAP = 0;
|
|
EasyStar.PriorityQueue.MIN_HEAP = 1;
|
|
|
|
/**
|
|
* Represents a single instance of EasyStar.
|
|
* A path that is in the queue to eventually be found.
|
|
*/
|
|
EasyStar.instance = function() {
|
|
this.isDoneCalculating = true;
|
|
this.pointsToAvoid = {};
|
|
this.startX;
|
|
this.callback;
|
|
this.startY;
|
|
this.endX;
|
|
this.endY;
|
|
this.nodeHash = {};
|
|
this.openList;
|
|
};
|
|
/**
|
|
* EasyStar.js
|
|
* github.com/prettymuchbryce/EasyStarJS
|
|
* Licensed under the MIT license.
|
|
*
|
|
* Implementation By Bryce Neal (@prettymuchbryce)
|
|
**/
|
|
EasyStar.js = function() {
|
|
var STRAIGHT_COST = 1.0;
|
|
var DIAGONAL_COST = 1.4;
|
|
var syncEnabled = false;
|
|
var pointsToAvoid = {};
|
|
var collisionGrid;
|
|
var costMap = {};
|
|
var pointsToCost = {};
|
|
var allowCornerCutting = true;
|
|
var iterationsSoFar;
|
|
var instances = [];
|
|
var iterationsPerCalculation = Number.MAX_VALUE;
|
|
var acceptableTiles;
|
|
var diagonalsEnabled = false;
|
|
|
|
/**
|
|
* Sets the collision grid that EasyStar uses.
|
|
*
|
|
* @param {Array|Number} tiles An array of numbers that represent
|
|
* which tiles in your grid should be considered
|
|
* acceptable, or "walkable".
|
|
**/
|
|
this.setAcceptableTiles = function(tiles) {
|
|
if (tiles instanceof Array) {
|
|
// Array
|
|
acceptableTiles = tiles;
|
|
} else if (!isNaN(parseFloat(tiles)) && isFinite(tiles)) {
|
|
// Number
|
|
acceptableTiles = [tiles];
|
|
}
|
|
};
|
|
|
|
/**
|
|
* Enables sync mode for this EasyStar instance..
|
|
* if you're into that sort of thing.
|
|
**/
|
|
this.enableSync = function() {
|
|
syncEnabled = true;
|
|
};
|
|
|
|
/**
|
|
* Disables sync mode for this EasyStar instance.
|
|
**/
|
|
this.disableSync = function() {
|
|
syncEnabled = false;
|
|
};
|
|
|
|
/**
|
|
* Enable diagonal pathfinding.
|
|
*/
|
|
this.enableDiagonals = function() {
|
|
diagonalsEnabled = true;
|
|
}
|
|
|
|
/**
|
|
* Disable diagonal pathfinding.
|
|
*/
|
|
this.disableDiagonals = function() {
|
|
diagonalsEnabled = false;
|
|
}
|
|
|
|
/**
|
|
* Sets the collision grid that EasyStar uses.
|
|
*
|
|
* @param {Array} grid The collision grid that this EasyStar instance will read from.
|
|
* This should be a 2D Array of Numbers.
|
|
**/
|
|
this.setGrid = function(grid) {
|
|
collisionGrid = grid;
|
|
|
|
//Setup cost map
|
|
for (var y = 0; y < collisionGrid.length; y++) {
|
|
for (var x = 0; x < collisionGrid[0].length; x++) {
|
|
if (!costMap[collisionGrid[y][x]]) {
|
|
costMap[collisionGrid[y][x]] = 1
|
|
}
|
|
}
|
|
}
|
|
};
|
|
|
|
/**
|
|
* Sets the tile cost for a particular tile type.
|
|
*
|
|
* @param {Number} The tile type to set the cost for.
|
|
* @param {Number} The multiplicative cost associated with the given tile.
|
|
**/
|
|
this.setTileCost = function(tileType, cost) {
|
|
costMap[tileType] = cost;
|
|
};
|
|
|
|
/**
|
|
* Sets the an additional cost for a particular point.
|
|
* Overrides the cost from setTileCost.
|
|
*
|
|
* @param {Number} x The x value of the point to cost.
|
|
* @param {Number} y The y value of the point to cost.
|
|
* @param {Number} The multiplicative cost associated with the given point.
|
|
**/
|
|
this.setAdditionalPointCost = function(x, y, cost) {
|
|
pointsToCost[x + '_' + y] = cost;
|
|
};
|
|
|
|
/**
|
|
* Remove the additional cost for a particular point.
|
|
*
|
|
* @param {Number} x The x value of the point to stop costing.
|
|
* @param {Number} y The y value of the point to stop costing.
|
|
**/
|
|
this.removeAdditionalPointCost = function(x, y) {
|
|
delete pointsToCost[x + '_' + y];
|
|
}
|
|
|
|
/**
|
|
* Remove all additional point costs.
|
|
**/
|
|
this.removeAllAdditionalPointCosts = function() {
|
|
pointsToCost = {};
|
|
}
|
|
|
|
/**
|
|
* Sets the number of search iterations per calculation.
|
|
* A lower number provides a slower result, but more practical if you
|
|
* have a large tile-map and don't want to block your thread while
|
|
* finding a path.
|
|
*
|
|
* @param {Number} iterations The number of searches to prefrom per calculate() call.
|
|
**/
|
|
this.setIterationsPerCalculation = function(iterations) {
|
|
iterationsPerCalculation = iterations;
|
|
};
|
|
|
|
/**
|
|
* Avoid a particular point on the grid,
|
|
* regardless of whether or not it is an acceptable tile.
|
|
*
|
|
* @param {Number} x The x value of the point to avoid.
|
|
* @param {Number} y The y value of the point to avoid.
|
|
**/
|
|
this.avoidAdditionalPoint = function(x, y) {
|
|
pointsToAvoid[x + "_" + y] = 1;
|
|
};
|
|
|
|
/**
|
|
* Stop avoiding a particular point on the grid.
|
|
*
|
|
* @param {Number} x The x value of the point to stop avoiding.
|
|
* @param {Number} y The y value of the point to stop avoiding.
|
|
**/
|
|
this.stopAvoidingAdditionalPoint = function(x, y) {
|
|
delete pointsToAvoid[x + "_" + y];
|
|
};
|
|
|
|
/**
|
|
* Enables corner cutting in diagonal movement.
|
|
**/
|
|
this.enableCornerCutting = function() {
|
|
allowCornerCutting = true;
|
|
};
|
|
|
|
/**
|
|
* Disables corner cutting in diagonal movement.
|
|
**/
|
|
this.disableCornerCutting = function() {
|
|
allowCornerCutting = false;
|
|
};
|
|
|
|
/**
|
|
* Stop avoiding all additional points on the grid.
|
|
**/
|
|
this.stopAvoidingAllAdditionalPoints = function() {
|
|
pointsToAvoid = {};
|
|
};
|
|
|
|
/**
|
|
* Find a path.
|
|
*
|
|
* @param {Number} startX The X position of the starting point.
|
|
* @param {Number} startY The Y position of the starting point.
|
|
* @param {Number} endX The X position of the ending point.
|
|
* @param {Number} endY The Y position of the ending point.
|
|
* @param {Function} callback A function that is called when your path
|
|
* is found, or no path is found.
|
|
*
|
|
**/
|
|
this.findPath = function(startX, startY, endX, endY, callback) {
|
|
// Wraps the callback for sync vs async logic
|
|
var callbackWrapper = function(result) {
|
|
if (syncEnabled) {
|
|
callback(result);
|
|
} else {
|
|
Script.setTimeout(function() {
|
|
callback(result);
|
|
}, 1);
|
|
}
|
|
}
|
|
|
|
// No acceptable tiles were set
|
|
if (acceptableTiles === undefined) {
|
|
throw new Error("You can't set a path without first calling setAcceptableTiles() on EasyStar.");
|
|
}
|
|
// No grid was set
|
|
if (collisionGrid === undefined) {
|
|
throw new Error("You can't set a path without first calling setGrid() on EasyStar.");
|
|
}
|
|
|
|
// Start or endpoint outside of scope.
|
|
if (startX < 0 || startY < 0 || endX < 0 || endX < 0 ||
|
|
startX > collisionGrid[0].length - 1 || startY > collisionGrid.length - 1 ||
|
|
endX > collisionGrid[0].length - 1 || endY > collisionGrid.length - 1) {
|
|
throw new Error("Your start or end point is outside the scope of your grid.");
|
|
}
|
|
|
|
// Start and end are the same tile.
|
|
if (startX === endX && startY === endY) {
|
|
callbackWrapper([]);
|
|
return;
|
|
}
|
|
|
|
// End point is not an acceptable tile.
|
|
var endTile = collisionGrid[endY][endX];
|
|
var isAcceptable = false;
|
|
for (var i = 0; i < acceptableTiles.length; i++) {
|
|
if (endTile === acceptableTiles[i]) {
|
|
isAcceptable = true;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (isAcceptable === false) {
|
|
callbackWrapper(null);
|
|
return;
|
|
}
|
|
|
|
// Create the instance
|
|
var instance = new EasyStar.instance();
|
|
instance.openList = new EasyStar.PriorityQueue("bestGuessDistance", EasyStar.PriorityQueue.MIN_HEAP);
|
|
instance.isDoneCalculating = false;
|
|
instance.nodeHash = {};
|
|
instance.startX = startX;
|
|
instance.startY = startY;
|
|
instance.endX = endX;
|
|
instance.endY = endY;
|
|
instance.callback = callbackWrapper;
|
|
|
|
instance.openList.insert(coordinateToNode(instance, instance.startX,
|
|
instance.startY, null, STRAIGHT_COST));
|
|
|
|
instances.push(instance);
|
|
};
|
|
|
|
/**
|
|
* This method steps through the A* Algorithm in an attempt to
|
|
* find your path(s). It will search 4-8 tiles (depending on diagonals) for every calculation.
|
|
* You can change the number of calculations done in a call by using
|
|
* easystar.setIteratonsPerCalculation().
|
|
**/
|
|
this.calculate = function() {
|
|
if (instances.length === 0 || collisionGrid === undefined || acceptableTiles === undefined) {
|
|
return;
|
|
}
|
|
for (iterationsSoFar = 0; iterationsSoFar < iterationsPerCalculation; iterationsSoFar++) {
|
|
if (instances.length === 0) {
|
|
return;
|
|
}
|
|
|
|
if (syncEnabled) {
|
|
// If this is a sync instance, we want to make sure that it calculates synchronously.
|
|
iterationsSoFar = 0;
|
|
}
|
|
|
|
// Couldn't find a path.
|
|
if (instances[0].openList.length === 0) {
|
|
var ic = instances[0];
|
|
ic.callback(null);
|
|
instances.shift();
|
|
continue;
|
|
}
|
|
|
|
var searchNode = instances[0].openList.shiftHighestPriorityElement();
|
|
|
|
var tilesToSearch = [];
|
|
searchNode.list = EasyStar.Node.CLOSED_LIST;
|
|
|
|
if (searchNode.y > 0) {
|
|
tilesToSearch.push({
|
|
instance: instances[0],
|
|
searchNode: searchNode,
|
|
x: 0,
|
|
y: -1,
|
|
cost: STRAIGHT_COST * getTileCost(searchNode.x, searchNode.y - 1)
|
|
});
|
|
}
|
|
if (searchNode.x < collisionGrid[0].length - 1) {
|
|
tilesToSearch.push({
|
|
instance: instances[0],
|
|
searchNode: searchNode,
|
|
x: 1,
|
|
y: 0,
|
|
cost: STRAIGHT_COST * getTileCost(searchNode.x + 1, searchNode.y)
|
|
});
|
|
}
|
|
if (searchNode.y < collisionGrid.length - 1) {
|
|
tilesToSearch.push({
|
|
instance: instances[0],
|
|
searchNode: searchNode,
|
|
x: 0,
|
|
y: 1,
|
|
cost: STRAIGHT_COST * getTileCost(searchNode.x, searchNode.y + 1)
|
|
});
|
|
}
|
|
if (searchNode.x > 0) {
|
|
tilesToSearch.push({
|
|
instance: instances[0],
|
|
searchNode: searchNode,
|
|
x: -1,
|
|
y: 0,
|
|
cost: STRAIGHT_COST * getTileCost(searchNode.x - 1, searchNode.y)
|
|
});
|
|
}
|
|
if (diagonalsEnabled) {
|
|
if (searchNode.x > 0 && searchNode.y > 0) {
|
|
|
|
if (allowCornerCutting ||
|
|
(isTileWalkable(collisionGrid, acceptableTiles, searchNode.x, searchNode.y - 1) &&
|
|
isTileWalkable(collisionGrid, acceptableTiles, searchNode.x - 1, searchNode.y))) {
|
|
|
|
tilesToSearch.push({
|
|
instance: instances[0],
|
|
searchNode: searchNode,
|
|
x: -1,
|
|
y: -1,
|
|
cost: DIAGONAL_COST * getTileCost(searchNode.x - 1, searchNode.y - 1)
|
|
});
|
|
}
|
|
}
|
|
if (searchNode.x < collisionGrid[0].length - 1 && searchNode.y < collisionGrid.length - 1) {
|
|
|
|
if (allowCornerCutting ||
|
|
(isTileWalkable(collisionGrid, acceptableTiles, searchNode.x, searchNode.y + 1) &&
|
|
isTileWalkable(collisionGrid, acceptableTiles, searchNode.x + 1, searchNode.y))) {
|
|
|
|
tilesToSearch.push({
|
|
instance: instances[0],
|
|
searchNode: searchNode,
|
|
x: 1,
|
|
y: 1,
|
|
cost: DIAGONAL_COST * getTileCost(searchNode.x + 1, searchNode.y + 1)
|
|
});
|
|
}
|
|
}
|
|
if (searchNode.x < collisionGrid[0].length - 1 && searchNode.y > 0) {
|
|
|
|
if (allowCornerCutting ||
|
|
(isTileWalkable(collisionGrid, acceptableTiles, searchNode.x, searchNode.y - 1) &&
|
|
isTileWalkable(collisionGrid, acceptableTiles, searchNode.x + 1, searchNode.y))) {
|
|
|
|
|
|
tilesToSearch.push({
|
|
instance: instances[0],
|
|
searchNode: searchNode,
|
|
x: 1,
|
|
y: -1,
|
|
cost: DIAGONAL_COST * getTileCost(searchNode.x + 1, searchNode.y - 1)
|
|
});
|
|
}
|
|
}
|
|
if (searchNode.x > 0 && searchNode.y < collisionGrid.length - 1) {
|
|
|
|
if (allowCornerCutting ||
|
|
(isTileWalkable(collisionGrid, acceptableTiles, searchNode.x, searchNode.y + 1) &&
|
|
isTileWalkable(collisionGrid, acceptableTiles, searchNode.x - 1, searchNode.y))) {
|
|
|
|
|
|
tilesToSearch.push({
|
|
instance: instances[0],
|
|
searchNode: searchNode,
|
|
x: -1,
|
|
y: 1,
|
|
cost: DIAGONAL_COST * getTileCost(searchNode.x - 1, searchNode.y + 1)
|
|
});
|
|
}
|
|
}
|
|
}
|
|
|
|
// First sort all of the potential nodes we could search by their cost + heuristic distance.
|
|
tilesToSearch.sort(function(a, b) {
|
|
var aCost = a.cost + getDistance(searchNode.x + a.x, searchNode.y + a.y, instances[0].endX, instances[0].endY)
|
|
var bCost = b.cost + getDistance(searchNode.x + b.x, searchNode.y + b.y, instances[0].endX, instances[0].endY)
|
|
if (aCost < bCost) {
|
|
return -1;
|
|
} else if (aCost === bCost) {
|
|
return 0;
|
|
} else {
|
|
return 1;
|
|
}
|
|
});
|
|
|
|
var isDoneCalculating = false;
|
|
|
|
// Search all of the surrounding nodes
|
|
for (var i = 0; i < tilesToSearch.length; i++) {
|
|
checkAdjacentNode(tilesToSearch[i].instance, tilesToSearch[i].searchNode,
|
|
tilesToSearch[i].x, tilesToSearch[i].y, tilesToSearch[i].cost);
|
|
if (tilesToSearch[i].instance.isDoneCalculating === true) {
|
|
isDoneCalculating = true;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (isDoneCalculating) {
|
|
instances.shift();
|
|
continue;
|
|
}
|
|
|
|
}
|
|
};
|
|
|
|
// Private methods follow
|
|
var checkAdjacentNode = function(instance, searchNode, x, y, cost) {
|
|
var adjacentCoordinateX = searchNode.x + x;
|
|
var adjacentCoordinateY = searchNode.y + y;
|
|
|
|
if (pointsToAvoid[adjacentCoordinateX + "_" + adjacentCoordinateY] === undefined) {
|
|
// Handles the case where we have found the destination
|
|
if (instance.endX === adjacentCoordinateX && instance.endY === adjacentCoordinateY) {
|
|
instance.isDoneCalculating = true;
|
|
var path = [];
|
|
var pathLen = 0;
|
|
path[pathLen] = {
|
|
x: adjacentCoordinateX,
|
|
y: adjacentCoordinateY
|
|
};
|
|
pathLen++;
|
|
path[pathLen] = {
|
|
x: searchNode.x,
|
|
y: searchNode.y
|
|
};
|
|
pathLen++;
|
|
var parent = searchNode.parent;
|
|
while (parent != null) {
|
|
path[pathLen] = {
|
|
x: parent.x,
|
|
y: parent.y
|
|
};
|
|
pathLen++;
|
|
parent = parent.parent;
|
|
}
|
|
path.reverse();
|
|
var ic = instance;
|
|
var ip = path;
|
|
ic.callback(ip);
|
|
return
|
|
}
|
|
|
|
if (isTileWalkable(collisionGrid, acceptableTiles, adjacentCoordinateX, adjacentCoordinateY)) {
|
|
var node = coordinateToNode(instance, adjacentCoordinateX,
|
|
adjacentCoordinateY, searchNode, cost);
|
|
|
|
if (node.list === undefined) {
|
|
node.list = EasyStar.Node.OPEN_LIST;
|
|
instance.openList.insert(node);
|
|
} else if (node.list === EasyStar.Node.OPEN_LIST) {
|
|
if (searchNode.costSoFar + cost < node.costSoFar) {
|
|
node.costSoFar = searchNode.costSoFar + cost;
|
|
node.parent = searchNode;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
};
|
|
|
|
// Helpers
|
|
var isTileWalkable = function(collisionGrid, acceptableTiles, x, y) {
|
|
for (var i = 0; i < acceptableTiles.length; i++) {
|
|
if (collisionGrid[y][x] === acceptableTiles[i]) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
return false;
|
|
};
|
|
|
|
var getTileCost = function(x, y) {
|
|
return pointsToCost[x + '_' + y] || costMap[collisionGrid[y][x]]
|
|
};
|
|
|
|
var coordinateToNode = function(instance, x, y, parent, cost) {
|
|
if (instance.nodeHash[x + "_" + y] !== undefined) {
|
|
return instance.nodeHash[x + "_" + y];
|
|
}
|
|
var simpleDistanceToTarget = getDistance(x, y, instance.endX, instance.endY);
|
|
if (parent !== null) {
|
|
var costSoFar = parent.costSoFar + cost;
|
|
} else {
|
|
costSoFar = simpleDistanceToTarget;
|
|
}
|
|
var node = new EasyStar.Node(parent, x, y, costSoFar, simpleDistanceToTarget);
|
|
instance.nodeHash[x + "_" + y] = node;
|
|
return node;
|
|
};
|
|
|
|
var getDistance = function(x1, y1, x2, y2) {
|
|
return Math.sqrt((x2 -= x1) * x2 + (y2 -= y1) * y2);
|
|
};
|
|
}
|
|
return EasyStar
|
|
} |