面向游戲地圖的尋徑算法的研究與實(shí)現(xiàn).pdf

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

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

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