A* Algorithm Explained- Pathfinding and Heuristics

What the A* Algorithm Actually Is

The A* algorithm is a pathfinding workhorse. It finds the shortest path from point A to point B faster than most alternatives, and it's used everywhere — video games, robotics, GPS systems, and anywhere else you need to navigate from one point to another through obstacles.

Developed in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at Stanford, A* combines the best parts of Dijkstra's algorithm and Greedy Best-First Search. It doesn't just find a path — it finds the optimal path by using a cost function that guides the search intelligently.

If you're here, you probably already know you need it. Let's get into how it actually works.

The Core Formula: f(n) = g(n) + h(n)

This is the entire algorithm in one equation. Every node in your search space gets scored, and the one with the lowest score gets explored next.

g(n) is the actual cost from your starting point to the current node. It's the distance you've already traveled — no guesses here.

h(n) is the heuristic estimate from the current node to your goal. This is where A* gets its intelligence. A good heuristic makes A* fast. A bad one makes it useless.

f(n) is the total score. A* always picks the node with the lowest f(n) value.

Why This Combination Works

Dijkstra's algorithm uses only g(n) — it explores equally in all directions until it finds the goal. It's guaranteed to find the shortest path, but it's slow.

Greedy Best-First Search uses only h(n) — it rushes toward the goal. It's fast, but it often finds a suboptimal path.

A* uses both. The g(n) component keeps it honest, ensuring you don't sacrifice path quality for speed. The h(n) component gives it direction, so you don't waste time exploring the wrong areas.

Understanding Heuristics

The heuristic is the make-or-break piece of A*. Your choice of heuristic determines whether A* is brilliant or useless.

A heuristic is an estimate. It should be fast to calculate and as accurate as possible. More importantly, it must be admissible — it must never overestimate the true cost to reach the goal.

Common Heuristics for Grid-Based Pathfinding

• Manhattan Distance — Used when movement is restricted to four directions (up, down, left, right). Calculated as |x1 - x2| + |y1 - y2|. Works great for city grid layouts.
• Euclidean Distance — Straight-line distance. Calculated as √((x1-x2)² + (y1-y2)²). Use this when you can move in any direction.
• Diagonal Distance (Chebyshev) — For eight-directional movement on a grid. Accounts for diagonal moves being equal to horizontal/vertical moves.
• Octile Distance — Like diagonal distance but assumes diagonal moves cost √2 times a cardinal move. More accurate for realistic movement costs.

Heuristic Properties

Admissible — Never overestimates. The estimate is always less than or equal to the true cost. An admissible heuristic guarantees A* finds the optimal path.

Consistent (Monotonic) — For every node, the heuristic satisfies h(n) ≤ cost(n, neighbor) + h(neighbor). A consistent heuristic means A* never revisits nodes, making it significantly faster.

A* vs Other Pathfinding Algorithms

Here's how A* stacks up against the alternatives:

A* is the safe choice. It's not always the fastest, but it consistently delivers optimal paths without the memory overhead of Dijkstra's.

How A* Actually Works (Step by Step)

Here's the algorithm in plain terms:

1. Add the starting node to the open set (nodes to evaluate). Set its g(n) to 0.
2. Add the goal node to the closed set (nodes already evaluated).
3. While the open set isn't empty:
   • Find the node in the open set with the lowest f(n) score. Call it the current node.
   • If the current node is the goal, you're done. Reconstruct the path.
   • Move the current node from open to closed.
   • For each neighbor of the current node:
     • If it's in the closed set, skip it.
     If it's not in the open set, add it and calculate its g, h, and f values. Set the current node as its parent.
     • If it's already in the open set, check if this path is better (lower g value). If so, update its values and parent.
4. If the open set is empty and you haven't found the goal, there's no path.

The open and closed sets are usually implemented as priority queues and hash sets respectively. The priority queue finds the minimum f(n) quickly. The hash set checks for existence in O(1) time.

