人工智能尋路算法在電子游戲中的研究和應(yīng)用.pdf

1、在電子游戲的設(shè)計(jì)和開發(fā)中，隨著硬件性能的不斷升級(jí)，游戲的音效和視覺效果都得到了極大的提高和改善。但人工智能技術(shù)的研究和應(yīng)用還相對(duì)落后，因而游戲中非玩家角色的行為表現(xiàn)就顯得很單調(diào)笨拙，嚴(yán)重影響游戲的品質(zhì)。因而近年來人工智能漸漸成為改善和提高游戲質(zhì)量的熱門研究課題，非玩家角色的行為既要聰明智能又要豐富多樣。在游戲軟件中，人工智能是一個(gè)重要而又復(fù)雜的模塊，而尋路算法是人工智能運(yùn)用于電子游戲中的最基本問題之一。 在當(dāng)今游戲工業(yè)界，A*算

2、法是被大家最廣泛使用的人工智能尋路算法，也是最有效的最短路徑搜索算法。A*算法實(shí)際上是一種基于廣度優(yōu)先搜索基礎(chǔ)上的啟發(fā)式搜索算法，通常采用估價(jià)函數(shù)：f(n)=g(n)+h(n)對(duì)當(dāng)前的搜索位置進(jìn)行評(píng)估。A*算法最緩慢的部分是在開啟列表中尋找F值最低的節(jié)點(diǎn)，二叉堆方法通過對(duì)開啟列表進(jìn)行快速排序等，極大的優(yōu)化了開啟列表內(nèi)節(jié)點(diǎn)元素的查找以及增刪速度，一般在大多數(shù)場合會(huì)加快2～3倍，并且隨著路徑長度增加，搜索速度呈幾何級(jí)數(shù)提升(10倍以上)。在