# What is A* Algorithm?

Nitika Sharma 10 Jun, 2024

## Introduction

The A* (A-star) algorithm is primarily used for pathfinding and graph traversal. It is famous for its efficiency in determining the shortest path. Fields such as artificial intelligence, robotics, and game development rely on this algorithm.

The A* algorithm’s key strength lies in its systematic exploration of a graph or grid. Starting from an initial node, it efficiently searches for the optimal path to the goal node. This efficiency is achieved by combining the comprehensive nature of Dijkstra’s algorithm and the heuristic approach of the Greedy Best-First Search.

The A* algorithm’s unique cost function sets it apart. By considering both the actual cost of reaching a node and an estimated heuristic of the remaining cost, it intelligently prioritizes the most promising paths. This dual consideration expedites the search, making it highly accurate and valuable.

In the subsequent article, we will delve into detailed examples of the A* algorithm in action, showcasing its effectiveness and versatility.

By maintaining a formal tone and using short, concise sentences, this version conveys the key points about the A* algorithm while retaining a professional and technical focus.

#### Overview

• Describe the primary use of A* in pathfinding and graph traversal.
• Explain the cost function components: g(n)g(n)g(n), h(n)h(n)h(n), and f(n)f(n)f(n).
• Identify and differentiate between Manhattan, Euclidean, and Diagonal heuristics.
• Implement the A* algorithm in Python for grid-based pathfinding.
• Recognize A*’s applications in AI, robotics, and game development.

## How Does the A* Algorithm Work?

The A* algorithm uses a combination of actual and heuristic distances to determine the best path. Here are the main components:

• g(n): The cost of the path from the start node to the current node nnn.
• h(n): A heuristic function that estimates the cost from node nnn to the goal.
• f(n): The total estimated cost of the path through node nnn (f(n)=g(n)+h(n)f(n) = g(n) + h(n)f(n)=g(n)+h(n)).

## A* Algorithm: Step-by-Step Guide

#### Initialization

• Create an open list to track nodes for evaluation.
• Make a closed list for nodes that have been evaluated.
• Add the start node to the open list, marking the beginning of your path.

#### Main Loop

• Continue until the open list is empty or the goal is reached:
• Select the node with the lowest f(x) value, indicating the most promising path.
• Move the selected node from the open list to the closed list.
• Examine each neighbor of the selected node to determine the next steps.

#### Evaluating Neighbors

• For each neighbor:
• If it is the goal, reconstruct the path and return it as the solution.
• Skip any neighbors already in the closed list, as they have been evaluated.
• If a neighbor is not in the open list:
• Add it and calculate its g(x), h(x), and f(x) values.
• For neighbors already in the open list:
• Check if the new path is more efficient (lower g(x) value).
• If so, update the g(x), h(x), and f(x) values, and set the current node as its parent

## Heuristics in A*

Heuristics are used to estimate the distance from the current node to the goal. Common heuristics include:

• Manhattan Distance: Used when movements are restricted to horizontal and vertical directions.
• Euclidean Distance: Used when movements can be in any direction.
• Diagonal Distance: Used when movements can be in eight possible directions (like a king in chess).

## Implementing A* Algorithm in Python

Now, let’s see how to implement the A* algorithm in Python. We’ll define a simple grid-based map where 0 represents walkable cells and 1 represents obstacles.

Code:

``````import heapq

import math

class Node:

def __init__(self, position, parent=None):

self.position = position

self.parent = parent

self.g = 0  # Distance from start node

self.h = 0  # Heuristic to goal

self.f = 0  # Total cost

def __eq__(self, other):

return self.position == other.position

def __lt__(self, other):

return self.f < other.f

def __repr__(self):

return f"({self.position}, f: {self.f})"

def heuristic(a, b):

return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def astar(maze, start, end):

open_list = []

closed_list = set()

start_node = Node(start)

end_node = Node(end)

heapq.heappush(open_list, start_node)

while open_list:

current_node = heapq.heappop(open_list)

if current_node == end_node:

path = []

while current_node:

path.append(current_node.position)

current_node = current_node.parent

return path[::-1]

for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:

node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])

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

if maze[node_position[0]][node_position[1]] != 0:

continue

new_node = Node(node_position, current_node)

if new_node.position in closed_list:

continue

new_node.g = current_node.g + 1

new_node.h = heuristic(new_node.position, end_node.position)

new_node.f = new_node.g + new_node.h

heapq.heappush(open_list, new_node)

return None

for node in open_list:

if neighbor == node and neighbor.g > node.g:

return False

return True

maze = [

[0, 1, 0, 0, 0, 0, 0],

[0, 1, 0, 1, 1, 1, 0],

[0, 0, 0, 0, 0, 0, 0],

[0, 1, 1, 1, 1, 1, 0],

[0, 0, 0, 0, 0, 0, 0]

]

start = (0, 0)

end = (4, 6)

path = astar(maze, start, end)

print(path)``````

Output:

[(0, 0), (1, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 6), (4, 6)]

#### Explanation of the Output

This path represents the sequence of steps from the starting point (0, 0) to the endpoint (4, 6). Here is a detailed step-by-step explanation of the traversal:

• Start at (0, 0): This is the initial position in the top-left corner of the maze.
• Move to (1, 0): Move one step down to the first row.
• Move to (2, 1): Move one step down and one step right, avoiding the obstacle in (1, 1).
• Move to (2, 2): Move one step right.
• Move to (2, 3): Move one step right.
• Move to (2, 4): Move one step right.
• Move to (2, 5): Move one step right.
• Move to (3, 6): Move diagonally down-right, skipping the obstacles and reaching the second last column in the third row.

Move to (4, 6): Move one step down to reach the goal position.

## Conclusion

This guide has provided a comprehensive overview of the A* algorithm’s functionality along with code implementation. A* algorithm is a valuable tool that simplifies complex problems, offering a strategic and efficient approach to finding optimal solutions.  I hope you find this article helpful in understanding this algorithm of python.

Q1. What is the A* algorithm?

A. A* is an informed search algorithm, a type of best-first search. It operates on weighted graphs, starting from a specific node and aiming to find the optimal path to the goal node. The algorithm considers various factors, such as distance and time, to identify the path with the smallest overall cost.

Q2. What is the AO Star algorithm?

A. The AO* algorithm employs AND-OR graphs to break down complex problems. The “AND” side of the graph represents interconnected tasks essential to achieving a goal, while the “OR” side stands for individual tasks. This approach simplifies problem-solving by identifying task dependencies and standalone actions.

Q3. What is the difference between the A* and AO* algorithms in AI?

A. A* finds the shortest path in single-path problems using a heuristic for cost estimation. AO* handles AND-OR decision graphs, solving subproblems with combined costs, ideal for complex decision-making and game-playing scenarios.

Nitika Sharma 10 Jun, 2024