A* Search Algorithm

A* (A-star) is an intelligent pathfinding algorithm that combines the guaranteed optimality of Dijkstra's algorithm with the efficiency of greedy best-first search. It uses heuristic guidance to find optimal paths while exploring minimal nodes.

Interactive Visualization

A* Pathfinding Visualization

Speed: 50ms

Current Tool: wall - Click to place walls

Click on the grid to place start, end, and wall nodes

Grid Visualization

F-cost (top): Total cost (G + H)

G-cost (bottom left): Distance from start

H-cost (bottom right): Heuristic to end

Legend:

Start Node

End Node

▓

Wall

Open Set

Closed Set

Current Node

●

Final Path

Empty

How A* Algorithm Works:

• Heuristic Search: Uses distance estimate to guide search toward goal

• F-cost = G-cost + H-cost: Total estimated cost through current node

• G-cost: Actual distance traveled from start to current node

• H-cost: Heuristic estimate from current node to goal (Manhattan distance)

• Open Set: Nodes to be evaluated (frontier)

• Closed Set: Nodes already evaluated

• Best-First: Always expands node with lowest F-cost

• Optimal: Guaranteed to find shortest path with admissible heuristic

Heuristic-Guided Search Strategy

A* employs a heuristic-guided search strategy that uses the evaluation function f(n) = g(n) + h(n) to intelligently direct the search toward the goal. This combination of actual cost and estimated remaining cost enables optimal pathfinding with maximum efficiency.

1. Evaluate

Calculate f(n) = g(n) + h(n) for each candidate node

2. Select Best

Choose node with lowest f(n) value from open set

3. Expand

Process neighbors and update costs if better path found

Key Insight

The magic of A* lies in its evaluation function f(n) = g(n) + h(n). The g(n) component ensures optimality by tracking actual costs, while h(n) provides guidance toward the goal. When h(n) is admissible (never overestimates), A* guarantees finding the optimal path.

How A* Search Works

Step-by-Step Process

Initialize: Add start node to open set with g(start) = 0, calculate f(start)

Select Node: Choose node with lowest f(n) value from open set

Goal Check: If current node is goal, reconstruct and return path

Expand: Move current to closed set, evaluate all valid neighbors

Update: Calculate g, h, f costs for neighbors; add to open set if better

The A* Evaluation Function

f(n) = g(n) + h(n) - Total estimated cost of path through node n

g(n): Actual cost from start node to node n

h(n): Heuristic estimate of cost from node n to goal

Admissible: h(n) ≤ actual cost from n to goal (never overestimate)

Consistent: h(n) ≤ cost(n, n') + h(n') for all neighbors n'

Example: Pathfinding with Obstacles

Setup: Start(0,0) → Goal(4,4), walls at (2,1), (2,2), (2,3)

Step 1: Expand (0,0), f-costs: (1,0)=6, (0,1)=6

Step 2: Expand (1,0), avoid blocked path, explore alternatives

Step 3: Heuristic guides search around obstacles

Step 4: Find optimal path: (0,0)→(1,0)→(1,1)→(3,1)→(4,4)

Result: Optimal path found with minimal node exploration

Heuristic Functions

Manhattan Distance

Formula: |x₁ - x₂| + |y₁ - y₂|

Best For: 4-directional movement (up, down, left, right)

Properties: Admissible, consistent, efficient to compute

Use Case: Grid-based games, robot navigation

Euclidean Distance

Formula: √[(x₁-x₂)² + (y₁-y₂)²]

Best For: 8-directional movement (including diagonals)

Properties: Admissible, consistent, more accurate

Use Case: Real-world navigation, flight paths

Heuristic Quality Impact

h(n) = 0 (Dijkstra):
Explores all directions equally
Guaranteed optimal, but slow
Maximum nodes explored

Perfect h(n):
Directly guides to goal
Explores minimal nodes
Optimal efficiency

Overestimating h(n):
May miss optimal path
Faster but not guaranteed optimal
Not admissible

Pseudocode

