import { manhattanDistance } from './other/helperFunctions';
import MapWithDefaultValue from './other/mapWithDefaultValue';
import { PriorityQueue } from 'libstl'; // note: imported from a node module
/** @module findPath */
/**
* Heavily modified implementation of the A* algorithm
* @param {Object} start object containing numeric attributes `x` and `y` that represent the first endpoint of the wire in grid pixels
* @param {Object} end object containing numeric attributes `x` and `y` that represent the second endpoint of the wire in grid pixels
* @param {Set} nonRoutable set of non routable nodes
* @param {Set} punishedButRoutable set of nodes that are not optimal for routing
* @return {Array} array of objects containing numeric attributes `x` and `y`
*/
export default function findPath(start, end, nonRoutable, punishedButRoutable) {
const distanceFunction = manhattanDistance;
const wireCrossPunishment = 1;
const wireBendPunishment = 1;
// number of nodes, that can be opened at once
// once is this limit exceeded, aStar will fail and return undefined
const maxNodeLimit = 100000;
let closedNodes = new Set();
let openNodes = new Set();
let openNodeQueue = new PriorityQueue();
// functions for working with open nodes:
/**
* add a new open node to the structure
* @param {Object} node object containing numeric attributes `x` and `y` that represent the first endpoint of the wire
* @param {number} fscore fScore of this node
*/
const addOpenNode = (node, fscore) => {
openNodes.add(node);
// flip the fscore, because PriorityQueue uses max heap
openNodeQueue.enqueue(node, 1 / fscore);
};
/**
* get the open node with the lowest fScore and remove it
* @return {Object} object containing numeric attributes `x` and `y` that represent the first endpoint of the wire
*/
const getOpenNode = () => {
const node = openNodeQueue.dequeue();
openNodes.delete(node);
return node;
};
let cameFrom = new Map();
// default value: infinity
let gScore = new MapWithDefaultValue(Infinity);
gScore.set(start, 0);
let startFScore = distanceFunction(start, end);
addOpenNode(start, startFScore);
openNodes.add(start);
openNodeQueue.enqueue(start, 1 / startFScore);
while (openNodes.size > 0) {
// get the value from openNodes that has the lowest fScore
const currentNode = getOpenNode();
// if we reached the end point, reconstruct the path and return it
if (currentNode.x == end.x && currentNode.y == end.y) {
return reconstructPath(cameFrom, currentNode);
}
// add this node to the closed nodes
closedNodes.add(currentNode);
// the farthest points accessible without avoiding obstacles in every direction
// (but max 50 in each direction)
for (let direction = 0; direction < 4; direction++) {
let newPoint = movePoint(currentNode, direction);
let wiresCrossed = 0;
for (let i = 0; i < 50; i++) {
// if newPoint is in the set of non routable points,
// don't add it and stop proceeding in this direction
if (setHasThisPoint(nonRoutable, newPoint)) {
// if this not the end or start point, break
if (
!(newPoint.x === end.x && newPoint.y === end.y) &&
!(newPoint.x === start.x && newPoint.y === start.y)
) {
break;
}
}
// skip this node, if it has been already closed
// or if it is on the list of non routable nodes
if (closedNodes.has(newPoint)) {
continue;
}
// calculate possible GScore by applying a punishment for each node ("bend") in the path
let newGScore = wireBendPunishment + gScore.getWithDefault(currentNode);
if (setHasThisPoint(punishedButRoutable, newPoint)) {
// if the node is in the set of punished nodes, apply the punishment
wiresCrossed++;
}
// apply the punishment for each wire crossed in this direction
// note: we are counting the wires crossed when exporting this direction, not the wires
// crossed in the final path, there will be probably only at most of these nodes in the
// final path, not multiple
newGScore += wiresCrossed * wireCrossPunishment;
// skip this node if it has worst estimage gscore than in the gscore table
if (newGScore >= gScore.getWithDefault(newPoint)) {
continue;
}
cameFrom.set(newPoint, currentNode);
gScore.set(newPoint, newGScore);
const newFScore = newGScore + distanceFunction(newPoint, end);
if (!openNodes.has(newPoint)) {
// add the point to the list of points
addOpenNode(newPoint, newFScore);
}
// move to the next point in the direciton
newPoint = movePoint(newPoint, direction);
}
}
if (openNodes.size > maxNodeLimit) {
console.log(
`aStar: Number of open nodes (${
openNodes.size
}) exceeded the limit for open nodes (${maxNodeLimit}).`
);
break;
}
}
// if we got here, the path was not found
return undefined;
}
/**
* returns `true` if the specified set of points contains the specified point (and returns `false` otherwise)
* @param {Set} set set of points
* @param {Object} point object containing numeric attributes `x` and `y`
*/
function setHasThisPoint(set, point) {
for (let item of set) {
if (item.x === point.x && item.y === point.y) {
return true;
}
}
return false;
}
/**
* Helper that moves the passed point in the specified direction. It simply adds or subtracts 1 from one of the coordinates depending on the direction attribute.
* @param {Object} point object containing numeric attributes `x` and `y`
* @param {number} direction directions:
* - 0: up
* - 1: right
* - 2: down
* - 3: left
* @return {Object} object containing numeric attributes `x` and `y`
*/
function movePoint({ x, y }, direction) {
// map direction do point coordinate modification
const dirMap = {
0: () => {
y -= 1;
},
1: () => {
x += 1;
},
2: () => {
y += 1;
},
3: () => {
x -= 1;
}
};
dirMap[direction]();
return { x, y };
}
/**
* helper backtracking function used by the aStar algorithm to construct the final path
* @param {Object} cameFrom object containing numeric attributes `x` and `y`
* @param {Object} currentNode object containing numeric attributes `x` and `y`
* @return {Array} array of objects containing numeric attributes `x` and `y`
*/
function reconstructPath(cameFrom, currentNode) {
let path = [];
path.push({
x: currentNode.x,
y: currentNode.y
});
while (cameFrom.has(currentNode)) {
currentNode = cameFrom.get(currentNode);
path.push({
x: currentNode.x,
y: currentNode.y
});
}
return path;
}