A* SEARCH ALGORITHM

Overview

A* is a graph traversal and pathfinding algorithm that finds the optimal path from start to goal. It uses a heuristic function to guide the search and guarantees the shortest path when the heuristic is admissible.

Key Components

›g(n) - Cost from start to node n
›h(n) - Heuristic cost to goal
›f(n) = g(n) + h(n) - Total cost
›Open/Closed sets for tracking

A* Algorithm

open_set = {start}
came_from = {}

while open_set not empty:
  current = node with lowest f(n)
  
  if current == goal:
    return reconstruct_path()
  
  open_set.remove(current)
  closed_set.add(current)
  
  for neighbor in current.neighbors:
    if neighbor in closed_set:
      continue
    
    tentative_g = g[current] + distance
    
    if tentative_g < g[neighbor]:
      came_from[neighbor] = current
      g[neighbor] = tentative_g
      f[neighbor] = g + h(neighbor)

Heuristics

Manhattan Distance

Euclidean Distance

Diagonal Distance

Custom Domain Heuristics