Real-World Applications

• Video games — NPC pathfinding, RTS unit movement, open-world navigation. Games like StarCraft and Age of Empires built their reputations partly on solid A* implementations.
• GPS and navigation — Finding driving routes. A* variants handle road networks with turn costs, traffic, and road types.
• Robotics — Robot navigation in warehouses, autonomous vehicles, drone flight planning.
• Puzzle solving — Eight puzzle, sliding tile puzzles, maze solving. A* with Manhattan distance is a classic AI homework assignment for a reason.
• Network routing — Finding optimal paths in communication networks.

Getting Started: Implementing A*

Here's a basic implementation in Python. This works for a 2D grid with four-directional movement.

import heapq

def astar(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    
    def heuristic(node):
        return abs(node[0] - goal[0]) + abs(node[1] - goal[1])
    
    open_set = [(0 + heuristic(start), 0, start)]
    came_from = {}
    g_score = {start: 0}
    
    while open_set:
        _, current_g, current = heapq.heappop(open_set)
        
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            neighbor = (current[0] + dr, current[1] + dc)
            
            if 0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols:
                if grid[neighbor[0]][neighbor[1]] == 1:  # obstacle
                    continue
                
                tentative_g = current_g + 1
                
                if neighbor not in g_score or tentative_g < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f_score = tentative_g + heuristic(neighbor)
                    heapq.heappush(open_set, (f_score, tentative_g, neighbor))
    
    return None  # No path found

To use this, pass a 2D list where 0 = walkable and 1 = obstacle. Start and goal are (row, col) tuples.

Key Implementation Details

Use a min-heap for the open set. Python's heapq gives you O(log n) insertion and O(log n) extraction of the minimum element.

Track g_scores in a dictionary. This lets you update a node's cost if you find a better path to it later.

Store the parent of each node so you can reconstruct the path once you reach the goal.

Common Mistakes and How to Fix Them

• Wrong heuristic for your movement type — Using Manhattan distance when your character can move diagonally. Use diagonal-aware heuristics instead.
• Heuristic overestimates the cost — This breaks optimality. The path A* finds might not be the shortest.
• Not handling unreachable goals — Always check if the open set is exhausted. Return None or raise an exception.
• Using mutable objects as dictionary keys — Tuples work. Lists don't. Use tuples for positions.
• Forgetting to mark nodes as visited — Without the closed set or g_score tracking, you'll loop forever.

When A* Is the Wrong Choice

A* struggles with certain scenarios:

• Very large search spaces — Memory usage grows with the open set. For massive maps, consider IDA* (iterative deepening) or memory-bounded variants.
• Dynamic environments — If obstacles change while pathfinding, A* needs to restart. Use D* Lite or similar incremental algorithms.
• Multiple agents — Standard A* doesn't handle moving obstacles. Use flow fields or cooperative pathfinding algorithms.
• Continuous spaces — A* works on graphs. For continuous movement, you need to discretize first or use sampling-based planners like RRT.

Optimizations Worth Knowing

Jump Point Search (JPS) skips over obvious intermediate nodes in uniform-cost grids. It's 10-100x faster than A* on large open areas. Use it when you have lots of open space with scattered obstacles.

Hierarchical Pathfinding (HPA*) divides the map into clusters and finds paths between cluster entrances first, then refines within clusters. Useful for large game worlds.

Contraction Hierarchies add shortcuts between frequently-used nodes. The preprocessing takes time, but queries become nearly instant. Standard for road network routing.

For most game development purposes, a clean A* implementation with JPS on top when needed covers 95% of your pathfinding needs.

The Bottom Line

A* is efficient, optimal, and well-understood. It works. The heuristic makes it fast, and the admissibility requirement keeps it correct. Implement it right, choose your heuristic correctly, and you have a pathfinding solution that handles the vast majority of use cases.

Don't overthink it. Get the basics working first. Optimize when you have measurable problems.