In this tutorial, we will be implementing the A (pronounced "A-star") algorithm in AI. The A algorithm is a popular choice for pathfinding and graph traversal, which involves finding a path between multiple points, called "nodes". It is widely used in AI for a variety of tasks, like finding the shortest route between two points on a map.
By the end of this tutorial, you'll have a solid understanding of how the A* algorithm works and how to implement it in AI.
Prerequisites: Basic understanding of Python and Graph Theory.
The A* algorithm uses a best-first search and finds the least-cost path from a given initial node to one goal node. It uses a heuristic to estimate the cost to reach the goal, thus ensuring high performance.
Here is a simple implementation of the A* algorithm using Python:
class Node():
"""A node 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
In the snippet above, we first define a Node class that we'll use to represent the nodes in our path. Each node has a parent (the node that led to this node), a position (its location), and g, h, and f values.
Before we continue, let's define some helper functions:
def return_path(current_node):
"""Returns the path from the start node to the given node"""
path = []
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
return path[::-1] # Return reversed path
This function return_path will return the path from the start node to the current node.
Now, let's implement the core of the A* algorithm:
def astar(maze, start, end):
"""Returns a list of tuples as a path from the given start to the given end in the given maze"""
# Create start and end node
start_node = Node(None, start)
end_node = Node(None, end)
# 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:
return return_path(current_node)
# 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
# Create new node
new_node = Node(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)
In the astar function above, we first create the start_node and end_node. We then initialize the open_list and closed_list which will hold the nodes we're considering (open) and have already considered (closed).
We then begin our main loop, which continues until we've considered all nodes or found the end_node. For each node, we calculate its g, h, and f values and check if we've found a more efficient path.
In this tutorial, we've covered how to implement the A algorithm in AI. We've learned about nodes, heuristic, g-cost, h-cost, and f-cost. We've also walked through a simple Python code that demonstrates how the A algorithm works.
For further learning, you can try implementing different heuristics and compare their efficiency. You can also try implementing A* algorithm on different types of graphs.
astar function to work with a weighted graph.Each of these exercises will help reinforce what you've learned and give you the opportunity to apply it in slightly different ways.