基于灰度圖像邊緣檢測的３Ｄ游戲路徑搜索

摘 要：著重研究了3D游戲中路徑搜索算法。其路徑搜索算法內(nèi)容包括障礙認(rèn)知與標(biāo)志、A路徑規(guī)劃、高度代價函數(shù)與路徑最短相結(jié)合的，由計算粒度引出的基于靜態(tài)障礙物體碰撞檢測的動態(tài)路徑規(guī)劃。該算法在實際的游戲引擎中進(jìn)行了測試，其效率和實時性都滿足要求。

關(guān)鍵詞：灰度圖像； 路徑搜索； 邊緣檢測； A算法

中圖分類號：TP391.41文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)06-2387-03

doi:10.3969/j.issn.1001-3695.2009.06.117

Path finding in 3D game based on gray image edge detection

SHEN Lina， HE Ming-yun b， CHEN Lei-ting b

(a.School of Software， b.School of Computer Science Engineering，University of Electronic Science Technology of China， Chengdu 610054，China)

Abstract:

This paper focused on path searching algorithm in the 3D games. The contents of the path searching algorithm included cognize and mark of the obstacle， route planning through A algorithm， dynamic route planning which combined with the cost function of high and shortest path searching and which derivatived by the granular computing and based on static obstacles object collision detection. This algorithm was tasted in the actual game engine， and it met the efficiency and real-time requirements were met.

Key words：gray image; path searching; edge detection; Aalgorithm

0 引言

隨著當(dāng)今游戲產(chǎn)業(yè)的迅猛發(fā)展，為了滿足玩家對于游戲渲染的真實感需求，游戲不得不逐漸由2D向3D過渡。3D游戲比2D游戲更能展示其空間信息和視覺真實效果，但提高了對游戲真實物理碰撞效果模擬以及角色智能行為模擬的要求。對于游戲程序設(shè)計師來說，除了完成2D游戲中應(yīng)有的如決策樹等復(fù)雜的游戲AI以外，使一個對象從點A智能地運動到點B成為了一項新的挑戰(zhàn)。而在當(dāng)今復(fù)雜的3D游戲環(huán)境中，這也是一項首先需要完成的任務(wù)。

當(dāng)前的3D路徑搜索方法，一般都是通過一些轉(zhuǎn)換將3D空間轉(zhuǎn)換為更為慣用的2D空間，如Greg Snook所提出的導(dǎo)航網(wǎng)格進(jìn)行尋徑；Thomas Young所提出的基于可視點尋徑。目前成熟的A*算法只針對二值障礙園，其障礙已經(jīng)通過集合方式標(biāo)示出來。本文提出了一種基于灰度圖像進(jìn)行邊緣檢測并結(jié)合A*算法進(jìn)行3D路徑查找的方法。

1 簡介

三維游戲中場景地形高度數(shù)據(jù)往往來自于高層灰度圖，因此三維游戲中物理碰撞檢測以及路徑規(guī)劃等都需要以該高層灰度圖為基礎(chǔ)。本文擬開發(fā)一個數(shù)字內(nèi)容創(chuàng)作環(huán)境，其地形基于灰度圖自動生成地形的高度：

h(x，y，m)=αg(x，y，n)+m(x，y，n)（1）

其中：x、y為對應(yīng)的點的坐標(biāo)；n為灰度圖對應(yīng)的灰度值；g(x，y，n)為原灰度圖像；α為變換系數(shù)，可以為任意常數(shù)，當(dāng)然如果想生成一些奇異的地形，也可以考慮將α設(shè)置為一個自定義的函數(shù)；m(x，y，n)為點與點間的插入點函數(shù)；h(x，y，m)為所要得到的對應(yīng)點的高度值。

當(dāng)自動產(chǎn)生地形高度值以后，編輯器自動加載地形紋理進(jìn)行渲染。除此之外，編輯器還可構(gòu)建場景中所需要的樹木、角色乃至諸如風(fēng)向、雨雪等自然景觀，如圖1所示。



