計算機游戲中地圖路徑發現算法的優化與實現

邱 磊

(武漢船舶職業技術學院計算機教研室,湖北武漢430050)

計算機游戲中地圖路徑發現算法的優化與實現

邱 磊

(武漢船舶職業技術學院計算機教研室,湖北武漢430050)

在概述地圖路徑發現問題的基礎上,給出了一個平滑A*算法所得路徑的方法.為了達到平滑路徑的目的,先采用了最直接的路線,忽略了轉彎,然后用一個預平滑過程來處理路徑,在A*算法找到路徑后再進行處理.討論了如何改進A*算法的啟發函數.給出一個引導型A*算法,主要的改變是將結點空間從二維擴展到三維,使搜索過程能曲線轉彎,避免了碰撞障礙物,實現了“合法”轉彎.

游戲地圖；路徑發現；A*算法；啟發函數

路徑發現算法是策略型計算機游戲中的關鍵技術,是游戲人工智能領域的基礎和重要組成部分.路徑發現系統使用啟發式搜索算法對游戲地圖進行搜索,現階段國內外的相關研究集中在算法的優化和搜索空間的簡化上.A*算法作為一種啟發式搜索算法［1］被廣泛地應用,很多文獻探討對A*算法的優化問題［2-4］.因此,對地圖路徑發現方法進行優化與改進,在提高計算機游戲的性能方面有較大應用價值,本文擬結合幾種現實化的技術優化地圖路徑發現算法,并對其進行實現與分析.

1 關于路徑發現問題

首先以一個虛構的亞斯蘭大陸地圖(圖1)來介紹路徑發現問題,假設要找到從月影村到萬念崖的最短路徑,每前進一步都有很多不同的路徑到不同的地點,可以通過評估函數來評估各條路徑的好壞,評估函數的作用就是預測評估各可能路徑的好壞,并返回一個數值.每走一步都選擇評估函數返回值最小的路徑,直到到達目的地,這種搜索算法稱之為最佳優先搜索.以當前所在地點到目的地的直線距離作為評估函數的返回值,則最佳優先搜索的搜索過程如圖2所示.

圖1 亞斯蘭大陸地圖

圖2 最佳優先搜索的樹狀展開圖

在搜索時,每一步先找到與當前所在地點連接的所有鄰近地點,然后使用評估函數,選擇評估函數返回數值最小的地點作為下一步的起點.比如當走到丁香谷后,應選擇凄惶嶺作為下一步的地點.這樣一步一步,直到發現評估函數返回值為0,表明已經到了目的地.但該算法實際上有嚴重的缺陷：首先,它所找到的路徑不是最短的,丁香谷的下一步應該選黑森林入口,而不是凄惶嶺.因為這個算法只顧眼前利益,無法保證長遠(全局)最優,因此習慣地稱之為“貪婪算法”.其次,貪婪算法有可能很慢,它有可能在一開始就沿著錯誤的路徑走下去,直到醒悟回來再往回折.比如,要從忘憂城走到水晶城堡,用貪婪算法的話第一步會走到惡魔城,但實際上惡魔城是一條死路.

上述問題的癥結就在于沒有考慮已經走過的路的距離,如果把估價函數改進一下：f(n)=g(n)+ h(n)［5-6］,其中g(n)為從起始點到地點n的實際最短距離；h(n)為從地點n到目的地的預測最短距離,稱之為啟發函數.使用f(n)這種估價函數的最佳優先搜索算法就叫做A*算法.可以從數學上證明：如果從地點n到目的地的實際最短距離總是大于或等于h(n)的話,則A*算法是全局最優的,也就是說A*算法總能找到最短的路徑［7］,而且還可以證明A*算法是效率最高的.使用A*算法搜索過程的樹狀展開圖如圖3所示.

圖3 A*算法搜索過程的樹狀展開圖

2 路徑發現算法的優化

路徑發現要求搜索的路徑盡量平滑和自然,本節探討幾種現實化的技術,以使游戲中各類物體能實現更真實、形象的運動.

