Unity3D隨機(jī)尋路算法設(shè)計(jì)

史寶明，賀元香，李 嵐

(蘭州文理學(xué)院 數(shù)字媒體學(xué)院，甘肅 蘭州 730010)

在進(jìn)行Unity3D游戲開發(fā)過程中，物體在場(chǎng)景中隨機(jī)游走是經(jīng)常要實(shí)現(xiàn)的功能，常見的游戲?qū)ο笥巫咄ǔＴO(shè)置固定的線路，讓游戲?qū)ο笱刂付ǖ能壽E行進(jìn)，這種方法易于實(shí)現(xiàn)，因而在游戲場(chǎng)景中較為常見，并且這種方式可以沿著地形精確的繪制游走路徑，靈活的控制和調(diào)整游走對(duì)象在游走路徑不同位置的角度、速度等參數(shù)，使得游走動(dòng)作連貫、逼真.但是這種方式由于游走路線固定不變，游戲?qū)ο竺看斡巫叩穆窂蕉家粯?，游走行為一成不變，?dǎo)致游戲交互中缺乏隨機(jī)性和趣味性.另外一種游走是通過設(shè)計(jì)尋路算法來實(shí)現(xiàn)，如Unity3D中的導(dǎo)航網(wǎng)格尋路[1-2]以及文獻(xiàn)[3-6]中所研究的算法，這種方式行走路徑由智能算法隨機(jī)產(chǎn)生，每次行走的路線是隨機(jī)的.但是游戲?qū)ο蟀催@種方式游走時(shí)，需著力解決游戲?qū)ο笤诓煌匦斡绊懴碌慕嵌?、速度匹配問題以及轉(zhuǎn)身問題，否則有可能出現(xiàn)游走動(dòng)作未匹配地形，或者游戲角色在轉(zhuǎn)身過程中的動(dòng)作怪異或不連貫，導(dǎo)致游走行為出現(xiàn)Bug，因此有必要深入探討游戲?qū)ο笤谟螒驁?chǎng)景中的隨機(jī)尋路算法.

1 理論基礎(chǔ)

隨機(jī)尋路算法的實(shí)現(xiàn)要著力解決游走對(duì)象在行進(jìn)過程中的角度控制問題和速度控制問題.角度控制實(shí)際上就是控制對(duì)象的選擇，這涉及歐拉角和四元數(shù)的轉(zhuǎn)換問題，角色行走過程中的速度控制問題考慮通過插值運(yùn)算函數(shù)來解決.本節(jié)通過深入討論歐拉角、四元數(shù)、插值運(yùn)算等相關(guān)的數(shù)學(xué)理論和應(yīng)用，來設(shè)計(jì)實(shí)現(xiàn)隨機(jī)尋路算法.

1.1 歐拉角與四元數(shù)

Unity3D游戲開發(fā)中，隨機(jī)游走時(shí)要時(shí)刻根據(jù)地形調(diào)整移動(dòng)對(duì)象的角度，這涉及對(duì)象的旋轉(zhuǎn)控制問題，常用的角度旋轉(zhuǎn)表示方法一般有歐拉角和四元數(shù).歐拉角是指在三維空間通過指定與三個(gè)旋轉(zhuǎn)軸相關(guān)聯(lián)的三個(gè)角度來表示任意方向的方法，是用來表示三維坐標(biāo)系中方向和方向變換的，由章動(dòng)角、旋進(jìn)角和自轉(zhuǎn)角三部分組成.歐拉角表示角度直觀方便，但采用不同的軸序旋轉(zhuǎn)有可能會(huì)造成不同的旋轉(zhuǎn)結(jié)果，因此需要按指定的軸序進(jìn)行旋轉(zhuǎn)，并且當(dāng)在旋轉(zhuǎn)過程中如果發(fā)生旋轉(zhuǎn)軸和坐標(biāo)軸重合的情況時(shí)，會(huì)引起萬向死鎖，這時(shí)會(huì)丟失一個(gè)方向上的旋轉(zhuǎn)能力，也就是說在這種狀態(tài)下無論怎樣旋轉(zhuǎn)都無法得到想要的旋轉(zhuǎn)效果.

由于歐拉角旋轉(zhuǎn)可能出現(xiàn)萬向死鎖問題，因此Unity3D游戲開發(fā)中更為常用的是四元數(shù)旋轉(zhuǎn).四元數(shù)是由愛爾蘭數(shù)學(xué)家哈密頓在1843年發(fā)明的數(shù)學(xué)概念[7].其本質(zhì)是一種高階復(fù)數(shù)，可以表示一個(gè)四維空間.四元數(shù)旋轉(zhuǎn)可以避免萬向死鎖現(xiàn)象、方便快捷，能提供平滑的插值效果，并且通常比矩陣旋轉(zhuǎn)的效率高，在游戲開發(fā)中有著廣泛的應(yīng)用[7-9].

