史寶明，賀元香，李 嵐

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

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

1 理論基礎(chǔ)

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

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

Unity3D游戲開發(fā)中，隨機游走時要時刻根據(jù)地形調(diào)整移動對象的角度，這涉及對象的旋轉(zhuǎn)控制問題，常用的角度旋轉(zhuǎn)表示方法一般有歐拉角和四元數(shù).歐拉角是指在三維空間通過指定與三個旋轉(zhuǎn)軸相關(guān)聯(lián)的三個角度來表示任意方向的方法，是用來表示三維坐標系中方向和方向變換的，由章動角、旋進角和自轉(zhuǎn)角三部分組成.歐拉角表示角度直觀方便，但采用不同的軸序旋轉(zhuǎn)有可能會造成不同的旋轉(zhuǎn)結(jié)果，因此需要按指定的軸序進行旋轉(zhuǎn)，并且當(dāng)在旋轉(zhuǎn)過程中如果發(fā)生旋轉(zhuǎn)軸和坐標軸重合的情況時，會引起萬向死鎖，這時會丟失一個方向上的旋轉(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ù)，可以表示一個四維空間.四元數(shù)旋轉(zhuǎn)可以避免萬向死鎖現(xiàn)象、方便快捷，能提供平滑的插值效果，并且通常比矩陣旋轉(zhuǎn)的效率高，在游戲開發(fā)中有著廣泛的應(yīng)用[7-9].

1.2 插值運算

游戲開發(fā)中當(dāng)游戲?qū)ο笤趫鼍爸须S機游走時，游戲?qū)ο笪恢煤徒嵌葧l(fā)生實時變化，通常采用逐幀更新的方式來改變對象的位置和角度，而位置和角度的確定一般通過已知的起始點和確定的目標點來進行逐幀計算得到，這就需要用到插值運算.

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

F=Lerp(start，end，t).

(1)

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

2 總體設(shè)計思路

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

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

Step2 在游走范圍內(nèi)隨機產(chǎn)生一個新目標點.

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

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

整個隨機尋路算法的程序流程如圖1所示.

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

3 算法詳細設(shè)計

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

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

3.2 隨機產(chǎn)生目標位置

在生成的矩形區(qū)域中隨機生成一個點作為目標位置targetPos，目標位置的確定方法如下：

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

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

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

圖2 隨機游走示例Fig.2 Random walk example map

3.3 位置偏移更新

3.3.1 逐幀勻速更新

pcurrent=pcurrent+d0×s，

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

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

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

3.3.2 插值運算更新

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

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

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

3.4 角度偏移更新

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

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

q=w+xi+yj+zk.

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

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

通過指定的旋轉(zhuǎn)軸和沿該軸旋轉(zhuǎn)的角度α可以構(gòu)造一個四元數(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軸上的分量.

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

(2)

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

(3)

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

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

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

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

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

4 實驗

4.1 實驗環(huán)境

4.2 實驗仿真與分析

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

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

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

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

5 結(jié)語

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