2.1 簡單平滑算法

標準A*算法求得路徑后,利用函數Walkable (point A,pointB),按照一給定的粒度(通常采用格子寬度的1/5)沿著從點A到點B的連線采樣.同時,基于圍繞游戲物體中心的菱形圖案的四個點,利用游戲物體的寬度,在每個點處檢查游戲物體是否重疊了任何相鄰的堵塞方格；如果遇到的是未堵塞的方格,該函數返回真,否則返回假.

算法執行時,在最后一個關鍵點能從當前位置被看到之前,所有的關鍵點都會被逐步忽略,由于加入了基于角色寬度的碰撞檢測,因此結果很精確.

2.2 曲線轉彎技術

我們要為游戲物體添加現實的曲線轉彎,以使它們每次需要轉彎時,改變方向顯得不那么生硬.為此,首先要知道什么是游戲物體的轉彎半徑：物體沿著某圈圈運動,該圓圈的半徑就是該物體的轉彎半徑.當在初始點朝著某個方向需要到達目標點時,可找到的最短路徑有兩種可能：一種是盡可能向左轉,走個圓圈至方向正好對準了目標點,然后繼續前進；一種是選擇右轉,然后進行相同處理.利用某些幾何關系,兩種最短路徑的長度可證明很容易被計算出來,然后選擇較短的一個.

2.3 引導型A*算法

引導型A*算法不用＜X,Y＞表示二維結點網格上結點的位置,而是采用三維的結點空間,用＜X,Y,方向＞表示結點的位置,新增的方向是指南針的八個方向之一.算法執行過程中,當在結點p去檢查其子結點q時,不僅要檢查q是否是一個堵塞的方格,還要檢查從p到q的曲線路徑是否是可行的；若可行并且沿著該路徑行進不會撞到任何被堵塞的方格,則認為該子結點是有效的.因此,對于給定的游戲物體尺寸和轉彎半徑,按上述檢查后求得的有效路徑才是“合法”的.

為了實現引導型A*算法,必須解決在考慮起始方向、后續方向定位以及轉彎半徑,甚至結束方向的情況下,如何計算從p到q的最短路徑.我們需要在地圖的當前位置和方位至下一個關鍵點之間計算出最短的“合法”路徑,并且在到達關鍵點時面向一個既定的方向：一種情況是沿著相同的方向(順時針或逆時針)繞過兩個圓弧；一種情況是沿著不同的轉向繞過兩個圓弧,求解過程中運用了三角幾何知識［］.

2.4 啟發函數的改進

改進的A*算法需要一個改進的啟發值［9］,標準A*算法的啟發函數只是從當前位置到目標點的直線距離,使用該啟發函數在每個位置都需要對八個基本方向進行等價的處理,這會導致搜索時間相當長.然而,為了利用當前點指向目標點的角度以及轉彎半徑,把啟發函數變成從當前位置到目標點的最短曲線距離加上指向目的地的角度,為了避免每次按上述計算,我們預先建立一個啟發代價表.該表內容為：從當前位置到任何角度、10個方格距離范圍以內的目標點的啟發值；對于超出10個方格距離的目標點按10個方格來計算,并加上與實際距離的差量.由于該表依賴于游戲物體的轉彎半徑,如果轉彎半徑改變,我們需要重新計算這個表.

2.5 簡單平滑算法的改進

在A*算法找到路徑后,首先用一個預平滑過程來處理路徑,然后再用本文的簡單平滑算法,與引導型-48(搜索3個方格距離內的所有方格稱為引導型-48搜索,共48*8=384個子結點)搜索的區別在于：只允許沿著之前A*算法找出來的路徑上的結點移動,并且假定每個結點的前方第1個、2個或第3個方格的相鄰方格都是原來路徑的關鍵點,同時修改啟發函數的代價使之朝著最初路徑確定的方向搜索.

3 實現與分析

圖4 路徑發現優化技術示意圖

