將許多單位分解成單獨的遊戲框架

Question

所以我的問題是，對於大型單位組，試圖在同一框架中爲所有單位尋找路徑導致明顯的減速。當路徑爲1或2個單位時，減速一般不明顯，但對於更多的情況，取決於路徑的複雜性，它可能變得非常慢。雖然我的A *可能可以提供一些調整，但我也知道另一種加速路徑的方法是在多個遊戲框架中進行尋路。什麼是一個很好的方法來完成這個？

我很抱歉，如果這是一個明顯或容易搜索的問題，我真的不知道如何將它放入可搜索的字符串中。

更多信息：這是一個*在直線網格上，並使用C＃和XNA框架編程。我計劃有可能高達50-75個單位需要路徑。

謝謝。

Answer 1

可擴展性

有這種情況的優化的幾種方法。首先，你可能不必分裂成多個遊戲框架。在某種程度上，可伸縮性似乎是問題。 100個單位至少比1個單位貴100倍。

那麼，我們如何才能使路徑更適合可伸縮性？那麼，這取決於你的遊戲設計。我會（可能錯誤地）假設一個典型的RTS場景。幾組單位，每組相對較近。許多靠近的單位的路徑解決方案將非常相似。這些單位可以請求從某種解決方法路徑。該路徑求解器可以保留最近的路徑請求及其解決方案的表格，並避免多次計算來自相同輸入的相同輸出。這叫做memoization。

此外，另一個可能涉及到使您的網格或圖形的層次結構。首先解決更簡單的圖形，然後切換到更詳細的圖形。如果高分辨率路徑太多以至於無法合理記憶，則多個單元可以使用相同的低分辨率路徑，以利用記憶，但是每個單元都會分別計算它們自己的高分辨率路徑。

多幀計算

至於試圖計算幀之間的分裂，也有我能想到手的幾種方法。

如果要採用多線程路由，可以使用工作線程池模型。每次單元請求路徑時，它都會排隊尋找解決方案。當工作線程空閒時，它被分配一個任務來解決。當線程解決任務時，您可以通過回調來通知單元，或者您可以讓單元查詢任務是否以某種方式完成，最有可能查詢每個幀。

如果沒有動態障礙物或它們分開處理，則可以使路徑求解程序使用的常數狀態。如果沒有，那麼將會有不可忽視的複雜性，甚至可能聽到這些線程鎖定可變的遊戲狀態信息。從一幀到下一幀，路徑可能無效，需要重新驗證每一幀。多線程可能最終成爲毫無意義的額外開銷，由於鎖定和同步，線程很少會並行運行。這只是一種可能性。

或者，您可以設計您的路徑查找算法以分立步驟運行。經過n個步驟後，檢查自算法開始以來經過的時間量。如果超過一定的時間，則路徑算法會保存其進度並返回。然後調用代碼可以檢查算法是否完成。在下一幀中，從原來的位置恢復路徑算法。重複，直到解決。即使使用單線程自願方法來解決路徑問題，如果遊戲狀態的變化影響幀之間路徑的有效性，那麼您將遇到不得不重新驗證幀上當前的解決方案的情況以框架爲基礎。

使用部分解決方案

不管是用上述兩種方法，你可能會遇到的單位問題命令有一個完整的尋路解決方案之前去的地方空轉多幀。在典型情況下，這可能是可以接受的，而且幾乎檢測不到。如果不是，您可以嘗試按原樣使用不完整的解決方案。如果每個不完整的解決方案差異過大，單位會表現得相當猶豫不決。在實踐中，這種「猶豫不決」可能也不會引起關注。

Answer 2

如果你的單位都是同一個目的地，那麼這個答案可能適用，否則，它只是一種思考。

我使用寬度優先的距離算法路徑單位。從你的目的地開始，並將它的距離標記爲0.任何相鄰的單元格都是1，與這些單元格相鄰的單元格是2等等。不要穿過障礙物，走過整個單板。通常O（A）時間複雜度，其中A是電路板面積。

然後，每當你想確定一個單位需要去哪個方向時，你只需找到距目的地最小距離的方格。 O（1）時間複雜度。

我會經常使用這種路徑算法進行塔防遊戲，因爲它的時間複雜度完全取決於板的大小（通常在TD遊戲中相當小），而不是單位數量（通常相當大）。它允許玩家定義他們自己的路徑（一個很好的功能），並且由於遊戲的性質，我只需要每輪運行一次。