A* Pathfinding Visualization

Heuristic shortest path search

A* is a heuristic search algorithm combining Dijkstra's shortest path guarantee with greedy search efficiency. It uses evaluation function f(n) = g(n) + h(n) to guide the search direction.

Start End Obstacle Open Closed Shortest Path
Click grid to draw/clear obstacles
Click 'Start' to view animation

Core Concepts

  • g(n): Actual cost from start to node n
  • h(n): Heuristic estimate from n to goal (e.g., Manhattan distance)
  • f(n) = g(n) + h(n): Total evaluation of node n
  • Always expand node with smallest f value from Open list
  • Search ends when selected node is the goal

Heuristic h(n) must be 'admissible' (never overestimate) to guarantee shortest path.

Time and Space Complexity

Metric Complexity Description
Time Complexity O(E) Worst case, depends on heuristic quality
Actual Performance Much better than Dijkstra Heuristic guidance reduces nodes explored
Space Complexity O(V) Store Open and Closed lists

A* vs Dijkstra: Dijkstra expands uniformly in all directions, A* prioritizes toward the goal.

Applications

  • NPC pathfinding and unit movement in games
  • Robot path planning
  • GPS navigation systems
  • Autonomous driving path decisions
  • Logistics delivery route optimization
Game Dev Robot Navigation Autonomous Driving Logistics

Implementation

import heapq

def heuristic(a, b):
    """曼哈顿距离"""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def astar(grid, start, goal):
    """A*寻路算法
    grid: 2D网格, 0=可通行, 1=障碍
    """
    rows, cols = len(grid), len(grid[0])
    
    # 四方向移动
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    open_set = []
    heapq.heappush(open_set, (0, start))
    
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    
    while open_set:
        _, current = heapq.heappop(open_set)
        
        if current == goal:
            # 重建路径
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        for dx, dy in directions:
            neighbor = (current[0] + dx, current[1] + dy)
            
            # 边界和障碍检查
            if (0 <= neighbor[0] < rows and
                0 <= neighbor[1] < cols and
                grid[neighbor[0]][neighbor[1]] == 0):
                
                tentative_g = g_score[current] + 1
                
                if tentative_g < g_score.get(neighbor, float('inf')):
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f = tentative_g + heuristic(neighbor, goal)
                    heapq.heappush(open_set, (f, neighbor))
    
    return None  # 无路径
import java.util.*;

public class AStar {
    
    static int heuristic(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }
    
    public static List<int[]> astar(
            int[][] grid, int[] start, int[] goal) {
        
        int rows = grid.length, cols = grid[0].length;
        int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        
        // 优先队列: [f值, x, y]
        PriorityQueue<int[]> openSet = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );
        
        Map<String, int[]> cameFrom = new HashMap<>();
        Map<String, Integer> gScore = new HashMap<>();
        
        String startKey = start[0] + "," + start[1];
        gScore.put(startKey, 0);
        openSet.offer(new int[]{
            heuristic(start, goal), start[0], start[1]
        });
        
        while (!openSet.isEmpty()) {
            int[] curr = openSet.poll();
            int x = curr[1], y = curr[2];
            
            if (x == goal[0] && y == goal[1]) {
                // 重建路径
                return reconstructPath(cameFrom, goal);
            }
            
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                    && grid[nx][ny] == 0) {
                    // 更新邻居...
                }
            }
        }
        return null;
    }
}