import BinaryHeap from "./BinaryHeap.js";
const SQRT2 = Math.sqrt(2);
const D2 = SQRT2 - 2;
class Graph {
/**
* Creates an instance of Graph.
* @param {Grid} gridIn input grid, each cell has to be a number weight where 0 = wall or pass the getWeight function in the options
* @param {object} [options={}]
*/
constructor(gridIn, options = {}) {
options = Object.assign({
diagonal: false,
getWeight: null
}, options);
this.nodes = [];
this.diagonal = !!options.diagonal;
this.grid = new Grid(gridIn.w, gridIn.h);
gridIn.each((x, y, c) => {
let weight = options.getWeight !== null ? options.getWeight(x, y, c) : c;
var node = new GridNode(x, y, weight);
this.grid.set(x, y, node);
this.nodes.push(node);
});
this.gridIn = gridIn;
this.init();
}
setNode(x, y, weight) {
var node = new GridNode(x, y, weight);
this.grid.set(x, y, node);
this.nodes[this.grid.index(x, y)] = node;
}
init() {
this.dirtyNodes = [];
for (var i = 0; i < this.nodes.length; i++) {
this.cleanNode(this.nodes[i]);
}
}
cleanNode(node) {
node.f = 0;
node.g = 0;
node.h = 0;
node.visited = false;
node.closed = false;
node.parent = null;
}
cleanDirty() {
for (var i = 0; i < this.dirtyNodes.length; i++) {
this.cleanNode(this.dirtyNodes[i]);
}
this.dirtyNodes = [];
}
markDirty(node) {
this.dirtyNodes.push(node);
}
neighbors(node) {
if (this.diagonal) {
return Object.values(this.grid.neighbours(node.x, node.y)).filter(c => c !== null);
} else {
return Object.values(this.grid.directNeighbours(node.x, node.y)).filter(c => c !== null);
}
}
toString() {
var graphString = [];
var grid = this.grid;
for (var x = 0; x < grid.w; x++) {
var rowDebug = [];
for (var y = 0; y < grid.h; y++) {
rowDebug.push(grid.get(x, y).weight);
}
graphString.push(rowDebug.join(" "));
}
return graphString.join("\n");
}
}
class GridNode {
constructor(x, y, weight) {
this.x = x;
this.y = y;
this.weight = weight;
this.f = 0;
this.g = 0;
this.h = 0;
this.visited = false;
this.closed = false;
this.parent = null;
}
toString() {
return "[" + this.x + " " + this.y + "]";
}
getCost(fromNeighbor) {
// Take diagonal weight into consideration.
if (fromNeighbor && fromNeighbor.x != this.x && fromNeighbor.y != this.y) {
return this.weight * SQRT2;
}
return this.weight;
}
isWall() {
return this.weight === 0;
}
}
/**
* Pathfinder that uses a binary heap to prioritize different node weights
*/
class PathfinderHeap {
/**
* @param {Grid} grid input grid, each cell has to be a number weight where 0 = wall or pass the getWeight function in the options
* @param {Boolean} diagonal also allow moving diagonal
*/
constructor(grid, options = {}) {
options = Object.assign({
diagonal: false,
getWeight: null,
caching: false,
onChange: null
}, options);
this.options = options;
this.graph = new Graph(grid, options);
this.cache = new Map();
if (options.onChange) {
grid.on("set", e => {
if (!options.onChange(e)) return;
this.graph.setNode(e.x, e.y, options.getWeight !== null ? options.getWeight(e.x, e.y, e.cell) : e.cell);
if (options.caching) this.cache.clear();
});
}
}
/**
* Calculate a path from start to end
* @param {Vector|Object} start start point
* @param {Vector|Object} end end point
* @returns {Array} Array of points in the form `{x:0, y:0}`
*/
calc(start, end) {
if (start.x === end.x && start.y === end.y) return [];
if (this.options.caching) {
let cached = this.getCached(start, end);
if (cached !== false) return cached;
}
this.graph.cleanDirty();
var heuristic = this.options.diagonal ? this.heuristikDiagonal : this.heuristikManhattan;
var closest = false;
var openHeap = this.getHeap();
start = this.graph.grid.get(start.x, start.y);
end = this.graph.grid.get(end.x, end.y);
var closestNode = start;
start.h = heuristic(start, end);
this.graph.markDirty(start);
openHeap.push(start);
while (openHeap.size() > 0) {
// Grab the lowest f(x) to process next. Heap keeps this sorted for us.
var currentNode = openHeap.pop();
// End case -- result has been found, return the traced path.
if (currentNode === end) {
let result = this.pathTo(currentNode);
if (this.options.caching) this.setCached(start, end, result);
return result;
}
// Normal case -- move currentNode from open to closed, process each of its neighbors.
currentNode.closed = true;
// Find all neighbors for the current node.
var neighbors = this.graph.neighbors(currentNode);
for (var i = 0, il = neighbors.length; i < il; ++i) {
var neighbor = neighbors[i];
if (neighbor.closed || (neighbor.isWall() && neighbor !== end)) {
// Not a valid node to process, skip to next neighbor.
continue;
}
// The g score is the shortest distance from start to current node.
// We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.
var gScore = currentNode.g + neighbor.getCost(currentNode);
var beenVisited = neighbor.visited;
if (!beenVisited || gScore < neighbor.g) {
// Found an optimal (so far) path to this node. Take score for node to see how good it is.
neighbor.visited = true;
neighbor.parent = currentNode;
neighbor.h = neighbor.h || heuristic(neighbor, end);
neighbor.g = gScore;
neighbor.f = neighbor.g + neighbor.h;
this.graph.markDirty(neighbor);
if (closest) {
// If the neighbour is closer than the current closestNode or if it's equally close but has
// a cheaper path than the current closest node then it becomes the closest node
if (neighbor.h < closestNode.h || (neighbor.h === closestNode.h && neighbor.g < closestNode.g)) {
closestNode = neighbor;
}
}
if (!beenVisited) {
// Pushing to heap will put it in proper place based on the 'f' value.
openHeap.push(neighbor);
} else {
// Already seen the node, but since it has been rescored we need to reorder it in the heap
openHeap.rescoreElement(neighbor);
}
}
}
}
if (closest) {
let result = this.pathTo(closestNode);
if (this.options.caching) this.setCached(start, end, result);
return result;
}
// No result was found - empty array signifies failure to find path.
if (this.options.caching) this.setCached(start, end, null);
return null;
}
getHeap() {
return new BinaryHeap(function(node) {
return node.f;
});
}
pathTo(node) {
var curr = node;
var path = [];
while (curr.parent) {
if (!curr.isWall()) {
path.unshift({
x: curr.x,
y: curr.y
});
}
curr = curr.parent;
}
path.unshift({
x: curr.x,
y: curr.y
});
return path;
}
heuristikManhattan(pos0, pos1) {
var d1 = Math.abs(pos1.x - pos0.x);
var d2 = Math.abs(pos1.y - pos0.y);
return d1 + d2;
}
heuristikDiagonal(pos0, pos1) {
var d1 = Math.abs(pos1.x - pos0.x);
var d2 = Math.abs(pos1.y - pos0.y);
return (d1 + d2) + (D2 * Math.min(d1, d2));
}
clonePath(p, reversed) {
if (!Array.isArray(p)) return p;
let ret = [];
for (let i = 0; i < p.length; i++) {
let index = reversed ? p.length - 1 - i : i;
ret.push({
x: p[index].x,
y: p[index].y
});
}
return ret;
}
getCached(start, end) {
let cachekey = [start.x, start.y, end.x, end.y].join(";");
let cachekey2 = [end.x, end.y, start.x, start.y].join(";");
if (this.cache.has(cachekey)) return this.clonePath(this.cache.get(cachekey));
if (this.cache.has(cachekey2)) return this.clonePath(this.cache.get(cachekey2));
return false;
}
setCached(start, end, path) {
let cachekey = [start.x, start.y, end.x, end.y].join(";");
let cachekey2 = [end.x, end.y, start.x, start.y].join(";");
this.cache.set(cachekey, this.clonePath(path));
this.cache.set(cachekey2, this.clonePath(path, true));
}
}
export default Graph