a* star algorithm in javascript

Here is the code for A* Algorithm in JavaScript:

index.tsx
function astar(start, goal, graph) {
  const heuristic = (a, b) => {
    const dx = a.x - b.x;
    const dy = a.y - b.y;
    return Math.sqrt(dx * dx + dy * dy);
  };

  const closedSet = new Set();
  const openSet = new Set([start]);
  const cameFrom = new Map();

  const gScore = new Map();
  gScore.set(start, 0);

  const fScore = new Map();
  fScore.set(start, heuristic(start, goal));

  while (openSet.size > 0) {
    const current = [...openSet].reduce((a, b) => fScore.get(a) < fScore.get(b) ? a : b);
    if (current === goal) {
      const path = [current];
      while (cameFrom.has(current)) {
        path.push(cameFrom.get(current));
        current = cameFrom.get(current);
      }
      return path;
    }

    openSet.delete(current);
    closedSet.add(current);

    for (const neighbor of graph.get(current)) {
      if (closedSet.has(neighbor)) continue;

      const tentativeGScore = gScore.get(current) + heuristic(current, neighbor);
      if (!openSet.has(neighbor)) openSet.add(neighbor);
      else if (tentativeGScore >= gScore.get(neighbor)) continue;

      cameFrom.set(neighbor, current);
      gScore.set(neighbor, tentativeGScore);
      fScore.set(neighbor, tentativeGScore + heuristic(neighbor, goal));
    }
  }

  return null;
}
1269 chars
47 lines

To use this algorithm, you need to provide the start and goal nodes, and a graph which is represented by a Map where the keys are nodes and the values are arrays of neighboring nodes.

For example:

index.tsx
const graph = new Map();
graph.set("A", ["B"]);
graph.set("B", ["A", "C", "D"]);
graph.set("C", ["B", "E"]);
graph.set("D", ["B", "E"]);
graph.set("E", ["C", "D"]);

console.log(astar("A", "E", graph)); // Output: ["A", "B", "C", "E"]
235 chars
9 lines

In this example, the graph looks like this:

index.tsx
 A -- B -- C
      |
      D -- E
34 chars
4 lines

And the shortest path from A to E is A -> B -> C -> E.

gistlibby LogSnag