Implementing the A* Search Algorithm in Python

Updated: at 04:23 AM

The A* (pronounced “A star”) search algorithm is one of the most popular and effective pathfinding algorithms used in computer science and artificial intelligence. It is an informed search method that aims to find the shortest path between a starting node and a goal node in a graph or grid by exploiting heuristics to guide its search.

In this comprehensive guide, we will learn how to implement the A* algorithm in Python step-by-step, with example code snippets and detailed explanations.

Table of Contents

Open Table of Contents

Overview of the A* Algorithm

The A* algorithm is best suited for pathfinding problems in graphs and grids, where you need to find the shortest path between two points. It combines features of both uniform-cost search and pure heuristic search to efficiently compute optimal solutions.

Some key properties of A*:

At a high level, A* algorithm works as follows:

  1. Initialize open and closed list of nodes
  2. Set starting node as current node
  3. Loop until solution found:
    • Consider current node’s neighbors
    • Add neighbors to open list
    • Set f-cost for each neighbor (g+h)
    • Sort open list by lowest f-cost
    • Set lowest f-cost node as current node
    • Move current node to closed list
  4. Reconstruct path by traversing pointers backwards from goal

Where:

By leveraging heuristics, A* can find optimal solutions faster than brute force methods.

Implementing the A* Algorithm in Python

We will implement a basic version of the A* algorithm for pathfinding in a 2D grid/graph.

Our implementation will have the following key components:

Let’s go through each section step-by-step:

The Node Class

First, we’ll create a Node class to represent each node on our 2D grid map. Each node will store its position on the grid, its neighbors, and other useful data.

class Node:

    def __init__(self, pos: tuple, g_cost: float, h_cost: float):
        self.pos = pos # (x, y) tuple
        self.g_cost = g_cost
        self.h_cost = h_cost
        self.f_cost = self.g_cost + self.h_cost

        self.parent = None #previous node

The __init__() constructor takes a position tuple, g_cost and h_cost values. It calculates the f_cost and sets the initial parent to None.

We’ll also add comparator methods to the Node class so we can compare and sort nodes efficiently:

    def __lt__(self, other):
        return self.f_cost < other.f_cost

This __lt__() method allows us to compare two nodes using their f_cost values.

A* Search Algorithm

Next, we’ll implement the main A* search logic inside an AStar class:

class AStar:

    def __init__(self, map_grid):
        self.open = [] #open list
        self.closed = [] #closed list
        self.map_grid = map_grid

The __init__() method takes the grid map as input and initializes the open and closed lists to empty.

    def search(self, start_node, goal_node):

        self.open.append(start_node)

        while self.open:

            #sort open list to get node with lowest cost first
            self.open.sort()
            current_node = self.open.pop(0)

            #add current node to closed list
            self.closed.append(current_node)

            if current_node == goal_node:
                #reached goal node
                return self.reconstruct_path(goal_node)

            #check every neighbor
            neighbors = self.get_neighbors(current_node)

            for neighbor in neighbors:
                if neighbor in self.closed:
                    continue

                g_cost = current_node.g_cost + 1 #cost to move
                h_cost = self.heuristic(neighbor, goal_node)
                f_cost = g_cost + h_cost

                #check if we found cheaper path
                if neighbor in self.open:
                    if neighbor.f_cost > f_cost:
                        self.update_node(neighbor, g_cost, h_cost)
                else:
                    self.update_node(neighbor, g_cost, h_cost)

        #no path found
        return None

The main search() method takes the start and goal nodes as input. We add the start node to the open list to begin.

It then loops while there are nodes in the open list, sorting it to get the lowest f-cost node each iteration.

We pop the node off and add it to closed. Check if it is our goal, return the path if so.

Otherwise, look at the current node’s neighbors. For each valid new neighbor, calculate costs and update its values if we found a lower cost path.