ALGORITHM AStar(start, goal, heuristic)
BEGIN
    // Initialize open and closed sets
    openSet = priority queue ordered by f-cost
    closedSet = empty set
    
    // Initialize start node
    start.g = 0
    start.h = heuristic(start, goal)
    start.f = start.g + start.h
    start.parent = null
    
    openSet.add(start)
    
    WHILE openSet is not empty DO
        // Get node with lowest f-cost
        current = openSet.removeMin()
        
        // Check if we reached the goal
        IF current == goal THEN
            RETURN reconstructPath(current)
        END IF
        
        // Move current from open to closed set
        closedSet.add(current)
        
        // Process all neighbors
        FOR each neighbor OF current DO
            // Skip if wall or already evaluated
            IF neighbor.isWall OR neighbor IN closedSet THEN
                CONTINUE
            END IF
            
            // Calculate tentative g-cost
            tentativeG = current.g + movementCost(current, neighbor)
            
            // Check if this path to neighbor is better
            IF tentativeG < neighbor.g THEN
                // Update neighbor
                neighbor.parent = current
                neighbor.g = tentativeG
                neighbor.h = heuristic(neighbor, goal)
                neighbor.f = neighbor.g + neighbor.h
                
                // Add to open set if not already there
                IF neighbor NOT IN openSet THEN
                    openSet.add(neighbor)
                END IF
            END IF
        END FOR
    END WHILE
    
    // No path found
    RETURN empty path
END

ALGORITHM reconstructPath(goalNode)
BEGIN
    path = empty list
    current = goalNode
    
    WHILE current is not null DO
        path.prepend(current)
        current = current.parent
    END WHILE
    
    RETURN path
END

// Heuristic functions
FUNCTION manhattanDistance(a, b)
    RETURN |a.x - b.x| + |a.y - b.y|
END

FUNCTION euclideanDistance(a, b)
    RETURN √[(a.x - b.x)² + (a.y - b.y)²]
END

Complexity Analysis

Metric	Best Case	Average Case	Worst Case
Time Complexity	O(d)	O(b^d)	O(b^d)
Space Complexity	O(d)	O(b^d)	O(b^d)
Optimality	Guaranteed	Guaranteed	Guaranteed*

*With admissible and consistent heuristic

Why A* is Efficient

• Heuristic Guidance: Reduces search space by focusing on promising directions
• Optimal Pruning: Admissible heuristics ensure no optimal solutions are discarded
• Best-First Strategy: Always expands most promising nodes first
• Early Termination: Stops immediately upon reaching goal

Factors Affecting Performance

• Heuristic Quality: Better heuristics lead to fewer node expansions
• Branching Factor (b): Number of neighbors per node
• Solution Depth (d): Length of optimal path
• Problem Structure: Obstacles and terrain complexity

Optimality Guarantees

A* guarantees finding the optimal solution when the heuristic is admissible and consistent:

Admissible: h(n) ≤ h*(n)
Never overestimates actual cost to goal
Ensures optimality

Consistent: h(n) ≤ c(n,n') + h(n')
Triangle inequality property
Ensures efficiency and optimal node expansions

Code Examples

Here are implementations of A* search in different programming languages. Each version includes both Manhattan and Euclidean distance heuristics, support for diagonal movement, and efficient priority queue management.

 import heapq
import math
from typing import List, Tuple, Optional, Set

class Node:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y
        self.g_cost = float('inf')  # Distance from start
        self.h_cost = 0.0           # Heuristic distance to goal
        self.f_cost = float('inf')  # Total cost (g + h)
        self.parent = None
        self.is_wall = False
    
    def calculate_f_cost(self):
        self.f_cost = self.g_cost + self.h_cost
    
    def __lt__(self, other):
        if self.f_cost == other.f_cost:
            return self.h_cost < other.h_cost
        return self.f_cost < other.f_cost
    
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    
    def __hash__(self):
        return hash((self.x, self.y))

def manhattan_distance(a: Node, b: Node) -> float:
    """Calculate Manhattan distance heuristic (admissible for 4-directional movement)"""
    return abs(a.x - b.x) + abs(a.y - b.y)

