重复洪水填充优化

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

我的问题是，新的不可跨越区域可能经常引入（最多16次），网格相当大（约500乘500），所以即使O（mn）洪水填充解决方案也需要相当很长的时间。我查看了不同的floodfill实现，找不到类似于我想要的任何内容。

所以我的问题是，有没有什么办法来优化重复洪水填充调用基于以前的网格和新的不可交叉区域（它将永远是矩形）的列表？

2012-07-31 Mamick

我很抱歉，如果我不够清楚;我不想超载任何信息太多的人，这是我第一次问一个问题（在我总能找到其他人问的问题之前）。网格大小是固定的，有nxm个正方形，可以水平和垂直移动，更新只会将所有方块标记为不可交叉（或可交叉）。 – Mamick 2012-07-31 22:39:37

首先将可交叉方块与洪水填充算法分割成连接的组件。

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

当你标记的区域为可交配，考虑到区域外的所有可交配广场相邻的广场上region.Join与S.成员的所有组件的集合S

2012-07-31 22:43:33

谢谢，这太棒了！还有一个问题：当非跨区域稀疏时，还有什么可以做的，因为只有一个大的区域才能通过？ – Mamick 2012-07-31 22:53:43

回答