V-Lab@ANDC

A* Search Algorithm

Aim

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.

A* pathfinding animation
Theory & Application

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.

Two Types of Cost

The algorithm's combines two types of costs:

Past Cost — \(g(n)\)

The actual cost of the path from the starting node to the current node \(n\).

Future Cost — \(h(n)\)

A heuristic estimate of the cost from the current node \(n\) to the goal node.

\( f(n) = g(n) + h(n) \) A* always selects the node with the lowest \(f(n)\) value, prioritising paths that are both cheap to reach and look promising.

The Heuristic Function (used to compute the Future Cost \(h(n)\))

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.

Open & Closed Lists

The algorithm operates by maintaining two sets of nodes:

  • Open List: Nodes that have been discovered but not yet evaluated.
  • Closed List: Nodes that have already been evaluated.

Steps of the Algorithm

  1. Add the starting node to the open list.
  2. While the open list is not empty, choose the node with the lowest \(f(n)\) value.
  3. Move the chosen node from the open list to the closed list.
  4. If the chosen node is the destination to be reached,the path has been found.
  5. If not, evaluate all of the chosen node's neighbors. For each neighbor:
    • Calculate its \(g(n)\) and \(f(n)\) values.
    • If it is a new path or low cost path then, add it to the open list.
  6. Repeat steps 2–5 until the goal is reached.

Applications in the Real World

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:

🎮

Video Games

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.

🤖

Robotics & Autonomous Vehicles

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.

📦

Logistics and Route Optimization

Companies like Amazon and FedEx use A* or similar algorithms to find the most efficient delivery routes for their drivers, saving time and fuel.

🌐

Network Routing

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.

Procedure

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:


  • Past Cost \(g(n)\): Cost of the path from the source node to the current node \(n\).
  • Future Cost \(h(n)\): Estimated cost from the current node \(n\) to the goal node, calculated using a heuristic function.

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.


Types of Heuristics \(h(n)\)