本文對地形灰度圖進(jìn)行邊緣檢測，通過一定的閾值篩選，描繪出地形中梯度變化顯著的障礙物輪廓，同時將人工場景編輯中所定義的樹木、房屋等不可逾越的物體以基于粒度的計算方式設(shè)置為障礙物，得到一個二值圖像；然后再以該二值圖像為背景，利用改進(jìn)的A*算法，基于路徑的規(guī)劃和能量最小函數(shù)對任意兩點間的最短路徑進(jìn)行搜索；最后將得到的路徑在3D地形上以射線查詢的方式把物體所要移動的點恢復(fù)到場景內(nèi)。

2 障礙物認(rèn)知與標(biāo)志

2.1 地形灰度圖的邊緣檢測

所謂圖像的邊緣是指圖像局部區(qū)域亮度變化顯著的部分。該區(qū)域的灰度剖面一般可以看做是一個階躍，即從一個在很小的緩沖區(qū)域內(nèi)的灰度值急劇變化到另一個灰度相差較大的灰度值，因此圖像的邊緣確定了整個3D場景的障礙物輪廓。邊緣檢測便是通過一定的圖像處理步驟描繪出圖像梯度變化顯著的輪廓，圖像檢測處理過程如圖2所示。



本文采用綜合評價比較好的Canny算法對灰度圖進(jìn)行邊緣化處理：

a）地形灰度圖使用帶有指定標(biāo)準(zhǔn)差σ的高斯濾波器來平滑圖像以減少噪聲。高斯函數(shù)為

H(x，y)=e－r2/（2σ2）(1)

其中：r=a2+b2；σ是標(biāo)準(zhǔn)差。

G(x，y)=f(x，y)×H(x，y)(2)

其中：f(x，y)為原灰度圖；G(x，y)為平滑后的結(jié)果圖像。

b）對每一點計算局部梯度和邊緣方向，邊緣點定義為梯度方向上其強(qiáng)度的局部最大點。

局部梯度：g(x，y)=G2x+G2y1/2(3)

邊緣方向：α(x，y)=arctan(Gy/Gx)(4)

其中：Gx、Gy為Sobel邊緣檢測器中使用掩模數(shù)字化的近似一階導(dǎo)數(shù)值，如圖3、4所示。

Gx=(z7+2z8+z9)－(z1+2z2+z3)(5)

Gy=(z3+2z6+z9)－(z1+2z4+z7)(6)

其中：z1～z9為定義的圖像的鄰域，如圖5所示。



c）上一步所確定的邊緣點會產(chǎn)生梯度幅度圖中的脊。算法會追蹤所有的脊的頂部，并將所有不在脊頂部的像素設(shè)為零，其表現(xiàn)為輸出一條細(xì)線，該細(xì)線便作為地形中障礙物的邊緣。

d）算法通過將8連接的弱像素集成到強(qiáng)像素，執(zhí)行邊緣鏈接。

2.2 加載人工輸入障礙

當(dāng)手動編輯地形紋理時，編譯器會將水面、樹木、房屋等不能逾越的物體設(shè)置為障礙物。處理方法為將通過邊緣檢測生成的二值圖像上所對應(yīng)的點的值直接設(shè)置為1。

當(dāng)灰度圖通過轉(zhuǎn)換為高度圖后如圖6~8所示，像素點之間會插入許多的動態(tài)點以平滑地形中的坡度。如圖9中的點1~11和對應(yīng)的圖10中的點1~11中插入的灰色區(qū)域，也就是式(1)中m(x，y，n)所生成的點。由于人工障礙物的設(shè)置是在轉(zhuǎn)換后的地形上直接進(jìn)行編輯，那么手動編輯的障礙物就有可能設(shè)置在插值的點上，如圖10中的點12。這些點不會在原灰度圖中體現(xiàn)出來，但卻會直接影響到路徑搜索的結(jié)果。然而由于變換后的地形非常龐大以至于不可能通過保存生存后的地形來實現(xiàn)關(guān)于該種類型點的查詢，因而考慮對結(jié)果進(jìn)行動態(tài)的碰撞檢測。

