// Heuristics for AStar
// Manhattan distance heuristic calculates the distance between two points in a
// grid based on the sum of the absolute differences of their Cartesian
// coordinates multiplied by 10 to maintain consistency with the g cost of
// adjacent nodes.
function getManhattanDistance(key0, key1) {
return 10 * (Math.abs(key1[0] - key0[0]) + Math.abs(key1[1] - key0[1]));
}
// Diagonal distance heuristic calculates the distance between two points in a
// grid based on the maximum of the absolute differences of their Cartesian
// coordinates, multiplied by 10 to maintain consistency with the g cost of
// adjacent nodes.
function getDiagonalDistance(key0, key1) {
return 10 * Math.max(Math.abs(key1[0] - key0[0]), Math.abs(key1[1] - key0[1]));
}
// Euclidean distance heuristic calculates the straight-line distance between
// two points in a grid using the Pythagorean theorem, multiplied by 10 to
// maintain consistency with the g cost of adjacent nodes.
function getEuclideanDistance(key0, key1) {
let dx = key1[1] - key0[1];
let dy = key1[0] - key0[0];
return Math.round(10 * Math.sqrt(dx * dx + dy * dy));
}
// No distance heuristic returns 0 for any two points, effectively turning the
// A* algorithm into Dijkstra's algorithm, which explores all possible paths
// without using any heuristic guidance.
function getNoDistance(key0, key1) {
return 0;
}
// A* search algorithm implementation without any specific domain code. It
// must be used as a base class for domain-specific implementations.
class AStar {
// The constructor takes a heuristic function that estimates the cost from
// a node to the goal. By default, it uses the getNoDistance heuristic,
// which effectively turns the A* algorithm into Dijkstra's algorithm.
constructor(heuristic = getNoDistance) {
this.heuristic = heuristic; // The heuristic function.
this.domain = undefined; // Domain specific code. Must be set in
// derived class by using a class derived from
// AStar.Domain class.
// Fundamental containers used by run method. Declared as members to use
// outside of run method for debugging and visualization purposes.
this.closedlist = undefined;
this.openlist = undefined;
}
// Node is used to keep track of visited nodes or nodes to be visited during
// search by AStar algorithms. Must be used as a base class for domain-specific
// implementations of the Node.
static Node = class {
// Constructor that initializes the key, g cost, h cost, direction info,
// and parent key.
constructor(key = [], g = 0, h = 0, info = '', parentKey = []) {
this.key = key; // Coordinates of the node.
this.g = g; // Cost from the start node to this node.
this.h = h; // Heuristic cost from this node to the goal.
this.f = g + h; // Total cost.
this.info = info; // Additional info about the node. Used for path
// reconstruction. It stores the direction taken
// to reach this node from its parent.
this.parentKey = parentKey; // Key of the parent node.
// Used for path reconstruction.
}
// Comparison function for priority queue. It compares nodes based on their
// f value. Can be overridden in derived classes to implement different
// comparison logic.
less(another) {
return this.f < another.f;
}
// Update function of the node. Can be overridden in derived classes
// to extend the update or implement different update logic.
update(parentKey, g, h = 0) {
this.g = g;
this.h = h;
this.f = g + h;
this.parentKey = parentKey;
}
// Serialization function that turns a node object into a string.
toString() {
return this.key.join(',') + ' ' + this.g + ' ' + this.h + ' ' + this.f +
(this.info ? ' ' + this.info : '') +
(this.parentKey.length ? ' ' + this.parentKey.join(',') : '');
}
}
// Domain-specific code for AStar algorithm.
static Domain = class {
// Enforced interface method to create and return a new node with
// the given key. This method is intended to be overridden
// in subclasses to create domain-specific node instances.
newNode(key, g = 0, h = 0, info = '', parentKey = []) {
throw new Error("Method 'newNode()' must be implemented.");
}
// Enforced interface method to get adjacent nodes for a given key.
// Method returns an array of Node objects. This method is intended to
// be overridden in subclasses to provide domain-specific logic for
// retrieving adjacent nodes.
getAdjacents(key) {
throw new Error("Method 'getAdjacents()' must be implemented.");
}
}
// The run function implements A* algorithm to find the shortest
// path between the starting node and the target node.
async run(startingKey, targetKey, yieldInterval = 100) {
this.closedlist = undefined;
this.openlist = undefined;
let lastYieldAt = performance.now();
// The main loop of the algorithm continues until the next step is not
// the last.
while (this.next(startingKey, targetKey))
// Yield control based on time interval to prevent freezing the UI
if (performance.now() - lastYieldAt >= yieldInterval) {
await new Promise(resolve => setTimeout(resolve, 0));
lastYieldAt = performance.now();
}
// Once the target node is found or the open list is empty, the path is
// retrieved.
return this.closedlist.getPath(targetKey);
}
// One step of the A* algorithm. It processes the node with the lowest g
// value from the open list and explores its adjacent nodes. This method can
// be used outside run() for visualizing the algorithm's progress step by step.
next(startingKey, targetKey) {
if (this.openlist == undefined) {
this.openlist = new PriorityQueue();
// Add the starting node to the open list to begin the search process.
this.openlist.push(this.domain.newNode(startingKey));
}
if (this.closedlist == undefined) {
this.closedlist = new HashTable();
}
if (this.openlist.empty())
return false; // No more nodes to process, stop processing.
// Get the node with the lowest g value from the open list and set
// it as the current node.
let current = this.openlist.pop();
// If this node is the target node, the search is complete.
if (compareArrays(current.key, targetKey)) {
this.closedlist.add(current);
return false; // Target found, stop processing.
}
// Get the adjacent nodes of the current node and process each one.
let adjacents = this.domain.getAdjacents(current.key);
for (let adjacent of adjacents) {
// Skip adjacent nodes that are already in the closed list.
if (!this.closedlist.find(adjacent.key)) {
// Calculate the new g value for the adjacent node.
let new_g = current.g + adjacent.g;
// Check if the adjacent node is already in the open list
// and pop it if found.
let openlist_found = this.openlist.pop(adjacent.key);
// If the adjacent node is not in the open list, it is added
// with its new g and h values and parent set to the current
// node.
if (!openlist_found) {
adjacent.update(current.key, new_g,
this.heuristic(adjacent.key, targetKey));
this.openlist.push(adjacent);
}
else {
// Reinserted either updated or unchanged.
if (new_g < openlist_found.g)
openlist_found.update(current.key, new_g,
this.heuristic(openlist_found.key, targetKey));
this.openlist.push(openlist_found);
}
}
}
// After processing all adjacent nodes, the current node is added to
// the closed list to mark it as visited and prevent reprocessing.
this.closedlist.add(current);
return true; // Continue processing.
}
getPath(targetKey) {
return this.closedlist.getPath(targetKey);
}
}