从二维网格上的碰撞数据构建距离图
Building a distance map from collision data on a 2d grid
正如标题所说，我有一个数组，代表一个带有 walkable/nonwalkable 数据的二维网格。
我想从该数组创建一个新数组，其中的整数表示到最近的不可行走节点的步数。
我现在要做的是让网格中的每个节点检查半径为 1、2、3 的所有邻居，依此类推，直到我们遇到不可行走的节点。但是因为我需要检查所有节点和多个邻居，所以速度很慢。
我要完成的是图像中的数字。红色代表不可行走的节点。
Grid example
有没有快速的方法？
如果这很重要，我是用 c# 做的，但如果我得到任何其他语言的示例，我可能会弄明白。
是的，运行 BFS 从所有不可行走的单元开始。
您将所有不可行走的单元格添加到队列中。当队列不为空时，您获取第一个元素，通过查看它的邻居并添加 1 来计算距离（如果它不可步行，您可以将其设置为 0）。然后你将所有它看不见的邻居添加到队列的末尾并将它们标记为可见。
这在时间和 space 中都是 O(N*M) 复杂度。在这种情况下，只有邻居相邻的网格，这是 O(N)，因为边的上限约为 2N。
对此有一个有效的算法。不幸的是，我找不到它所谓的参考。它基本上分为两个通道。假设不可行走节点的值为零，而可行走节点最初有一个最大值：
- 从左上角开始
- 从左到右，从上到下处理每个节点
- 取上面的值和左边的值中的最小值
- 给值加一
- 如果该值小于当前节点值，则用该值更新节点。
重复该过程，但从右下角开始，以相反的顺序处理节点，而是检查右侧和下方的值。
这假设您现在允许对角线遍历，但如果需要，可以调整该方法。
正如标题所说，我有一个数组，代表一个带有 walkable/nonwalkable 数据的二维网格。
我想从该数组创建一个新数组，其中的整数表示到最近的不可行走节点的步数。
我现在要做的是让网格中的每个节点检查半径为 1、2、3 的所有邻居，依此类推，直到我们遇到不可行走的节点。但是因为我需要检查所有节点和多个邻居，所以速度很慢。
我要完成的是图像中的数字。红色代表不可行走的节点。 Grid example
有没有快速的方法？ 如果这很重要，我是用 c# 做的，但如果我得到任何其他语言的示例，我可能会弄明白。
是的，运行 BFS 从所有不可行走的单元开始。
您将所有不可行走的单元格添加到队列中。当队列不为空时，您获取第一个元素，通过查看它的邻居并添加 1 来计算距离（如果它不可步行，您可以将其设置为 0）。然后你将所有它看不见的邻居添加到队列的末尾并将它们标记为可见。
这在时间和 space 中都是 O(N*M) 复杂度。在这种情况下，只有邻居相邻的网格，这是 O(N)，因为边的上限约为 2N。
对此有一个有效的算法。不幸的是，我找不到它所谓的参考。它基本上分为两个通道。假设不可行走节点的值为零，而可行走节点最初有一个最大值：
- 从左上角开始
- 从左到右，从上到下处理每个节点
- 取上面的值和左边的值中的最小值
- 给值加一
- 如果该值小于当前节点值，则用该值更新节点。
重复该过程，但从右下角开始，以相反的顺序处理节点，而是检查右侧和下方的值。
这假设您现在允许对角线遍历，但如果需要，可以调整该方法。