3

在 Python 中实现距离图时，我需要一些帮助。

我有一个 numpy 格式的二进制迷宫（1 = 墙壁，0 = 空闲空间），我想在其中实现从迷宫中某个点传出的距离图。距离图不得穿墙。

我的迷宫看起来像这样，距离图应该从蓝色区域出来。我拥有的二进制映射

我认为距离图应该从蓝色区域向外演化，并给迷宫中的每个体素一个代表最短距离的值。为了给你一个想法，我认为距离图应该以这种方式发展

有人知道如何实现这个甚至是代码示例吗？

感谢您的每一个帮助！

我在以下 WeTransfer 链接https://wetransfer.com/downloads/63800d0f06667fa7644a4a5d1a68fc5a20200121121741/744d2c中上传了 numpy

我使用的起点是 (56,104)

4

2 回答 2

3

您可以使用正在传播的前端，例如：

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]

最后结果

于 2020-01-20T13:15:49.117 回答
0

您可以使用此算法执行此操作：

  1. 将所有距离设置为某个较大的数字，例如 9e99，起点除外（显然距离为 0）。
  2. 您遍历所有单元格，每个单元格min(i + 1)在所有相邻单元格中获取 for 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

停止

于 2020-01-20T12:49:49.237 回答