Mar-27-2019, 04:03 PM
Dear all,
I am stuck with this code. It appears to be working for most of the situations. But for this particular maze, it fails. I have a 2D array of 0/1 where 0 represents the wall and I am trying to get from point start to point end in the shortest manner.
Here is the code and below is the maze for which it fails. I would really appreciate any input.
00000000000000000000
00111111111111111s11
00000001000000001100
01000101000001111000
10111011000000101000
10000010000000101001
111111e1111111111000
11111111110000000000
I am stuck with this code. It appears to be working for most of the situations. But for this particular maze, it fails. I have a 2D array of 0/1 where 0 represents the wall and I am trying to get from point start to point end in the shortest manner.
Here is the code and below is the maze for which it fails. I would really appreciate any input.
import time import os basic_operations = 0 def main(): i = 0 for file in os.listdir(): if file.startswith("maze") and file.endswith(".txt"): i += 1 print("Maze", i) if i==1: maze = readMazeFromFile(file) printMaze(maze) maze = convertmaze(maze) start = findStart(maze) end = findEnd(maze) printMaze(maze) startTime = time.time() path = BFS(maze, start, end) endTime = time.time() if path == None: printMaze(maze) print("No path to destination.") else: printPath(maze, path) print("Shortest path: ") print(path) print(len(path)) print("Time taken:", endTime-startTime, "secs") print("Basic operations: ", basic_operations) print("\n") def BFS(maze, start, end): '''"Brute-Force Search" :param maze(list): the maze to be navigated :param start(tuple): the starting coordinates (row, col) :param end(tuple): the end coordinates (row, col) :return: shortest path from start to end ''' queue = [start] visited = set() while len(queue) != 0: if queue[0] == start: path = [queue.pop(0)] # Required due to a quirk with tuples in Python else: path = queue.pop(0) front = path[-1] if front == end: return path elif front not in visited: for adjacentSpace in getAdjacentSpaces(maze, front, visited): newPath = list(path) newPath.append(adjacentSpace) queue.append(newPath) global basic_operations basic_operations += 1 visited.add(front) return None def getAdjacentSpaces(maze, space, visited): ''' Returns all legal spaces surrounding the current space :param space: tuple containing coordinates (row, col) :return: all legal spaces ''' spaces = list() spaces.append((space[0]-1, space[1])) # Up spaces.append((space[0]+1, space[1])) # Down spaces.append((space[0], space[1]-1)) # Left spaces.append((space[0], space[1]+1)) # Right final = list() for i in spaces: print(i[0]) print(i[1]) if maze[i[0]][i[1]] != '*' and i not in visited: final.append(i) return final def findStart(maze): for i in range(len(maze)): for j in range(len(maze[0])): if maze[i][j] == 's': return tuple([i, j]) return None def findEnd(maze): for i in range(len(maze)): for j in range(len(maze[0])): if maze[i][j] == 'e': return tuple([i, j]) return None def readMazeFromFile(f): maze = list() with open(f) as file: for line in file: maze.append(list(line.rstrip())) return maze def convertmaze(maze): for i in range(len(maze)): for j in range(len(maze[0])): if maze[i][j]=='0': maze[i][j]='*' if maze[i][j]=='1': maze[i][j]='.' return maze def printMaze(maze): for i in range(len(maze)): for j in range(len(maze[0])): print(maze[i][j], end="") print() def printPath(maze, path): for i in range(len(maze)): for j in range(len(maze[0])): if tuple([i, j]) in path and maze[i][j] != 's' and maze[i][j] != 'e': print("x", end="") else: print(maze[i][j], end="") print()And here is the maze where it fails:
00000000000000000000
00111111111111111s11
00000001000000001100
01000101000001111000
10111011000000101000
10000010000000101001
111111e1111111111000
11111111110000000000