面向游戲地圖的尋徑算法的研究與實現.pdf

1、游戲行業(yè)的高速發(fā)展促使了游戲人工智能技術的新變革。面向游戲地圖的尋徑算法一直是研究游戲人工智能的熱點和基本問題之一，而A*算法是目前游戲地圖尋徑中使用最廣泛的算法，是解決尋徑問題最有效的肩發(fā)式搜索算法。A*算法在不同的數據結構影響下會有明顯的搜索效率差異，啟發(fā)函數的設計對A*算法的運行速度也會呈現出不同的影響。目前對A*算法的研究大多是理論方面的工作，而有關A*算法在實際的游戲項目中的應用研究較少，這是當前游戲地圖尋徑算法的一個值得研究

2、的內容。
　　本文首先根據A*算法的性質，提出帶有標志位的搜索節(jié)點的數據結構，使用最小二元堆來實現OPEN表，并通過仿真實驗程序和數據圖表進行對比研究。利用A*算法評估函數的特點，提出帶有權重的啟發(fā)函數，進而提高尋徑算法的搜索效率。其次，結合尋徑算法的實際應用，利用導航網格簡化復雜龐大的游戲地圖，縮小A*算法的搜索狀態(tài)空間;提出分時路徑搜索，使用路徑拼接法處理動態(tài)障礙物，并為評估函數引入地形代價的計算，以提高游戲地圖尋徑的真實性。

3、最后，本文使用Cocos2d-X游戲引擎設計和開發(fā)了一個游戲地圖尋徑的演示程序。
　　實驗結果證明，A*算法使用帶有標志位的搜索數據結構比不使用標志位的在搜索效率上要快3～22倍;使用最小二元堆實現OPEN表比使用數組可以減少40％～60％的尋徑時間:帶權的啟發(fā)函數能對部分地圖減少40％左右需要擴展的節(jié)點數。在游戲地圖尋徑實際應用中，尋徑算法在復雜的地圖環(huán)境下也能保持不錯的搜索效率，并能避開動態(tài)障礙物和計算出新的路徑，且所搜索的最