重複洪水填充優化

我正在使用基於網格的系統，具有可交叉和不可交叉的方塊以及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

回答