Implementing A* Algorithm

import heapq

​

​

def a_star_algorithm(grid, start, target):

    # Create a priority queue to store the open nodes

    open_nodes = []

​

    # Create a set to store the visited nodes

    visited = set()

​

    # Create a dictionary to store the parent nodes

    parents = {}

​

    # Create a dictionary to store the g-score for each node

    g_scores = {}

​

    # Create a dictionary to store the f-score for each node

    f_scores = {}

​

    # Initialize the g-score and f-score for the start node

    g_scores[start] = 0

    f_scores[start] = heuristic(start, target)

​

    # Add the start node to the priority queue

    heapq.heappush(open_nodes, (f_scores[start], start))

​

    while open_nodes:

        # Remove the node with the lowest f-score from the priority queue

        current = heapq.heappop(open_nodes)[1]