A* Search Algorithm: Your Guide to Efficient Pathfinding

What is an A* Algorithm?

It is a search algorithm used to find the shortest path between an initial and a final point. It is often used for map traversal to find the shortest path. A* was initially designed as a graph traversal problem to help build a robot that can find its own course. It remains a widely popular algorithm for graph traversal.

It searches for shorter paths first, thus making it an optimal and complete algorithm. An optimal algorithm will find the least cost outcome for a problem, while a complete algorithm finds all the possible outcomes of a problem.

Another aspect that makes A* so powerful is its implementation of weighted graphs. A weighted graph uses numbers to represent the cost of taking each path or course of action. This means that the algorithms can take the path with the least cost, and find the best route in terms of distance and time.

Figure 1: Weighted Graph

A major drawback of the algorithm is its space and time complexity. It takes a large amount of space to store all possible paths and a lot of time to find them.

Want To Become an AI Engineer? Look No Further!

AI Engineer Master's ProgramExplore Program

Applications of A* Algorithm

The A* algorithm is widely used in various domains for pathfinding and optimization problems. It has applications in robotics, video games, route planning, logistics, and artificial intelligence. In robotics, A* helps robots navigate obstacles and find optimal paths. In video games, it enables NPCs to navigate game environments intelligently. Route planning applications use A* to find the shortest or fastest routes between locations. Logistics industries utilize A* for vehicle routing and scheduling. A* is also employed in AI systems, such as natural language processing and machine learning, to optimize decision-making processes. Its versatility and efficiency make it a valuable algorithm in many real-world scenarios.

Why A* Search Algorithm?

A* Search Algorithm is a simple and efficient search algorithm that can be used to find the optimal path between two nodes in a graph. It will be used for the shortest path finding. It is an extension of Dijkstra’s shortest path algorithm (Dijkstra’s Algorithm). The extension here is that, instead of using a priority queue to store all the elements, we use heaps (binary trees) to store them. The A* Search Algorithm also uses a heuristic function that provides additional information regarding how far away from the goal node we are. This function is used in conjunction with the f-heap data structure in order to make searching more efficient.

Let us now look at a brief explanation of the A* algorithm.

Explanation

In the event that we have a grid with many obstacles and we want to get somewhere as rapidly as possible, the A* Search Algorithms are our savior. From a given starting cell, we can get to the target cell as quickly as possible. It is the sum of two variables’ values that determines the node it picks at any point in time. 

At each step, it picks the node with the smallest value of ‘f’ (the sum of ‘g’ and ‘h’) and processes that node/cell. ‘g’ and ‘h’ is defined as simply as possible below:

• ‘g’ is the distance it takes to get to a certain square on the grid from the starting point, following the path we generated to get there. 
• ‘h’ is the heuristic, which is the estimation of the distance it takes to get to the finish line from that square on the grid.

Heuristics are basically educated guesses. It is crucial to understand that we do not know the distance to the finish point until we find the route since there are so many things that might get in the way (e.g., walls, water, etc.). In the coming sections, we will dive deeper into how to calculate the heuristics.

Let us now look at the detailed algorithm of A*. 

Become an Expert in All Things AI and ML!

AI Engineer Master's ProgramExplore Program

Algorithm

Initial condition - we create two lists - Open List and Closed List.

Now, the following steps need to be implemented -

• The open list must be initialized. 
• Put the starting node on the open list (leave its f at zero). Initialize the closed list. 
• Follow the steps until the open list is non-empty:

1. Find the node with the least f on the open list and name it “q”.
2. Remove Q from the open list.
3. Produce q's eight descendants and set q as their parent.
4. For every descendant:

i) If finding a successor is the goal, cease looking

ii)Else, calculate g and h for the successor.

successor.g = q.g + the calculated distance between the successor and the q.

successor.h = the calculated distance between the successor and the goal. We will cover three heuristics to do this: the Diagonal, the Euclidean, and the Manhattan heuristics.

successor.f = successor.g plus successor.h

iii) Skip this successor if a node in the OPEN list with the same location as it but a lower f value than the successor is present.

