1、9.4.3尋路算法路徑選擇問題是游戲開發中經常遇到的問題，比如熱門的Android游戲crystallight， 游戲中的敵人需要尋找到一條路徑前進，直到被殺死或者是到達終點；又如，棋類游戲中， 需要為棋子選擇最”理智”的行進路徑，以達到最佳棋面；再如，9.3.5節中提到的復雜游戲 AI，其核心就是為”飛機”尋找一條最理想的逃生路線。此外，在非規則實體的碰撞檢測中， 也需要選擇較優的路徑到達碰撞邊緣。類似的路徑選擇問題經常出現，但是如何合理地實現 尋路算法，是很多程序員需要解決的難題。A*算法知多少很多游戲開發者一提到尋路算法，就想到A*算法；一提到A*算法，就望而卻步。下面 將揭開A*算法的

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

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

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