Почему этот простой BFS на сетке не работает (python) - PullRequest
Новая
       13

Почему этот простой BFS на сетке не работает (python)

0 голосов
/ 19 апреля 2020

Итак, я пытаюсь узнать о широте в первую очередь, используя веб-сайт под названием «игры с красными шариками», и я застрял очень рано (цель A *) более часа, я посмотрел этот код и не могу найти проблему. Я хочу, чтобы функция bfs выполняла поиск кратчайшего пути между началом и целью, но по какой-то причине она идет по длинному и странному пути.

Веб-сайт, который я использую для изучения bfs * * https://www.redblobgames.com/pathfinding/a-star/introduction.html

Код- 

from collections import deque

def neighbors(maze, current):
    n = []
    y = current[0]
    x = current[1]
    if y + 1 < len(maze) and maze[y + 1][x] == " ":
        n.append((y + 1, x))
    if x + 1 < len(maze[0]) and maze[y][x + 1] == " ":
        n.append((y, x + 1))
    if y - 1 >= 0 and maze[y - 1][x] == " ":
        n.append((y - 1, x))
    if x - 1 >= 0 and maze[y][x - 1] == " ":
        n.append((y, x - 1))
    return n

def bfs(maze, start, goal):
    frontier = deque()
    frontier.append(start)
    came_from = {}
    came_from[start] = None
    while frontier:
        current = frontier.pop()
        if current == goal:
            break

        for next in neighbors(maze, current):
            if next not in came_from:
                frontier.append(next)
                came_from[next] = current      

    current = goal
    path = []
    while current != start:
        path.append(current)
        current = came_from[current]
    #path.append(start)
    path.reverse()
    return path

maze = [[" "," "," "," "," "],
        [" "," "," "," "," "],
        [" "," "," "," "," "],
        [" "," "," "," "," "],
        [" "," "," "," "," "]]
#(1 0), (1 1), (2 1), (2 2), (3 2), (3 3), (4 3), (4 4)
path = bfs(maze, (1, 0), (4, 3))
print(path)

Число, помеченное #, является желаемым результатом, но я получаю это:

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (2, 3), (2, 2) , (2, 1), (3, 1), (4, 1), (4, 2), (4, 3)]

...