📝 What You’ll Learn

• What the A* pathfinding algorithm is
• How it combines Dijkstra’s and Greedy Best-First Search
• How to implement it in JavaScript
• Real-world analogy and use cases
• Heuristic functions and performance best practices

🔍 What Is the A* Algorithm?

A* (pronounced A-star) is a graph traversal and pathfinding algorithm that finds the shortest path from a start node to a goal node.

It combines the cost from the start (known as g) and a heuristic estimate of the cost to the goal (known as h) to form a total score f = g + h.

Unlike Dijkstra’s algorithm, which blindly expands all nearby paths, A* uses heuristics to prioritize nodes that look promising.

🧭 When Should You Use A*?

• When you need the shortest path on a map or grid
• When performance matters and you're not okay with brute-force search
• In real-time games, robotics, routing systems, etc.

📦 Core Concepts

Term	Meaning
g	Cost from start to current node
h	Heuristic estimate to goal
f = g + h	Total estimated cost of path through node
Open Set	Nodes to evaluate (priority queue or array)
Closed Set	Already evaluated nodes

💡 Heuristic: Manhattan Distance

For grid-based movement (no diagonals), the common heuristic is Manhattan distance:

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

This ensures admissibility — meaning it never overestimates — which guarantees optimality.

🧱 JavaScript Implementation (Grid Example)

function aStar(start, end, grid) {
  const openSet = [start];
  const closedSet = new Set();

  start.g = 0;
  start.f = heuristic(start, end);

  while (openSet.length > 0) {
    openSet.sort((a, b) => a.f - b.f);
    const current = openSet.shift();

    if (current === end) {
      return reconstructPath(current);
    }

    closedSet.add(current);

    for (const neighbor of getNeighbors(current, grid)) {
      if (neighbor.wall || closedSet.has(neighbor)) continue;

      const tentativeG = current.g + 1;

      if (!openSet.includes(neighbor) || tentativeG < neighbor.g) {
        neighbor.g = tentativeG;
        neighbor.f = neighbor.g + heuristic(neighbor, end);
        neighbor.previous = current;

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

  return []; // no path found
}

function reconstructPath(node) {
  const path = [];
  while (node) {
    path.unshift(node);
    node = node.previous;
  }
  return path;
}

🚧 Real-World Analogy

Imagine you're navigating a city using a map.

• g is how far you've walked.
• h is a straight-line guess to your destination.
• A* balances both, helping you choose the route that looks fastest and actually is.

⚠️ Common Pitfalls

• ❌ Using an inadmissible heuristic (overestimates cost) — breaks optimality
• ❌ Forgetting to update a node’s g when a better path is found
• ❌ Not using a priority queue — sorting openSet each loop is inefficient

✅ Best Practices

• Use a min-heap or binary heap for the openSet for large grids
• Always ensure the heuristic is admissible and consistent
• Visualize openSet/closedSet/path when debugging
• For weighted grids, adjust g accordingly

🎯 Use Cases

• Game AI (NPC pathfinding)
• Robot motion planning
• Map-based navigation (e.g. GPS)
• Puzzle solving (e.g. 8-puzzle)

📘 Recap

• A* finds the shortest path using f = g + h
• It combines Dijkstra’s algorithm with a heuristic
• It's efficient and optimal (with the right heuristic)
• Ideal for grid navigation, games, and intelligent agents