Неверные результаты алгоритма A */Path-Finding

Вопрос задан: 11 месяцев назад Последняя активность: 11 месяцев назад
up -2 down

Я пытаюсь настроить поиск пути, в котором я прохожу лабиринт (массив 1/0 с 1, являющимся препятствиями), начальную точку/конечную точку и чтобы он возвращал оптимальный путь.

В качестве базы я использую следующий код, с измененной функцией main, как показано ниже. https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2

def main():
    maze = [[0,1,0,0,...],[0,0,0,0...],[...]...,[...]] #Example 2D List
    start = (4, 33)
    end = (200, 200)

    path = astar(maze, start, end)
    print(path)

#Create blank image for openCV
    img = np.zeros((221,221,3), np.uint8)
    x, y = 0, 0
    red = [0, 0, 255]

#Draw obstacles
    for row in maze:
        y+=1
        x=0
        for value in row:
            x+=1
            if value == 1: img[y, x]=red

#Draw path
    for x, y in path:
        img[y, x] = (255, 0, 0)

    cv2.imshow("Image", img)
    cv2.waitKey(0)
    cv2.destroyAllWindows()

Полный лабиринт для создания карты находится здесь: https://pastebin.com/wT6dGQnjэто упрощенный случай более крупного проекта, поэтому список здесь был «жестко запрограммирован».

Ниже приведен вывод, который кажется неправильным, поскольку путь пересекает несколько препятствий: Результаты

1 ответ

Возможно, для Вашего проекта будут необходимы бесплатные векторные карты. На нашем сайте представлены карты для всех стран.

Реклама

up 0 down

Я думаю, проблема в том, как вы рисуете стены, а не путь. Вы начинаете с y=1 а также, кажется, переключить х и у там. Я использовал лабиринт 10х10 в исходном коде, и все выглядело правильно, когда я изменил часть рисунка на стене следующим образом:

n = 10
img = np.zeros((n,n,3), np.uint8)
x, y = 0, 0
red = [0, 0, 255]

# Draw the walls in red.  This is the part I changed.
for i in range(n):
    for j in range(n):
        if maze[i][j] == 1:
            img[i,j] = red

# Draw the path in blue
for x, y in path:
    img[x, y] = (255, 0, 0)

Там, вероятно, более эффективный способ, хотя вы можете отобразить maze в img не делая двух вложенных for петли, как я сделал здесь.