Tasks:

Maze Generation:

a$)$ Implement a function to generate a random maze with a size of $1010$ and density of obstacles using Python.

b$)$ The maze should have a defined starting point $($S$)$ and a goal point $($G$).$

c$)$ Each run of the algorithms should produce a different maze configuration in terms of starting point, goal

point and obstacle location. However, in each run, all $3$ algorithms should use the same maze. Maze

configuration changes from run to run but remains the same within each run of three algorithms.

Depth$-$First Search $($DFS$)$:

a$)$ Implement the Depth$-$First Search algorithm in Python to find a path from the starting point to the goal point.

b$)$ Visualize the explored paths and the final solution.

Breadth$-$First Search $($BFS$)$:

a$)$ Implement the Breadth$-$First Search algorithm in Python to find a path from the starting point to the goal point.

b$)$ Visualize the explored paths and the final solution.

$A^{**}$ Algorithm:

a$)$ Implement the $A^{**}$ algorithm in Python with an appropriate heuristic function to find an optimal path from

the starting point to the goal point.

b$)$ Visualize the explored paths and the final solution.

Performance Evaluation:

a$)$ Compare the performance of DFS$,$ BFS$,$ and $A^{**}$ algorithm in terms of:

i$)$ Solution Path Length

ii$)$ Number of Nodes Expanded

ii$)$ Time Execution

Visualization:

a$)$ Implement a visualization tool in Python to display the maze, explored paths, and the final solution for

each algorithm.

b$)$ The visualization should be interactive and highlight the progress of the search.

Report:

a$)$ Write a report documenting your Python implementation, including:

i$)$ Overview of the problem and maze generation.

ii$)$ Description of each implemented algorithm.

ii$)$ Results of the performance evaluation.

iv$)$ Visualizations and observations.

Note:

The exact behavior of each run depends on the algonthm's determinism, the characteristics of the maze, and any

randam or heuristic elements involved. It's essential to cansider these factors when interpreting and analyzing the

results of multiple runs on the same size of the maze. You can gain valuable insights by investigating the reasons

behind different paths and varlations in algorithm behawor

To record the performance of each algorithm, run each algorithm $10$ times each with a different maze configuration. Record

the performance of each run of the algorithm using the following table: