遊戲中的自動尋路有怎樣的演算法？

01-25

很多遊戲都有自動尋路，但是即使是這樣的一個被人吐槽很多的設定也有著高下之分，有些遊戲自動尋路都是拐直角彎，讓人覺得十分生硬；而有些遊戲卻自動尋路的十分自然，甚至能夠避開許多遊戲沒有建模的貼圖景物（比如花壇，一般人不會跑上去），不會讓人覺得有多少不自然。
關於遊戲的自動尋路中蘊含的演算法，有哪些？如何讓自動尋路更優化呢（更符合人特點，更有效率，自動避礙等等）？

打開這個你就知道

PathFinding.js

a* 作為基本方法

但是對於地圖的數據結構描述是不同的在rpg 中場景基本固定使用way point 技術可以預先設定一些點人物尋路只會經過這些點

還有使用navmap 技術通過多邊形描述地圖信息

對於clash of clans 這種小規則地圖則使用 uniform grid 的方式描述地圖信息

通過a*尋到的路徑不是最終遊戲使用的路徑因為這種路徑受到地圖信息約束路徑比較生硬可以採用 steer behavior 相關演算法來進行路徑修正

對於 uniform grid 描述的地圖可以採用步進網格技術將路徑修正成直線而不是彎彎曲曲的折線

當然對於rts 遊戲還涉及到一群士兵如何尋路問題稱作 cooperate movement 這又是另外一個坑了

對於rpg 中做任務直接的自動尋路則完全可以策劃手動點上兩個位置之間的路點即可不需要尋路

可以參考維基百科

A*，效率好，實現容易，針對不同應用容易優化！

應該都是啟發式搜索吧，但直接使用A*的可能性不大。奇葩的數據會讓A*的啟發函數變得很無力然後退化退化退化到窮舉的水平的，尤其是無解的情況，由於A*的常數比一般的搜索都大，所以A*這時的效率甚至比窮舉還低

但是我們也是有解決方案的，迭代加深的啟發式搜索在這裡就很好，無排序/演算法簡練/對於巨大無比的搜索樹處理更優秀等等等等

詳情搜索 IDA* ～

應該都是a start演算法，遊戲是否自然要看這個遊戲ai的處理了。魔獸爭霸的怪物尋路也是用的a start