Advertisement
informaticage

BFS Path finder

Mar 10th, 2021
1,101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.31 KB | None | 0 0
  1. def make_maze(maze_string):
  2.     return maze_string.split('\n')
  3.  
  4.  
  5. def bfs_explore_maze(maze):
  6.     destination = (len(maze) - 1, len(maze) - 1)
  7.     start = (0, 0)
  8.     queue = [start]
  9.     visited = [[False for x in maze] for y in maze]
  10.     visited[start[0]][start[1]] = True
  11.     while len(queue) > 0:
  12.        
  13.         # print(queue)
  14.         current_node = queue.pop(0)
  15.         if(current_node == destination):
  16.             return True
  17.  
  18.         for neighboor in get_neighboors(current_node, maze):
  19.             # print(neighboor, visited[neighboor[0]][neighboor[1]])
  20.             if(visited[neighboor[0]][neighboor[1]] == False):
  21.                 visited[neighboor[0]][neighboor[1]] = True
  22.                 queue.append(neighboor)
  23.  
  24.     return False
  25.  
  26.  
  27. def get_neighboors(tup, maze):
  28.     neighboors = []
  29.     i = tup[0]
  30.     j = tup[1]
  31.     if(i + 1 < len(maze) and maze[i][j] != 'W'):
  32.         neighboors.append((i + 1, j))
  33.     if(i - 1 >= 0 and maze[i][j] != 'W'):
  34.         neighboors.append((i - 1, j))
  35.     if(j + 1 < len(maze) and maze[i][j] != 'W'):
  36.         neighboors.append((i, j + 1))
  37.     if(j - 1 >= 0 and maze[i][j] != 'W'):
  38.         neighboors.append((i, j - 1))
  39.  
  40.     return neighboors
  41.  
  42. def path_finder(maze_string):
  43.     maze = make_maze(maze_string)
  44.     can_exit = bfs_explore_maze(maze)
  45.     return can_exit
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement