基于改進(jìn)A-算法的游戲地圖尋徑的研究.pdf

1、隨著計(jì)算機(jī)硬件性能的不斷提升和軟件技術(shù)的飛速發(fā)展，游戲行業(yè)也相應(yīng)得到發(fā)展。近幾年來，游戲里面的聲音和視覺效果方面都得到了極大的提高和改善。但是，游戲中的人工智能技術(shù)的研究和應(yīng)用還相對(duì)比較落后，所以游戲中虛擬角色的行為表現(xiàn)就顯得比較單調(diào)和笨拙，只能重復(fù)做幾個(gè)簡(jiǎn)單的動(dòng)作，行走看起來非常機(jī)械，嚴(yán)重影響到了游戲的品質(zhì)。然而，人工智能技術(shù)能夠使虛擬角色看起來更加聰明更加智能化，因此，近幾年來人工智能方面的技術(shù)就成為了改善和提高游戲品質(zhì)的熱門研究課

2、題。在游戲軟件中，人工智能是一個(gè)既重要又復(fù)雜的模塊，而尋路算法又是人工智能運(yùn)用予游戲中的最基本和最重要的問題之一。
　　 A*算法是目前被游戲開發(fā)人員最廣泛使用的人工智能尋路算法。A*算法是一種啟發(fā)式搜索算法，它采用的估價(jià)函數(shù)是：F(n)=G(n)+H(n)，G(n)表示起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)實(shí)際走的距離，H(n)表示當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離的估價(jià)值。利用這個(gè)函數(shù)計(jì)算出下一步將要搜索的所有節(jié)點(diǎn)的估價(jià)值，通過比較選擇估價(jià)值最小的節(jié)點(diǎn)，

3、作為下一步要走的節(jié)點(diǎn)，因此找到的是最優(yōu)路徑。本文首先優(yōu)化OPEN表中節(jié)點(diǎn)的查找速度，然后運(yùn)用將單個(gè)物體路徑搜索和A*算法相結(jié)合的分級(jí)路徑搜索方法來搜索路徑。運(yùn)用C++語言實(shí)現(xiàn)標(biāo)準(zhǔn)的A*算法和改進(jìn)后的算法進(jìn)行路徑搜索，然后根據(jù)統(tǒng)計(jì)它們搜索的節(jié)點(diǎn)數(shù)和搜索路徑所花費(fèi)的時(shí)間，來驗(yàn)證改進(jìn)后的算法的可行性和有效性。
　　 本文采用32*32的矩形方格來模擬游戲地圖，黑色的方格代表障礙物，也即是代表游戲中的建筑物、墻、河流等無法通過的區(qū)域。具

4、體的研究方法和步驟如下：
　　 第一，經(jīng)過分析，我們可知A*算法最耗費(fèi)時(shí)間的部分是：在OPEN表中查找F值最小的節(jié)點(diǎn)。本文采用二叉堆的方法，通過對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序。采用二叉堆的方法比一般的排序方法更加高效，極大的優(yōu)化了OPEN表內(nèi)查找、增加和刪除節(jié)點(diǎn)的速度。通過對(duì)比實(shí)驗(yàn)驗(yàn)證了采用二叉堆的方式來優(yōu)化OPEN表中節(jié)點(diǎn)的查找速度的A*算法比標(biāo)準(zhǔn)的A*算法的搜索效率提高了5％。
　　 第二，在大型的游戲地圖中，A*算法

5、需要搜索的節(jié)點(diǎn)數(shù)量仍然非常巨大。通過分析我們發(fā)現(xiàn)，在沒有障礙物的情況下，起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間就是一條直線路徑。所以本文采用將單個(gè)物體尋徑算法和A*算法相結(jié)合的分級(jí)路徑搜索算法，進(jìn)一步提升游戲地圖路徑搜索的速度。通過對(duì)比實(shí)驗(yàn)驗(yàn)證了采用分級(jí)路徑搜索算法比標(biāo)準(zhǔn)的A*算法的搜索效率提高了11.5％。
　　 最后，本文將前面兩個(gè)方面的改進(jìn)和優(yōu)化方法綜合在一起，運(yùn)用這個(gè)綜合的算法來尋找路徑。通過對(duì)比實(shí)驗(yàn)驗(yàn)證了這個(gè)基于改進(jìn)A*算法的綜合路徑