iv) Skip the successor if there is a node in the CLOSED list with the same position as the successor but a lower f value; otherwise, add the node to the open list end (for loop).

• Push Q into the closed list and end the while loop.

We will now discuss how to calculate the Heuristics for the nodes.

Heuristics

We can easily calculate g, but how do we calculate h? 

There are two methods that we can use to calculate the value of h:

1. Determine h's exact value (which is certainly time-consuming).

(or)

2. Utilize various techniques to approximate the value of h. (less time-consuming).

Let us discuss both methods.

Exact Heuristics

Although we can obtain exact values of h, doing so usually takes a very long time.

The ways to determine h's precise value are listed below.

1. Before using the A* Search Algorithm, pre-calculate the distance between every pair of cells.

2. Using the distance formula/Euclidean Distance, we may directly determine the precise value of h in the absence of blocked cells or obstructions.

Let us look at how to calculate Approximation Heuristics.

Approximation Heuristics

To determine h, there are typically three approximation heuristics:

1. Manhattan Distance

The Manhattan Distance is the total of the absolute values of the discrepancies between the x and y coordinates of the current and the goal cells. 

The formula is summarized below -

h = abs (curr_cell.x – goal.x) + 

     abs (curr_cell.y – goal.y)

We must use this heuristic method when we are only permitted to move in four directions - top, left, right, and bottom.

Let us now take a look at the Diagonal Distance method to calculate the heuristic.

2. Diagonal Distance

It is nothing more than the greatest absolute value of differences between the x and y coordinates of the current cell and the goal cell. 

This is summarized below in the following formula -

dx = abs(curr_cell.x – goal.x)

dy = abs(curr_cell.y – goal.y)

h = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

where D is the length of every node (default = 1) and D2 is the diagonal

We use this heuristic method when we are permitted to move only in eight directions, like the King’s moves in Chess.

Let us now take a look at the Euclidean Distance method to calculate the heuristic.

3. Euclidean Distance

The Euclidean Distance is the distance between the goal cell and the current cell using the distance formula:

 h = sqrt ( (curr_cell.x – goal.x)^2 + 

            (curr_cell.y – goal.y)^2 )

We use this heuristic method when we are permitted to move in any direction of our choice.

Your AI/ML Career is Just Around The Corner!

AI Engineer Master's ProgramExplore Program

The Basic Concept of A* Algorithm

A heuristic algorithm sacrifices optimality, with precision and accuracy for speed, to solve problems faster and more efficiently.

All graphs have different nodes or points which the algorithm has to take, to reach the final node. The paths between these nodes all have a numerical value, which is considered as the weight of the path. The total of all paths transverse gives you the cost of that route.

Initially, the Algorithm calculates the cost to all its immediate neighboring nodes,n, and chooses the one incurring the least cost. This process repeats until no new nodes can be chosen and all paths have been traversed. Then, you should consider the best path among them. If f(n) represents the final cost, then it can be denoted as :

f(n) = g(n) + h(n), where :

g(n) = cost of traversing from one node to another. This will vary from node to node

h(n) = heuristic approximation of the node's value. This is not a real value but an approximation cost

Master Tools You Need For Becoming an AI Engineer

AI Engineer Master's ProgramExplore Program

How Does the A* Algorithm Work?

Figure 2: Weighted Graph 2

Consider the weighted graph above, which contains nodes and the distance between them. Let's say you start from A and have to go to D.

Now, since the start is at the source A, which will have some initial heuristic value. Hence, the results are

f(A) = g(A) + h(A)
f(A) = 0 + 6 = 6

Next, take the path to other neighboring vertices :

f(A-B) = 1 + 4

f(A-C) = 5 + 2

Now take the path to the destination from these nodes, and calculate the weights :

f(A-B-D) = (1+ 7) + 0

f(A-C-D) = (5 + 10) + 0

It is clear that node B gives you the best path, so that is the node you need to take to reach the destination.

Pseudocode of A* Algorithm

The text below represents the pseudocode of the Algorithm. It can be used to implement the algorithm in any programming language and is the basic logic behind the Algorithm.

