Design an interactive lab to explore A* Algorithm for path finding by using optimal combination of cost and heuristics to find shortest paths on maps.
Design an interactive lab to explore A* Algorithm for path finding by using optimal combination of cost and heuristics to find shortest paths on maps.
The A* Search Algorithm is an informed, best-first search algorithm that finds the shortest path between a starting node and a goal node in a weighted graph. Unlike uninformed search algorithms such as Dijkstra's algorithm, that explore a graph blindly, A* algorithm makes use of heuristic to extend its path search thereby making it efficient search method. It evaluates each node using the function \(f(n) = g(n) + h(n)\), where \(g(n)\) is the actual cost from the start node to the current node, \(h(n)\) is the estimated cost from the current node to the goal, and \(f(n)\) is the total estimated cost. By prioritizing the node with the lowest \(f(n)\) value, A* efficiently identifies the optimal path.
The algorithm's combines two types of costs:
The actual cost of the path from the starting node to the current node \(n\).
A heuristic estimate of the cost from the current node \(n\) to the goal node.
The heuristic function is used to estimate the future cost, denoted by h(n), which represents the estimated cost of reaching the goal node from the current node.The choice of the heuristic function is critical for the performance of A*. A good heuristic can significantly speed up the search by directing the algorithm towards the goal. For A* to guarantee finding the optimal (shortest) path, the heuristic must be admissible. This means that the estimated cost from node \(n\) to the goal node must never exceed the actual cost. A common admissible heuristic for navigation problems is the straight-line or Euclidean distance to the goal, as it is impossible for a path to be shorter than a straight line.
The algorithm operates by maintaining two sets of nodes:
The A* algorithm is widely used in various fields Which require an optimal path selection to meet their objective. Few of which are briefly described below:
A* is used to determine the movement of non-player characters (NPCs) in games, allowing them to navigate complex environments and find the shortest route to a destination.
Used for path planning in robotics, allowing robots to move around a room without hitting obstacles. Autonomous vehicles use A* to calculate the most efficient and safe routes.
Companies like Amazon and FedEx use A* or similar algorithms to find the most efficient delivery routes for their drivers, saving time and fuel.
Applied in network systems to find the best path for data packets to travel from a source to a destination, ensuring fast and reliable data transmission.
This section shows how the A* algorithm finds the shortest path from the source node to the goal node. To find the best route, the algorithm calculates two specific costs:
The algorithm combines these two values using the evaluation function \(f(n) = g(n) + h(n)\). It stores the discovered nodes in a priority queue (Open List), where each node is ordered according to its \(f(n)\) value. At every step, the node with the lowest \(f(n)\) is removed from the priority queue and explored first, allowing the algorithm to efficiently identify the shortest path toward the goal.
Depending on the problem, A* uses different methods to estimate the future cost \(h(n)\). Here are some common heuristics:
Formula:
h(n) = √((x₂ − x₁)² + (y₂ − y₁)²)
For the points A(3,4) and B(0,0):
h(n) = √((3 − 0)² + (4 − 0)²)
= √(9 + 16)
= √25
= 5
NOTE: Here, A(3,4) and B(0,0) are the spatial coordinates of two nodes in a 2D Cartesian plane, where the first value represents the x-coordinate and the second value represents the y-coordinate.
Formula:
h(n) = |x₂ − x₁| + |y₂ − y₁|
For the points A(3,4) and B(0,0):
h(n) = |3 − 0| + |4 − 0|
= 3 + 4
= 7
The graph given below is the search graph for the A* algorithm. The goal is to find the optimal path from the source node (S) to the goal node (G) while minimizing the total cost \(f(n)\).
Note: For the purpose of this demonstration, we are using the assumed distance for \(h(n)\) values, which are not calculated based on a specific mathematical formula but rather on assumptions about the environment or the problem being solved.

