🚀 Supercharge your YouTube channel's growth with AI.
Try YTGrowAI FreeA* Algorithm – Introduction to The Algorithm (With Python Implementation)
In this article, let me walk you through the A* Algorithm – one of the most widely used pathfinding algorithms in computer science. I first encountered it while building a game AI, and I keep coming back to it because it solves such a broad range of problems so cleanly. At its core, A* finds the shortest path from a start node to a goal node, making it indispensable for game development, robotics, and GPS navigation.
What makes A* stand out is its use of a heuristic – a mental shortcut that estimates how far each node is from the goal. This lets it prioritize promising paths without exhaustively exploring every possibility. If you’ve used Dijkstra’s algorithm before, A* is like Dijkstra with a GPS – it still guarantees the optimal path but gets there faster by cheating intelligently.
TLDR
- A* uses f(N) = g(N) + h(N) to evaluate nodes – g is the actual cost from start, h is the estimated cost to the goal
- h must be admissible (never overestimate) for A* to guarantee the optimal path
- The algorithm maintains an open set (candidates) and closed set (explored nodes), expanding the lowest f-score node each iteration
- Common heuristics: Manhattan distance for grids, Euclidean distance for continuous spaces
- Applications: game pathfinding (NPCs, RTS units), GPS routing, robot navigation, puzzle solving (8-puzzle, 15-puzzle)
What is the A* Algorithm?
A* (pronounced “A-star”) was first published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at Stanford. It extends the ideas of Dijkstra’s shortest path algorithm by adding a heuristic that guides the search toward the goal. The result is an algorithm that is both complete (will find a path if one exists) and optimal (will find the shortest path) when the heuristic is admissible.
The algorithm evaluates each node using a cost function:
f(N) = g(N) + h(N)
Here, g(N) is the actual cost of the path from the start node to N – this is the sum of all edge costs along the path discovered so far. The h(N) is a heuristic estimate of the minimum cost from N to the goal. This is where domain-specific knowledge enters the algorithm.
A* expands nodes in order of increasing f(N). The open set is a priority queue sorted by f-score. Each iteration, it removes the node with the lowest f-score, adds its neighbors to the open set if they haven’t been visited or found via a cheaper path, and continues until the goal is removed from the open set.
The algorithm maintains two sets: an open set of candidate nodes and a closed set of already-explored nodes. For each neighbor of a node being expanded, A* checks whether a shorter path has been found. If so, it updates that neighbor’s g-score and parent pointer.
A* vs Other Search Algorithms
Understanding what makes A* different requires comparing it to the algorithms it builds on.
Dijkstra’s Algorithm explores nodes in order of increasing g(N) – it finds the shortest path but considers all directions equally. This is thorough but slow for large graphs.
Greedy Best-First Search explores nodes in order of increasing h(N) – it races toward the goal but ignores path cost, so it can find long, winding routes that technically reach the goal faster.
A* sits between them. By combining g(N) and h(N), it balances exploration cost against proximity to the goal. When h(N) = 0 for all nodes, A* becomes Dijkstra. When g(N) = 0 for all nodes, A* becomes Greedy Best-First. The art of using A* is choosing a heuristic that guides the search without overestimating.
Implementing A* in Python
Let me show you a clean, readable A* implementation. I’ll use a grid-based example because it’s intuitive to visualize, but the same structure works for any graph.
A* pathfinding on a 5×5 grid with obstacles. The agent moves up, down, left, or right (no diagonals). Movement cost is 1 per step. The heuristic is Manhattan distance – the minimum number of steps required ignoring obstacles.
import heapq
class Node:
def __init__(self, pos, parent=None):
self.pos = pos
self.parent = parent
self.g = 0 # cost from start
self.h = 0 # heuristic cost to goal
self.f = 0 # total: g + h
def __lt__(self, other):
return self.f < other.f
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def astar(grid, start, goal):
open_set = []
start_node = Node(start)
goal_node = Node(goal)
heapq.heappush(open_set, start_node)
while open_set:
current = heapq.heappop(open_set)
if current.pos == goal_node.pos:
path = []
while current:
path.append(current.pos)
current = current.parent
return path[::-1]
closed = set()
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = current.pos[0] + dx, current.pos[1] + dy
if not (0 <= nx < len(grid) and 0 <= ny < len(grid[0]):
continue
if grid[nx][ny] == 1: # obstacle
continue
neighbor_pos = (nx, ny)
if neighbor_pos in closed:
continue
neighbor = Node(neighbor_pos, current)
neighbor.g = current.g + 1
neighbor.h = manhattan(neighbor.pos, goal_node.pos)
neighbor.f = neighbor.g + neighbor.h
heapq.heappush(open_set, neighbor)
closed.add(neighbor_pos)
return None
# 0 = walkable, 1 = obstacle
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 0],
]
start = (0, 0)
goal = (4, 4)
path = astar(grid, start, goal)
print("Path:", path)
print("Steps:", len(path) - 1 if path else "No path")
The algorithm uses a min-heap (priority queue) ordered by f-score. Each node stores its position, parent pointer (for path reconstruction), g-cost, h-cost, and f-cost. The main loop pops the node with the lowest f-score, checks if it’s the goal, then generates valid neighbors (within bounds, not obstacles). If a neighbor hasn’t been visited, it gets added to the heap. When the goal is popped, the parent chain reconstructs the path.
Path: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]
Steps: 8
Solving the 8-Puzzle with A*
The 8-puzzle is a classic AI exercise – a 3×3 grid with 8 numbered tiles and one empty space. You can slide tiles into the empty space. The goal is to arrange them in order. Let me implement an A* solver for this using the misplaced tiles heuristic.
A* solver for the 8-puzzle using the misplaced tiles heuristic. The heuristic counts how many tiles are not in their goal position, providing an admissible estimate of the remaining cost.
from copy import deepcopy
import numpy as np
import time
def bestsolution(state):
bestsol = np.array([], int).reshape(-1, 9)
count = len(state) - 1
while count != -1:
bestsol = np.insert(bestsol, 0, state[count]["puzzle"], 0)
count = state[count]["parent"]
return bestsol.reshape(-1, 3, 3)
def misplaced_tiles(puzzle, goal):
mscost = np.sum(puzzle != goal) - 1
return mscost if mscost > 0 else 0
def coordinates(puzzle):
pos = np.array(range(9))
for p, q in enumerate(puzzle):
pos[q] = p
return pos
def evaluvate_misplaced(puzzle, goal):
steps = np.array(
[("up", [0, 1, 2], -3), ("down", [6, 7, 8], 3),
("left", [0, 3, 6], -1), ("right", [2, 5, 8], 1)],
dtype=[("move", str, 1), ("position", list), ("head", int)],
)
dtstate = [("puzzle", list), ("parent", int), ("gn", int), ("hn", int)]
costg = coordinates(goal)
parent = -1
gn = 0
hn = misplaced_tiles(coordinates(puzzle), costg)
state = np.array([(puzzle, parent, gn, hn)], dtstate)
dtpriority = [("position", int), ("fn", int)]
priority = np.array([(0, hn)], dtpriority)
while True:
priority = np.sort(priority, kind="mergesort", order=["fn", "position"])
position, fn = priority[0]
priority = np.delete(priority, 0, 0)
puzzle, parent, gn, hn = state[position]
puzzle = np.array(puzzle)
blank = int(np.where(puzzle == 0)[0])
gn = gn + 1
start_time = time.time()
for s in steps:
if blank not in s["position"]:
openstates = deepcopy(puzzle)
openstates[blank], openstates[blank + s["head"]] = \
openstates[blank + s["head"]], openstates[blank]
if not (np.all(list(state["puzzle"]) == openstates, 1)).any():
end_time = time.time()
if (end_time - start_time) > 2:
print("The 8 puzzle is unsolvable")
break
hn = misplaced_tiles(coordinates(openstates), costg)
q = np.array([(openstates, position, gn, hn)], dtstate)
state = np.append(state, q, 0)
fn = gn + hn
q = np.array([(len(state) - 1, fn)], dtpriority)
priority = np.append(priority, q, 0)
if np.array_equal(openstates, goal):
print("The 8 puzzle is solvable")
return state, len(priority)
return state, len(priority)
# Initial state: 2 8 3 / 1 6 4 / 7 0 5
puzzle = [2, 8, 3, 1, 6, 4, 7, 0, 5]
# Goal state: 1 2 3 / 8 0 4 / 7 6 5
goal = [1, 2, 3, 8, 0, 4, 7, 6, 5]
state, visited = evaluvate_misplaced(puzzle, goal)
bestpath = bestsolution(state)
for row in bestpath:
print(" ".join(str(t) for t in row))
totalmoves = len(bestpath) - 1
print(f"Steps to reach goal: {totalmoves}")
print(f"Total nodes visited: {len(state) - visited}")
The implementation uses structured NumPy arrays to store state efficiently. The misplaced_tiles function calculates the heuristic by counting tiles not in their final position. The main loop extracts the lowest f-score node from the priority queue, generates all valid moves (up/down/left/right by swapping the blank tile), and adds new states to the queue if they haven’t been seen before. The parent pointers allow path reconstruction once the goal is reached.
The 8 puzzle is solvable
2 8 3
1 6 4
7 0 5
2 8 3
1 0 4
7 6 5
2 0 3
1 8 4
7 6 5
0 2 3
1 8 4
7 6 5
1 2 3
0 8 4
7 6 5
1 2 3
8 0 4
7 6 5
Steps to reach goal: 5
Total nodes visited: 6
When to Use A*
A* is the right choice when you have a graph or grid, you know the cost of moving between nodes, you can estimate the remaining cost to the goal, and you need the shortest path.
Game development is the most common use case. Real-time strategy games use A* for unit pathfinding. Tower defense games use it to place towers within range of enemy paths. Even simple games like Pac-Man use variants of A* for ghost movement.
GPS and navigation systems rely on A* for route planning. The road network is the graph, edge costs are travel times, and the heuristic is distance-as-the-crow-flies. Traffic-aware variants adjust edge costs in real time.
Robotics and motion planning use A* in configuration space – the robot’s possible positions become graph nodes, with edges representing valid movements. This lets robots plan collision-free paths through complex environments.
A* is overkill when the search space is very small (just use BFS), when no admissible heuristic exists, or when any path is acceptable (use greedy best-first).
FAQ
Q: What happens if h(N) overestimates the true cost?
If the heuristic overestimates, A* may find a suboptimal path. The algorithm no longer guarantees optimality. Heuristics that overestimate are called inadmissible, and they make A* behave more like greedy best-first search.
Q: Can A* handle moving obstacles?
The standard A* algorithm assumes a static graph. For moving obstacles, there are extensions like D* (Dynamic A*) that replan efficiently when the environment changes. Temporal constraints add significant complexity to pathfinding.
Q: Is A* faster than Dijkstra?
Yes, when a good heuristic is available. A* expands fewer nodes than Dijkstra because the heuristic guides the search. The improvement depends on the quality of the heuristic – a tight lower bound like Manhattan distance on a grid produces much faster search than a loose bound.
Q: What is the memory complexity of A*?
A* stores all visited nodes in the closed set and all frontier nodes in the open set. In the worst case, this is O(|V|) where V is the number of nodes in the graph. For large search spaces, this can be significant – IDA* (iterative deepening A*) uses less memory by trading speed for space.
Summary
The A* Algorithm is a cornerstone of pathfinding in computer science. Its combination of actual path cost and heuristic estimate gives it the best of both worlds – the guarantee of Dijkstra’s optimality with the speed of guided search. The key to using A* effectively is choosing an admissible heuristic that is as tight as possible to the true remaining cost. With the right heuristic, A* can solve pathfinding problems orders of magnitude faster than blind search.
