What is the A* algorithm?

Explanation

A* algorithm has 3 parameters:

g : the cost of moving from the initial cell to the current cell. Basically, it is the sum of all the cells that have been visited since leaving the first cell.
h : also known as the heuristic value, it is the estimated cost of moving from the current cell to the final cell. The actual cost cannot be calculated until the final cell is reached. Hence, h is the estimated cost. We must make sure that there is never an over estimation of the cost.
f : it is the sum of g and h. So, f = g + h

The way that the algorithm makes its decisions is by taking the f-value into account. The algorithm selects the smallest f-valued cell and moves to that cell. This process continues until the algorithm reaches its goal cell.

class box():
    """A box class for A* Pathfinding"""
    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position
        self.g = 0
        self.h = 0
        self.f = 0
    def __eq__(self, other):
        return self.position == other.position
def astar(maze, start, end):
    """Returns a list of tuples as a path from the given start to the given end in the given board"""
    # Create start and end node
    start_node = box(None, start)
    start_node.g = start_node.h = start_node.f = 0
    end_node = box(None, end)
    end_node.g = end_node.h = end_node.f = 0
    # Initialize both open and closed list
    open_list = []
    closed_list = []
    # Add the start node
    open_list.append(start_node)
    # Loop until you find the end
    while len(open_list) > 0:
        # Get the current node
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index
        # Pop current off open list, add to closed list
        open_list.pop(current_index)
        closed_list.append(current_node)
        # Found the goal
        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1] # Return reversed path
        # Generate children
        children = []
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares
            # Get node position
            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
            # Make sure within range
            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0:
                continue
            # Make sure walkable terrain
            if maze[node_position[0]][node_position[1]] != 0:
                continue
            # Create new node
            new_node = box(current_node, node_position)
            # Append
            children.append(new_node)
        # Loop through children
        for child in children:
            # Child is on the closed list
            for closed_child in closed_list:
                if child == closed_child:
                    continue
            # Create the f, g, and h values
            child.g = current_node.g + 1
            child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2)
            child.f = child.g + child.h
            # Child is already in the open list
            for open_node in open_list:
                if child == open_node and child.g > open_node.g:
                    continue
            # Add the child to the open list
            open_list.append(child)
def main():
    board = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
    start = (0, 0)
    end = (6, 6)
    path = astar(board, start, end)
    print(path)
if __name__ == '__main__':
    main()

Explanation

Line 1-10: We a class named box. It's used as a representation for each node in the pathfinding algorithm. Each node has a parent, a position, and values g, h, and f representing the cost functions used in the A* algorithm.
Line 12 - 13: The method defines how two box objects are compared for equality and compares their position.
Line 16-96: This function takes a 2D array (a maze) in this scenerio and a starting and ending position.
- Line 25-30: Initialization of open and closed lists for nodes.
- Line 33: This loop continues until the open list is empty.
- Line 36-41: Find the node in the list with the lowest f value.
- Line 44-45: Moves the node from the open list to the closed list.
- Line 48-54: If the current node is the end node, reconstruct and return the path by following the parent pointers back to the start node.
- Line 57-58: Generate possible adjacent positions (neighbours) to the current node.
- Line 61-65: Check if the generated position is within the maze boundaries.
- Line 68-68: Check if the generated position is a walkable terrain (0 in the maze).
- Line 78-96: Iterate through the children and check if any child is already in the closed list then calculate the g, h, and f values for the child node. Check if the child is already in the open list and if so, compare their g values. Now, Add the child to the open list if it's not already there or if it has a lower g value.

Now, lets see another example with different problem.

Let's consider a real-life application of the A* algorithm in robotics: path planning for a mobile robot in a warehouse environment.

Imagine a scenario where a robot needs to navigate through a warehouse to deliver goods from a starting location to various destinations. The warehouse layout includes:

Shelves
Aisles
Obstacles

The robot needs to find the shortest path while avoiding collisions.

Condition: The robot can move horizontally and vertically between adjacent cells, but it cannot move diagonally.

Let's see the solution to the problem.

Code

class Node:
    def __init__(self, x, y, g=float('inf'), h=0, f=float('inf'), parent=None):
        self.x = x
        self.y = y
        self.g = g  # tentative distance from start node
        self.h = h  # heuristic distance to goal node
        self.f = f  # total estimated distance: f = g + h
        self.parent = parent  # parent node
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    def __hash__(self):
        return hash((self.x, self.y))
def heuristic(node, goal):
    # Manhattan distance heuristic
    return abs(node.x - goal.x) + abs(node.y - goal.y)
def find_min_f_node(open_list):
    min_f_node = open_list[0]
    for node in open_list:
        if node.f < min_f_node.f:
            min_f_node = node
    return min_f_node
def astar(start, goal, warehouse):
    open_list = []
    closed_set = set()
    open_list.append(start)
    start.g = 0
    start.f = start.g + heuristic(start, goal)
    while open_list:
        current = find_min_f_node(open_list)
        open_list.remove(current)
        if current == goal:
            path = []
            while current:
                path.append((current.x, current.y))
                current = current.parent
            return path[::-1]
        closed_set.add(current)
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_x, next_y = current.x + dx, current.y + dy
            if 0 <= next_x < len(warehouse) and 0 <= next_y < len(warehouse[0]) and warehouse[next_x][next_y] != 1:
                neighbor = Node(next_x, next_y)
                if neighbor in closed_set:
                    continue
                tentative_g = current.g + 1  # assuming constant cost of movement
                if tentative_g < neighbor.g:
                    neighbor.parent = current
                    neighbor.g = tentative_g
                    neighbor.h = heuristic(neighbor, goal)
                    neighbor.f = neighbor.g + neighbor.h
                    if neighbor not in open_list:
                        open_list.append(neighbor)
    return None  # No path found
def main():
    warehouse = [
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
    ]
    # Define start and goal nodes
    start = Node(0, 0)
    goal = Node(6, 6)
    # Find path
    path = astar(start, goal, warehouse)
    # Output the result
    if path:
        print("Path found:")
        for node in path:
            print(node)
    else:
        print("No path found")
if __name__ == '__main__':
    main()

Explanation

Line 10-11: The __eq__ method is overridden to allow comparison between nodes using their coordinates.
Line 13-14: This method is implemented to allow nodes to be used as keys in sets.
Line 16-18: This function uses manhattan distance to calculate the heuristic distance between nodes.
Line 48-65: For each node in the open list, it examines its neighbors (up, down, left, and right) and calculates their tentative distances (g). If a shorter path to a neighbor is found, it updates the neighbor's g, h, and f values and adds it to the open list.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is the A* algorithm?

How it works

Explanation

Example

Code

Explanation

Code

Explanation