• Make an open list containing starting node
  • If it reaches the destination node :
• Make a closed empty list 
• If it does not reach the destination node, then consider a node with the lowest f-score in the open list

We are finished

• Else :

Put the current node in the list and check its neighbors

• For each neighbor of the current node :
• If the neighbor has a lower g value than the current node and is in the closed list:

Replace neighbor with this new node as the neighbor’s parent

• Else If (current g is lower and neighbor is in the open list):

Replace the neighbor with the lower g value and change the neighbor’s parent to the current node.

• Else If the neighbor is not in both lists:

Add it to the open list and set its g

How to Implement the A* Algorithm

1. How to Implement the A* Algorithm in Python

Consider the graph shown below. The nodes are represented in pink circles, and the weights of the paths along the nodes are given. The numbers above the nodes represent the heuristic value of the nodes.

Figure 3: Weighted graph for A* Algorithm

You start by creating a class for the algorithm. Now, describe the open and closed lists. Here, you are using sets and two dictionaries - one to store the distance from the starting node, and another for parent nodes. And initialize them to 0, and the start node.

Figure 4: Initializing important parameters

Now, find the neighboring node with the lowest f(n) value. You must also code for the condition of reaching the destination node. If this is not the case, put the current node in the open list if it's not already on it, and set its parent nodes.

Figure 5: Adding nodes to open list and setting parents of nodes

If the neighbor has a lower g value than the current node and is in the closed list, replace it with this new node as the neighbor's parent.

Figure 6: Checking distances and updating the g values

If the current g is lower than the previous g, and its neighbor is in the open list, replace it with the lower g value and change the neighbor's parent to the current node.

If the neighbor is not in both lists, add it to the open list and set its g value.

Figure 7: Checking distances, updating the g values, and adding parents

Now, define a function to return neighbors and their distances.

                                              Figure 8: Defining neighbors

Also, create a function to check the heuristic values.

Figure 9: Defining a function to return heuristic values

Let’s describe our graph and call the A star function.

Figure 10: Calling A* function

The algorithm traverses through the graph and finds the path with the least cost

 which is through E => D => G.

2. How to Implement the A* Algorithm in C++

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cmath>

struct Node {
    int x, y;
    float g, h;
    Node* parent;

    Node(int x, int y, float g, float h, Node* parent = nullptr)
        : x(x), y(y), g(g), h(h), parent(parent) {}

    float f() const { return g + h; }

    bool operator<(const Node& other) const {
        return f() > other.f();
    }
};

