algorithm - 重复洪水填充优化

Question

我正在使用基于网格的系统，该系统具有可交叉和不可交叉的方 block ，A* 用于查找路径，并使用洪水填充来查看是否可以找到路径(查看两个区域是否相连)。

我的问题是新的不可穿越区域可能会非常频繁地引入(每秒最多 16 次)并且网格相当大(大约 500 x 500)所以即使是 O(mn) 的洪水填充解决方案也需要相当长的时间多少时间。我查看了 floodfill 的不同实现，但找不到与我想要的类似的东西。

所以我的问题是，有没有什么方法可以根据之前的网格和新的不可穿越区域列表(始终为矩形)优化重复的洪水填充调用？

Answer 1

首先使用洪水填充算法将可交叉正方形划分为连通的组件。

当您将一个区域标记为不可交叉时，请考虑该区域外与该区域中先前可交叉的方 block 相邻的所有可交叉方 block 的集合 S。对于在 S 中至少有两个成员的每个组件 C，使用洪水填充检查 C 是否已断开连接。

当您将一个区域标记为可交叉时，考虑该区域外与该区域中的一个正方形相邻的所有可交叉正方形的集合 S。将所有组件与 S 中的一个成员连接起来。