尋路演算法中如何處理動態障礙物？

01-08

比如同伴或者敵人，類似war3的那種

如果障礙物不會改變地圖的拓撲結構的話，可以在局部使用A*演算法。如果是同伴的話，一般來說一個人尋路，剩下的保持隊形。

crowd simulation，google之。

很多尋路已經帶有crowd simulation的改良，可以針對自己目前使用的尋路基底找找看。

我是這樣做的，走路過程中如果遇到動態障礙物，就在路徑中從當前點往下查第一個非障礙點，然後做局部尋路，並把路徑點插入到原路徑中。這兩點之間距離一般很小，計算量微乎其微。

Sven Koenig的D* Lite，有詳細的演算法證明和實現代碼。