Add start node (S) to the open list.
\(g(S)\) = 0 (Actual cost from S\(→\)S)
\(h(S)\) = 14 (Guess Cost from S\(→\)G)
\(f(S)=g(S)+h(S)\) = 0 + 14 = 14
Open List = [\(S(f=14)\)]
Closed List = []
At the end of iteration 1 :-
| \(Node\) | \(g(n)\) | \(h(n)\) | \(f(n)\) | \(Path\) |
|---|---|---|---|---|
| \(B\) | 4 | 12 | 16 | \(S→B\) |
| \(C\) | 3 | 11 | 14 | \(S→C\) |
At the end of iteration 2 :-
| \(Node\) | \(g(n)\) | \(h(n)\) | \(f(n)\) | \(Path\) |
|---|---|---|---|---|
| \(B\) | 4 | 12 | 16 | \(S→B\) |
| \(D\) | 10 | 6 | 16 | \(S→C→D\) |
| \(E\) | 13 | 4 | 17 | \(S→C→E\) |
At the end of iteration 3 :-
| \(Node\) | \(g(n)\) | \(h(n)\) | \(f(n)\) | \(Path\) |
|---|---|---|---|---|
| \(D\) | 10 | 6 | 16 | \(S→C→D\) |
| \(E\) | 13 | 4 | 17 | \(S→C→E\) |
| \(F\) | 9 | 11 | 20 | \(S→B→F\) |
At the end of iteration 4 :-
| \(Node\) | \(g(n)\) | \(h(n)\) | \(f(n)\) | \(Path\) |
|---|---|---|---|---|
| \(E\) | 12 | 4 | 16 | \(S→C→D→E\) |
| \(F\) | 9 | 11 | 20 | \(S→B→F\) |
At the end of iteration 5 :-
| \(Node\) | \(g(n)\) | \(h(n)\) | \(f(n)\) | \(Path\) |
|---|---|---|---|---|
| \(F\) | 9 | 11 | 20 | \(S→B→F\) |
| \(G\) | 17 | 0 | 17 | \(S→C→D→E→G\) |
The shortest path from start node (S) to goal node (G) is \( S \rightarrow C \rightarrow D \rightarrow E \rightarrow G \) with a total cost of 17.
The algorithm will return the shortest path from the start node to the goal node if one exists.
If no path exists, it will return failure (typically represented as null or -1).
# Python
# Installation:
# - Ensure pygame is installed.
# - Run: pip install pygame
# How to Use:
# 1. First, select the Source and Destination nodes on the grid using the left mouse click.
# - Source Node: Orange
# - Destination Node: Cyan
# 2. Add walls to the grid by left-clicking on other cells.
# 3. Remove walls or nodes by right-clicking.
# 4. Press the Spacebar to start the A* search after setting the source and destination.
# 5. To refresh the grid, press the "C" key.
# Additional Notes:
# - The grid is represented visually.
# - Walls act as barriers that the pathfinding algorithm cannot traverse.
import pygame
import math
from queue import PriorityQueue
WIDTH=800
WIN=pygame.display.set_mode((WIDTH,WIDTH))
pygame.display.set_caption("A* Path finding")
RED = (255,0,0)
GREEN = (0,255,0)
BLUE = (0,0,255)
YELLOW = (255,255,0)
WHITE = (255,255,255)
BLACK = (0,0,0)
PURPLE = (128,0,128)
ORANGE = (255,165,0)
GREY = (128,128,128)
TURQUOISE = (64,224,208)
class Spot: #NODE CLASS
def __init__(self,row,col,width,total_rows):
self.row=row
self.col=col
self.x=row*width
self.y=col*width
self.color=WHITE
self.neighbors=[]
self.width=width
self.total_rows=total_rows
def get_pos(self):
return self.row,self.col
def is_closed(self):
return self.color==RED
def is_open(self):
return self.color==GREEN
def is_barrier(self):
return self.color==BLACK
def is_start(self):
return self.color==ORANGE
def is_end(self):
return self.color==TURQUOISE
def reset(self):
self.color=WHITE
def make_start(self):
self.color=ORANGE
def make_close(self):
self.color =RED
def make_open(self):
self.color=GREEN
def make_barrier(self):
self.color=BLACK
def make_end(self):
self.color=TURQUOISE
def make_path(self):
self.color=PURPLE
def draw(self ,win):
pygame.draw.rect(win,self.color,(self.x ,self.y ,self.width,self.width))
# Try adding diagonal movements
def update_neighbors(self,grid):
self.neighbors=[]
if self.row< self.total_rows-1 and not grid[self.row+1][self.col].is_barrier(): #DOWN
self.neighbors.append(grid[self.row+1][self.col])
if self.row>0 and not grid[self.row-1][self.col].is_barrier(): #UP
self.neighbors.append(grid[self.row-1][self.col])
if self.col< self.total_rows-1 and not grid[self.row][self.col+1].is_barrier(): #RIGHT
self.neighbors.append(grid[self.row][self.col+1])
if self.col>0 and not grid[self.row][self.col-1].is_barrier(): #LEFT
self.neighbors.append(grid[self.row][self.col-1])
def __lt__(self,other):
return False
def h(p1,p2):
x1,y1=p1
x2,y2=p2
return (abs(x1-x2)+abs(y1-y2)) # Try euclidean distance if implementing diagonal movements too
def reconstruct_path(came_from,current,draw):
while current in came_from:
current=came_from[current]
current.make_path()
draw()
def algorithm(draw,grid,start,end):
count=0
open_set=PriorityQueue()
open_set.put((0,count,start))
came_from={}
g_score={spot:float("inf")for row in grid for spot in row}
g_score[start]=0
f_score={spot:float("inf")for row in grid for spot in row}
f_score[start]=h(start.get_pos(),end.get_pos())
open_set_hash={start}
while not open_set.empty():
for event in pygame.event.get():
if event.type==pygame.QUIT:
pygame.quit()
current =open_set.get()[2]
open_set_hash.remove(current)
if current ==end:
reconstruct_path(came_from,end,draw)
end.make_end()
start.make_start()
return True
for neighbor in current.neighbors:
temp_g_score=g_score[current]+1
if temp_g_score< g_score[neighbor]:
came_from[neighbor]=current
g_score[neighbor]=temp_g_score
f_score[neighbor]=temp_g_score+h(neighbor.get_pos(),end.get_pos())
if neighbor not in open_set_hash:
count+=1
open_set.put((f_score[neighbor],count,neighbor))
open_set_hash.add(neighbor)
neighbor.make_open()
draw()
if current!=start:
current.make_close()
return False
def make_grid(rows,width):
grid=[]
gap=width//rows
for i in range(rows):
grid.append([])
for j in range(rows):
spot=Spot(i,j,gap,rows)
grid[i].append(spot)
return grid
def draw_grid(win,rows,width):
GAP=width//rows
for i in range(rows):
pygame.draw.line(win,GREY,(0,i*GAP),(width,i*GAP))
for j in range(rows):
pygame.draw.line(win,GREY,(j*GAP,0),(j*GAP,width))
def draw(win,grid,rows,width):
win.fill(WHITE)
for row in grid:
for spot in row:
spot.draw(win)
draw_grid(win,rows,width)
pygame.display.update()
def get_clicked_pos(pos,rows,width):
gap=width//rows
y,x=pos
row=y//gap
col=x//gap
return row,col
def main(win,width):
ROWS=50
grid=make_grid(ROWS,width)
start=None
end=None
run=True
while run:
draw(win,grid,ROWS,width)
for event in pygame.event.get():
if event.type==pygame.QUIT:
run=False
if pygame.mouse.get_pressed()[0]: #left
pos=pygame.mouse.get_pos()
row,col=get_clicked_pos(pos,ROWS,width)
spot= grid[row][col]
if not start and spot!=end:
start=spot
start.make_start()
elif not end and spot!=start:
end=spot
end.make_end()
elif spot !=end and spot !=start:
spot.make_barrier()
elif pygame.mouse.get_pressed()[2]: #right
pos=pygame.mouse.get_pos()
row,col=get_clicked_pos(pos,ROWS,width)
spot= grid[row][col]
spot.reset()
if spot==start:
start=None
elif spot==end:
end=None
if event.type==pygame.KEYDOWN:
if event.key==pygame.K_SPACE and start and end:
for row in grid:
for spot in row:
spot.update_neighbors(grid)
algorithm(lambda:draw(win,grid,ROWS,width),grid,start,end)
if event.key==pygame.K_c:
start=None
end=None
grid=make_grid(ROWS,width)
pygame.quit()
if __name__=='__main__':
main(WIN,WIDTH)
Select a Start Node and then a Goal Node to watch the A* algorithm explore the graph step-by-step.
Note: Use a larger screen for a better visualization experience.
g: The actual cost from the start node to the current node.
h: The heuristic estimate from the current node to the goal.
f: The total estimated cost to reach the goal (sum of g and h).
The A* pathfinding algorithm applies an appropriate heuristic-based search method to find the shortest path from the start node to the goal node. It considers both the actual cost to reach a node (g) and the estimated cost to the goal (h), using the formula f = g + h to prioritize node exploration. The algorithm returns the sequence of nodes representing the shortest path if a solution exists; otherwise, it indicates that no valid path is available.
The provided interactive visuals and simulations allow the user to easily comprehend the functionality of the A* algorithm for finding the optimal path
Test your understanding of the A* Search Algorithm by answering ten carefully designed questions.
Answer 10 multiple-choice questions on the A* Search Algorithm. Click the button below when you're ready.