A* Path Algorithm

A* (A-Star) Algorithm is a widely used graph-based pathfinding algorithm that efficiently finds the shortest path between two nodes in a weighted graph. First described by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968, A* combines the benefits of Dijkstra’s Algorithm with heuristic-based search to guide exploration toward the goal. It is extensively used in video game AI, robotics, GPS navigation systems, and route planning applications. The algorithm operates by using both the actual cost from the start node and an estimated cost (heuristic) to the goal, allowing it to explore promising paths first and find optimal solutions more efficiently than uninformed search algorithms.

Algorithm

A* Algorithm works by finding the shortest path from a starting node to a goal node in a weighted graph using both actual cost and estimated cost. It begins by initializing the starting node’s cost to 0 and all other nodes to infinity. A heuristic function estimates the distance from each node to the goal, guiding the search toward the target. A priority queue processes nodes based on their total estimated cost (f = g + h), where g is the actual cost from the start and h is the heuristic estimate to the goal. From the current node, the algorithm examines its neighbors, updating their costs if a shorter path is found. When updating a neighbor’s cost, both the actual cost and heuristic are recalculated, and the neighbor is added to the priority queue with its new total estimated cost. This process continues until the goal node is reached or all reachable nodes have been explored, ensuring an optimal path is found while exploring fewer nodes than uninformed search algorithms.

function AStar(startNode, endNode):
    // Initialize a priority queue to manage nodes by their total cost (cost + heuristic)
    // Nodes with lower total costs will be processed first
    nodes = PriorityQueue()

    // Initialize the start node with cost 0
    // All other nodes implicitly have infinite cost
    startNode.Cost = 0
    
    // Calculate heuristic (estimated distance from start to end)
    // This guides the search toward the goal
    heuristic = Distance(startNode, endNode)
    
    // Add to queue with priority = cost + heuristic (f = g + h)
    nodes.Enqueue(startNode, priority = startNode.Cost + heuristic)

    // Process nodes until we find the end node or exhaust all options
    while nodes is not empty:
        // Get the node with lowest f-score (cost + heuristic) from the queue
        // This node is most promising for reaching the goal efficiently
        currentNode = nodes.Dequeue()

        // If this is our target node, we've found the shortest path
        // Build the path and return success
        if currentNode == endNode:
            CreatePath(endNode, path)
            return true

        // Check each connection from current node
        // This explores all possible paths one step further
        for each neighbor in currentNode.neighbors:
            // Calculate actual cost to reach this neighbor
            // Cost = (cost to current) + (distance from current to neighbor)
            cost = currentNode.Cost + Distance(currentNode, neighbor)

            // If we found a shorter path to this neighbor
            // Update its cost and set current node as its predecessor
            if cost < neighbor.Cost:
                neighbor.Cost = cost
                neighbor.Previous = currentNode

                // Calculate heuristic (estimated distance from neighbor to end)
                // This estimates how far neighbor is from the goal
                heuristic = Distance(neighbor, endNode)
                
                // Add/Update neighbor in priority queue with priority = cost + heuristic
                // The heuristic helps prioritize nodes closer to the goal
                nodes.EnqueueWithoutDuplicates(neighbor, priority = cost + heuristic)

    // No path found to end node
    return false