问重复充水优化
EN

Stack Overflow用户

提问于 2012-08-01 06:24:49

回答 1查看 400关注 0票数 1

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

我的问题是，新的不可穿越区域可能会被频繁引入(每秒高达16次)，并且网格相当大(大约500乘500)，因此即使是O(mn)泛洪填充解决方案也需要相当长的时间。我已经看过floodfill的不同实现，但找不到任何与我想要的相似的东西。

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

回答已采纳

发布于 2012-08-01 06:43:34

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

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

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

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/11749931

复制

相似问题

问重复充水优化EN