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

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

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

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