A* Pathfinding Algorithm Explained

The A* algorithm is one of the most powerful pathfinding algorithms used in modern applications. It efficiently finds the shortest path between two points in a graph while minimizing the number of nodes explored.

A* is widely used in video games, robotics, and navigation systems because it combines the strengths of Dijkstra's algorithm with heuristic guidance.

The Core Idea

A* evaluates nodes using a scoring function that estimates the total cost of reaching the goal.

The function is defined as:

f(n) = g(n) + h(n)

• g(n): cost from start node to node n
• h(n): heuristic estimate from n to the goal
• f(n): estimated total cost of the path

Why Heuristics Matter

The heuristic guides the search toward the goal. A good heuristic dramatically reduces the number of nodes explored.

For example, in grid maps the Manhattan distance is often used as a heuristic.

How A* Works

1. Add the start node to the open set
2. Select the node with the lowest f(n)
3. Move it to the closed set
4. Update neighbor costs
5. Repeat until the goal is reached

JavaScript Implementation

function heuristic(a, b) {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

function aStar(start, goal, neighbors) {
  const open = [start];
  const cameFrom = new Map();

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

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

  while (open.length > 0) {
    open.sort((a, b) => fScore.get(a) - fScore.get(b));
    const current = open.shift();

    if (current === goal) return cameFrom;

    for (const neighbor of neighbors(current)) {
      const tentative = gScore.get(current) + 1;

      if (!gScore.has(neighbor) || tentative < gScore.get(neighbor)) {
        cameFrom.set(neighbor, current);
        gScore.set(neighbor, tentative);
        fScore.set(neighbor, tentative + heuristic(neighbor, goal));

        if (!open.includes(neighbor)) {
          open.push(neighbor);
        }
      }
    }
  }
}

Applications

• Video game AI pathfinding
• Robot navigation
• Route planning
• Map navigation systems

Conclusion

The A* algorithm is widely considered the gold standard for pathfinding. Its ability to combine actual path cost with heuristic guidance allows it to find optimal paths efficiently.