在眾多尋路算法中，A* 的確是比較不錯的。但在游戲?qū)ぢ奉I(lǐng)域，A* 耗時過大，顯然需要改進。

改進

我的想法是預(yù)先將地圖按照一定的規(guī)則劃分為多個區(qū)域，這些區(qū)域彼此連通，并且計算好彼此連通的區(qū)域之間的來往的消耗（預(yù)計算部分，經(jīng)檢測耗時極少）。
?

從幾千個正方形組成的障礙矩陣中構(gòu)造出一張數(shù)據(jù)量大大減少的帶權(quán)連通圖。

每次尋路時自動檢測起始位置和終點分別在圖中的哪兩個節(jié)點，在很短時間內(nèi)構(gòu)造出一條最短路徑。

接著，計算進入以及離開每個區(qū)域的比較適合的點，再經(jīng)過路徑平滑算法，得到的路徑與傳統(tǒng) A* 沒有明顯區(qū)別，但是中間節(jié)點減少，耗時大大減少。經(jīng)過計算，耗時為傳統(tǒng) A* 的 1/800 - 1/1000，取得相當(dāng)顯著的效果。而且對于 A* 其他的改進措施，也可以用在該改進方法上，如雙向 A*，在較復(fù)雜的圖中可以明顯加快尋路速度。并且該尋路代碼也可以放在非主線程中，影響更是可以忽略不計。
?

（改進 A* 路徑）

（傳統(tǒng) A* 路徑）

在障礙圖中的信息發(fā)生改變時，可以重新進行計算，買QQ靚號得出新的帶權(quán)連通圖，并且廣播所有已經(jīng)尋路完成但是還沒有達到終點的物體，使其修改路徑，耗時同樣在可接受范圍內(nèi)。


總結(jié)

該 A* 改進算法是典型的以空間換時間的算法（雖然耗費的空間也很少，在游戲領(lǐng)域可以忽略）

接下去我會繼續(xù)研究比如策略游戲中一個群體單位尋路算法的改進，因為他們無論起始點是否在同個區(qū)域，在帶權(quán)連通圖中總會經(jīng)過相同的節(jié)點，這些計算完全可以緩存下來，減輕后面計算的負載。

總結(jié)

以上是生活随笔為你收集整理的游戏寻路中 A* 算法的改进的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。