圖4 (a)使用標準A*算法路徑發現后返回的結果,產生了不盡人意的“Z字形”效果；圖4(b)采用后處理技術平滑后的路徑；圖4(c)為沿著轉彎半徑進行平滑轉彎的效果；圖4(d)為引導性A*算法實現的“合法”轉彎,使得搜索過程能曲線轉彎,避免了碰撞障礙物.轉彎半徑成為了搜索的一部分,這就保證在整條路徑里只包含“合法”的轉彎.

如圖5所示,標準A*算法找到的最短的路徑是從a到c,但由于c處周圍障礙物間的“空隙”使得轉彎半徑的大小不足以使游戲物體在c處右轉彎,于是此種情況下,標準A*算法將返回一個無效的路徑.若采用本文的引導型A*算法,游戲物體在發現上述障礙物情況后,會尋找一條穿過位置b的替代路徑.但同時我們會發現,即使在b處,一個90°的左轉彎同樣由于障礙物間的“空隙”太小而不可行.于是,引導型A*算法最終選擇了先做一個右轉圈,然后再繼續前進.

圖5 路經發現算法的優化實現

4 結束語

算法實現的結果說明,地圖路徑發現算法的優化有效地平滑了標準A*算法計算出的路徑,避開了由于轉彎半徑太小游戲物體無法轉彎的情況,保證了最優路徑的求解.引導型A*算法的時間主要花費在檢查堵塞單元的內部循環上,通過代碼優化,可使性能提高一倍,另外,針對啟發函數的改進及48結點平滑的修改均能加快發現潛在的路徑,所有這些優化為玩家帶來了審美上更加愉悅的體驗.總之,地圖路徑發現算法作為游戲引擎中的一個核心組成部分,仍是人工智能領域的一個熱點問題,通常需混合多種技術才能得到一個比較好的解決方案,本文對此做了有益的探索.

［1］李艷,陳彩,李鐵松,等.游戲地圖中的分層動態路徑搜索算法［J］.計算機工程,2012(1)：288-289.

［2］林篤斌,李欣.基于DEM格網的改進型A*路徑搜索算法［J］.計算機工程與設計,2011(10)：3414-3418.

［3］李楠,趙擎,徐肖豪.基于A*算法的機場滑行路徑優化研究［J］.計算機仿真,2012(7)：88-92.

［4］王殿君.基于改進A*算法的室內移動機器人路徑規劃［J］.清華大學學報：自然科學版,2012(8)：1085-1089.

［5］Anand A.Path planning in agents with incomplete information in dynamic environments［D］.Melbourne：Royal Melbourne Institute of Technology,2011.

［6］邱磊.基于A*算法的游戲地圖尋路實現及性能比較［J］.陜西科技大學學報：自然科學版,2011(6)：89-93.

［7］葉展.游戲的設計與開發：夢開始的地方［M］.北京：人民交通出版社,2003：265-267.

［8］Pinter M.Toward More Realistic Pathfinding［DB/OL］.(2001-03-14).http：//www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php.

［9］邱磊.2D游戲地圖的尋路實現［J］.湖南工業大學學報,2012 (1)：66-69.

(編輯:姚佳良)

Optimization and implementation of pathfinding algorithms for game maps

QIU Lei
(Staff Room of Computer,Wuhan Institute of Shipbuilding Technology,Wuhan 430050,China)

Based on the summary of the pathfinding questions,a method of smoothing the path which A*algorithm computed was given.In order to achieve this effect,we firstly took the most direct route,regardless of the angle,and then used a new pre-smoothing path before the standard A*algorithm found and completed its path.We introduced how to modify heuristic of A*algorithm,and gave a directional A*algorithm.The main change to the algorithm was the addition of a third dimension to two-dimension node,which enabled searching process include curved turns,and avoid collisions.

game map；pathfinding；A*algorithm；heuristic

1672―6197(2013)01―0038―04

TP312；TP391

A

2012- 11- 11

邱磊,男,tsuly@163.com