最優(yōu)路徑算法

1、9.4.3尋路算法路徑選擇問(wèn)題是游戲開(kāi)發(fā)中經(jīng)常遇到的問(wèn)題，比如熱門(mén)的Android游戲crystallight， 游戲中的敵人需要尋找到一條路徑前進(jìn)，直到被殺死或者是到達(dá)終點(diǎn)；又如，棋類(lèi)游戲中， 需要為棋子選擇最”理智”的行進(jìn)路徑，以達(dá)到最佳棋面；再如，9.3.5節(jié)中提到的復(fù)雜游戲 AI，其核心就是為”飛機(jī)”尋找一條最理想的逃生路線(xiàn)。此外，在非規(guī)則實(shí)體的碰撞檢測(cè)中， 也需要選擇較優(yōu)的路徑到達(dá)碰撞邊緣。類(lèi)似的路徑選擇問(wèn)題經(jīng)常出現(xiàn)，但是如何合理地實(shí)現(xiàn) 尋路算法，是很多程序員需要解決的難題。A*算法知多少很多游戲開(kāi)發(fā)者一提到尋路算法，就想到A*算法；一提到A*算法，就望而卻步。下面 將揭開(kāi)A*算法的

2、神秘面紗。A*算法確實(shí)是最高效、最流行的尋路算法，是搜索算法最深層的延伸A*算法由4個(gè) 要素組成：A*=估價(jià)函數(shù)+并查集+堆+廣搜。A*算法必須有強(qiáng)大的算法功底和長(zhǎng)年累月的實(shí) 戰(zhàn)積累方能實(shí)現(xiàn)。另外，A*也并非總是最適合的算法，它僅僅是在不同運(yùn)用領(lǐng)域表現(xiàn)出更 強(qiáng)的通用性，僅僅是在數(shù)據(jù)統(tǒng)計(jì)范疇內(nèi)性能期望值最高。那么，A*是否適合移植到Android平臺(tái)呢？我們需要進(jìn)一步分析它的特點(diǎn)與專(zhuān)長(zhǎng)。A* 算法的精髓是以空間換取時(shí)間，它的運(yùn)用前提是：解空間充分大，運(yùn)算時(shí)間受到剛性限制， 而存儲(chǔ)空間（一般是內(nèi)存）相對(duì)充足。如果將它移植到Android平臺(tái)上，其一，手機(jī)系統(tǒng)的內(nèi) 存資源彌足珍貴，A*算法將完全失去

3、用武之地；其二，手機(jī)游戲的尋路空間相對(duì)較小，解 空間相對(duì)狹隘。因而，搜索算法的瓶頸不再是冗余的搜索嘗試，而估價(jià)函數(shù)的開(kāi)銷(xiāo)以及冗長(zhǎng) 的代碼將成為新的瓶頸。因此，A*算法并不是Android手機(jī)游戲的唯一選擇，針對(duì)不同的 路徑選擇需要，應(yīng)該定制不同的搜索算法。量身定制尋路算法設(shè)計(jì)尋路算法應(yīng)該基于兩個(gè)原則：開(kāi)發(fā)者力所能及、算法力所能及。算法功底不是很雄厚的開(kāi)發(fā)者，不必追求華麗的A*算法，可根據(jù)實(shí)際需要寫(xiě)一個(gè)普通 的寬搜或者廣搜算法。畢竟手機(jī)游戲的解空間與PC游戲差了不止一個(gè)數(shù)量級(jí)，常規(guī)搜索的 時(shí)間開(kāi)銷(xiāo)也不會(huì)龐大。游戲開(kāi)發(fā)者需要認(rèn)真做好的是優(yōu)化。其實(shí)，開(kāi)發(fā)尋路算法的大門(mén)一直 都敞開(kāi)著，只要開(kāi)發(fā)者能夠找

4、準(zhǔn)游戲的定位，選準(zhǔn)突破的方向。例如，熱門(mén)塔防游戲-Robo Defense，它的搜索空間很小，對(duì)常規(guī)的搜索算法做一些優(yōu)化，即能實(shí)現(xiàn)即時(shí)尋路。具備深厚算法功底的開(kāi)發(fā)者可以根據(jù)不同的路徑選擇需求，選擇最恰當(dāng)?shù)膶ぢ匪惴?。?duì) 于解空間較小、實(shí)時(shí)性較高的游戲，A*算法將是最恰當(dāng)?shù)倪x擇，設(shè)計(jì)高效的估計(jì)函數(shù)將成 為算法性能的關(guān)鍵；如果解空間較大，內(nèi)存空間緊缺，那么采用迭代加深搜索算法效果更佳，此算法的內(nèi)存消耗微乎其微，而且能夠保證最先搜到最短路徑；如果游戲中的精靈需要持續(xù) 尋路（比如NPC每走一步，都要尋找一次最優(yōu)路徑），那么遺傳算法將是再適合不過(guò)的選 擇了，每執(zhí)行一輪遺傳算法得到的最終種群、經(jīng)過(guò)移位和補(bǔ)位處理可以用來(lái)優(yōu)化下一輪的初 始種群，這將極其顯著地消除重復(fù)性搜索嘗試。需要特別注意的是，使用人工智能算法實(shí)現(xiàn) 尋路，雖然不能總是獲得最優(yōu)路線(xiàn)，但是量身定做的智能算法能夠進(jìn)一步節(jié)約內(nèi)存消耗，能 夠讓游戲在Android手機(jī)上面更加流暢地運(yùn)行，同時(shí)，智能算法求解出的，智能”路線(xiàn)往往也 會(huì)給玩家?guī)?lái)意外的驚喜與趣味。比如，螞蟻吃蛋糕游戲應(yīng)用了人工