Карта расстояний для каждого пикселя в python

Question

Мне нужна помощь в реализации карты расстояний в Python.

У меня есть двоичный лабиринт (1 = стены, 0 = свободное пространство) в формате numpy, в котором я хотел бы реализовать карта расстояний, исходящая из определенной точки в лабиринте. Карты расстояний не должны проходить сквозь стены.

Лабиринт, который у меня есть, выглядит следующим образом, поэтому карта расстояний должна исходить из синей области. Бинарная карта, которая у меня есть

Я думаю, что карта расстояний должна эволюционировать из синей области и дать каждому вокселю в лабиринте значение, которое представляет кратчайшее расстояние. Чтобы дать вам представление, Я думаю, что карта distace должна развиваться таким образом

У кого-нибудь есть идеи о том, как реализовать это или, возможно, даже примеры кода?

Спасибо за каждую помощь!

Я загрузил numpy по следующей ссылке WeTransfer https://wetransfer.com/downloads/63800d0f06667fa7644a4a5d1a68fc5a20200121121741/744d2c

Начальная точка, которую я использую (56,104)

Answer 1

Вы можете использовать переднюю сторону, например:

import matplotlib.pyplot as plt


def cond(x, y, max_x, max_y, maze):
    return 0 <= x < max_x and 0 <= y < max_y and maze[y][x] == 0

def neighbours(point, maze):
    max_x = len(maze[0])
    max_y = len(maze)
    x = point[0]
    y = point[1]

    list_neighbours = [(i, y) for i in (x - 1, x + 1) if cond(i, y, max_x, max_y, maze)] \
                      + [(x, j) for j in (y - 1, y + 1) if cond(x, j, max_x, max_y, maze)]

    return list_neighbours


maze = [
    [0, 0, 1, 1],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0]
]

start = (0, 0)
maze_copy = [[-1] * len(maze[0]) for _ in range(len(maze))]

front = [(0, 0)]
step = 0
while front:
    new_front = []
    for point in front:
        new_front += [p for p in neighbours(point, maze) if maze_copy[p[1]][p[0]] == -1]
        maze_copy[point[1]][point[0]] = step

    step += 1
    front = list(set(new_front))

print(maze_copy)
plt.imshow(maze_copy, cmap='hot', interpolation='nearest')
plt.show()

В коде 1 представляет стены и 0 пересекающиеся части. Я сделал копию лабиринта для отслеживания уже посещенных пикселей.

Идея состоит в том, чтобы иметь фронт, который будет распространяться и заполнять maze_copy.

, что приводит к следующему заполнению :

[0, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, -1, -1]
[3, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, 4, -1]
[3, 4, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, 4, 5]
[3, 4, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, 6]
[2, 3, 4, 5]
[3, 4, -1, 6]

Answer 2

Вы можете сделать это, используя этот алгоритм:

1. Установите все расстояния на некоторое большое число, например 9e99, за исключением начальной точки (которая, очевидно, имеет расстояние 0).
2. Вы l oop по всем ячейкам, каждая ячейка получает значение min(i + 1) для i во всех соседних ячейках (кроме стен)
3. Вы повторяете шаг № 2. До тех пор, пока значения не изменятся

Немного более сложным, но более быстрым подходом было бы сделать то же самое, но зацикливаться только на ячейках рядом с ячейками, которые были обновлены в предыдущей итерации

Например, мой лабиринт:

0, 0, 0
0, 1, 0
0, 1, 0

Здесь 1 - стена, а 0 - не стена. Вверху слева моя отправная точка. Расстояния:

 0, 9e9, 9e9
9e9, 9e9, 9e9
9e9, 9e9, 9e9

Повтор:

 0,   1, 9e9
 1, 9e9, 9e9
9e9, 9e9, 9e9

 0,   1, 2
 1, 9e9, 9e9
 2, 9e9, 9e9

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 9e9

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 4

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 4

Стоп