BFS on a grid with obstacles python

Question

I have these two functions to compute a BFS of a binary grid with 1's being the obstacles, but its not working correctly. I tried to debug with some print statements and noticed that my queue is not filling up correctly. In my get_neighbors function, I check every neighbor of a given position (up, down ,left, right) and append the valid options to a queue of moves. "move_count" tracks total steps in BFS path, "nodes_left_in_layer" tracks # of nodes needed to be popped off of queue before taking the next step, and "nodes_in_next_layer" tracks how many nodes were added in the BFS expansion so we can correctly update "nodes_left_in_layer" on the next iteration.

On the first iteration of get_neighbors using the example grid below, the queue is filled correctly with queue = [(0, 2),(0, 0)]. When (0, 2) is popped off of the queue however, the queue doesn't get filled with (1, 2) even though its the only valid option from (2, 0). Instead it just continues and assumes no valid positions can be reached from (2, 0) and then pops (0, 0) off of the queue and checks its neighbors. Because the start position was visited already and all other neighbors are invalid moves, it determines that there is no path from start to end. I am struggling to see why this is happening.

Example:

    grid = [[0,0,0],[1, 1, 0],[1, 1, 0]]
    start = (0, 1)
    goal = (2, 2)

    def get_neighbors(grid, current, visited, nodes_in_next_layer, queue): 
        
        R = len(grid)
        C = len(grid[0])
        
        dr = [-1, 1, 0, 0]
        dc = [0, 0, 1, -1]
        
        r = current[0]
        c = current[1]
        
        for i in range(4):
            rr = r + dr[i]
            cc = c + dc[i]
            print(rr, cc)
            if rr < 0 or cc < 0: 
                continue
            if rr >= R or cc >= C:
                continue
            if visited[rr][cc]: 
                continue
            if grid[rr][cc] == 1:
                continue
            
            #print(rr, cc)
            
            queue.append((rr, cc))
            visited[rr][cc] = True
            nodes_in_next_layer += 1
    
    
    def shortest_path_grid(grid, start, goal):
    
        move_count = 0
        nodes_left_in_layer = 1
        nodes_in_next_layer = 0
        done = False
        
        queue = []
        visited = [[False] * (len(grid))] * (len(grid)) 
    
        queue.append(start)
        visited[start[0]][start[1]] = True
        
        while size(queue) > 0:
            current = queue.pop(0)
            
            #print(current)
            if current == goal:
                done = True
                break
            get_neighbors(grid, current, visited, nodes_in_next_layer, queue)
            print(queue)
            nodes_left_in_layer -= 1
            if nodes_left_in_layer == 0:
                nodes_left_in_layer = nodes_in_next_layer
                nodes_in_next_layer = 0
                move_count += 1
     
        if done:
            return move_count
        return -1

question from:https://stackoverflow.com/questions/65875823/bfs-on-a-grid-with-obstacles-python

Answer 1

Waitting for answers