float heuristic(int x1, int y1, int x2, int y2) {
    return std::sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

std::vector<Node> get_neighbors(const Node& node, const std::vector<std::vector<int>>& grid) {
    std::vector<Node> neighbors;
    std::vector<std::pair<int, int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    for (auto& dir : directions) {
        int newX = node.x + dir.first;
        int newY = node.y + dir.second;
        if (newX >= 0 && newX < grid.size() && newY >= 0 && newY < grid[0].size() && grid[newX][newY] == 0) {
            neighbors.emplace_back(newX, newY, node.g + 1, 0, nullptr);
        }
    }
    return neighbors;
}

void reconstruct_path(Node* node) {
    while (node) {
        std::cout << "(" << node->x << "," << node->y << ") ";
        node = node->parent;
    }
    std::cout << std::endl;
}

void astar(const std::vector<std::vector<int>>& grid, int startX, int startY, int goalX, int goalY) {
    std::priority_queue<Node> openList;
    std::unordered_map<int, std::unordered_map<int, Node*>> allNodes;

    Node* startNode = new Node(startX, startY, 0, heuristic(startX, startY, goalX, goalY));
    openList.push(*startNode);
    allNodes[startX][startY] = startNode;

    while (!openList.empty()) {
        Node current = openList.top();
        openList.pop();

        if (current.x == goalX && current.y == goalY) {
            reconstruct_path(&current);
            return;
        }

        auto neighbors = get_neighbors(current, grid);
        for (auto& neighbor : neighbors) {
            neighbor.h = heuristic(neighbor.x, neighbor.y, goalX, goalY);
            neighbor.parent = allNodes[current.x][current.y];

            if (!allNodes[neighbor.x][neighbor.y] || neighbor.g < allNodes[neighbor.x][neighbor.y]->g) {
                allNodes[neighbor.x][neighbor.y] = new Node(neighbor);
                openList.push(neighbor);
            }
        }
    }

    std::cout << "No path found" << std::endl;
}

3. How to Implement the A* Algorithm in Java

import java.util.*;

class Node implements Comparable<Node> {
    int x, y;
    double g, h;
    Node parent;

    Node(int x, int y, double g, double h, Node parent) {
        this.x = x;
        this.y = y;
        this.g = g;
        this.h = h;
        this.parent = parent;
    }

    double f() {
        return g + h;
    }

    @Override
    public int compareTo(Node other) {
        return Double.compare(this.f(), other.f());
    }
}

public class AStar {
    static double heuristic(int x1, int y1, int x2, int y2) {
        return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
    }

    static List<Node> getNeighbors(Node node, int[][] grid) {
        List<Node> neighbors = new ArrayList<>();
        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        for (int[] dir : directions) {
            int newX = node.x + dir[0];
            int newY = node.y + dir[1];
            if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 0) {
                neighbors.add(new Node(newX, newY, node.g + 1, 0, null));
            }
        }
        return neighbors;
    }

    static void reconstructPath(Node node) {
        while (node != null) {
            System.out.print("(" + node.x + "," + node.y + ") ");
            node = node.parent;
        }
        System.out.println();
    }

    static void astar(int[][] grid, int startX, int startY, int goalX, int goalY) {
        PriorityQueue<Node> openList = new PriorityQueue<>();
        Map<String, Node> allNodes = new HashMap<>();

        Node startNode = new Node(startX, startY, 0, heuristic(startX, startY, goalX, goalY), null);
        openList.add(startNode);
        allNodes.put(startX + "," + startY, startNode);

        while (!openList.isEmpty()) {
            Node current = openList.poll();

            if (current.x == goalX && current.y == goalY) {
                reconstructPath(current);
                return;
            }

            for (Node neighbor : getNeighbors(current, grid)) {
                neighbor.h = heuristic(neighbor.x, neighbor.y, goalX, goalY);
                neighbor.parent = current;

                String key = neighbor.x + "," + neighbor.y;
                if (!allNodes.containsKey(key) || neighbor.g < allNodes.get(key).g) {
                    allNodes.put(key, neighbor);
                    openList.add(neighbor);
                }
            }
        }

        System.out.println("No path found");
    }
}

4. How to Implement the A* Algorithm in C#

using System;
using System.Collections.Generic;

class Node : IComparable<Node> {
    public int x, y;
    public float g, h;
    public Node parent;

    public Node(int x, int y, float g, float h, Node parent = null) {
        this.x = x;
        this.y = y;
        this.g = g;
        this.h = h;
        this.parent = parent;
    }

    public float F() {
        return g + h;
    }

    public int CompareTo(Node other) {
        return F().CompareTo(other.F());
    }
}

class AStar {
    static float Heuristic(int x1, int y1, int x2, int y2) {
        return (float)Math.Sqrt(Math.Pow(x2 - x1, 2) + Math.Pow(y2 - y1, 2));
    }

    static List<Node> GetNeighbors(Node node, int[,] grid) {
        List<Node> neighbors = new List<Node>();
        int[,] directions = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

        for (int i = 0; i < directions.GetLength(0); i++) {
            int newX = node.x + directions[i, 0];
            int newY = node.y + directions[i, 1];
            if (newX >= 0 && newX < grid.GetLength(0) && newY >= 0 && newY < grid.GetLength(1) && grid[newX, newY] == 0) {
                neighbors.Add(new Node(newX, newY, node.g + 1, 0, null));
            }
        }
        return neighbors;
    }

    static void ReconstructPath(Node node) {
        while (node != null) {
            Console.Write($"({node.x},{node.y}) ");
            node = node.parent;
        }
        Console.WriteLine();
    }

    public static void AStarSearch(int[,] grid, int startX, int startY, int goalX, int goalY) {
        PriorityQueue<Node> openList = new PriorityQueue<Node>();
        Dictionary<string, Node> allNodes = new Dictionary<string, Node>();

        Node startNode = new Node(startX, startY, 0, Heuristic(startX, startY, goalX, goalY));
        openList.Enqueue(startNode);
        allNodes.Add($"{startX},{startY}", startNode);

        while (openList.Count > 0) {
            Node current = openList.Dequeue();

            if (current.x == goalX && current.y == goalY) {
                ReconstructPath(current);
                return;
            }

            foreach (Node neighbor in GetNeighbors(current, grid)) {
                neighbor.h = Heuristic(neighbor.x, neighbor.y, goalX, goalY);
                neighbor.parent = current;

                string key = $"{neighbor.x},{neighbor.y}";
                if (!allNodes.ContainsKey(key) || neighbor.g < allNodes[key].g) {
                    allNodes[key] = neighbor;
                    openList.Enqueue(neighbor);
                }
            }
        }

        Console.WriteLine("No path found");
    }
}

5. How to Implement the A* Algorithm in JavaScript

class Node {
    constructor(x, y, g, h, parent = null) {
        this.x = x;
        this.y = y;
        this.g = g;
        this.h = h;
        this.parent = parent;
    }

    f() {
        return this.g + this.h;
    }
}

function heuristic(x1, y1, x2, y2) {
    return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
}

function getNeighbors(node, grid) {
    const neighbors = [];
    const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]];

    for (const [dx, dy] of directions) {
        const newX = node.x + dx;
        const newY = node.y + dy;
        if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] === 0) {
            neighbors.push(new Node(newX, newY, node.g + 1, 0, null));
        }
    }
    return neighbors;
}

function reconstructPath(node) {
    while (node) {
        console.log(`(${node.x},${node.y})`);
        node = node.parent;
    }
}

function astar(grid, startX, startY, goalX, goalY) {
    const openList = [];
    const allNodes = new Map();

    const startNode = new Node(startX, startY, 0, heuristic(startX, startY, goalX, goalY));
    openList.push(startNode);
    allNodes.set(`${startX},${startY}`, startNode);

    while (openList.length > 0) {
        openList.sort((a, b) => a.f() - b.f());
        const current = openList.shift();

        if (current.x === goalX && current.y === goalY) {
            reconstructPath(current);
            return;
        }

        const neighbors = getNeighbors(current, grid);
        for (const neighbor of neighbors) {
            neighbor.h = heuristic(neighbor.x, neighbor.y, goalX, goalY);
            neighbor.parent = current;

            const key = `${neighbor.x},${neighbor.y}`;
            if (!allNodes.has(key) || neighbor.g < allNodes.get(key).g) {
                allNodes.set(key, neighbor);
                openList.push(neighbor);
            }
        }
    }

    console.log("No path found");
}

These implementations are basic and assume a grid-based map where 0 represents a walkable cell, and any other value represents an obstacle. The A* algorithm uses a priority queue (or similar structure) to explore nodes with the lowest cost first. The heuristic used is the Euclidean distance, but other heuristics like Manhattan distance can also be applied depending on the problem.

Make sure to adjust these implementations to fit the specific needs of your application, such as adding more sophisticated handling of obstacles, implementing a better priority queue, or improving the path reconstruction.

Advantages of A* Algorithm in AI

The A* algorithm offers several advantages.

• Firstly, it guarantees finding the optimal path when used with appropriate heuristics.
• Secondly, it is efficient and can handle large search spaces by effectively pruning unpromising paths.
• Thirdly, it can be easily tailored to accommodate different problem domains and heuristics.
• Fourthly, A* is flexible and adaptable to varying terrain costs or constraints. Additionally, it is widely implemented and has a vast amount of resources and support available.

Overall, the advantages of A* algorithm in AI make it a popular choice for solving pathfinding and optimization problems.

Disadvantages of A* Algorithm in AI

While the A* algorithm in AI has numerous advantages, it also has some limitations.

