The A* Algorithm

function aStar(graph, start, goal):
    openSet = [start]      // Nodes to evaluate
    closedSet = []         // Already evaluated
    
    gScore[start] = 0      // Cost from start
    fScore[start] = heuristic(start, goal)  // Estimated total cost
    
    while openSet is not empty:
        current = node in openSet with lowest fScore
        
        if current == goal then
            return reconstructPath(current)
        end if
        
        move current from openSet to closedSet
        
        for each neighbour of current:
            if neighbour in closedSet then
                continue
            end if
            
            tentativeG = gScore[current] + dist(current, neighbour)
            
            if neighbour not in openSet then
                add neighbour to openSet
            elseif tentativeG >= gScore[neighbour] then
                continue  // Not a better path
            end if
            
            // Best path found
            cameFrom[neighbour] = current
            gScore[neighbour] = tentativeG
            fScore[neighbour] = gScore[neighbour] + heuristic(neighbour, goal)
        end for
    end while
    
    return FAILURE  // No path found
end function