如圖11和12所示，當(dāng)忽略插值點障礙時，A到B的最短路徑應(yīng)該為A→1→5→9→B。而圖10中，當(dāng)設(shè)置插值點障礙后，由于點1到點5中間插入了障礙12，尋徑算法在動態(tài)檢測到點12為不可通過時，將直接進(jìn)行下一輪的路徑搜索，最后搜索的結(jié)果為A→1→2→6→9→B。顯然，這與不加入插值障礙的結(jié)果是截然不同的。



路徑搜索必須是基于結(jié)果二值圖像所描述的靜態(tài)障礙物碰撞檢測的基礎(chǔ)上，對其作動態(tài)的路徑規(guī)劃。

3 對結(jié)果圖片進(jìn)行路徑搜索

將上幾步處理后的二值圖像作為結(jié)果圖片，采用A算法進(jìn)行二維路徑搜索。與之不同的是，本文對傳統(tǒng)的A算法作了一些優(yōu)化。

3.1 傳統(tǒng)A*算法

傳統(tǒng)A算法跟蹤記錄兩個狀態(tài)表，稱為open狀態(tài)表和close狀態(tài)表，分別表示未檢查狀態(tài)和已檢查狀態(tài)。開始時close狀態(tài)表為空，open狀態(tài)表記錄初始狀態(tài)。當(dāng)?shù)_始時，算法將open表中最合適的狀態(tài)取出進(jìn)行驗證。如果這個狀態(tài)不是目標(biāo)狀態(tài)，則將它的相鄰位置排序；否則，它將被放入open表中。如果它已經(jīng)在open表中并且它是一個代價更低的路徑，則關(guān)于這些位置的信息將被更新；如果它已經(jīng)在close表中，由于已經(jīng)被檢驗過，它將被略過。當(dāng)目標(biāo)找到以前open表就已經(jīng)變空，則意味著沒有從該起始位置到目標(biāo)位置的路徑。

3.2 高度代價函數(shù)

本文在最短路徑搜索中引入高度代價函數(shù)E=∑ni=1XiYi。其中：Xi為高度的代價值；Yi為所對應(yīng)的高度，如表1所示。其目的是讓物體在移動中模擬人的思維——盡量地選擇平地而不是爬坡以減少能量消耗，引入每個高度所對應(yīng)的線性運動所需的時間。簡單地說就是，面對一個平面和一個土坡，物體更愿意選擇平面作為自己的行徑路線，而不是代價較高的土坡。

雖然這在2D的地形中會造成路徑的扭曲，但是在3D地形中，隨著Z方向上高度的引入，這種視覺差異會大大地降低。

4 游戲場景中的實現(xiàn)

在最短路徑確定以后，首先在灰度圖轉(zhuǎn)換后所確定的地形最高點上方，將最短路徑所對應(yīng)的點用數(shù)組進(jìn)行存儲；然后當(dāng)物體需要沿著該路徑移動的時候，依次以每一個點為起點，對地面作射線查詢，射線與地面的交點就是物體所需移動到的點位置。

如圖13所示，zh為灰度圖轉(zhuǎn)換為地形高度值中的最高點，因此所確定的兩點間最短路徑的點所組成的數(shù)組pi必須保證高度值大于zh；然后以pi為定點，以與地面法向方向相反的方向作射線，射線與地形的交點zi就是要查詢的路徑中移動點的位置信息。按照點的數(shù)組的順序，將所有的點所對應(yīng)的高度都查詢出來，然后物體按順序進(jìn)行移動，至此就完成了物體在3D地形中兩點間的最短路徑移動。

5 關(guān)于改進(jìn)的思考

1)邊緣檢測的不足

