Path Finding in a Maze Using the A Search Algorithm

Problem Statement

Pathfinding is an important Artificial Intelligence problem in which an agent must find the shortest path from a starting position to a goal position while avoiding obstacles.

In this practical, the A* Search Algorithm is implemented using Python to solve a pathfinding problem in a two-dimensional maze. A* selects the most promising cell by considering both:

$$f(n)=g(n)+h(n)$$

where:

• $g(n)$ = actual cost from the start cell to the current cell
• $h(n)$= estimated distance from the current cell to the goal
• $f(n)$= estimated total cost of the path  

Example of A* Cost Calculation

Consider the following small grid:

      Column

        0   1   2

Row 0   S   0   0

Row 1   0   A   0

Row 2   0   0   G

Where

• S = Start = (0,0)
• A = Current Cell = (1,1)
• G = Goal = (2,2)

Suppose the A* algorithm is currently at cell A (1,1).

Step 1: Calculate g(n)

The value g(n) represents the actual distance travelled from the Start node to the Current node.

From the start,

(0,0)
   ↓
(1,0)
   →
(1,1)

The algorithm has taken 2 steps.

Therefore,

g(n) = 2 


Step 2: Calculate h(n)
The heuristic value is calculated using the Manhattan Distance.
Formula:
$$h(n)=\mathrm{\mid }{x}_1-x_2\mathrm{\mid }+\mathrm{\mid }{y}_1-y_2\mathrm{\mid }$$
Current Cell 
(1,1)
Goal Cell
(2,2)
Calculation 
h(n)

= |1-2| + |1-2|

= 1 + 1

= 2 
Therefore,
h(n)=2
Step 3: Calculate f(n)

Formula

$$f(n)=g(n)+h(n)$$
Substitute the values
f(n)

= 2 + 2

= 4 
Therefore,
f(n)=4

Go through Jupyter Notebook

Short Introduction

A* is an informed search algorithm because it uses additional information called a heuristic to guide the search toward the goal.

Unlike BFS, which explores cells level by level, A* prioritizes cells that appear closer to the destination. Therefore, it generally explores fewer cells and reaches the goal more efficiently.

Maze Representation

Symbol/Value	Meaning
0	Free cell
1	Obstacle or wall
S	Starting position
G	Goal position

The agent can move:

• Up
• Down
• Left
• Right

Diagonal movement is not allowed.