I just implemented a version of A* search in JavaScript for educational purposes. I'd really love it if you could take a look and tell me how to improve my code.
The grid passed in is just a multidimensional array (2-D array) where each slot in the inner array is an object with property weight.
The point of this function is to build an "algorithm visualizer", where I have all the nodes that were visited by A* (visited) and all the nodes that A* eventually selected to be part of the shortest path (path). I later take this and display this to the user with my UI logic.
In terms of the heuristic, I use Euclidean Distance.
import PriorityQueue from "./data structures/priorityqueue";
export default function astar(grid, startNode, endNode) {
function isValid(r, c) {
if (r < 0 || c < 0) {
return false;
}
if (r < grid.length && c < grid[r].length) {
return true;
}
return false;
}
function calculateHeuristic(r, c) {
let row = (endNode[0] - r) ** 2;
let col = (endNode[1] - c) ** 2;
return (row + col) ** (1 / 2);
}
let dist = [], // represents distances from start to node
visited = [], // list of all the nodes A* visits
ordering = []; // final ordering
for (let r = 0; r < grid.length; r++) {
let row = [],
orderingRow = [];
for (let c = 0; c < grid[r].length; c++) {
row.push(Number.MAX_VALUE);
orderingRow.push(null);
}
dist.push(row);
ordering.push(orderingRow);
}
let d = 0;
let pqueue = new PriorityQueue();
let priority = calculateHeuristic(startNode[0], startNode[0]) + d;
pqueue.enqueue([startNode[0], startNode[1], startNode, d], priority);
let cur,
neighbors = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1]
];
while (!pqueue.isEmpty()) {
cur = pqueue.dequeue();
let r = cur.element[0],
c = cur.element[1],
origin = cur.element[2],
d = cur.element[3];
visited.push([r, c]);
if (dist[r][c] <= d) {
continue;
}
ordering[r][c] = origin;
dist[r][c] = d;
if (r === endNode[0] && c === endNode[1]) {
break;
}
for (let n of neighbors) {
let rr = r + n[0];
let cc = c + n[1];
if (!isValid(rr, cc)) {
continue;
}
let dd = d + grid[rr][cc].weight;
if (dd < dist[rr][cc]) {
priority = dd + calculateHeuristic(rr, cc);
pqueue.enqueue([rr, cc, [r, c], dd], priority);
}
}
}
let path = [endNode];
let r = endNode[0],
c = endNode[1];
while (r !== startNode[0] || c !== startNode[1]) {
path.push(ordering[r][c]);
[r, c] = ordering[r][c];
}
path.reverse();
return { visited, path };
}
Thank you for reading and I look forward to your critiques.