Depending on the problem, A* uses different methods to estimate the future cost \(h(n)\). Here are some common heuristics:


  • Euclidean Distance: Calculates the straight-line distance between the current node and the goal. It is used in scenarios where movement can occur in any direction, such as in a 2D plane or 3D space.

    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

    Euclidean Heuristic
  • 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.


  • Manhattan Distance: It calculates the distance between two points by only moving horizontally and vertically. It is used in grid-based pathfinding problems where diagonal movement is not allowed.

    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

    Manhattan Heuristic

  • Assumed Distance (Guess): In some cases, a heuristic may be based on an educated guess or domain-specific knowledge about the problem. This heuristic is not based on a specific mathematical formula but rather on assumptions about the environment or the problem being solved.
    Assumed Heuristic



  • Search Graph


    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)\).

    • The red numbers next to the nodes represent the heuristic values \(h(n)\) for each node, which estimate the cost to reach the goal node (G) from that node.
    • The black numbers on the edges represent the actual cost to move from one node to another. For example, the cost to move from node S to node B is 4, and the cost to move from node S to node C is 3.

    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.

    A*-Graph

    Initialization


    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 = []


    Iteration 1


    1. Is Open List Empty? \(→\) NO \(→\) Choose node with lowest \(f\) value \(→\) \(S\)
    2. Move the chosen node from Open List to Closed List
      Open List = []
      Closed List = [\(S\)]
    3. Is the chosen node goal? \(→\) NO \(→\) Evaluate all the neighbors of chosen node \((S)\) :- \(B\) , \(C\)
    4. For \(B\) :-
      Calculate \(g(B)\) and \(f(B)\).
      \(g(B)\) = 4 (Actual cost from \(S→B\))
      \(h(B)\) = 12 (Guess cost from \(B→G\))
      \(f(B) = g(B) + h(B)\) = 4 + 12 = 16
    5. Is it a new or a better cost path to \(B\) ? \(→\) YES \(→\) Add \(B\) to open list
      Open List = [\(B(f=16)\)]
    6. For \(C\) :-
      Calculate \(g(C)\) and \(f(C)\).
      \(g(C)\) = 3 (Actual cost from \(S→C\))
      \(h(C)\) = 11 (Guess cost from \(C→G\))
      \(f(C) = g(C) + h(C)\) = 3 + 11 = 14
    7. Is it a new or a better cost path to \(C\) ? \(→\) YES \(→\) Add \(C\) to open list
      Open List = [\(B(f=16), C(f=14)\)]

    At the end of iteration 1 :-

    Open List = [\(B(f=16), C(f=14)\)]
    Closed List = [\(S\)]


    \(Node\) \(g(n)\) \(h(n)\) \(f(n)\) \(Path\)
    \(B\) 4 12 16 \(S→B\)
    \(C\) 3 11 14 \(S→C\)

    Iteration 2


    1. Is Open List Empty? \(→\) NO \(→\) Choose node with lowest \(f\) value \(→\) \(C\)
    2. Move the chosen node from Open List to Closed List
      Open List = [\(B(f=16)\)]
      Closed List = [\(S, C\)]
    3. Is the chosen node goal? \(→\) NO \(→\) Evaluate all the neighbors of chosen node \((C)\) :- \(D\) , \(E\)
    4. For \(D\) :-
      Calculate \(g(D)\) and \(f(D)\).
      \(g(D)\) = 3 + 7 = 10 (Actual cost from \(S→C→D\))
      \(h(D)\) = 6 (Guess cost from \(D→G\))
      \(f(D) = g(D) + h(D)\) = 10 + 6 = 16
    5. Is it a new or a better cost path to \(D\) ? \(→\) YES \(→\) Add D to open list
      Open List = [\(B(f=16),\) \(D(f=16)\)]
    6. For \(E\) :-
      Calculate \(g(E)\) and \(f(E)\).
      \(g(E)\) = 3 + 10 = 13 (Actual cost from \(S→C→E\))
      \(h(E)\) = 4 (Guess cost from \(E→G\))
      \(f(E) = g(E) + h(E)\) = 13 + 4 = 17
    7. Is it a new or a better cost path to \(E\) ? \(→\) YES \(→\) Add \(E\) to open list
      Open List = [\(B(f=16), D(f=16), E(f=17)\)]

    At the end of iteration 2 :-

    Open List = [\(B(f=16), D(f=16), E(f=17)\)]
    Closed List = [\(S,C\)]


    \(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\)

    Iteration 3


    1. Is Open List Empty? \(→\) NO \(→\) Choose node with lowest \(f\) value \(→\) \(B\)
      (In case of tie we can chose either nodes; here we decided to chose B since it came first in the open list.)
    2. Move the chosen node from Open List to Closed List
      Open List = [\(D(f=16), (E(f=17)\)]
      Closed List = [\(S, C, B\)]
    3. Is the chosen node goal? \(→\) NO \(→\) Evaluate all the neighbors of chosen node \((B)\) :- \(F\) , \(E\)
    4. For \(F\) :-
      Calculate \(g(F)\) and \(f(F)\).
      \(g(F)\) = 4 + 5 = 9 (Actual cost from \(S→B→F\))
      \(h(F)\) = 11 (Guess cost from \(F→G\))
      \(f(F) = g(F) + h(F)\) = 9 + 11 = 20
    5. Is it a new or a better cost path to \(F\) ? \(→\) YES \(→\) Add \(F\) to open list
      Open List = [\(D(f=16), E(f=17), F(f=20)\)]
    6. For \(E\) :-
      Calculate \(g(E)\) and \(f(E)\).
      \(g(E)\) = 4 + 12 = 16 (Actual cost from \(S→B→E\))
      \(h(E)\) = 4 (Guess cost from \(E→G\))
      \(f(E) = g(E) + h(E)\) = 16 + 4 = 20
    7. Is it a new or a better cost path to \(E\) ? \(→\) NO \(→\) Don't add new \(f\) value of \(E\) to open list
      Open List = [\(D(f=16), E(f=17), F(f=20)\)]

    At the end of iteration 3 :-

    Open List = [\(D(f=16), E(f=17), F(f=20)\)]
    Closed List = [\(S, C, B\)]


    \(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\)

    Iteration 4


    1. Is Open List Empty? \(→\) NO \(→\) Choose node with lowest \(f\) value \(→\) \(D\)
    2. Move the chosen node from Open List to Closed List
      Open List = [\(E(f=17), F(f=20)\)]
      Closed List = [\(S, C, B, D\)]
    3. Is the chosen node goal? \(→\) NO \(→\) Evaluate all the neighbors of chosen node \((D)\) :- \(E\)
    4. For \(E\) :-
      Calculate \(g(E)\) and \(f(E)\).
      \(g(E)\) = 3 + 7 + 2 = 12 (Actual cost from \(S→C→D→E\))
      \(h(E)\) = 4 (Guess cost from \(E→G\))
      \(f(E) = g(E) + h(E)\) = 12 + 4 = 16
    5. Is it a new or a better cost path to \(E\) ? \(→\) YES \(→\) Add new \(f\) value of \(E\) to open list
      Open List = [\(E(f=16), F(f=20)\)]

    At the end of iteration 4 :-

    Open List = [\(E(f=16), F(f=20)\)]
    Closed List = [\(S, C, B, D\)]


    \(Node\) \(g(n)\) \(h(n)\) \(f(n)\) \(Path\)
    \(E\) 12 4 16 \(S→C→D→E\)
    \(F\) 9 11 20 \(S→B→F\)

    Iteration 5


    1. Is Open List Empty? \(→\) NO \(→\) Choose node with lowest \(f\) value \(→\) \(E\)
    2. Move the chosen node from Open List to Closed List
      Open List = [\(F(f=20)\)]
      Closed List = [\(S, C, B, D, E\)]
    3. Is the chosen node goal? \(→\) NO \(→\) Evaluate all the neighbors of chosen node \((E)\) :- \(G\)
    4. For \(G\) :-
      Calculate \(g(G)\) and \(f(G)\).
      \(g(G)\) = 3 + 7 + 2 + 5 = 17 (Actual cost from \(S→C→D→E→G\))
      \(h(G)\) = 0 (Guess cost from \(G→G\))
      \(f(G) = g(G) + h(G)\) = 17 + 0 = 17
    5. Is it a new or a better cost path to \(G\) ? \(→\) YES \(→\) Add \(G\) to open list
      Open List = [\(F(f=20), G(f=17)\)]

    At the end of iteration 5 :-

    Open List = [\(F(f=20), G(f=17)\)]
    Closed List = [\(S, C, B, D, E\)]


    \(Node\) \(g(n)\) \(h(n)\) \(f(n)\) \(Path\)
    \(F\) 9 11 20 \(S→B→F\)
    \(G\) 17 0 17 \(S→C→D→E→G\)

    Iteration 6


    1. Is Open List Empty? \(→\) NO \(→\) Choose node with lowest \(f\) value \(→\) \(G\)
    2. Move the chosen node from Open List to Closed List
      Open List = [\(F(f=20)\)]
      Closed List = [\(S, C, B, D, E, G\)]
    3. Is the chosen node goal? \(→\) YES \(→\) Stop the execution and return the path to chosen node \((G)\)

    Final Result

    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).

