Understanding the A* Search Algorithm: Principles, Heuristics, and JavaScript Implementation

Preface: The article, originally authored by front‑end engineer Wei Chuan‑kai from Qiwu Team, introduces the A* search algorithm.

Principle: A* combines best‑first search and Dijkstra's algorithm, using the evaluation function f(n)=g(n)+h(n) where g(n) is the cost from the start node and h(n) is a heuristic estimate to the goal. The algorithm maintains an open set (priority queue) and a closed set, repeatedly expanding the node with the lowest f(n) until the goal is reached.

Implementation: The main JavaScript implementation is provided below.

function aStar(start, goal, heuristicFunction) {
  // open set as priority queue
  const openSet = new PriorityQueue();
  openSet.add(start);
  const closeSet = [];
  const gScore = { [start]: 0 };
  const hScore = { [start]: heuristicFunction(start, goal) };
  const fScore = { [start]: hScore[start] };
  const cameFrom = {};

  while (!openSet.isEmpty()) {
    const current = openSet.pollFirst();
    if (current === goal) {
      return reconstructPath(cameFrom, goal);
    }
    closeSet.add(current);
    for (let neighbor of neighborNodes(current)) {
      if (closeSet.includes(neighbor)) continue;
      const tentativeGScore = gScore[current] + distance(neighbor, current);
      if (!openSet.includes(neighbor) || tentativeGScore < gScore[neighbor]) {
        cameFrom[neighbor] = current;
        gScore[neighbor] = tentativeGScore;
        hScore[neighbor] = heuristicFunction(neighbor, goal);
        fScore[neighbor] = gScore[neighbor] + hScore[neighbor];
        openSet.add(neighbor);
      }
    }
  }
}
function reconstructPath(cameFrom, current) {
  const bestPath = [current];
  while (cameFrom[current]) {
    current = cameFrom[current];
    bestPath.unshift(current);
  }
  return bestPath;
}

Heuristic functions: The article discusses how different choices of h(n) affect optimality and speed, ranging from h(n)=0 (equivalent to Dijkstra) to admissible heuristics that never overestimate, to aggressive heuristics that may sacrifice optimality.

2‑D grid heuristics: For grid maps, Manhattan distance (L1), Chebyshev distance (L∞), and Euclidean distance (L2) are presented with their formulas and assumptions about movement costs.

Relaxation techniques: Static and dynamic weighting of the heuristic are introduced to obtain ε‑suboptimal solutions faster, including formulas for weighted and depth‑dependent heuristics.

References: Links to the Wikipedia page on A* and a Stanford game programming comparison page are listed.