def euclidean_distance(a: Node, b: Node) -> float:
    """Calculate Euclidean distance heuristic (admissible for 8-directional movement)"""
    dx = a.x - b.x
    dy = a.y - b.y
    return math.sqrt(dx * dx + dy * dy)

def get_neighbors(node: Node, grid: List[List[Node]], allow_diagonal: bool) -> List[Node]:
    """Get valid neighboring nodes for pathfinding"""
    neighbors = []
    rows, cols = len(grid), len(grid[0])
    
    # 4-directional movement
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # Add diagonal directions if allowed
    if allow_diagonal:
        directions.extend([(-1, -1), (-1, 1), (1, -1), (1, 1)])
    
    for dx, dy in directions:
        new_x, new_y = node.x + dx, node.y + dy
        
        # Check bounds and walls
        if (0 <= new_x < cols and 0 <= new_y < rows):
            neighbor = grid[new_y][new_x]
            if not neighbor.is_wall:
                neighbors.append(neighbor)
    
    return neighbors

def get_movement_cost(current: Node, neighbor: Node) -> float:
    """Calculate movement cost between adjacent nodes"""
    dx = abs(current.x - neighbor.x)
    dy = abs(current.y - neighbor.y)
    
    # Diagonal movement
    if dx == 1 and dy == 1:
        return math.sqrt(2)  # ≈ 1.414
    # Straight movement
    return 1.0

def reconstruct_path(goal_node: Node) -> List[Node]:
    """Reconstruct path from goal to start using parent pointers"""
    path = []
    current = goal_node
    
    while current is not None:
        path.append(current)
        current = current.parent
    
    path.reverse()
    return path

def a_star_search(grid: List[List[Node]], start: Node, goal: Node, 
                  allow_diagonal: bool = True) -> Tuple[List[Node], int]:
    """
    A* pathfinding algorithm implementation
    
    Returns:
        Tuple containing path and number of nodes explored
    
    Time Complexity: O(b^d) where b is branching factor, d is depth
    Space Complexity: O(b^d) for storing open and closed sets
    """
    # Initialize start node
    start.g_cost = 0
    start.h_cost = euclidean_distance(start, goal) if allow_diagonal else manhattan_distance(start, goal)
    start.calculate_f_cost()
    
    # Priority queue for open set (nodes to be evaluated)
    open_set = [start]
    open_set_hash = {start}  # For O(1) membership testing
    closed_set: Set[Node] = set()  # Already evaluated nodes
    
    nodes_explored = 0
    
    while open_set:
        # Get node with lowest F-cost
        current = heapq.heappop(open_set)
        open_set_hash.remove(current)
        
        # Add to closed set
        closed_set.add(current)
        nodes_explored += 1
        
        # Check if we reached the goal
        if current == goal:
            return reconstruct_path(current), nodes_explored
        
        # Process each neighbor
        for neighbor in get_neighbors(current, grid, allow_diagonal):
            # Skip if already evaluated
            if neighbor in closed_set:
                continue
            
            # Calculate tentative G-cost
            movement_cost = get_movement_cost(current, neighbor)
            tentative_g_cost = current.g_cost + movement_cost
            
            # If this path to neighbor is better than any previous one
            if tentative_g_cost < neighbor.g_cost:
                # Update neighbor costs
                neighbor.parent = current
                neighbor.g_cost = tentative_g_cost
                neighbor.h_cost = (euclidean_distance(neighbor, goal) if allow_diagonal 
                                  else manhattan_distance(neighbor, goal))
                neighbor.calculate_f_cost()
                
                # Add to open set if not already there
                if neighbor not in open_set_hash:
                    heapq.heappush(open_set, neighbor)
                    open_set_hash.add(neighbor)
    
    # No path found
    return [], nodes_explored

def create_grid(width: int, height: int) -> List[List[Node]]:
    """Create a 2D grid of nodes"""
    grid = []
    for y in range(height):
        row = []
        for x in range(width):
            row.append(Node(x, y))
        grid.append(row)
    return grid

