BFS Great Escape

def bfs_paths(player_id, forbidden_moves):
    # debug(f'BFS player {player_id} - {len(forbidden_moves)} forbidden moves = {forbidden_moves}')
    start_x, start_y, walls_left = players[player_id]
    # queue = [(start_x, start_y, [], [])]
    queue = deque([(start_x, start_y, [], [])])
    nodes_count = 0
    new_start = time.time()
    while queue:
        # x, y, path, visited_states = queue.pop(0)
        x, y, path, visited_states = queue.popleft()
        # la petite fourmi se deplace pour chercher son chemin
        for (dx, dy), _dir in DIRECTIONS.items():
            if (x, y, _dir) in forbidden_moves:
                continue
            new_x, new_y = (x + dx, y + dy)
            if 0 <= new_x < width and 0 <= new_y < height:
                # state = hash((new_x, new_y, _dir))
                state = (new_x, new_y)
                # debug(state)
                if state in visited_states:
                    continue
                if (player_id == 0 and new_x == width - 1) or (player_id == 1 and new_x == 0) or (player_id == 2 and new_y == height - 1):
                    debug(f'BFS player {player_id} - nodes_count = {nodes_count}')
                    debug(f'remaining time after BFS player {player_id} = {round((time.time() - new_start) * 1000, 2)} ms')
                    yield path + [_dir]
                else:
                    node = (new_x, new_y, path + [_dir], visited_states + [state])
                    # queue.append(node)
                    queue.append(node)
                    nodes_count += 1

def shortest_path(player_id, forbidden_moves):
    try:
        return next(bfs_paths(player_id, forbidden_moves))
    except StopIteration:
        return None