Python Maze BFS Shortest Path

Question

I am learning searching algorithms and am trying to implement the BFS algorithm to check if a goal is reachable in a maze given a starting position. The maze was imported from a txt file as a 2D array. My solution seems to find the goal however I am not able to display just the path that was taken I can only display all the nodes that were visited. I would like to display the maze after the algorithm is ran with markers denoting the path that was taken. Currently displaying indices visited with the "." symbol. The ampersand represents a wall that cannot be passed. Here is my code:

def BFS(maze, start, goal):

queue = deque([start])

visited = set(([start]))

while(queue):

    x, y = queue.popleft()

    if ((x,y) == goal):
        return x

    if (start != (x,y)):
        maze[x][y] = '.'

    visited.add((x,y))

    if (maze[x][y+1] != "&" and (x,y+1) not in visited):
        queue.append((x,y+1))

    if (maze[x][y-1] != "&" and (x,y-1) not in visited):
        queue.append((x,y-1))

    if (maze[x-1][y] != "&" and (x-1,y) not in visited):
        queue.append((x-1,y)) 

    if (maze[x+1][y] != "&" and (x+1,y) not in visited):
        queue.append((x+1,y))

Thank you

Kodean Kodean · Accepted Answer · 2019-11-04T08:35:06

I was able to figure it out. I had to use a dictionary that stored each called node with the node that called it. Afterwards once I got to the goal I looped through each dictionary key value pair starting with my goal as the key to find my path.

Python Maze BFS Shortest Path

1 Answers