A* Search: A Comprehensive Guide

Tahsin Soyak
3 min readJul 21, 2024

--

The A* (A-star) search algorithm is a powerful tool for finding the shortest path from a starting node to a target node in a graph. It is widely used in pathfinding for games, robotics, and various optimization problems.

Key Concepts

A* search uses the evaluation function:

f(n)=g(n)+h(n)

  • f(n): Total cost from start to goal through node n.
  • g(n): Cost from the start node to node n.
  • h(n): Heuristic estimate of the cost from node n to the goal.

How A* Search Works

  1. Initialization: Start with the initial node in the priority queue with f(n)=g(n)+h(n).
  2. Node Expansion: Extract the node with the lowest f(n) value. If it’s the goal node, the search ends.
  3. Neighbor Evaluation: For each neighbor of the current node, compute the tentative g(n). If it offers a better path, update g(n) and f(n), then add it to the queue.
  4. Repeat: Continue expanding nodes until the goal is reached or the queue is empty.

Example Code

Here’s a simple Python example demonstrating the A* algorithm on a grid:

import heapq

def heuristic(a, b):
# Manhattan distance heuristic
return abs(b[0] - a[0]) + abs(b[1] - a[1])

def astar(grid, start, goal):
# Priority queue: stores tuples of (f, current_node)
open_list = []
heapq.heappush(open_list, (0 + heuristic(start, goal), start))

came_from = {}
g_score = {start: 0}
f_score = {start: heuristic(start, goal)}

while open_list:
_, current = heapq.heappop(open_list)

if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
path.reverse()
return path

x, y = current
neighbors = [(x + dx, y + dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]]

for neighbor in neighbors:
if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] == 0:
tentative_g_score = g_score[current] + 1
if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
heapq.heappush(open_list, (f_score[neighbor], neighbor))

return None # Path not found

# Example usage
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]
]

start = (0, 0)
goal = (4, 4)
path = astar(grid, start, goal)
print("Path:", path)

Output: Path: [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)]

Summary

  • A Search*: An efficient algorithm for finding the shortest path using a heuristic.
  • f(n) = g(n) + h(n): Balances the cost to reach the node and the estimated cost to the goal.
  • Priority Queue: Ensures nodes are expanded in the order of their total cost.

A* search is optimal and complete, making it an invaluable tool in solving complex pathfinding problems. Whether in games, robotics, or optimization, A* helps in navigating the most efficient routes to success.

A* Search

Artificial Intelligence — Tutorial #6 “A* Search”

For previous subject go here -> https://medium.com/p/4672bbc5e48c

For next subject go here -> https://medium.com/p/46e33f1ecc02

Let me know if you’d like any further refinements or additions to this post! tahsinsoyakk@gmail.com

--

--