Next we need to implement the helper methods called by search():

    def get_neighbors(self, node):
        pass #calculate valid adjacent nodes

    def heuristic(self, node, goal):
        pass #estimate cost to goal

    def reconstruct_path(self, goal_node):
        pass #follow parents back to start

    def update_node(self, node, g_cost, h_cost):
        pass #update if we find better path

Helper Functions

Let’s implement the helper methods:

    def get_neighbors(self, node):
        dirs = [[1,0], [0,1], [-1,0], [0,-1]]
        neighbors = []

        for dir in dirs:
            neighbor_pos = (node.pos[0] + dir[0], node.pos[1] + dir[1])

            #check if new pos in bounds
            if (0 <= neighbor_pos[0] < self.map_grid.shape[0] and
                0 <= neighbor_pos[1] < self.map_grid.shape[1]):

                #check if traversable
                if self.map_grid[neighbor_pos] != 1:
                    neighbors.append(neighbor_pos)

        return neighbors

get_neighbors() calculates the adjacent nodes, ensuring they are within grid bounds and not blocked.

For the heuristic, we’ll use the Manhattan distance, which is the absolute grid distance between two points:

    def heuristic(self, node, goal):
        d = abs(node.pos[0] - goal.pos[0]) + abs(node.pos[1] - goal.pos[1])
        return d

To reconstruct the path after finding the goal node:

    def reconstruct_path(self, goal_node):
        path = [goal_node]
        current = goal_node

        while current.parent != start_node:
            path.append(current.parent)
            current = current.parent

        return path[::-1] #reverse path

We follow parent nodes backwards until the start, then reverse the list.

Finally, to update a node if we find a better path:

    def update_node(self, node, g_cost, h_cost):
        node.g_cost = g_cost
        node.h_cost = h_cost
        node.f_cost = g_cost + h_cost
        node.parent = current_node

This updates the node’s cost values if the new f-cost is lower.

And that covers the core A* algorithm implementation in Python!

Example Usage

Let’s look at a simple example of using our AStar class to find a path on a small grid:

grid = np.array([
    [0,0,0,0,1],
    [0,0,0,0,0],
    [0,0,1,0,0],
    [0,0,1,0,0],
    [0,0,0,0,0]
])

start = Node((0,0))
goal = Node((len(grid)-1, len(grid[0])-1))

astar = AStar(grid)
path = astar.search(start, goal)

We create a 5x5 grid with some obstacles, define the start and end nodes, instantiate the AStar class, and call search() to find the shortest path from start to goal while avoiding obstacles.

The returned path contains a list of node positions that form the optimal path. We can render this visually on the grid map.

This demonstrates how to apply the A* algorithm to grid pathfinding problems in a simple Python implementation.

Optimizations and Improvements

There are many ways we can optimize or extend our basic A* implementation:

Applying these optimizations can significantly improve A* performance on larger graphs and complex grids.

Some other ideas for improvements:

There is substantial scope to tailor the A* implementation to your specific use case. The algorithm is very versatile.

The A* algorithm excels at finding shortest paths in graphs and grids. This makes it applicable to a wide range of problems:

Pathfinding - Navigation in video games, maps, robotics

Travel routing - Find fastest route in road networks, public transit

Wire routing - Laying out circuit designs

Board games - Chess, checkers, puzzles like the 15-puzzle

Network routing - Optimizing packet routing in networks

Machine learning - Heuristic search in decision trees, neural networks

Bioinformatics - Alignment of protein or gene sequences

Robotics - Motion planning algorithms for robots

A* combines heuristic guidance with guaranteed optimality, making it a go-to approach for shortest path problems across many domains.

Summary

In this guide, we learned how to implement the powerful A* pathfinding algorithm in Python through an object-oriented approach:

The A* algorithm is widely used for finding shortest paths due to its excellent performance. This step-by-step Python implementation guide provides a solid foundation for applying A* to pathfinding problems in any graph-based domain.