Exploring Artificial Intelligence

What is A*?

A* (A-star) is the most popular pathfinding algorithm. It combines Dijkstra"s guaranteed shortest path with heuristic guidance toward the goal.

The Formula

A* evaluates nodes using: f(n) = g(n) + h(n)

• g(n) - Actual cost from start to node n
• h(n) - Estimated cost from n to goal (heuristic)
• f(n) - Total estimated cost through n

Heuristics & Movement

Grid (4-dir): Use Manhattan - it exactly matches the movement cost.

Free Space (8-dir): Use Euclidean or Chebyshev - they match diagonal movement costs.

• Manhattan - |dx| + |dy|
• Euclidean - sqrt(dx² + dy²)
• Chebyshev - max(|dx|, |dy|)
• Dijkstra - h=0 (no heuristic)

Other Algorithms

• BFS - Breadth-first search explores all nodes at depth d before d+1. Guarantees shortest path (by hop count).
• DFS - Depth-first search explores as deep as possible before backtracking. Fast but does not guarantee shortest path.

function A*(start, goal):
    openSet ← {start}
    closedSet ← {}
    g[start] ← 0
    f[start] ← h(start, goal)
    while openSet is not empty:
        current ← node in openSet with lowest f
        if current = goal:
            return reconstructPath(current)
        openSet.remove(current)
        closedSet.add(current)
        for each neighbor of current:
            if neighbor in closedSet: continue
            tentativeG ← g[current] + cost(current, neighbor)
            if tentativeG < g[neighbor]:
                parent[neighbor] ← current
                g[neighbor] ← tentativeG
                f[neighbor] ← g[neighbor] + h(neighbor, goal)
                if neighbor not in openSet:
                    openSet.add(neighbor)
    return "no path found"