What is a-star?

A* (pronounced “A-star”) is a computer algorithm that finds the shortest path between two points on a map or graph. It combines the speed of a greedy search with the accuracy of Dijkstra’s algorithm by using a “cost” estimate to decide which steps to explore next.

Let's break it down

  • Node: a point on the map (like a city or a grid square).
  • Edge: a connection between two nodes (a road or a possible move).
  • g(n): the exact cost it took to reach node n from the start.
  • h(n): a guessed cost from node n to the goal (called a heuristic).
  • f(n) = g(n) + h(n): the total estimated cost; A* always expands the node with the lowest f‑value. The algorithm repeatedly picks the most promising node, updates its neighbors, and stops when it reaches the goal.

Why does it matter?

A* gives you the best possible route quickly, which is crucial for anything that needs real‑time decisions-like video game characters moving intelligently, robots navigating a warehouse, or GPS apps giving you the fastest directions. It balances speed and optimality better than many other path‑finding methods.

Where is it used?

  • Video games (enemy AI, character movement)
  • Navigation apps (Google Maps, Waze)
  • Robotics (autonomous vacuum cleaners, drones)
  • Network routing (finding efficient data paths)
  • Puzzle solvers (e.g., sliding‑tile games)

Good things about it

  • Finds the optimal path if the heuristic is admissible (never overestimates).
  • Usually faster than Dijkstra’s algorithm because it focuses on promising areas.
  • Flexible: you can change the heuristic to suit different environments (grid, road network, 3‑D space).
  • Simple to implement and understand for beginners.

Not-so-good things

  • Requires a good heuristic; a poor guess can make it as slow as brute‑force search.
  • Can consume a lot of memory for large maps because it stores many nodes in the open list.
  • Not ideal for highly dynamic environments where obstacles change constantly; the algorithm may need to restart.
  • Performance degrades on very high‑dimensional spaces (e.g., complex robot motion planning).