Code

                
              # 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)
            

A* Search Visualizer

Interactive A* Search Simulator

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.

Graph Visualization

SELECT START NODE

Current Node

Open List

Empty

Closed List

Empty
g(n)
h(n)
f(n)
Expanded
0
Graph Legend
Start Node
Goal Node
Current Node
Open List
Closed List
Unvisited Node
Final Path Node
Shortest Path
Algorithm Progress Step 0 / 0

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).

Select the start node to begin.
Result

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

A* Search Challenge

Test your understanding of the A* Search Algorithm by answering ten carefully designed questions.

Ready to Test Yourself?

Answer 10 multiple-choice questions on the A* Search Algorithm. Click the button below when you're ready.

References
Team & Tools
Students
  • Adi Maqsood
    B. Sc. (H) Computer Science, IV yr. (2025–26)
  • Aditya Maurya
    B. Sc. (H) Computer Science, IV yr. (2025–26)
Mentors
  • Prof. Sharanjit Kaur
    Professor, Department of Computer Science
  • Priyanka Sharma
    Assistant Professor, Department of Computer Science
Tools Used
  • HTML – for structuring the web pages.
  • CSS – for styling and designing the user interface.
  • JavaScript (Vanilla JS) – for implementing the A* algorithm, quiz, and interactive features.
  • HTML5 Canvas API – for rendering the graph and visualizing the A* search algorithm.
  • Figma – for designing figures, diagrams, and UI mockups.