/**
*
* This file encodes the A* search algorithm
* optimised for the "Complex World" problem.
* Practical n.1
* Author: Stefano Marzo
* Created: 25/10/2021
* Ported on AB: 28/10/2021
*
*/
/**
*
* the Stack mantains the elements ordered by their cost.
* it allows to get the minimum cost Node in O(1) time complexity
* it adds new node in order in O(log_2(n)) time complexity
*
*/
class Stack{
constructor(){
this.stack = [];
}
/**
*
* @param{*} el the element to add to the list
*
* Adds new node in order with respect to the node cost.
* Time complexity is O(log_2(n)).
*
*/
add(el) {
this.stack.splice(this.sortedIndex(this.stack, el.cost), 0, el);
}
/**
*
* @returns one of the nodes with minimum cost
*
*/
getNext() {
return this.stack.shift();
}
/**
*
* @param {*} list array to look into
* @param {*} val new element to insert e.g. node cost
*
* @returns the index in which to insert the new item,
* leaving the list sorted.
*
*/
sortedIndex(list, val) {
let lower = 0;
let higher = list.length;
let middle = 0;
while (lower < higher) {
middle = (lower + higher) >>> 1; //bit shifting (like (lower+higher)/2)
if (list[middle].cost < val) lower = middle + 1;
else higher = middle;
}
return lower;
}
}
/**
*
* HashTable of the states reached,
* it takes track of all the position (i,j) covered during the search.
*
*/
class StateTable{
constructor(){
this.states = [];
}
}
/**
*
* Structure to support the node in the graph search
* in this case, instead of saving the entire state in
* the node, it is sufficient to save only a sub-state
* indicating the coordinates, what is in the direction:
* top, bottom, left, right
*
*/
class Node{
constructor(parent, cost, depth, posI, posJ){
this.parent = parent;
this.cost = cost; //depth + manhattan distance
this.depth = depth;
this.posI = posI;
this.posJ = posJ;
this.whatsUP = GRID[posI-1][posJ];
this.whatsDOWN = GRID[posI+1][posJ];
this.whatsLEFT = GRID[posI][posJ-1];
this.whatsRIGHT = GRID[posI][posJ+1];
}
}
/**
*
* The A* search is supported by the class AStar
* the main method to use is .search() that returns
* the last node (goal).
* From the goal, it is possible to abtain the path
* as a array of coordinates with the method
* .getPath(lastNode).
*
*/
class AStar{
constructor(iStart, jStart, iEnd, jEnd, heuristic = function() {
return Math.abs(this.iEnd - this.iStart) + Math.abs(this.jEnd - this.jStart);
}){
this.stack = new Stack();
this.stateTable = new StateTable();
this.nodeCreated = 0;
this.iterationsCount = 0;
this.createNode(null, iStart, jStart);
this.iStart = iStart;
this.jStart = jStart;
this.iEnd = iEnd;
this.jEnd = jEnd;
this.distance = heuristic;
}
/**
*
* @param {*} parent the parent node to be linked
* @param {*} posI the i coordinate of the node
* @param {*} posJ the j coordinate of the node
*
* Creates a new node based on position and parent
* the new node is added to the Stack IIF it is
* the first time that we visit that state.
* This feature is implemented by using an hash table.
* In this manner, by allocating at most an amount of
* memory proportional to the number of grid cells,
* it is guaranteed that one state is not visited and
* so expanded more than once.
* Moreover the cost and depth are calculated and
* new nodes are added to the Stack
*
*/
createNode(parent, posI, posJ) {
if(typeof this.stateTable.states[posI+''+posJ] === 'undefined') {
let cost = 0;
let depth = 0;
if(parent != null) {
cost = parent.depth + this.distance();
depth = parent.depth + 1;
}
let node = new Node(parent, cost, depth, posI, posJ);
this.stack.add(node);
this.stateTable.states[posI+''+posJ] = false;
this.nodeCreated += 1;
}
}
/**
*
* a while loop that expands the best node until the solution
* is found. if no solution is possible then returns null
*
* @returns the last node expanded containing the solution
* or null
*
*/
search() {
let next = this.stack.getNext();
while(!this.isGoal(next)) {
this.expand(next);
next = this.stack.getNext();
if(next === undefined) return null;
}
return next;
}
/**
*
* @param {*} node the last node of the path
*
* @returns a list containg the {i,j} coordinates
* leading from the start point to the end point
* towards the best possible path.
*
*/
getPath(node) {
if (node === null) return null; // if no solution return null
let path = [];
while(node.parent != null) {
path.unshift({i: node.posI, j: node.posJ}); //unshift push array element
node = node.parent;
}
return path;
}
/**
*
* @param {*} node the next node to expand
*
* analyse the parameter node and call .getPossibleNodes(node)
* to generate the new node neighbours.
* For each neighbour a node is created
*
*/
expand(node) {
if(typeof this.stateTable.states[node.posI+''+node.posJ] !== 'undefined') {
let nextPossibleNodes = this.getPossibleNodes(node);
for(let next of nextPossibleNodes) {
this.createNode(node, next.posI, next.posJ);
}
}
}
/**
*
* @param {*} node the node to be analysed
*
* uses the information stored in the node to create a map
* of coordinates that are used to expand the node
*
*/
getPossibleNodes(node) {
let nextPossibleNodes = [];
if(node.whatsUP == GRID_BLANK || node.whatsUP == GRID_ATTACK_AREA){
nextPossibleNodes.push({posI: node.posI-1, posJ: node.posJ});
}
if(node.whatsDOWN == GRID_BLANK || node.whatsDOWN == GRID_ATTACK_AREA){
nextPossibleNodes.push({posI: node.posI+1, posJ: node.posJ});
}
if(node.whatsLEFT == GRID_BLANK || node.whatsLEFT == GRID_ATTACK_AREA){
nextPossibleNodes.push({posI: node.posI, posJ: node.posJ-1});
}
if(node.whatsRIGHT == GRID_BLANK || node.whatsRIGHT == GRID_ATTACK_AREA){
nextPossibleNodes.push({posI: node.posI, posJ: node.posJ+1});
}
return nextPossibleNodes;
}
/**
*
* @param {*} node the node to be assesed
*
* @returns if the node coordinates are equals to the goal coordinates
*
*/
isGoal(node) {
return node.posI == this.iEnd && node.posJ == this.jEnd;
}
/**
* @returns the average number of branches expanded
*/
getAverageExpansion() {
return this.nodeCreated/this.iterationsCount;
}
}