對于將灰度圖進(jìn)行邊緣檢測從而確定地形中的障礙物位置，從原理上說就是一個邊緣檢測的實現(xiàn)。但是當(dāng)今的邊緣檢測技術(shù)總體上說都還不是很成熟，因此本文在邊緣檢測的閾值選取中就更應(yīng)該小心，以避免物體在運動中出現(xiàn)較大的抖動。

2）直線的平滑

后期的工作中主要考慮采用Catmull-Rom樣條曲線來完成直線的平滑工作。

output_point = point_1 * (-0.5f*u*u*u + u*u - 0.5f*u) +

point_2 * (1.5f*u*u*u-2.5f*u*u - 1.0f) +

point_3 * (-1.5f*u*u*u + 2.0fu*u + 0.5f*u) +

point_4 * (0.5f*u*u*u - 0.5f*u*u) ;

每次調(diào)用Catmull-Rom公式時，它將在第二個和第三個輸入點間近似u%的地方給出一個點。其中：u是自行定義的一個數(shù)。這樣所生成的路線看上去將會更加理性，而非因數(shù)據(jù)差異過大所造成的醉漢式的路線。

6 結(jié)束語

三維空間中的最短路徑查詢一直以來都是游戲開發(fā)中的難點，本文擬通過對灰度圖像的處理實現(xiàn)關(guān)于3D空間中兩點間的最短路徑查詢。下一步將繼續(xù)完善關(guān)于最短路徑查詢的效率和視覺美感間的矛盾。

參考文獻(xiàn):

[1]WOODS R E， GONZALEZ R C， EDDINS S L.數(shù)字圖像處理:MATLAB版[M].北京:電子工業(yè)出版社，2005.

[2]劉瑞禎，于仕琪.OpenCV教程[M].北京：北京航空航天大學(xué)出版社，2007.

[3]NILSSON N J. Artificial intelligence: a new synthesis[M].San Francisco:Morgan Kaufmann，1998.

[4]ENCARNASIIO P， PASCOAL A. 3D path following for autonomous underwater vehicle[C]//Proc of the 39th IEEE Conference on Decision and Control.2000.

[5]HELBLE H， CAMERON S. 3-D path planning and target trajectory prediction for the Oxford aerial tracking system[C]//Proc of IEEE International Conference on Robotics and Automation. 2007:1042-1048.

[6]HUI Y C， PRAKASH E C， CHAUDHARI N S. Game AI: artifical intelligence for 3D path finding[C]//Proc of IEEE Pegion 10 Confe-rence. Piscataway:IEEE Press， 2004:306-309.

[7]ZELEZNIK R C， KEEFE D F. Tech-note: dynamic dragging for input of 3D trajectories[C]//Proc of IEEE Symposium on 3D User Interfaces.2008:51-54.

[8]DARKEN C J， ANDEREGG B G， McDOWELL P L. Game Al in Delta3D[C]//Proc of IEEE Symposium on Computational Intelligence and Games.2007:312-319.

[9]HARALDSDOTTIR A， SCHARL J， BERGE M E， et al. Performance analysis of arrival management with 3D paths and speed control[C]//Proc of the 26th Digital Avionics Systems Conference.2007:5-13.

[10]DAI Guang-ming， DU An-hong， LI Qing-hua. Planning of moving path based on simplified terrain[C]//Proc of the 2nd International Conference on Machine Learning and Cybernetics.2003:1915-1918.

[11]WANG Xun， JIN Jian-qiu. An edge detection algorithm based on improved canny operator[C]//Proc of the 7th International Conference on Intelligent Systems Design and Applications.2007:623-628.

[12]SHI Hong-jan， WARD R. Canny edge based image expansion[C]//Proc of IEEE International Symposium on Circuits and Systems. 2002:785-788.

[13]BAO P N， ZHANG Lei， WU Xiao-lin. Canny edge detection enhancement by scale multiplication[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2005，27(9):1485-1490.