# Example usage
if __name__ == "__main__":
    # Create a 10x10 grid
    grid = create_grid(10, 10)
    
    # Set start and goal
    start = grid[0][0]
    goal = grid[9][9]
    
    # Add some walls
    walls = [(3, 3), (3, 4), (3, 5), (4, 3), (5, 3)]
    for x, y in walls:
        grid[y][x].is_wall = True
    
    # Run A* search
    path, explored = a_star_search(grid, start, goal, allow_diagonal=True)
    
    if path:
        print(f"Path found! Length: {len(path)} nodes")
        print(f"Nodes explored: {explored}")
        print("Path coordinates:")
        for node in path:
            print(f"  ({node.x}, {node.y})")
    else:
        print("No path found!")
        print(f"Nodes explored: {explored}") 
 import java.util.*;

class Node implements Comparable<Node> {
    int x, y;
    double gCost = Double.POSITIVE_INFINITY;  // Distance from start
    double hCost = 0;                         // Heuristic distance to goal
    double fCost = Double.POSITIVE_INFINITY;  // Total cost (g + h)
    Node parent = null;
    boolean isWall = false;
    
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public void calculateFCost() {
        fCost = gCost + hCost;
    }
    
    @Override
    public int compareTo(Node other) {
        if (Double.compare(fCost, other.fCost) == 0) {
            return Double.compare(hCost, other.hCost);
        }
        return Double.compare(fCost, other.fCost);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Node node = (Node) obj;
        return x == node.x && y == node.y;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public class AStarAlgorithm {
    
    /**
     * Calculate Manhattan distance heuristic (admissible for 4-directional movement)
     */
    public static double manhattanDistance(Node a, Node b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }
    
    /**
     * Calculate Euclidean distance heuristic (admissible for 8-directional movement)
     */
    public static double euclideanDistance(Node a, Node b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return Math.sqrt(dx * dx + dy * dy);
    }
    
    /**
     * Get valid neighboring nodes for pathfinding
     */
    public static List<Node> getNeighbors(Node node, Node[][] grid, boolean allowDiagonal) {
        List<Node> neighbors = new ArrayList<>();
        int rows = grid.length;
        int cols = grid[0].length;
        
        // 4-directional movement
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // Add diagonal directions if allowed
        if (allowDiagonal) {
            int[][] diagonalDirs = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
            int[][] allDirs = new int[8][2];
            System.arraycopy(directions, 0, allDirs, 0, 4);
            System.arraycopy(diagonalDirs, 0, allDirs, 4, 4);
            directions = allDirs;
        }
        
        for (int[] dir : directions) {
            int newX = node.x + dir[0];
            int newY = node.y + dir[1];
            
            // Check bounds and walls
            if (newX >= 0 && newX < cols && newY >= 0 && newY < rows) {
                Node neighbor = grid[newY][newX];
                if (!neighbor.isWall) {
                    neighbors.add(neighbor);
                }
            }
        }
        
        return neighbors;
    }
    
    /**
     * Calculate movement cost between adjacent nodes
     */
    public static double getMovementCost(Node current, Node neighbor) {
        int dx = Math.abs(current.x - neighbor.x);
        int dy = Math.abs(current.y - neighbor.y);
        
        // Diagonal movement
        if (dx == 1 && dy == 1) {
            return Math.sqrt(2);  // ≈ 1.414
        }
        // Straight movement
        return 1.0;
    }
    
    /**
     * Reconstruct path from goal to start using parent pointers
     */
    public static List<Node> reconstructPath(Node goalNode) {
        List<Node> path = new ArrayList<>();
        Node current = goalNode;
        
        while (current != null) {
            path.add(current);
            current = current.parent;
        }
        
        Collections.reverse(path);
        return path;
    }
    
    /**
     * A* pathfinding algorithm implementation
     */
    public static SearchResult aStarSearch(Node[][] grid, Node start, Node goal, boolean allowDiagonal) {
        // Initialize start node
        start.gCost = 0;
        start.hCost = allowDiagonal ? euclideanDistance(start, goal) : manhattanDistance(start, goal);
        start.calculateFCost();
        
        // Priority queue for open set (nodes to be evaluated)
        PriorityQueue<Node> openSet = new PriorityQueue<>();
        Set<Node> openSetHash = new HashSet<>();  // For O(1) membership testing
        Set<Node> closedSet = new HashSet<>();    // Already evaluated nodes
        
        openSet.offer(start);
        openSetHash.add(start);
        
        int nodesExplored = 0;
        
        while (!openSet.isEmpty()) {
            // Get node with lowest F-cost
            Node current = openSet.poll();
            openSetHash.remove(current);
            
            // Add to closed set
            closedSet.add(current);
            nodesExplored++;
            
            // Check if we reached the goal
            if (current.equals(goal)) {
                return new SearchResult(reconstructPath(current), nodesExplored);
            }
            
            // Process each neighbor
            for (Node neighbor : getNeighbors(current, grid, allowDiagonal)) {
                // Skip if already evaluated
                if (closedSet.contains(neighbor)) {
                    continue;
                }
                
                // Calculate tentative G-cost
                double movementCost = getMovementCost(current, neighbor);
                double tentativeGCost = current.gCost + movementCost;
                
                // If this path to neighbor is better than any previous one
                if (tentativeGCost < neighbor.gCost) {
                    // Update neighbor costs
                    neighbor.parent = current;
                    neighbor.gCost = tentativeGCost;
                    neighbor.hCost = allowDiagonal ? euclideanDistance(neighbor, goal) 
                                                   : manhattanDistance(neighbor, goal);
                    neighbor.calculateFCost();
                    
                    // Add to open set if not already there
                    if (!openSetHash.contains(neighbor)) {
                        openSet.offer(neighbor);
                        openSetHash.add(neighbor);
                    }
                }
            }
        }
        
        // No path found
        return new SearchResult(new ArrayList<>(), nodesExplored);
    }
    
    /**
     * Create a 2D grid of nodes
     */
    public static Node[][] createGrid(int width, int height) {
        Node[][] grid = new Node[height][width];
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                grid[y][x] = new Node(x, y);
            }
        }
        return grid;
    }
    
