基于加速A-算法的游戲網(wǎng)格地圖尋徑研究.pdf

1、隨著游戲行業(yè)的迅速發(fā)展，人們對(duì)游戲應(yīng)用中自動(dòng)尋路算法的有效性和性能都提出了更高的要求。自動(dòng)尋路是指在有阻擋的游戲地圖中搜尋兩點(diǎn)之間最佳的可通行路徑。如何高效地完成自動(dòng)尋路是游戲研究領(lǐng)域中重要的方向之一。
　　在游戲網(wǎng)格地圖尋路算法的研究中，最常見(jiàn)的算法為A*算法。A*算法是啟發(fā)式算法，其啟發(fā)函數(shù)為f(n)=g(n)+h(n)。對(duì)于游戲網(wǎng)格地圖中的節(jié)點(diǎn)n，g(n)是起始節(jié)點(diǎn)至節(jié)點(diǎn)n已花費(fèi)路徑成本的實(shí)際值，h(n)是節(jié)點(diǎn)n至目標(biāo)節(jié)點(diǎn)路

2、徑成本的估計(jì)值。A*算法通過(guò)在路徑查找的過(guò)程中，通過(guò)選取最小f(n)值節(jié)點(diǎn)作為路徑節(jié)點(diǎn)，可以有效地計(jì)算兩點(diǎn)之間最短可行路徑。
　　A*算法的研究中存在以下難點(diǎn)問(wèn)題：第一，標(biāo)準(zhǔn)A*算法中 f(n)的度量方法為曼哈頓距離，該度量方法不能廣泛地適用于不同類(lèi)型的游戲網(wǎng)格地圖。第二， A*算法集合操作的時(shí)間復(fù)雜度是影響游戲性能的關(guān)鍵因素，在當(dāng)代游戲?qū)π阅芤笤絹?lái)越高的背景下，如何提高A*算法的性能是A*算法研究面臨的主要挑戰(zhàn)。第三，在兩個(gè)節(jié)

3、點(diǎn)之間通常存在多個(gè)最佳等效路徑，A*算法會(huì)考察所有等效路徑從而影響了A*算法的運(yùn)行效率。本文針對(duì)上述三個(gè)問(wèn)題，進(jìn)行了以下研究：
　　(1)研究了A*算法啟發(fā)式函數(shù)f(n)=g(n)+h(n)在不同游戲網(wǎng)格類(lèi)型中選擇不同度量方法的差異，獲得了在不同游戲網(wǎng)格類(lèi)型中A*算法啟發(fā)式函數(shù)的選擇方案。
　　(2)通過(guò)組合優(yōu)先隊(duì)列和字典類(lèi)，提出了一種優(yōu)化數(shù)據(jù)結(jié)構(gòu)集合替代A*算法中的集合，降低了A*算法數(shù)據(jù)操作的時(shí)間復(fù)雜度。
　　(3