我正在為名為Blockade的棋盤游戲制作游戲引擎，現在我正在嘗試在一個位置生成所有合法移動。規則與實際游戲并不完全相同，它們并不重要。要點是：棋盤是一個矩陣，每移動一個棋子，你就移動一個棋子并放置一堵墻。
簡而言之，我必須在每次潛在的合法移動（想象一個兵不移動而只是放置一堵墻）之后，找出從每個棋子到每個目標的有效路徑是否存在，以排除非法移動。或者更確切地說，如果我將其簡化為一個子問題，那么移除幾條邊（放置一堵墻）是否會移除到節點的所有路徑。
強制執行需要O(k*n*m)，其中n和m是棋盤尺寸，k是潛在合法移動的數量。搜索路徑（最壞的情況；遍歷電路板的大部分）非常昂貴，但我正在考慮使用動態編程或其他一些想法/演算法可以更快地完成，因為位置相同，只是墻壁位置發生了變化，或者相反，在圖形方面，圖形是相同的，洗掉的邊只是改變了。歡迎任何形式的優化。
編輯：
細化墻壁（封鎖）。一堵墻是兩個正方形寬/高（取決于它是水平的還是垂直的）因此它通常會移除至少四個邊緣，例如：
| | r
q | 噸
在這個 2x2 矩陣中，在中間放置一堵墻（如圖所示）將消除跳躍和跳躍：
p 和 t、q 和 r、p 和 r、q 和 t
uj5u.com熱心網友回復：
如果我沒有完全理解您提出的問題，我會提前道歉；關于封鎖游戲如何運作的知識（我完全不熟悉），您似乎在問題中暗示了一些默認的背景關系知識。
但是，根據維基百科上有關游戲規則的快速瀏覽，以及我從您的問題中收集到的資訊，我的理解是您實際上是在詢問如何確保移動是合法的。根據我的理解，非法移動是墻壁/封鎖放置，使任何棋子都無法達到其目標狀態。
在這種情況下，我相信一個相當有效的可行解決方案如下。
將 pawn 的路徑樹定義為從 pawn 到每個可到達位置的（可能但不一定是最短的）路徑樹。這個想法是，您希望為每個 pawn 維護一個路徑樹，以便可以在每次封鎖放置時有效地更新它。可以通過觀察和實施以下內容來完成上一句中描述的內容：
- 當一個封鎖被放置時，它會從圖中移除 2 條邊，這可以在所有現有的路徑樹中切斷（最多）兩條邊
- 在使用 Boykov-Komolgrov 最大流演算法的“采用”演算法切斷邊緣后，可以有效地重新計算每個 pawn 的路徑樹。
- 一旦每個 pawns 路徑樹被有效地重新計算，只需檢查每個 pawn 是否仍然可以訪問其目標狀態，如果沒有將移動標記為非法
- 對每個可能的移動重復（在搜索程序中根據需要重置圖形）
以下是有關采用演算法的資源，這些資源對于高效執行所描述的作業至關重要：
- 作為 BK-maxflow 一部分的開源實作：https ://www.boost.org/doc/libs/1_66_0/libs/graph/doc/boykov_kolmogorov_max_flow.html
- 作者作為 BK-maxflow 的一部分實施：https ://pub.ist.ac.at/~vnk/software.html
- BK maxflow演算法的采用（階段）演算法詳解：https ://www.csd.uwo.ca/~yboykov/Papers/pami04.pdf的3.2.3節
請注意，閱讀上面最后一個要點中包含的采用演算法的描述對于理解如何有效地采用路徑樹的孤立部分最為關鍵。
就這種方法的效率而言，我相信平均而言，您應該期望O(1)每個采用的邊緣的平均操作，這意味著這種方法應該花費大約O(k)時間來計算k您希望計算的板狀態數量在哪里。
請注意，pawn 路徑樹實際上應該是一個以目標節點為根的反向樹，這將允許對給定封鎖配置的所有合法 pawn 放置進行計算。
uj5u.com熱心網友回復：
幾點建議：
檢查之后是否有從 A 到 B 的路徑
每次移動都會從圖形/網格中洗掉一個節點。所以我們想知道的是，從 A 到 B 的路徑上是否有關鍵節點（可能被阻塞以破壞路徑的單個點。這是一個經典的流問題。對于這個應用程式，您希望將頂點容量設定為 1并推送 2 個單位的流（基本上只是為了驗證至少有 2 條路徑）。如果有 2 條路徑，則沒有一個塊可以斷開您與目的地的連接。您可以使用隱式圖對其進行優化，但是如果您對此不熟悉，可以創建圖表以更好地對其進行可視化。這應該是 O(N*M)，即您的網格的大小。
優化
由于這是一款游戲，您知道設定不會從一個步驟到另一個步驟發生顯著變化。因此，您可以跟蹤這兩條路徑。如果 blocade 未放置在任何路徑上，則可以忽略它。您已經有 2 條通往目的地的路徑。
如果塊確實落在其中一條路徑上，請僅取消該路徑，然后尋找另一條路徑（重用您已有的路徑）。
您還可以加快 pawn 的移動速度。這可能有點技巧，但您想要的是移動源。我假設 pawn 一次只移動幾個單元格，也許不需要找到全新的路徑，您可以簡單地調整它們以連接到新位置，從而加快更新速度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391641.html