    public static void main(String[] args) {
        // Create a 10x10 grid
        Node[][] grid = createGrid(10, 10);
        
        // Set start and goal
        Node start = grid[0][0];
        Node goal = grid[9][9];
        
        // Add some walls
        int[][] walls = {{3, 3}, {3, 4}, {3, 5}, {4, 3}, {5, 3}};
        for (int[] wall : walls) {
            grid[wall[1]][wall[0]].isWall = true;
        }
        
        // Run A* search
        SearchResult result = aStarSearch(grid, start, goal, true);
        
        if (!result.path.isEmpty()) {
            System.out.println("Path found! Length: " + result.path.size() + " nodes");
            System.out.println("Nodes explored: " + result.nodesExplored);
            System.out.println("Path coordinates:");
            for (Node node : result.path) {
                System.out.println("  (" + node.x + ", " + node.y + ")");
            }
        } else {
            System.out.println("No path found!");
            System.out.println("Nodes explored: " + result.nodesExplored);
        }
    }
}

class SearchResult {
    List<Node> path;
    int nodesExplored;
    
    public SearchResult(List<Node> path, int nodesExplored) {
        this.path = path;
        this.nodesExplored = nodesExplored;
    }
} 
 #include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <limits>

struct Node {
    int x, y;
    double gCost = std::numeric_limits<double>::infinity();  // Distance from start
    double hCost = 0;                                        // Heuristic distance to goal
    double fCost = std::numeric_limits<double>::infinity();  // Total cost (g + h)
    Node* parent = nullptr;
    bool isWall = false;
    
    Node(int x, int y) : x(x), y(y) {}
    
    void calculateFCost() {
        fCost = gCost + hCost;
    }
    
    // For priority queue (min-heap)
    bool operator>(const Node& other) const {
        if (fCost == other.fCost) {
            return hCost > other.hCost;
        }
        return fCost > other.fCost;
    }
    
