I am trying to create a maze-solving algorithm. I watched a few tutorials online, and have come across the BFS algorithm. I tried implementing it my self. This is what I wrote:
import queue, numpy, time
from PIL import Image
def maze(mazename, start=True, end=True):
q = queue.Queue()
img = Image.open(mazename)
array = numpy.array(img).tolist()
for x, y in enumerate(array):
for i, h in enumerate(y):
if h == 0:
array[x][i] = (0, 0, 0)
else:
array[x][i] = (255, 255, 255)
if start and end:
for x, y in enumerate(array[0]):
if y == (255, 255, 255):
start = [x+1, 1]
for x, y in enumerate(array[-1]):
if y == (255, 255, 255):
end = [x+1, len(array)]
start[0] = start[0]-1
start[1] = start[1]-1
end[0] = end[0]-1
end[1] = end[1]-1
start = tuple(start)
q.put("")
while True:
#Checking for end
parse = q.get()
m = list(start)
for i in parse:
if i == "D":
m[1] = m[1]+1
if i == "U":
m[1] = m[1]-1
if i == "L":
m[0] = m[0]-1
if i == "R":
m[0] = m[0]+1
print(m, end)
if m == end:
m = list(start)
array[m[1]][m[0]] = (255, 0, 0)
for i in parse:
if i == "D":
m[1] = m[1]+1
array[m[1]][m[0]] = (255, 0, 0)
if i == "U":
m[1] = m[1]-1
array[m[1]][m[0]] = (255, 0, 0)
if i == "L":
m[0] = m[0]-1
array[m[1]][m[0]] = (255, 0, 0)
if i == "R":
m[0] = m[0]+1
array[m[1]][m[0]] = (255, 0, 0)
return array
#Find new trails
directions = ["U", "D", "L", "R"]
if m[0] == 0:
directions.remove("L")
elif array[m[1]][m[0]-1] == (0, 0, 0):
directions.remove("L")
if m[0]+1 == len(array[0]):
directions.remove("R")
elif array[m[1]][m[0]+1] == (0, 0, 0):
directions.remove("R")
if m[1] == 0:
directions.remove('U')
elif array[m[1]-1][m[0]] == (0, 0, 0):
directions.remove('U')
if m[1]+1 == len(array):
directions.remove("D")
elif array[m[1]+1][m[0]] == (0, 0, 0):
directions.remove("D")
for direction in directions:
q.put(parse+direction)
t1 = time.time()
arr = maze(input("Enter maze file name: "))
print(time.time()-t1)
Image.fromarray(numpy.array(arr).astype(numpy.uint8)).show()
I tried it on this image: https://raw.githubusercontent.com/mikepound/mazesolving/master/examples/tiny.png It worked just fine. It took it between 3 and 7 seconds.
I then tried it on this image: https://raw.githubusercontent.com/mikepound/mazesolving/master/examples/normal.png
It has been running for the past 15 minutes, and it still hasn't passed the 10 row of the 40x40 image once. It checks the same numbers hundreds of times and I can't figure out why. Could someone point out the flaw in my algorithm and help me fix it? I've tried implementing a visited list, it just slows down the program. Thanks
You are missing a list for visited. You should keep track of where you have been so far in order not to repeat the same locations.
When you have a visited list you can use it to check to see if you have already been at that pixel before you make the move.
def maze(mazename, start=True, end=True):
q = queue.Queue()
visited = []
img = Image.open(mazename)
array = numpy.array(img).tolist()
for x, y in enumerate(array):
for i, h in enumerate(y):
if h == 0:
array[x][i] = (0, 0, 0)
else:
array[x][i] = (255, 255, 255)
if start and end:
for x, y in enumerate(array[0]):
if y == (255, 255, 255):
start = [x+1, 1]
for x, y in enumerate(array[-1]):
if y == (255, 255, 255):
end = [x+1, len(array)]
start[0] = start[0]-1
start[1] = start[1]-1
end[0] = end[0]-1
end[1] = end[1]-1
start = tuple(start)
q.put("")
while True:
#Checking for end
parse = q.get()
m = list(start)
for i in parse:
if i == "D":
m[1] = m[1]+1
if i == "U":
m[1] = m[1]-1
if i == "L":
m[0] = m[0]-1
if i == "R":
m[0] = m[0]+1
if m not in visited:
visited.append(m)
print(m, end)
if m == end:
m = list(start)
array[m[1]][m[0]] = (255, 0, 0)
for i in parse:
if i == "D":
m[1] = m[1]+1
array[m[1]][m[0]] = (255, 0, 0)
if i == "U":
m[1] = m[1]-1
array[m[1]][m[0]] = (255, 0, 0)
if i == "L":
m[0] = m[0]-1
array[m[1]][m[0]] = (255, 0, 0)
if i == "R":
m[0] = m[0]+1
array[m[1]][m[0]] = (255, 0, 0)
return array
#Find new trails
directions = ["U", "D", "L", "R"]
if m[0] == 0:
directions.remove("L")
elif array[m[1]][m[0]-1] == (0, 0, 0):
directions.remove("L")
if m[0]+1 == len(array[0]):
directions.remove("R")
elif array[m[1]][m[0]+1] == (0, 0, 0):
directions.remove("R")
if m[1] == 0:
directions.remove('U')
elif array[m[1]-1][m[0]] == (0, 0, 0):
directions.remove('U')
if m[1]+1 == len(array):
directions.remove("D")
elif array[m[1]+1][m[0]] == (0, 0, 0):
directions.remove("D")
for direction in directions:
q.put(parse+direction)