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

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

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

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

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

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