1.2 插值運(yùn)算

游戲開發(fā)中當(dāng)游戲?qū)ο笤趫?chǎng)景中隨機(jī)游走時(shí)，游戲?qū)ο笪恢煤徒嵌葧?huì)發(fā)生實(shí)時(shí)變化，通常采用逐幀更新的方式來改變對(duì)象的位置和角度，而位置和角度的確定一般通過已知的起始點(diǎn)和確定的目標(biāo)點(diǎn)來進(jìn)行逐幀計(jì)算得到，這就需要用到插值運(yùn)算.

Unity3D的線性插值函數(shù)Lerp()可以實(shí)現(xiàn)兩個(gè)材質(zhì)之間、兩個(gè)向量之間、兩個(gè)浮點(diǎn)數(shù)之間、兩個(gè)顏色之間的插值運(yùn)算.在隨機(jī)尋路算法中，隨機(jī)游走對(duì)象位置的變化、角度的旋轉(zhuǎn)都可采用插值運(yùn)算來實(shí)現(xiàn)，這樣可避免生硬的角色移動(dòng)和旋轉(zhuǎn)，讓移動(dòng)、旋轉(zhuǎn)的動(dòng)作保持連貫.Unity3D中的插值函數(shù)可表示為

F=Lerp(start，end，t).

(1)

其中：start為插值的起始值；end為插值的終止值；t為插值點(diǎn)，其取0到1之間的浮點(diǎn)數(shù).start和end的取值可為材質(zhì)、浮點(diǎn)數(shù)、二維向量、三維向量和顏色值等，這里著重使用向量的插值運(yùn)算.

2 總體設(shè)計(jì)思路

隨機(jī)尋路算法主要包括隨機(jī)游走范圍的產(chǎn)生、隨機(jī)產(chǎn)生目標(biāo)點(diǎn)、位置偏移更新和角度偏移更新等幾個(gè)部分.整個(gè)隨機(jī)尋路算法的設(shè)計(jì)如下：

Step1 場(chǎng)景初始化，確定游戲?qū)ο箅S機(jī)游走的范圍.

Step2 在游走范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)新目標(biāo)點(diǎn).

Step3 游走對(duì)象從當(dāng)前位置開始，采用插值函數(shù)來逐幀更新對(duì)象的位置和角度.

Step4 判斷游戲?qū)ο笫欠竦竭_(dá)目標(biāo)點(diǎn)，如果到達(dá)目標(biāo)點(diǎn)，則跳轉(zhuǎn)到Step2；否則計(jì)算位置偏移值和角度偏移值，調(diào)整游戲?qū)ο蟮奈恢煤徒嵌群螅祷豐tep3.

整個(gè)隨機(jī)尋路算法的程序流程如圖1所示.

圖1 隨機(jī)尋路算法流程Fig.1 Flow chart of random routing algorithm

3 算法詳細(xì)設(shè)計(jì)

3.1 產(chǎn)生隨機(jī)游走范圍

游戲?qū)ο箅S機(jī)游走范圍的確定通過定義一個(gè)public類型的Rect對(duì)象moveRect來進(jìn)行限定，moveRect對(duì)象需要設(shè)置根坐標(biāo)(x，y)和寬高(width，height)來定義一個(gè)矩形區(qū)域(見圖2)，游戲設(shè)計(jì)過程中可根據(jù)游戲?qū)ο笤趫?chǎng)景中的位置來確定moveRect對(duì)象的初始化參數(shù).并可使用Gizmos對(duì)象的DrawWireCube()方法繪制立方體線框?qū)⒕匦螀^(qū)域顯示出來.

3.2 隨機(jī)產(chǎn)生目標(biāo)位置

在生成的矩形區(qū)域中隨機(jī)生成一個(gè)點(diǎn)作為目標(biāo)位置targetPos，目標(biāo)位置的確定方法如下：

targetPos.x=Random.Range(moveRect.xMin，moveRect.xMax)，

targetPos.z=Random.Range(moveRect.yMin，moveRect.yMax).

其中：moveRect.xMin3，moveRect.xMax，moveRect.yMin，moveRect.yMax分別為矩形對(duì)象moveRect在x，y方向上的最小值和最大值.Random.Range()方法則是在指定的一個(gè)區(qū)間內(nèi)返回一個(gè)隨機(jī)值.一般游戲?qū)ο笫谴_定其在xz平面上的隨機(jī)位置，而矩形對(duì)象采用的是xy坐標(biāo)平面，因此這里進(jìn)行簡(jiǎn)單的變換，將矩形區(qū)域的y值賦值給游戲?qū)ο蟮膠坐標(biāo)值.當(dāng)游戲?qū)ο笠苿?dòng)到目標(biāo)點(diǎn)后，自動(dòng)生成下一個(gè)目標(biāo)點(diǎn)，反復(fù)此過程，直到程序結(jié)束為止，詳細(xì)游走過程成如圖2所示.

