我正在使用基于网格的系统,该系统具有可交叉和不可交叉的正方形,带有 A* 用于查找路径,并使用洪水填充来查看是否可以找到路径(查看两个区域是否连接)。
我的问题是,可能会非常频繁地引入新的不可穿越区域(每秒最多 16 次),并且网格相当大(大约 500 x 500),所以即使是 O(mn) 洪水填充解决方案也需要相当长的时间. 我查看了 Floodfill 的不同实现,但找不到与我想要的类似的东西。
所以我的问题是,有没有什么方法可以根据先前的网格和新的不可穿越区域列表(始终是矩形)来优化重复的洪水填充调用?