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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
The algorithm evaluates each node using a cost function:<\/p>\n\n\n\n
f(N) = g(N) + h(N)<\/strong><\/p>\n\n\n\n Here, g(N)<\/strong> 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)<\/strong> is a heuristic estimate of the minimum cost from N to the goal. This is where domain-specific knowledge enters the algorithm.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n The algorithm maintains two sets: an open set<\/strong> of candidate nodes and a closed set<\/strong> 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.<\/p>\n\n\n\n Understanding what makes A* different requires comparing it to the algorithms it builds on.<\/p>\n\n\n\n Dijkstra’s Algorithm<\/strong> 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.<\/p>\n\n\n\n Greedy Best-First Search<\/strong> 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n 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.<\/p>\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n 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.<\/p>\n\n\n 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.<\/p>\n\n\n\n Game development<\/strong> 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.<\/p>\n\n\n\n GPS and navigation<\/strong> 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.<\/p>\n\n\n\n Robotics and motion planning<\/strong> 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.<\/p>\n\n\n\n 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).<\/p>\n\n\n\n Q: What happens if h(N) overestimates the true cost?<\/strong><\/p>\n\n\n\n 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.<\/p>\n\n\n\n Q: Can A* handle moving obstacles?<\/strong><\/p>\n\n\n\n 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.<\/p>\n\n\n\n Q: Is A* faster than Dijkstra?<\/strong><\/p>\n\n\n\n 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.<\/p>\n\n\n\n Q: What is the memory complexity of A*?<\/strong><\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n","protected":false},"excerpt":{"rendered":" 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 […]<\/p>\n","protected":false},"author":41,"featured_media":36166,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-36163","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-examples"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/36163","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/41"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=36163"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/36163\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media\/36166"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=36163"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=36163"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=36163"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}A* vs Other Search Algorithms<\/h2>\n\n\n\n
Implementing A* in Python<\/h2>\n\n\n\n
\nimport heapq\n\nclass Node:\n def __init__(self, pos, parent=None):\n self.pos = pos\n self.parent = parent\n self.g = 0 # cost from start\n self.h = 0 # heuristic cost to goal\n self.f = 0 # total: g + h\n\n def __lt__(self, other):\n return self.f < other.f\n\ndef manhattan(a, b):\n return abs(a[0] - b[0]) + abs(a[1] - b[1])\n\ndef astar(grid, start, goal):\n open_set = []\n start_node = Node(start)\n goal_node = Node(goal)\n heapq.heappush(open_set, start_node)\n\n while open_set:\n current = heapq.heappop(open_set)\n\n if current.pos == goal_node.pos:\n path = []\n while current:\n path.append(current.pos)\n current = current.parent\n return path[::-1]\n\n closed = set()\n\n for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n nx, ny = current.pos[0] + dx, current.pos[1] + dy\n if not (0 <= nx < len(grid) and 0 <= ny < len(grid[0]):\n continue\n if grid[nx][ny] == 1: # obstacle\n continue\n neighbor_pos = (nx, ny)\n if neighbor_pos in closed:\n continue\n\n neighbor = Node(neighbor_pos, current)\n neighbor.g = current.g + 1\n neighbor.h = manhattan(neighbor.pos, goal_node.pos)\n neighbor.f = neighbor.g + neighbor.h\n\n heapq.heappush(open_set, neighbor)\n closed.add(neighbor_pos)\n\n return None\n\n# 0 = walkable, 1 = obstacle\ngrid = [\n [0, 0, 0, 0, 0],\n [0, 1, 1, 0, 0],\n [0, 0, 0, 0, 0],\n [0, 0, 1, 1, 0],\n [0, 0, 0, 0, 0],\n]\nstart = (0, 0)\ngoal = (4, 4)\npath = astar(grid, start, goal)\nprint("Path:", path)\nprint("Steps:", len(path) - 1 if path else "No path")\n\n<\/pre><\/div>\n\n\n\nPath: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]\nSteps: 8\n\n<\/pre><\/div>\n\n\n
Solving the 8-Puzzle with A*<\/h2>\n\n\n\n
\nfrom copy import deepcopy\nimport numpy as np\nimport time\n\ndef bestsolution(state):\n bestsol = np.array([], int).reshape(-1, 9)\n count = len(state) - 1\n while count != -1:\n bestsol = np.insert(bestsol, 0, state[count]["puzzle"], 0)\n count = state[count]["parent"]\n return bestsol.reshape(-1, 3, 3)\n\ndef misplaced_tiles(puzzle, goal):\n mscost = np.sum(puzzle != goal) - 1\n return mscost if mscost > 0 else 0\n\ndef coordinates(puzzle):\n pos = np.array(range(9))\n for p, q in enumerate(puzzle):\n pos[q] = p\n return pos\n\ndef evaluvate_misplaced(puzzle, goal):\n steps = np.array(\n [("up", [0, 1, 2], -3), ("down", [6, 7, 8], 3),\n ("left", [0, 3, 6], -1), ("right", [2, 5, 8], 1)],\n dtype=[("move", str, 1), ("position", list), ("head", int)],\n )\n dtstate = [("puzzle", list), ("parent", int), ("gn", int), ("hn", int)]\n costg = coordinates(goal)\n parent = -1\n gn = 0\n hn = misplaced_tiles(coordinates(puzzle), costg)\n state = np.array([(puzzle, parent, gn, hn)], dtstate)\n dtpriority = [("position", int), ("fn", int)]\n priority = np.array([(0, hn)], dtpriority)\n\n while True:\n priority = np.sort(priority, kind="mergesort", order=["fn", "position"])\n position, fn = priority[0]\n priority = np.delete(priority, 0, 0)\n puzzle, parent, gn, hn = state[position]\n puzzle = np.array(puzzle)\n blank = int(np.where(puzzle == 0)[0])\n gn = gn + 1\n start_time = time.time()\n\n for s in steps:\n if blank not in s["position"]:\n openstates = deepcopy(puzzle)\n openstates[blank], openstates[blank + s["head"]] = \\\n openstates[blank + s["head"]], openstates[blank]\n\n if not (np.all(list(state["puzzle"]) == openstates, 1)).any():\n end_time = time.time()\n if (end_time - start_time) > 2:\n print("The 8 puzzle is unsolvable")\n break\n\n hn = misplaced_tiles(coordinates(openstates), costg)\n q = np.array([(openstates, position, gn, hn)], dtstate)\n state = np.append(state, q, 0)\n fn = gn + hn\n q = np.array([(len(state) - 1, fn)], dtpriority)\n priority = np.append(priority, q, 0)\n\n if np.array_equal(openstates, goal):\n print("The 8 puzzle is solvable")\n return state, len(priority)\n\n return state, len(priority)\n\n# Initial state: 2 8 3 \/ 1 6 4 \/ 7 0 5\npuzzle = [2, 8, 3, 1, 6, 4, 7, 0, 5]\n# Goal state: 1 2 3 \/ 8 0 4 \/ 7 6 5\ngoal = [1, 2, 3, 8, 0, 4, 7, 6, 5]\n\nstate, visited = evaluvate_misplaced(puzzle, goal)\nbestpath = bestsolution(state)\n\nfor row in bestpath:\n print(" ".join(str(t) for t in row))\n\ntotalmoves = len(bestpath) - 1\nprint(f"Steps to reach goal: {totalmoves}")\nprint(f"Total nodes visited: {len(state) - visited}")\n\n<\/pre><\/div>\n\n\n\nThe 8 puzzle is solvable\n2 8 3\n1 6 4\n7 0 5\n\n2 8 3\n1 0 4\n7 6 5\n\n2 0 3\n1 8 4\n7 6 5\n\n0 2 3\n1 8 4\n7 6 5\n\n1 2 3\n0 8 4\n7 6 5\n\n1 2 3\n8 0 4\n7 6 5\n\nSteps to reach goal: 5\nTotal nodes visited: 6\n\n<\/pre><\/div>\n\n\n
When to Use A*<\/h2>\n\n\n\n
FAQ<\/h2>\n\n\n\n
Summary<\/h2>\n\n\n\n