• One disadvantage is that A* can be computationally expensive in certain scenarios, especially when the search space is extensive and the number of possible paths is large.
• The algorithm may consume significant memory and processing resources.
• Another limitation is that A* heavily relies on the quality of the heuristic function. If the heuristic is poorly designed or does not accurately estimate the distance to the goal, the algorithm's performance and optimality may be compromised.
• Additionally, A* may struggle with certain types of graphs or search spaces that exhibit irregular or unpredictable structures.

What if the search space in A* Algorithm is not a grid and is a graph?

The A* algorithm can be applied to non-grid search spaces that are represented as graphs. In this case, the nodes in the graph represent states or locations, and the edges represent the connections or transitions between them. The key difference lies in the definition of neighbors for each node, which is determined by the edges in the graph rather than the adjacent cells in a grid. A* algorithm can still be used to find the optimal path in such graph-based search spaces by appropriately defining the heuristic function and implementing the necessary data structures and algorithms to traverse the graph.

Want To Become an AI Engineer? Look No Further!

AI Engineer Master's ProgramExplore Program

A* Algorithm Example

A* has been successfully applied in numerous real-world scenarios. For instance, in robotic path planning, A* helps robots navigate through dynamic environments while avoiding obstacles. In game development, A* is used to create intelligent enemy AI that can chase and follow the player efficiently. In logistics and transportation, A* assists in finding the optimal routes for delivery vehicles, minimizing time and cost. Additionally, A* algorithm has applications in network routing, such as finding the shortest path in a computer network. These examples highlight the versatility and practicality of A* algorithm concepts and implementations in various domains.

Master the A* Algorithm in AI

In this tutorial, an introduction to the powerful search algorithm’, you learned about everything about the algorithm and saw the basic concept behind it. You then looked into the working of the algorithm, and the pseudocode for A*.

Simplilearn's Artificial Intelligence Engineer Master Program is designed to help learners decode the mystery of artificial intelligence and its business applications. The course helps you master the AI concepts and workflows, machine learning and deep learning, NLP, generati9ve AI and more. Explore and enroll today!

Choose the Right Program

Supercharge your career in AI and ML with Simplilearn's comprehensive courses. Gain the skills and knowledge to transform industries and unleash your true potential. Enroll now and unlock limitless possibilities!

Program Name	AI Engineer	Post Graduate Program In Artificial Intelligence	Post Graduate Program In Artificial Intelligence
Geo	All Geos	All Geos	IN/ROW
University	Simplilearn	Purdue	Caltech
Course Duration	11 Months	11 Months	11 Months
Coding Experience Required	Basic	Basic	No
Skills You Will Learn	10+ skills including data structure, data manipulation, NumPy, Scikit-Learn, Tableau and more.	16+ skills including chatbots, NLP, Python, Keras and more.	8+ skills including Supervised & Unsupervised Learning Deep Learning Data Visualization, and more.
Additional Benefits	Get access to exclusive Hackathons, Masterclasses and Ask-Me-Anything sessions by IBM Applied learning via 3 Capstone and 12 Industry-relevant Projects	Purdue Alumni Association Membership Free IIMJobs Pro-Membership of 6 months Resume Building Assistance	Upto 14 CEU Credits Caltech CTME Circle Membership
Cost	$$	$$$$	$$$$
	Explore Program	Explore Program	Explore Program

FAQs

1. Why is it called the A* algorithm in AI?

The A* algorithm gets its name from two key features. The "A" stands for "Admissible" as it uses an admissible heuristic to estimate costs. The "*" signifies that it combines actual and estimated costs to make informed decisions during the search process.

2. What are the properties of A* algorithm in AI?

The A* algorithm possesses properties of completeness, optimality, and efficiency. It guarantees finding a solution if one exists (completeness), finds the optimal path with the lowest cost (optimality), and efficiently explores fewer nodes by utilizing heuristics (efficiency).

3. What are the main components of A* algorithm in AI?

The main components of the A* algorithm include an open list to track nodes to explore, a closed list to store evaluated nodes, a heuristic function to estimate costs, a cost function to assign costs to actions, and a priority queue to determine the order of node expansion based on estimated costs.