After concluding the first lecture of Harvard's AI course on edX, I have decided to implement the concepts taught, first being the depth-first search algorithm.
The objective of this program is to input a maze in text file mazefile and find a path from S to G using the depth-first search algorithm.
The project currently consists of 4 files, (1) the code with the class methods to operate or use the (2) text file which contains the maze, another text file (3) that contains the result file (where the AI has explored) and the main python script (4). Here they are, feel free to copy and paste these into a folder and to see how they run.
processText.py (file 1)
#code to process the mazefile file.
class importMaze:
def __init__(self,maze):
self.fileLines = []
self.fileName = maze
self.switch = False
self.toBeReturned = []
def processThis(self):
f = open(self.fileName,"r")
for x in f:
self.fileLines.append(x[:-1])
f.close()
for i in self.fileLines:
if self.switch == True:
if str(i) == "END":
self.switch = False
else:
self.toBeReturned.append(i)
else:
if str(i) == "START":
self.switch = True
return self.toBeReturned
class mazePointer:
def __init__(self,mazearray):
self.Sample = mazearray
self.initialPosition = []
for y in range(0, len(self.Sample)):
for x in range(0,len(self.Sample[y])):
if str(self.Sample[y][x]) == "S":
self.initialPosition = [x,y]
self.currentPosition = self.initialPosition
def whatIs(self,xcoordinate,ycoordinate):
return (self.Sample[ycoordinate])[xcoordinate]
def nearbyFreeSpaces(self,search):
self.freeSpaces = []
if self.whatIs(self.currentPosition[0]-1,self.currentPosition[1]) == search:
self.freeSpaces.append([self.currentPosition[0]-1,self.currentPosition[1]])
if self.whatIs(self.currentPosition[0]+1,self.currentPosition[1]) == search:
self.freeSpaces.append([self.currentPosition[0]+1,self.currentPosition[1]])
if self.whatIs(self.currentPosition[0],self.currentPosition[1]-1) == search:
self.freeSpaces.append([self.currentPosition[0],self.currentPosition[1]-1])
if self.whatIs(self.currentPosition[1],self.currentPosition[1]+1) == search:
self.freeSpaces.append([self.currentPosition[1],self.currentPosition[1]+1])
return self.freeSpaces
def moveTo(self,position):
self.currentPosition = position
TestingTrack.py (the main file)
from processText import importMaze, mazePointer
testObject = importMaze("mazefile")
environment = testObject.processThis()
finger = mazePointer(environment)
frontier = []
explored = []
result = ""
def Search():
global result
if len(finger.nearbyFreeSpaces("G")) == 1: #If the goal is bordering this space
result = finger.nearbyFreeSpaces("G")[0]
explored.append(finger.currentPosition)
else:
newPlaces = finger.nearbyFreeSpaces("F") #finds the free spaces bordering
for i in newPlaces:
if i in explored: #Skips the ones already visited
pass
else:
frontier.append(i)
while result == "":
explored.append(finger.currentPosition)
Search()
finger.moveTo(frontier[-1])
frontier.pop(-1)
exploredArray = []
for y in range(len(environment)): #Recreates the maze, fills in 'E' in where the AI has visited.
holder = ""
for x in range(len(environment[y])):
if [x,y] in explored:
holder+= "E"
else:
holder+= str(environment[y][x])
exploredArray.append(holder)
def createResult(mazeList,title,append): #Creating the file
file = open("resultfile",append)
string = title + " \n F - Free \n O - Occupied \n S - Starting point \n G - Goal \n E - Explored/Visited \n (Abdulaziz Albastaki 2020) \n \n (top left coordinate - 0,0) \n "
for i in exploredArray:
string+= "\n" + str(i)
string+= "\n \n Original problem \n"
for i in environment:
string+= "\n" +str(i)
file.write(string)
file.close()
def tracingPath():
initialExplored = explored
proceed = True
newExplored = []
for i in explored:
finger.moveTo() #incomplete
print(explored)
createResult(exploredArray,"DEPTH FIRST SEARCH", "w")
mazefile (the program will read this file to get the maze)
F - Free
O - Occupied
S - Starting point
G - Goal
(Abdulaziz Albastaki 2020)
START
OOOOOOOOOOOOOOOO
OFFFFFFFFFFFFFGO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OSFFFFFFFFFFFFFO
OOOOOOOOOOOOOOOO
END
Made by Abdulaziz Albastaki in October 2020
You can change the maze and its size however it must
-Respect the key above
-Have ONE Starting point and goal
-The maze must be in between 'START' and 'END'
-The maze MUST be surrounded by occupied space
SAMPLE PROBLEMS:
OOOOOOOOOOOOOOOO
OFFFFFFFFFFFFFGO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OSFFFFFFFFFFFFFO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOO
OFOFFFFFOOOFFFOOO
OFFFOOOFOOFFOOOFO
OFOOOOOFOOFOOOOFO
OSFGFFFFFFFFFFFFO
OOOOOOOOOOOOOOOOO
There is also a resultfile, however if you would just create an empty textfile with that name (no extension), the program will fill it in with results.
The problem is with the resultfile, here it is:
DEPTH FIRST SEARCH
F - Free
O - Occupied
S - Starting point
G - Goal
E - Explored/Visited
(Abdulaziz Albastaki 2020)
(top left coordinate - 0,0)
OOOOOOOOOOOOOOOO
OFFFFFFFFFFFFFGO
OFOOOOOOOOOOOOEO
OFOOOOOOOOOOOOEO
OFOOOOOOOOOOOOEO
OEOOOOOOOOOOOOEO
OEFFFEEEEEEEEEEO
OOOOOOOOOOOOOOOO
Original problem
OOOOOOOOOOOOOOOO
OFFFFFFFFFFFFFGO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OSFFFFFFFFFFFFFO
OOOOOOOOOOOOOOOO
The AI skipped a few spaces to get to the goal, why is it doing so?
Feel free to ask me for any clarifications.
There are the following issues:
the last if block in nearbyFreeSpaces uses a wrong index:
if self.whatIs(self.currentPosition[1],self.currentPosition[1]+1) == search:
self.freeSpaces.append([self.currentPosition[1],self.currentPosition[1]+1])
should be:
if self.whatIs(self.currentPosition[0],self.currentPosition[1]+1) == search:
self.freeSpaces.append([self.currentPosition[0],self.currentPosition[1]+1])
The final position is not correctly added to the path. The last line of this block:
if len(finger.nearbyFreeSpaces("G")) == 1: #If the goal is bordering this space
result = finger.nearbyFreeSpaces("G")[0]
explored.append(finger.currentPosition)
...should be:
explored.append(result)