圖2 隨機(jī)游走示例Fig.2 Random walk example map

3.3 位置偏移更新

3.3.1 逐幀勻速更新

pcurrent=pcurrent+d0×s，

詳細(xì)的位置偏移更新情況如圖3所示.

圖3 位置偏移更新Fig.3 Position offset update map

這種逐幀更新的方法雖然看似是勻速的，實(shí)際上由于每幀的執(zhí)行時(shí)間長(zhǎng)短不一樣，并不能得到真正意義上的勻速移動(dòng)，因此實(shí)際應(yīng)用中一般采用插值運(yùn)算來進(jìn)行位置更新.

3.3.2 插值運(yùn)算更新

當(dāng)確定了游戲?qū)ο蟮某跏嘉恢胮start和目標(biāo)位置后ptarget，可以使用插值運(yùn)算的方式來實(shí)現(xiàn)對(duì)象位置的平緩移動(dòng)，假設(shè)從開始幀到當(dāng)前幀的執(zhí)行時(shí)間為Δt，速度控制參數(shù)為s，根據(jù)式(1)則有

pcurrent=Lerp(pstart，ptarget，Δts).

其中速度控制參數(shù)s由游戲?qū)ο筮\(yùn)動(dòng)的總時(shí)間決定，這種方式可有效克服每幀執(zhí)行時(shí)間長(zhǎng)短的差異對(duì)物體移動(dòng)速度的影響.

3.4 角度偏移更新

游戲?qū)ο笤谶M(jìn)行角度偏移更新時(shí)，旋轉(zhuǎn)偏移通常要借助歐拉角和四元數(shù)的轉(zhuǎn)換來完成，以下為歐拉角與四元數(shù)的詳細(xì)轉(zhuǎn)換過程.

歐拉角一般用一個(gè)三維向量(θ，φ，ψ)來表示，其中θ，φ，ψ分別表示沿坐標(biāo)軸x，y，z三個(gè)軸的旋轉(zhuǎn)角度.而一個(gè)四元數(shù)可以表示為

q=w+xi+yj+zk.

其中：w，x，y，z為實(shí)數(shù)；i，j，k為三個(gè)虛數(shù)單位，并且滿足：

四元數(shù)被廣泛應(yīng)用在計(jì)算機(jī)圖形學(xué)中表示三維空間的旋轉(zhuǎn)操作.在Unity3D游戲開發(fā)中，通常用四元數(shù)來表示游戲?qū)ο蟮男D(zhuǎn).

通過指定的旋轉(zhuǎn)軸和沿該軸旋轉(zhuǎn)的角度α可以構(gòu)造一個(gè)四元數(shù)，其表示為

w=cos(α/2)，x=sin(α/2)cos(βx)，y=sin(α/2)cos(βy)，z=sin(α/2)cos(βz).

其中：α為沿指定的旋轉(zhuǎn)軸旋轉(zhuǎn)的角度；βx，βy，βz分別為該旋轉(zhuǎn)軸在x、y、z軸上的分量.

一個(gè)歐拉角(θ，φ，ψ)可通過式(2)轉(zhuǎn)換為一個(gè)四元數(shù)

(2)

而一個(gè)四元數(shù)q=[w，x，y，z]T可通過式(3)轉(zhuǎn)換為一個(gè)歐拉角

(3)

一般而言，游戲?qū)ο蟮某蚨际敲嫦蛞苿?dòng)方向的，當(dāng)游戲?qū)ο蟮竭_(dá)一點(diǎn)，再重新向一個(gè)新的目標(biāo)點(diǎn)移動(dòng)時(shí)，就涉及對(duì)象角度旋轉(zhuǎn)的問題，也就是對(duì)象的轉(zhuǎn)身問題.轉(zhuǎn)身過程一般在較短的時(shí)間內(nèi)完成，通常采用角度插值運(yùn)算的方式來進(jìn)行轉(zhuǎn)身角度更新.假設(shè)qcurrent為游戲?qū)ο螽?dāng)前位置的角度值，qtarget為目標(biāo)點(diǎn)角度值，Δt為開始幀到當(dāng)前幀的執(zhí)行時(shí)間，θ為旋轉(zhuǎn)速度控制參數(shù)，根據(jù)式(1)有

qcurrent=Lerp(qcurrent，qtarget，Δtθ)，

其中游戲?qū)ο笮D(zhuǎn)速度的快慢由旋轉(zhuǎn)速度控制參數(shù)θ決定.

