Python help just change pdf files to py files, already has code, instructions in homework, easy assignment make an offer

Week 5 and 6 Assignment

In this project, we are going to implement depth and breadth first search for pacman to reach a food in a maze. The program consists of three files: problem.py, search.py and graphicsUtils.py. You need to implement the Depth and Breadth first search in the search.py file.

Your task is:

1. Method readMaze(filename) in problemConfiguration.py reads a file filename that contains a maze. The program search.py call the readMaze and pass it the maze1.txt.

The file maze1.txt contains the following maze:

****************

*P *

****** ***** **

* * *

* ******** ****

* * *

********* ******

* .*

****************

(0, 0)

Screen position

1. The only thing that is changing in this problem is Pacman position. So, the state is agent (Pacman) position. After performing an action the agent position changes to a new position. However, we want to save the sequence of actions that are applied on Pacman to reach the food. So, our state is (actions, pacmanPos); where action is a set of actions; for example ['l', 'u', 'l', 'l'] to indicate pacman moves from its start position: to the left, then up, the left, then left. See actions in next point.

2. Actions available for the intelligent agent (Pacman) is ['l', 'r', 'u', 'd'] for left, right, up and down; respectively.

   1. Left action changes Pacman by (0, -1)

   2. Right action changes Pacman by (0, 1)

   3. Up action changes Pacman by (-1, 0)

   4. Down action changes Pacman by (1, 0)

3. The food is an image food5.png:

1. Open the file problem.py study it very well, make sure you understand it, the most methods you will use, legalActions, Successor, isGoal and startState.

   1. Write down the isGoal() method.

   2. Write down the startState() method.

2. Open the file search.py, you will see the function search(). Inside search you will implement your breadth first search. To make your algorithm complete, write the graph search version of BFS where you should avoid exploring states that already explored; use explored list to record the explored states. Some libraries that you need will help you:

   1. p = pr.Problem() to get an instance of the problem class in the problemConfiguation.py file. Note there is an import ProblemConfiguration as pr at the top of search.py file.

   2. p.legalActions to get the actions from a current position:

p.legalActions(currentPos) it will return a list of actions available from the current position currentPos of Pacman. The possible actions: 'l' for left, 'r' for right, 'u' for up and 'd' for down.

1. 1. p.successor to get the next position after applying the action on the current position: newPos = p.successor(action, currentPos); where newPos is a tuple (x, y).

   2. p.isGoal: method to check if the currentPos of Pacman is at the goal (food). This method returns either true or false: p.isGoal(currentPos)

   3. P.startState: methods that return the start state; that is currentPos of pacman: currentPos = p.startState().

Your Task:

1. Implement the depth first search; if you completed the breadth first search, then change one line; which is the direction of inserting the new state to the frontier. To make your algorithm complete, write the graph search version of DFS where you should avoid exploring states that already explored; use explored list to record the explored states.

2. Change the maze file in search.py to maze2.txt; change the xStep and yStep in problemConfiguration.py to 32 and 26; respectively, then run the program search.py (if still the maze is not visible in your screen, then reduce more the xStep and yStep). How many states are explored using breadth search first? Declare a variable that count the number of explored nodes in explored list.

What to submit:

1. Source code of your search.py program.

2. This document with answers of point (a) and (b) in (5).