    bool operator==(const Node& other) const {
        return x == other.x && y == other.y;
    }
};

// Hash function for Node (for unordered_set)
struct NodeHash {
    std::size_t operator()(const Node* node) const {
        return std::hash<int>()(node->x) ^ (std::hash<int>()(node->y) << 1);
    }
};

struct NodeEqual {
    bool operator()(const Node* a, const Node* b) const {
        return a->x == b->x && a->y == b->y;
    }
};

/**
 * Calculate Manhattan distance heuristic (admissible for 4-directional movement)
 */
double manhattanDistance(const Node* a, const Node* b) {
    return std::abs(a->x - b->x) + std::abs(a->y - b->y);
}

/**
 * Calculate Euclidean distance heuristic (admissible for 8-directional movement)
 */
double euclideanDistance(const Node* a, const Node* b) {
    double dx = a->x - b->x;
    double dy = a->y - b->y;
    return std::sqrt(dx * dx + dy * dy);
}

/**
 * Get valid neighboring nodes for pathfinding
 */
std::vector<Node*> getNeighbors(Node* node, std::vector<std::vector<Node>>& grid, bool allowDiagonal) {
    std::vector<Node*> neighbors;
    int rows = grid.size();
    int cols = grid[0].size();
    
    // 4-directional movement
    std::vector<std::pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    // Add diagonal directions if allowed
    if (allowDiagonal) {
        directions.push_back({-1, -1});
        directions.push_back({-1, 1});
        directions.push_back({1, -1});
        directions.push_back({1, 1});
    }
    
    for (const auto& dir : directions) {
        int newX = node->x + dir.first;
        int newY = node->y + dir.second;
        
        // Check bounds and walls
        if (newX >= 0 && newX < cols && newY >= 0 && newY < rows) {
            Node* neighbor = &grid[newY][newX];
            if (!neighbor->isWall) {
                neighbors.push_back(neighbor);
            }
        }
    }
    
    return neighbors;
}

/**
 * Calculate movement cost between adjacent nodes
 */
double getMovementCost(const Node* current, const Node* neighbor) {
    int dx = std::abs(current->x - neighbor->x);
    int dy = std::abs(current->y - neighbor->y);
    
    // Diagonal movement
    if (dx == 1 && dy == 1) {
        return std::sqrt(2);  // ≈ 1.414
    }
    // Straight movement
    return 1.0;
}

/**
 * Reconstruct path from goal to start using parent pointers
 */
std::vector<Node*> reconstructPath(Node* goalNode) {
    std::vector<Node*> path;
    Node* current = goalNode;
    
    while (current != nullptr) {
        path.push_back(current);
        current = current->parent;
    }
    
    std::reverse(path.begin(), path.end());
    return path;
}

/**
 * A* pathfinding algorithm implementation
 * 
 * @param grid 2D vector of Node objects
 * @param start Starting node
 * @param goal Goal node
 * @param allowDiagonal Whether diagonal movement is allowed
 * @return pair containing path and number of nodes explored
 * 
 * Time Complexity: O(b^d) where b is branching factor, d is depth
 * Space Complexity: O(b^d) for storing open and closed sets
 */
std::pair<std::vector<Node*>, int> aStarSearch(std::vector<std::vector<Node>>& grid, 
                                               Node* start, Node* goal, bool allowDiagonal) {
    // Initialize start node
    start->gCost = 0;
    start->hCost = allowDiagonal ? euclideanDistance(start, goal) : manhattanDistance(start, goal);
    start->calculateFCost();
    
    // Priority queue for open set (nodes to be evaluated)
    std::priority_queue<Node*, std::vector<Node*>, std::greater<Node*>> openSet;
    std::unordered_set<Node*, NodeHash, NodeEqual> openSetHash;  // For O(1) membership testing
    std::unordered_set<Node*, NodeHash, NodeEqual> closedSet;    // Already evaluated nodes
    
    openSet.push(start);
    openSetHash.insert(start);
    
    int nodesExplored = 0;
    
    while (!openSet.empty()) {
        // Get node with lowest F-cost
        Node* current = openSet.top();
        openSet.pop();
        openSetHash.erase(current);
        
        // Add to closed set
        closedSet.insert(current);
        nodesExplored++;
        
        // Check if we reached the goal
        if (*current == *goal) {
            return {reconstructPath(current), nodesExplored};
        }
        
        // Process each neighbor
        for (Node* neighbor : getNeighbors(current, grid, allowDiagonal)) {
            // Skip if already evaluated
            if (closedSet.find(neighbor) != closedSet.end()) {
                continue;
            }
            
            // Calculate tentative G-cost
            double movementCost = getMovementCost(current, neighbor);
            double tentativeGCost = current->gCost + movementCost;
            
            // If this path to neighbor is better than any previous one
            if (tentativeGCost < neighbor->gCost) {
                // Update neighbor costs
                neighbor->parent = current;
                neighbor->gCost = tentativeGCost;
                neighbor->hCost = allowDiagonal ? euclideanDistance(neighbor, goal) 
                                                : manhattanDistance(neighbor, goal);
                neighbor->calculateFCost();
                
                // Add to open set if not already there
                if (openSetHash.find(neighbor) == openSetHash.end()) {
                    openSet.push(neighbor);
                    openSetHash.insert(neighbor);
                }
            }
        }
    }
    
    // No path found
    return {std::vector<Node*>(), nodesExplored};
}

/**
 * Create a 2D grid of nodes
 */
std::vector<std::vector<Node>> createGrid(int width, int height) {
    std::vector<std::vector<Node>> grid;
    grid.reserve(height);
    
    for (int y = 0; y < height; y++) {
        std::vector<Node> row;
        row.reserve(width);
        for (int x = 0; x < width; x++) {
            row.emplace_back(x, y);
        }
        grid.push_back(std::move(row));
    }
    
    return grid;
}

int main() {
    // Create a 10x10 grid
    auto grid = createGrid(10, 10);
    
    // Set start and goal
    Node* start = &grid[0][0];
    Node* goal = &grid[9][9];
    
    // Add some walls
    std::vector<std::pair<int, int>> walls = {{3, 3}, {3, 4}, {3, 5}, {4, 3}, {5, 3}};
    for (const auto& wall : walls) {
        grid[wall.second][wall.first].isWall = true;
    }
    
    // Run A* search
    auto [path, explored] = aStarSearch(grid, start, goal, true);
    
    if (!path.empty()) {
        std::cout << "Path found! Length: " << path.size() << " nodes\n";
        std::cout << "Nodes explored: " << explored << "\n";
        std::cout << "Path coordinates:\n";
        for (const Node* node : path) {
            std::cout << "  (" << node->x << ", " << node->y << ")\n";
        }
    } else {
        std::cout << "No path found!\n";
        std::cout << "Nodes explored: " << explored << "\n";
    }
    
    return 0;
} 

Practical Applications

Excellent For

• Video Game AI: NPC pathfinding with optimal routes and natural movement
• Robotics Navigation: Mobile robot path planning with obstacle avoidance
• GPS Route Planning: Finding optimal routes considering traffic and distance
• Puzzle Solving: 15-puzzle, sliding puzzles, maze solving
• AI Planning: Task scheduling and resource allocation
• Network Routing: Optimal packet routing with QoS constraints

Consider Alternatives When

• Very Large Search Spaces: Memory requirements become prohibitive
• No Good Heuristic: When h(n) provides little guidance
• Any Path Acceptable: When optimality is not required (use greedy search)
• Dynamic Environments: Frequently changing obstacles or costs
• Real-Time Constraints: When strict time limits require approximate solutions

Real-World Applications

Entertainment & Games: Strategy games (StarCraft, Age of Empires), RPG character movement, procedural level generation, AI opponent behavior, racing game optimal racing lines, puzzle game solvers

Industrial Applications: Autonomous vehicle navigation, drone flight path optimization, robotic arm motion planning, warehouse automation, 3D printing toolpath generation, manufacturing workflow optimization