另外，由于Unity中游戲?qū)ο蟮膔otation屬性是用四元數(shù)來表示的，而對(duì)象在旋轉(zhuǎn)時(shí)，通常更為直觀的表示方式是歐拉角形式，可通過Quaternion.Euler()方法在四元數(shù)和歐拉角之間進(jìn)行轉(zhuǎn)換，再進(jìn)行應(yīng)用，具體轉(zhuǎn)換過程參考式(2)和式(3).

歐拉角旋轉(zhuǎn)容易引起萬向死鎖，而四元數(shù)對(duì)于數(shù)值計(jì)算的偏差不敏感，數(shù)值上的小誤差引起的只是旋轉(zhuǎn)姿態(tài)小的調(diào)整.在計(jì)算機(jī)游戲和動(dòng)畫設(shè)計(jì)中，采用四元數(shù)容易實(shí)現(xiàn)對(duì)攝像機(jī)及游戲?qū)ο蠼嵌鹊倪B續(xù)微調(diào)，并可避免歐拉角旋轉(zhuǎn)產(chǎn)生的萬向死鎖問題.

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

4.2 實(shí)驗(yàn)仿真與分析

為了直觀的演示游戲?qū)ο蟮碾S機(jī)游走，通過在隨機(jī)游走所經(jīng)過的路徑上標(biāo)注小球的方式來標(biāo)識(shí)游戲?qū)ο蟮囊苿?dòng)路徑，其中灰色小球序列為物體逐幀走過的路徑，灰色大球?yàn)槟繕?biāo)點(diǎn)序列.初始化時(shí)，設(shè)置游戲?qū)ο笥巫叩姆秶?、游走速?開始時(shí)，自動(dòng)生成第一個(gè)目標(biāo)點(diǎn)，當(dāng)游戲?qū)ο笠苿?dòng)到該目標(biāo)點(diǎn)時(shí)，會(huì)自動(dòng)生成下一個(gè)新的目標(biāo)點(diǎn)，如此反復(fù)，可以實(shí)現(xiàn)游戲?qū)ο箅S機(jī)游走的功能，圖4和圖5為兩次程序運(yùn)行的結(jié)果.

可以看出，圖4(A)、圖5(A)為游戲?qū)ο筮\(yùn)動(dòng)到第1個(gè)目標(biāo)點(diǎn)，并自動(dòng)生成第2個(gè)目標(biāo)點(diǎn)的狀態(tài)，圖4(B)、圖5(B) 為運(yùn)動(dòng)到第2個(gè)目標(biāo)點(diǎn)，并自動(dòng)生成第3個(gè)目標(biāo)點(diǎn)的狀態(tài)，圖4(C)、圖5(C) 為運(yùn)動(dòng)到第3個(gè)目標(biāo)點(diǎn)，并自動(dòng)生成第4個(gè)目標(biāo)點(diǎn)的狀態(tài)，圖4(D) 和圖5(D)為運(yùn)動(dòng)了一段時(shí)間后的狀態(tài).可以看出，當(dāng)前一個(gè)目標(biāo)點(diǎn)路徑與下一個(gè)目標(biāo)點(diǎn)路徑的夾角較大時(shí)，兩條路徑之間的路徑過渡為圓弧狀，表明角度的偏移在不斷地進(jìn)行更新，即游戲?qū)ο笤诼窂睫D(zhuǎn)彎處的角度在不斷地迭代變化.

(A) Frame 73；(B) Frame 222；(C) Frame345；(D) Frame1200圖5 第二次運(yùn)行結(jié)果Fig.5 Second run results

(A) Frame 75；(B) Frame 239；(C) Frame 380；(D) Frame 688圖4 第一次運(yùn)行結(jié)果Fig.4 First run results

5 結(jié)語

將隨機(jī)尋路算法編寫為一個(gè)腳本，掛在游戲?qū)ο笊?，就可以靈活的實(shí)現(xiàn)場(chǎng)景中游戲?qū)ο蟮碾S機(jī)游走，大大方便和簡(jiǎn)化了游戲開發(fā)中隨機(jī)游走功能的實(shí)現(xiàn)過程，因而具有廣闊的應(yīng)用前景.需要注意的是，在進(jìn)行位置更新和角度更新時(shí)，當(dāng)物體在坡度平緩的地面上移動(dòng)，可以得到很好的效果，當(dāng)物體在坡度較大且地形復(fù)雜的地面上移動(dòng)時(shí)，可通過將目標(biāo)路徑進(jìn)行細(xì)分的方式來逐段控制物體的移動(dòng)，使得在局部范圍內(nèi)保持地形變化一致，進(jìn)而解決游戲?qū)ο笪茨芎偷孛婧芎觅N合的問題.