algorithm - 重复洪水填充优化

Question

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

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

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

Answer 1

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

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

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