maze.py

from search import Problem

"""Basic class for representing a maze.

Each maze cell is one of the following:

. is an empty cell

x is a goal

# is a wall

o is a teleporter (there are exactly two teleporter locations, or none)

"""

class Maze:

def __init__(self,maze_string,maze_size):

"""define the maze using a string, and the maze width and height"""

# remove whitespace

width,height = maze_size

maze_string = "".join(maze_string.split())

assert len(maze_string) == width*height

self.matrix = self._string_to_matrix(maze_string,maze_size)

self.maze_size = maze_size

self.teleporters = [ i for i,c in enumerate(maze_string) if c == 'o' ]

self.teleporters = [ (i//width,i%width) for i in self.teleporters ]

self.goals = [ i for i,c in enumerate(maze_string) if c == 'x' ]

self.goals = [ (i//width,i%width) for i in self.goals ]

assert len(self.teleporters) == 0 or len(self.teleporters) == 2

def __repr__(self,position=None):

if position is not None:

x,y = position

marker = self.matrix[x][y]

self.matrix[x][y] = '+'

# draw maze as string

st = " ".join( "".join(row) for row in self.matrix )

# restore marker

if position is not None:

self.matrix[x][y] = marker

return st

asap python pls

In this project, we will model a maze solving problem as a state space problem, which can then be solved using search. Consider the following maze, drawn out using ASCII text: \#\#\#\#\#\#\#\#\#\#\#\#\#\#\# \#+ . . . . . . . .\#\# \#\#\#\#\#.\#.\#\#\#\#\#.\# \#.....\#...o\#. . \#. \#\#\#\#\#.\#\#\#\#\#.\# #..x# \#\#\#\#\#\#\#\#\#\#\#\#\#\#\# This maze is an mn grid of cells, where we use the following symbols: - a plus (+) denotes a player in the maze; - a cross (x) denotes the goal cell; - a dot (.) denotes an empty cell; - a hash (\#) denotes a wall that the player cannot enter; - a circle (o) denotes a portal/teleporter which the player can use to teleport to another part of the maze Our goal is to find a shortest path that allows the player to reach the goal cell. The player can perform five different actions (each action has a cost of one): - move UP a cell - move DOWN a cell - move LEFT a cell - move RIGHT a cell - or TELEPORT from one portal (o) to another portal (o) The player cannot move into a cell containing a wall. The player can only teleport when they are occupying a cell containing a portal. In this project, a maze may either contain exactly two portals, or none at all. This project is based on the python code repository of the book "AI: A Modern Approach" (AIMA) by Russel \& Norvig, which is available at https://github.com/aimacode/aima-python. We will use their abstract class Problem which allows us define a search problem, which can then be subsequently solved with one of a number of provided search algorithms. Note that their python code is based on Python version 3.7 and up. If you have not coded in python before, I suggest downloading the free version of PyCharm, which is an IDE for developing and debugging python programs. Skeleton code is provided to help you get started. It already includes the relevant files from the AIMA repository, so you do not have to download the AIMA repository yourself. maze.py is the file that you will modify and turn in. test.py is an included testing script that is the main script to run. search.py includes the abstract class Problem, as well as other examples (including EightPuzzle for the sliding tile puzzle), which I also strongly suggest that you read. maze.py includes three classes: 1 - a Maze class which is a simple class that will take in the definition of a maze as a string, and convert it into a matrix, which can be indexed using the at function. The at function takes in a coordinate (x,y) as input, and returns a symbol representing the cell of the maze (i.e., whether it is empty, a wall, etc.) - a MazeState class which is simply just a maze and a position for the player (this suffices to define the state of a player in a maze). - a MazeProblem class, which is incomplete. The goal of this project is to complete this definition of a maze problem, so that it can be solved by one of the search algorithms already included in the AIMA repository. Once properly implemented, the included test.py script will run tests over multiple different mazes, each time showing the maze, the solution found, and the number of steps (actions) required to solve the maze (each action counts as one step)