a star Algorithm

The A* algorithm is a popular pathfinding and graph traversal algorithm, widely used in various applications such as video games, robotics, and transportation systems. It was first introduced by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968. A* is an informed search algorithm, meaning that it uses heuristic information to guide its search towards the goal. It combines the benefits of Dijkstra's algorithm, which guarantees the shortest path, and Greedy Best-First-Search, which prioritizes exploring nodes closer to the target. The A* algorithm efficiently explores the search space and is guaranteed to find the optimal path, given a suitable heuristic function. The A* algorithm maintains a priority queue, known as the open set, which holds the nodes to be visited, prioritized by their cost function value (f(n)). The cost function f(n) is the sum of two components: g(n), the actual cost from the starting node to the current node, and h(n), the estimated cost from the current node to the goal node, according to the heuristic function. At each step, A* selects the node with the lowest f(n) value from the open set, explores its neighbors, and updates their cost values. Nodes that have been visited are moved to the closed set. The algorithm continues until the goal node is reached or the open set is empty. The A* algorithm is both complete and optimal if the chosen heuristic is admissible (never overestimates the true cost) and consistent (satisfies the triangle inequality). 
grid = [
    [0, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 0],
    [0, 0, 0, 0, 1, 0],
]
 
"""
heuristic = [[9, 8, 7, 6, 5, 4],
             [8, 7, 6, 5, 4, 3],
             [7, 6, 5, 4, 3, 2],
             [6, 5, 4, 3, 2, 1],
             [5, 4, 3, 2, 1, 0]]"""
 
init = [0, 0]
goal = [len(grid) - 1, len(grid[0]) - 1]  # all coordinates are given in format [y,x]
cost = 1
 
# the cost map which pushes the path closer to the goal
heuristic = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
for i in range(len(grid)):
    for j in range(len(grid[0])):
        heuristic[i][j] = abs(i - goal[0]) + abs(j - goal[1])
        if grid[i][j] == 1:
            heuristic[i][j] = 99  # added extra penalty in the heuristic map
 
 
# the actions we can take
delta = [[-1, 0], [0, -1], [1, 0], [0, 1]]  # go up  # go left  # go down  # go right
 
 
# function to search the path
def search(grid, init, goal, cost, heuristic):
 
    closed = [
        [0 for col in range(len(grid[0]))] for row in range(len(grid))
    ]  # the reference grid
    closed[init[0]][init[1]] = 1
    action = [
        [0 for col in range(len(grid[0]))] for row in range(len(grid))
    ]  # the action grid
 
    x = init[0]
    y = init[1]
    g = 0
    f = g + heuristic[init[0]][init[0]]
    cell = [[f, g, x, y]]
 
    found = False  # flag that is set when search is complete
    resign = False  # flag set if we can't find expand
 
    while not found and not resign:
        if len(cell) == 0:
            return "FAIL"
        else:
            cell.sort()  # to choose the least costliest action so as to move closer to the goal
            cell.reverse()
            next = cell.pop()
            x = next[2]
            y = next[3]
            g = next[1]
 
            if x == goal[0] and y == goal[1]:
                found = True
            else:
                for i in range(len(delta)):  # to try out different valid actions
                    x2 = x + delta[i][0]
                    y2 = y + delta[i][1]
                    if x2 >= 0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]):
                        if closed[x2][y2] == 0 and grid[x2][y2] == 0:
                            g2 = g + cost
                            f2 = g2 + heuristic[x2][y2]
                            cell.append([f2, g2, x2, y2])
                            closed[x2][y2] = 1
                            action[x2][y2] = i
    invpath = []
    x = goal[0]
    y = goal[1]
    invpath.append([x, y])  # we get the reverse path from here
    while x != init[0] or y != init[1]:
        x2 = x - delta[action[x][y]][0]
        y2 = y - delta[action[x][y]][1]
        x = x2
        y = y2
        invpath.append([x, y])
 
    path = []
    for i in range(len(invpath)):
        path.append(invpath[len(invpath) - 1 - i])
    print("ACTION MAP")
    for i in range(len(action)):
        print(action[i])
 
    return path
 
 
a = search(grid, init, goal, cost, heuristic)
for i in range(len(a)):
    print(a[i])

LANGUAGE:

DARK MODE:

PROGRAMMING LANGUAGES:

Python

Java

Javascript

C#

C++

C

Ruby

Scala

MATLAB

Kotlin

Rust

R

Go