Objective

This task involves the implementation of versatile search algorithms to tackle maze puzzles resembling Pac$-$Man. The overarching aim throughout this assignment is to discover a route from the initial position to a designated destination point. This will be accomplished by creating two functions employing distinct search strategies.

This task is coded in Python $3.$ If you're not already familiar with Python, you can refer to the PythonLinks to an external site. tutorial. We suggest utilizing Python version $3\mathrm{.}8$ or a newer version.

Within this assignment, there are visualization tools that rely on pygameLinks to an external site.. To install pygame on your local system, you can make use of the pip$3$Links to an external site. utility.

Grasp the Maze

The purpose of this section is to provide you with insights into the data we're utilizing. It's important to note that in this MP $($Maze Puzzle$),$ we've already supplied the maze for you, so there's no need for you to create your own maze. The maze files required for this assignment can be found in the data$/$ directory. The image below illustrates what the maze will appear like when you open an interactive pygame$-$based visualization of the small maze in the data$/$part$-1/$ directory, along with a solution path from the initial point to the destination.

The agent is symbolized by the blue dot, and you have the ability to control its movement by using the arrow keys, which will then display a colored path. As for the black dots, they indicate the waypoints within the maze. It's worth noting that this particular maze includes just one waypoint, positioned in the lower$-$left corner.

Feel free to interact with the maze by executing the cell below. In case your environment does not identify 'python$3\text{'}$ or if you encounter an error, you can try using 'python' in the command initially. Additionally, ensure that you have all the required dependencies installed.

Maze API

It is helpful to understand some of the infrastructure we have provided in the starter code. All the important functions and variables you should use can be found in maze.py$.$ The Maze class is the abstraction that converts the input ASCII mazes into something whose properties you can access straightforwardly.

You can inspect the ASCII maze cells programatically using the $\_$getitem$\_\_($ : $\_$:$)$ subscript.

cell $=$ maze$[$row$,$ column$]$

Warning: this subscript uses matrix notation, meaning the first index is the row, not the column. Spatially, this means the y$-$coordinate comes before the x$-$coordinate. In the rest of this guide, we will use i to refer to a row index, and j to refer to a column index.

The maze size is given by the size member. The size.x value specifies the number of columns in the maze, and the size.y value specifies the number of rows in the maze.

rows $=$ maze.size.y

columns $=$ maze.size.x

Keep in mind that the coordinate order in size is reversed with respect to the two$-$dimensional indexing scheme! Each cell in the maze is represented by a single character of type str$.$ There are four kinds of cells, which should be self$-$explanatory:

$$ wall cells

$$ start cells

$$ waypoint cells

$$ empty cells

For this MP$,$ there would be just only one starting point and one waypoint point. What is more, you can determine what kind of cell a particular maze cell is by using the maze legend, available in the legend property. Code cells below import the maze with the picture shown above, and they give you an idea of how to determine the type of a cell at a certain position. You can also assume that any cell that is not a wall, start position, or waypoint is empty.

You should implement the state representation, transition model, and goal test necessary to solve the problem. Then implement the following search algorithms :

$($a$)$ Breadth$-$first search

The first function we will need to implement is the breadth$-$first search $($BFS$)$ for a single waypoint. Specifically, we will implement a function bfs$(\_$:$)$ in submitted.py

$($b$)$ Depth$-$first search

The second function we will need to implement is the depth$-$first search $($DFS$)$ for a single waypoint. Specifically, we will implement a function dfs$(\_$:$)$ in submitted.py

$($c$)$ A$*$ search

The third function we will need to implement is the depth$-$first search $($A$*)$ for a single waypoint. Specifically, we will implement a function astar$\_$single$(\_$:$)$ in submitted.py

Your program should run using Python $3\mathrm{.}8.$ Your code can only import extra modules if they are part of the standard python library. You should upload your source code along with this HW$.$ For this assignment, you should implement the Euclidian distance and Manhattan distance from the current position to the goal as the heuristic function for A$*$ search and best first.

For each maze, your report should include a solution output the solution cost, and the number of nodes expanded in your search.