邱 磊

(武漢船舶職業(yè)技術(shù)學(xué)院計(jì)算機(jī)教研室,湖北武漢430050)

計(jì)算機(jī)游戲中地圖路徑發(fā)現(xiàn)算法的優(yōu)化與實(shí)現(xiàn)

邱 磊

(武漢船舶職業(yè)技術(shù)學(xué)院計(jì)算機(jī)教研室,湖北武漢430050)

在概述地圖路徑發(fā)現(xiàn)問(wèn)題的基礎(chǔ)上,給出了一個(gè)平滑A*算法所得路徑的方法.為了達(dá)到平滑路徑的目的,先采用了最直接的路線,忽略了轉(zhuǎn)彎,然后用一個(gè)預(yù)平滑過(guò)程來(lái)處理路徑,在A*算法找到路徑后再進(jìn)行處理.討論了如何改進(jìn)A*算法的啟發(fā)函數(shù).給出一個(gè)引導(dǎo)型A*算法,主要的改變是將結(jié)點(diǎn)空間從二維擴(kuò)展到三維,使搜索過(guò)程能曲線轉(zhuǎn)彎,避免了碰撞障礙物,實(shí)現(xiàn)了“合法”轉(zhuǎn)彎.

游戲地圖；路徑發(fā)現(xiàn)；A*算法；啟發(fā)函數(shù)

路徑發(fā)現(xiàn)算法是策略型計(jì)算機(jī)游戲中的關(guān)鍵技術(shù),是游戲人工智能領(lǐng)域的基礎(chǔ)和重要組成部分.路徑發(fā)現(xiàn)系統(tǒng)使用啟發(fā)式搜索算法對(duì)游戲地圖進(jìn)行搜索,現(xiàn)階段國(guó)內(nèi)外的相關(guān)研究集中在算法的優(yōu)化和搜索空間的簡(jiǎn)化上.A*算法作為一種啟發(fā)式搜索算法［1］被廣泛地應(yīng)用,很多文獻(xiàn)探討對(duì)A*算法的優(yōu)化問(wèn)題［2-4］.因此,對(duì)地圖路徑發(fā)現(xiàn)方法進(jìn)行優(yōu)化與改進(jìn),在提高計(jì)算機(jī)游戲的性能方面有較大應(yīng)用價(jià)值,本文擬結(jié)合幾種現(xiàn)實(shí)化的技術(shù)優(yōu)化地圖路徑發(fā)現(xiàn)算法,并對(duì)其進(jìn)行實(shí)現(xiàn)與分析.

1 關(guān)于路徑發(fā)現(xiàn)問(wèn)題

首先以一個(gè)虛構(gòu)的亞斯蘭大陸地圖(圖1)來(lái)介紹路徑發(fā)現(xiàn)問(wèn)題,假設(shè)要找到從月影村到萬(wàn)念崖的最短路徑,每前進(jìn)一步都有很多不同的路徑到不同的地點(diǎn),可以通過(guò)評(píng)估函數(shù)來(lái)評(píng)估各條路徑的好壞,評(píng)估函數(shù)的作用就是預(yù)測(cè)評(píng)估各可能路徑的好壞,并返回一個(gè)數(shù)值.每走一步都選擇評(píng)估函數(shù)返回值最小的路徑,直到到達(dá)目的地,這種搜索算法稱之為最佳優(yōu)先搜索.以當(dāng)前所在地點(diǎn)到目的地的直線距離作為評(píng)估函數(shù)的返回值,則最佳優(yōu)先搜索的搜索過(guò)程如圖2所示.

圖1 亞斯蘭大陸地圖

圖2 最佳優(yōu)先搜索的樹(shù)狀展開(kāi)圖

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

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

圖3 A*算法搜索過(guò)程的樹(shù)狀展開(kāi)圖

2 路徑發(fā)現(xiàn)算法的優(yōu)化

路徑發(fā)現(xiàn)要求搜索的路徑盡量平滑和自然,本節(jié)探討幾種現(xiàn)實(shí)化的技術(shù),以使游戲中各類物體能實(shí)現(xiàn)更真實(shí)、形象的運(yùn)動(dòng).

2.1 簡(jiǎn)單平滑算法

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

算法執(zhí)行時(shí),在最后一個(gè)關(guān)鍵點(diǎn)能從當(dāng)前位置被看到之前,所有的關(guān)鍵點(diǎn)都會(huì)被逐步忽略,由于加入了基于角色寬度的碰撞檢測(cè),因此結(jié)果很精確.

2.2 曲線轉(zhuǎn)彎技術(shù)

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

2.3 引導(dǎo)型A*算法

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

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

2.4 啟發(fā)函數(shù)的改進(jìn)

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

2.5 簡(jiǎn)單平滑算法的改進(jìn)

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

3 實(shí)現(xiàn)與分析

圖4 路徑發(fā)現(xiàn)優(yōu)化技術(shù)示意圖

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

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

圖5 路經(jīng)發(fā)現(xiàn)算法的優(yōu)化實(shí)現(xiàn)

4 結(jié)束語(yǔ)

算法實(shí)現(xiàn)的結(jié)果說(shuō)明,地圖路徑發(fā)現(xiàn)算法的優(yōu)化有效地平滑了標(biāo)準(zhǔn)A*算法計(jì)算出的路徑,避開(kāi)了由于轉(zhuǎn)彎半徑太小游戲物體無(wú)法轉(zhuǎn)彎的情況,保證了最優(yōu)路徑的求解.引導(dǎo)型A*算法的時(shí)間主要花費(fèi)在檢查堵塞單元的內(nèi)部循環(huán)上,通過(guò)代碼優(yōu)化,可使性能提高一倍,另外,針對(duì)啟發(fā)函數(shù)的改進(jìn)及48結(jié)點(diǎn)平滑的修改均能加快發(fā)現(xiàn)潛在的路徑,所有這些優(yōu)化為玩家?guī)?lái)了審美上更加愉悅的體驗(yàn).總之,地圖路徑發(fā)現(xiàn)算法作為游戲引擎中的一個(gè)核心組成部分,仍是人工智能領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題,通常需混合多種技術(shù)才能得到一個(gè)比較好的解決方案,本文對(duì)此做了有益的探索.

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

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

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

［4］王殿君.基于改進(jìn)A*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版,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*算法的游戲地圖尋路實(shí)現(xiàn)及性能比較［J］.陜西科技大學(xué)學(xué)報(bào)：自然科學(xué)版,2011(6)：89-93.

［7］葉展.游戲的設(shè)計(jì)與開(kāi)發(fā)：夢(mèng)開(kāi)始的地方［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游戲地圖的尋路實(shí)現(xiàn)［J］.湖南工業(yè)大學(xué)學(xué)報(bào),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