A* Path Finding Algorithm

— algorithm with brain

Let’s start with what is the A* pathfinding algorithm. As it is mentioned, it is used to find a path between two nodes in a graph data structure. But how? That’s why you are here, aren’t you? Okay let’s start to discuss

Before diving into how the algorithm works, let’s ask why we should use this algorithm while there are a lot more options out there. First of all the algorithm is quite so simple, which has a simple formula than any other algorithm you can think of (more of that it is just an addition of two values). Then it has a brain — yes it finds the path just like we do. It doesn’t go randomly and get the path, but it blasts its superpower towards the end node to find the path. It only calculates the required nodes to get to the path.

Let’s compare this algorithm with Dijkstra’s algorithm. A* evaluates the nodes which are quite closer to the end node whereas Dijkstra’s algorithm evaluates all the neighboring nodes. Dijkstra’s algorithm time complexity is more than that of A* pathfinding algorithm. Let’s discuss how to implement the algorithm also learning how it works.

First of all, we need to know how to evaluate a node. Every node has three scores G score, H score, and F score. G score is the absolute distance from the starting node to the current node. The algorithm is made for weighted graphs (weighted graphs are which there is a value for every edge).

g score of current = old g score + distance between current and last visited node

In this example, the graph is an unweighted graph, so the distance between each node can be assumed as any constant value (let’s say 1). H score is the heuristic value of the current value. It is nothing but the approximate distance between the current node and the end node. This heuristic value can be calculated by various methods. One of them is Euclidean distance which is the absolute distance using the formula below:

This is one of the most used methods to find a heuristic. Another popular method is the Manhattan distance. It is simply the distance of the L shape that can be formed from start to end. The formula is simply:

d(p,q) = |p1-q1| + |p2-q2|

Now comes the main score, the F score. It is simply the addition of the G and H score of the node.

F = G + H

Pseudo Code:

// here we are using an array as a open_set 
// but usually the open_set is implemented as a Priority Queue
// an array to store the evaluated node
open_set = [start]
// an array to store the shortest path
came_from = []
// Object in JavaScript
// dictionary in Python
g_score = dictionary for all nodes with value as Infinity
g_score[start] = 0
f_score = dictionary for all nodes with value as Infinity
f_score[start] = h_score(start)
while open_set is not empty:
// in Priority Queue, the lowest item will be removed automatically and returned
    current = node with lowest f_score in open_set
    if current == end:
        exit()
// if open_set is not implemented with priority queue, then remove the current node from the open_set
    open_set.remove(current)
neighbors = all neighbors of the current node
    for neighbor of neighbors:
        // calculating the g_score
        temp_g_score = g_score[current] + distance between current and the neighbor
        if temp_g_score < g_score[neighbor]:
            // updating the old g_score and f_score of the neighbor 
            g_score[neighbor] = temp_g_score
            h_score = heuristic of neighbor
            f_score[neighbor] = temp_g_score + h_score
            // adding the neighbor to open_set if it is not there
            if neighbor is not in open_set:
                open_set.append(neighbor)

Let’s consider a table (and consider the table as a graph for now).

The red circle is our start node and we need to go to the green node. Let’s find the path. The open_set will have only the start node initially. Now we enter the loop and get all the neighbors of the current node (which is the start node). The neighbors of the start node (assuming that we can move only left, right, up, down but not diagonally) are the node to its left but not the bottom node as it is a wall (we can’t go there). Now we need to evaluate the neighbor nodes. After searching through the table we get the table evaluated as below:

The number on the bottom left is the G score and the bottom right is the H score. F score is the addition of G and H score. When two nodes have the same F score, we can choose the node randomly or based on the order it was added. The algorithm may seem like searching through all the nodes and get the node with the lowest score, just like any other algorithm. It will make sense when you have a larger graph, it will neglect many nodes for evaluation which doesn’t make sense for evaluation. The algorithm goes directly towards the end node.

from queue import PriorityQueue
def heuristic(pos1, pos2):
 # Manhattan Distance
 return abs(pos1.row - pos2.row) + abs(pos2.col - pos1.col)
def a_star(game):
 grid = game.grid
 start = game.start
 end = game.end
count = 0
 open_set = PriorityQueue()
 open_set.put((0, count, start))
closed_set = [start]
g_scores = {item: float("inf") for row in grid for item in row}
 g_scores[start] = 0
f_score = {item: float("inf") for row in grid for item in row}
 f_score[start] = heuristic(start, end)
from_list = {}
while not open_set.empty():
  current = open_set.get()[2]
  closed_set.remove(current)
if current == end:
   // the path is available in from_list 
   return
for neighbour in current.get_neighbours(grid):
   temp_g_score = g_scores[current] + 1
if temp_g_score < g_scores[neighbour]:
    from_list[neighbour] = current
    
    g_scores[neighbour] = temp_g_score
    h_score = heuristic(neighbour, end)
    f_score = temp_g_score + h_score
if neighbour not in closed_set:
     count += 1
     open_set.put((f_score, count, neighbour))
     closed_set.append(neighbour)

Here in the Priority Queue, we can’t check whether an element is in that set or not, So, I have created a new list for holding the items in the open_set. I just name it as the closed_set. If you refer to any other algorithm explanation the closed set will be used to hold the visited node same goes here but with a different implementation. The came_from is referred to as the from_list here, I just have named it like that. The code was written in Python, you can implement the same with any other language

Thanks for reading