CIS 314

# Trang Ngo (Katherine)

# Dr. Schep

# CIS 314 - 91

# 20 April 2017

#Maze.py

#Using breadth first search revise the maze program from the recursion chapter

#to find the shortest path out of a maze

import turtle

from supp import *

PART_OF_PATH = 'O'

EXPLORED = '.'

OBSTACLE = '+'

TO_EXPLORE = '-'

class Maze:

    def __init__(self,mazeFileName):

        rowsInMaze = 0

        columnsInMaze = 0

        self.mazelist = []

        mazeFile = open(mazeFileName,'r')

        rowsInMaze = 0

        for line in mazeFile:

            rowList = []

            col = 0

            for ch in line[:-1]:

                rowList.append(ch)

                if ch == 'S':

                    self.startRow = rowsInMaze

                    self.startCol = col

                col = col + 1

            rowsInMaze = rowsInMaze + 1

            self.mazelist.append(rowList)

            columnsInMaze = len(rowList)

        self.rowsInMaze = rowsInMaze

        self.columnsInMaze = columnsInMaze

        self.xTranslate = -columnsInMaze/2

        self.yTranslate = rowsInMaze/2

        self.t = turtle.Turtle()

        self.t.shape('turtle')

        self.wn = turtle.Screen()

        self.wn.setworldcoordinates(-(columnsInMaze-1)/2-.5,-(rowsInMaze-1)/2-.5,(columnsInMaze-1)/2+.5,(rowsInMaze-1)/2+.5)

    def drawMaze(self):

        self.t.speed(10)

        self.wn.tracer(0)

        for y in range(self.rowsInMaze):

            for x in range(self.columnsInMaze):

                if self.mazelist[y][x] == OBSTACLE:

                    self.drawCenteredBox(x+self.xTranslate,-y+self.yTranslate,'orange')

        self.t.color('black')

        self.t.fillcolor('blue')

        self.wn.update()

        self.wn.tracer(1)

    def drawCenteredBox(self,x,y,color):

        self.t.up()

        self.t.goto(x-.5,y-.5)

        self.t.color(color)

        self.t.fillcolor(color)

        self.t.setheading(90)

        self.t.down()

        self.t.begin_fill()

        for i in range(4):

            self.t.forward(1)

            self.t.right(90)

        self.t.end_fill()

    def moveTurtle(self,x,y):

        self.t.up()

        self.t.setheading(self.t.towards(x+self.xTranslate,-y+self.yTranslate))

        self.t.goto(x+self.xTranslate,-y+self.yTranslate)

    def dropBreadcrumb(self,color):

        self.t.dot(10,color)

    def updatePosition(self,vertex,val=None):

        if val:

            self.mazelist[vertex.getRow()][vertex.getCol()] = val

        self.moveTurtle(vertex.getCol(),vertex.getRow())

        if val == PART_OF_PATH:

            color = 'green'

        elif val == OBSTACLE:

            color = 'red'

        elif val == EXPLORED:

            color = 'black'

        elif val == TO_EXPLORE:

            color = 'gray'

        else:

            color = None

        if color:

            self.dropBreadcrumb(color)

    def isExit(self,row,col):

        return (row == 0 or

                row == self.rowsInMaze-1 or

                col == 0 or

                col == self.columnsInMaze-1 )

    def __getitem__(self,idx):

        return self.mazelist[idx]

def searchFrom(maze, startRow, startColumn):

    start = Vertex(startRow,startColumn)

    start.setDistance(0)

    vertQueue = Queue()

    vertQueue.enqueue(start)

    currentVert = start

    while (vertQueue.size() > 0) and not (maze.isExit(currentVert.getRow(),currentVert.getCol())):

        currentVert = vertQueue.dequeue()

        if maze.isExit(currentVert.getRow(),currentVert.getCol()):

            vertQueue = Queue()

            maze.updatePosition(currentVert,PART_OF_PATH)

            while currentVert.getPred():

                currentVert = currentVert.getPred()

                maze.updatePosition(currentVert,PART_OF_PATH)

        else:

            maze.updatePosition(currentVert,TO_EXPLORE)

            for nbr in nextMove(maze,currentVert.getRow(),currentVert.getCol()):

                nbr = Vertex(nbr[0],nbr[1])

                if (nbr.getStat() != TO_EXPLORE) and (nbr.getStat() != EXPLORED):

                    nbr.setStat(TO_EXPLORE)

                    maze.updatePosition(nbr,TO_EXPLORE)

                    nbr.setDistance(currentVert.getDistance() + 1)

                    nbr.setPred(currentVert)

                    vertQueue.enqueue(nbr)

            currentVert.setStat(EXPLORED)

            maze.updatePosition(currentVert,EXPLORED)

def nextMove(maze,x,y):

        newMoves = []

        moveOffsets = [(1,0),(0,-1),(-1,0),(0,1)]

        for i in moveOffsets:

            newX = x + i[0]

            newY = y + i[1]

            if legalCoord(maze,newX,newY):

                newMoves.append((newX,newY))

        return newMoves

def legalCoord(maze,x,y):

    if maze.mazelist[x][y] != OBSTACLE and maze.mazelist[x][y] != EXPLORED\

       and maze.mazelist[x][y] != TO_EXPLORE:

        return True

    else:

        return False

myMaze = Maze('maze1.txt')

myMaze.drawMaze()

myMaze.updatePosition(Vertex(myMaze.startRow,myMaze.startCol))

searchFrom(myMaze, myMaze.startRow, myMaze.startCol)

# class Vertex:

class Vertex:

    def __init__(self,row,col):

        self.id = (row,col)

        self.connectedTo = {}

        self.distance = None

        self.predecessor = None

        self.status = None

    def addNeighbor(self,nbr,weight=0):

        self.connectedTo[nbr] = weight

    def __str__(self):

        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):

        return self.connectedTo.keys()

    def getId(self):

        return self.id

    def getWeight(self,nbr):

        return self.connectedTo[nbr]

    def getDistance(self):

        return self.distance

    def setDistance(self,dist):

        self.distance = dist

    def getPred(self):

        return self.predecessor

    def setPred(self,vert):

        self.predecessor = vert

    def getStat(self):

        return self.status

    def setStat(self,status):

        self.status = status

    def getRow(self):

        return self.id[0]

    def getCol(self):

        return self.id[1]

#class Graph

class Graph:

    def __init__(self):

        self.vertList = {}

        self.numVertices = 0

    def addVertex(self,key):

        self.numVertices = self.numVertices + 1

        newVertex = Vertex(key)

        self.vertList[key] = newVertex

        return newVertex

    def getVertex(self,n):

        if n in self.vertList:

            return self.vertList[n]

        else:

            return None

    def __contains__(self,n):

        return n in self.vertList

    def addEdge(self,f,t,cost=0):

        if f not in self.vertList:

            nv = self.addVertex(f)

        if t not in self.vertList:

            nv = self.addVertex(t)

        self.vertList[f].addNeighbor(self.vertList[t], cost)

    def getVertices(self):

        return self.vertList.keys()

    def __iter__(self):

        return iter(self.vertList.values())

#class Queue

class Queue:

    def __init__(self):

        self.items = []

    def isEmpty(self):

        return self.items == []

    def enqueue(self, item):

        self.items.insert(0,item)

    def dequeue(self):

        return self.items.pop()

    def size(self):

        return len(self.items)