增進(jìn)平滑移動(dòng)效果的DeadReckoning算法

1、.32.電大理工總第228期2006年8月.32.電大理工總第228期.32.電大理工總第228期增進(jìn)平滑移動(dòng)效果的Dead Reckoning算法任廣偉遼寧廣捨電視大學(xué)（沈陽(yáng)110034） 9 網(wǎng)絡(luò)游戍中一個(gè)最常見(jiàn)的阿題就是&聯(lián)網(wǎng)自身存在的延時(shí)問(wèn)題，當(dāng)新數(shù)據(jù)包劍來(lái)的時(shí)候，游戲界面上 的角色就會(huì)產(chǎn)生抖動(dòng)現(xiàn)象.解決這個(gè)問(wèn)題的聶重要的方法就是Dead Reckoning算法.本文對(duì)傳統(tǒng)的DR算法進(jìn)行了改 進(jìn)，在其平滑機(jī)制中引入了 三次多數(shù)”方法，并在3D游戲中引入了方向預(yù)測(cè)方法.改進(jìn)后的算法在性能和游戲真實(shí).32.電大理工總第228期性方面取得了杖好的效果.關(guān)M Dead Reckoning 算法

2、 平滑技術(shù)0 引言MMOG（大型多人在線游戲，Massively Multiplayer Online Games）中存在的最主要的問(wèn)題就 是延遲問(wèn)題，這意味著在信息到達(dá)接收方之前需要 -定的時(shí)間。雖然有一些技術(shù)方法能夠減少或者限 制這些延遲，但是有一些延遲是永遠(yuǎn)都不會(huì)消失的。 對(duì)于網(wǎng)絡(luò)游戲來(lái)說(shuō)，其最吸引人的地方是多人的交 互性和協(xié)作性，視聽(tīng)覺(jué)效果的作用已經(jīng)退到次要的 位置。由于MM0G中存在著不可避免的延遲問(wèn)題， 怎樣提高游戲的一致性和響應(yīng)性避免由于網(wǎng)絡(luò)延遲 而產(chǎn)生的玩家界面不一致的問(wèn)題，就成了網(wǎng)絡(luò)游戲 平臺(tái)研究的首要問(wèn)題。雖然目前運(yùn)行的游戲中也 采用了一些方法來(lái)保證玩家界面的-致性，但是在

3、 性能和效果方面都存在著一些問(wèn)題。本文所做的研究正是針對(duì)這方面問(wèn)題。傳統(tǒng)的 DR算法是美國(guó)國(guó)防部為了解決軍事模擬中存在的 延遲問(wèn)題而提出的。主要用于解決同步過(guò)程中帶寬 占用過(guò)大和服務(wù)器壓力過(guò)大的問(wèn)題。同樣，在網(wǎng)絡(luò) 游戲同步中也存在著類似的問(wèn)題。所以在本文中， 對(duì)傳統(tǒng)的DR算法進(jìn)行了研究，并對(duì)其進(jìn)行了改進(jìn)。 改進(jìn)后的算法在游戲預(yù)測(cè)方法中引入了方向預(yù)測(cè)算 法，并且對(duì)傳統(tǒng)DR算法中的平滑算法進(jìn)行了改進(jìn)， 使其更適合在線游戲。而且，改進(jìn)后的算法在性能 和視覺(jué)效果方面取得了很大的改善。.1 相關(guān)工作1.1網(wǎng)絡(luò)游戲同步機(jī)制中存在的問(wèn)題由于網(wǎng)絡(luò)傳輸中存在的延遲現(xiàn)象，基于C/S結(jié) 構(gòu)下的網(wǎng)絡(luò)游戲的同步在保證客

4、戶端響應(yīng)本地用戶 指令流暢的情況下，沒(méi)法有效的保證同步的及時(shí)性 和有效性。當(dāng)新數(shù)據(jù)包到來(lái)的時(shí)候，游戲角色會(huì)產(chǎn) 生抖動(dòng)。同時(shí)，對(duì)網(wǎng)絡(luò)帶寬和服務(wù)器的壓力也很大。 通常的解決辦法包括：增加包發(fā)送的頻率，通過(guò)壓 縮減少包的大小,最殖要的就是DR（Dead reckoning） 算法。DR算法游戲中的DR算法由兩部分組成：位置預(yù)測(cè)和平 滑移動(dòng)。位置預(yù)測(cè)：用于減少在游戲中延遲產(chǎn)生的 影響，這種技術(shù)盡力猜測(cè)對(duì)象將要采取的行動(dòng)，按 照位置預(yù)測(cè)公式推算實(shí)體的移動(dòng)位置.這樣就可以 避免每次玩家移動(dòng)都發(fā)送一個(gè)更新包，減少了對(duì)網(wǎng) 絡(luò)帶寬和服務(wù)器的壓力。平滑移動(dòng)：用于在玩家接 收到更新包以后玩家實(shí)體從初始位置平滑移動(dòng)到

5、更 新后的位置。但是，當(dāng)前的DR算法所采用的平滑算 法存在著一些缺陷，由于沒(méi)有考虔玩家速度的更新， 玩家實(shí)體移動(dòng)到新位置后的移動(dòng)方向看起來(lái)會(huì)很不 真實(shí)，影響游戲的真實(shí)性。而且，當(dāng)前的DR算法沒(méi) 有考慮玩家實(shí)體位置方向的預(yù)測(cè)，無(wú)法更真實(shí)的表 現(xiàn)實(shí)體的自身的旋轉(zhuǎn)等信息。2 増進(jìn)平淆移動(dòng)效果的DR算法增進(jìn)平滑移動(dòng)效果的DR算法主要由三部分組 成：位置預(yù)測(cè)，方向預(yù)測(cè)和平滑移動(dòng)。2.1位置預(yù)測(cè)，位置預(yù)測(cè)是DR算法用于推測(cè)實(shí)體下一步將要移 動(dòng)到的位置的公式，文中的位置預(yù)測(cè)方案采用了傳 統(tǒng)的DR算法中的位置預(yù)測(cè)方法，即：P=P0+V0AtP=Po+V0At+l/2AoAt2使用這兩個(gè)公式可以計(jì)算推測(cè)出在At

6、時(shí)間后， 實(shí)體將要處于哪個(gè)位賈。2.2方向預(yù)測(cè)方案方向預(yù)測(cè)用于推算實(shí)體自身的偏移、旋轉(zhuǎn)等移 動(dòng)。引入了方向預(yù)測(cè)以后，實(shí)體自身的運(yùn)動(dòng)狀態(tài)更 加豐富，這樣玩家感受到的游戲更加真實(shí)、可信。在時(shí)間 t+At 時(shí)，world coordinate 變換為 body coordinate的方向矩陣為：Rk-b = DRlR0w.bdead reckoning矩陣的計(jì)算方法把時(shí)間S的實(shí)體的body coordinate變換為時(shí)間 to+At的實(shí)體的body coordinate的矩陣定義為：DRX1yos( | 3 | At)w qt/ | Q | 2+cos( | 3 I t)Isin | 3 I tQ/

7、 I 3 I因?yàn)樯厦嬗玫降慕撬俣仁莃ody coordinate中的 速度，而角速度是用Euler (world coordinate)角度 來(lái)表示的，所以下面要給出一些轉(zhuǎn)換公式：World coordinate (Euler)角速度轉(zhuǎn)變?yōu)?body coordinate角速度的公式：3 產(chǎn)d 0/dt(d 0/dt) e3y=(d 0/dt) Q+(d Wdt) sincos w cos Qs 6 Theta()： 0=sinAi3Psi(y)： cos1 An/cos 0 *sgnAi2Phi(0)： 0=8sA33/cos 0 *sgnA23 2.3平滑移動(dòng)三次參數(shù)方法提供了一個(gè)最現(xiàn)實(shí)的

8、方式來(lái)創(chuàng)建 個(gè)dead reckoning路徑。這是因?yàn)槲覀冊(cè)谌螀?shù) 方法中考慮了起點(diǎn)的付酥速度和終點(diǎn)的付置速度。 其產(chǎn)生的結(jié)果是：采用三次參數(shù)方法的對(duì)象的運(yùn)動(dòng) 沒(méi)有急進(jìn)的現(xiàn)象產(chǎn)生，除非是延遲特別嚴(yán)重的情況 下。(1)三次參數(shù)方法使用三次參數(shù)方法來(lái)創(chuàng)建路徑是一些簡(jiǎn)單的代 數(shù)竽式。首先考慮輸入的四個(gè)(x, y, z)數(shù)對(duì)。第 一個(gè)數(shù)對(duì)代表了對(duì)象的起始位賈(Po)。類似的，第三 個(gè)數(shù)對(duì)表示數(shù)據(jù)的更新位置(P2)。通常，為了實(shí)現(xiàn)更 好的同步，擬采用終點(diǎn)位置后的一點(diǎn)預(yù)測(cè)位置P3,P3是實(shí)體以更新速度運(yùn)行T時(shí)間后的位置。然后讓 實(shí)體以一個(gè)較快的速度Vs=( P-Po)/T移動(dòng)到P3點(diǎn)，同 時(shí)，把P3點(diǎn)

9、作為第四個(gè)數(shù)對(duì)。最重要的數(shù)對(duì)就是第 二個(gè)和第三個(gè)：它們代農(nóng)對(duì)象的速度。第二個(gè)數(shù) 對(duì)用來(lái)計(jì)算以對(duì)象現(xiàn)在的速度，在.(.時(shí)間之后這個(gè) 對(duì)象將在哪里出現(xiàn)。第三個(gè)數(shù)對(duì)是更新位置，同時(shí) 以對(duì)象的更新速度運(yùn)動(dòng)。A.下面就足用來(lái)創(chuàng)建曲線的參數(shù)等式x=At3+Bt2+ct+Dy=Et3+Ft2+Gt+H zslP+J+Kt+L t是時(shí)間變量。它的范圍從最初點(diǎn)0到終點(diǎn)T。B描述參數(shù)方程中的系數(shù)變量的解法 給定n個(gè)互異節(jié)點(diǎn)心及對(duì)應(yīng)的函數(shù)值yi= f(xWQ,若以Xi(i=l,n)為節(jié)點(diǎn)的插值多項(xiàng)式 為：y=C+C2X+”+CnXi求該多項(xiàng)式的系數(shù)Ci(i=l,!)即為三次參數(shù)方 程中的系數(shù)。 應(yīng)用Vandermo

10、nde矩陣的方法求得，-k=lk=l rn jbk=b 如i&+s 如1, k=n-l , ，1C 一旦這些等式被創(chuàng)建了，下一步就是要決定在 游戲中怎么實(shí)現(xiàn)它。下面的方法是很簡(jiǎn)單和有效的。 允許一個(gè)對(duì)象遵循物理法則移動(dòng)(根據(jù)速度 和加速度)。 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)的時(shí)候開(kāi)始創(chuàng)建到下一個(gè) 位置的曲線。 曲線上的數(shù)對(duì)1和數(shù)對(duì)2可以通過(guò)使用現(xiàn)在 的位置和速度來(lái)找到。Coord 1 = XoidCoord2 = xoid + voW 數(shù)對(duì)3和數(shù)對(duì)4更難獲得。他們?nèi)Q于更新 數(shù)據(jù)包的速度。如果在從位置1到位置4的過(guò)程中 有新的PDU到達(dá)，那么我們定義它為NewPackage。 對(duì)數(shù)對(duì)4來(lái)說(shuō)，使用新數(shù)據(jù)包來(lái)計(jì)

11、算在T秒之后的 最終位置。同樣的信息也nJ以被用來(lái)計(jì)算在新時(shí)間的對(duì)象的速度。Coord3 = Coord4 - (Vp + 葉小)Coord4 = Xpactet + Vpacket +0.5*這個(gè)方法聯(lián)合了 dead reckoning算法的兩種形 式：立方抖動(dòng)方法和二次方程移動(dòng)方法。這樣結(jié)果看 起來(lái)更加現(xiàn)實(shí)。 讓這個(gè)對(duì)象沿著這條曲線走時(shí)間To 曲線的末端，再?gòu)牡谝徊街匦麻_(kāi)始。這樣結(jié)果看起來(lái)就會(huì)像下面的一樣平滑hiHf.li Smoothing path3 改進(jìn)后平滑纂法的性館分析本小節(jié)主要對(duì)同步機(jī)制算法進(jìn)行簡(jiǎn)單的性能分 析，并對(duì)同步機(jī)制中采用的平滑算法在游戲中取得 的視覺(jué)效果進(jìn)行測(cè)試。平滑

12、算法效果圖如下，wnrr to xarrlinear” 方式quadratic”方法三次方法Fig.2i Performance analysis of smoothing method m the algorithm 2中平淆方的性誼分析在“poim-tspoim”方法中，實(shí)體被簡(jiǎn)單的從舊 位置拖拽到更新后的位Eo采用這種方法實(shí)現(xiàn)很 簡(jiǎn)單，但是對(duì)實(shí)體的每一次移動(dòng)都要發(fā)送一個(gè)更新 包，對(duì)本來(lái)就很緊張的帶寬來(lái)說(shuō)是一個(gè)很大的壓力： 同時(shí)在玩家的屏幕上，實(shí)體也是一跳一跳的前進(jìn)的, 給人一種很不真實(shí)的視覺(jué)效果。在“l(fā)inear”方法中，實(shí)體以一條直線路徑運(yùn)動(dòng) 到更新厲的位置上。使用這種方法，實(shí)體的每一

13、次 更新運(yùn)動(dòng)都是按直線方式運(yùn)動(dòng)的，這樣實(shí)體B在玩 家A屏幕上移動(dòng)起來(lái)變得非常的不現(xiàn)實(shí)，經(jīng)常會(huì)出 現(xiàn)很生便的拐角。在“quadratic”方法中，實(shí)體以二次方路徑的形 式運(yùn)動(dòng)到更新后的位置上。使用這種方法，可以使B 在玩家A屏幕上的移動(dòng)變得比較的有人性化一些。 但是該方法的考慮也足不周全的，僅僅只考虎了初 始位置到更新位置的方向，而沒(méi)有考慮新的PDU包 中的方向描述，那么實(shí)體B從更新位置開(kāi)始模擬行 走的時(shí)候，仍然是會(huì)出現(xiàn)比較牛硬的拐角，在“三次參數(shù)”方法中，實(shí)體按照三次參數(shù)方 程的路徑形式從初始位置運(yùn)動(dòng)到更新位置上。在此 種方法中不僅考慮了路徑的運(yùn)動(dòng)形式，而且還考堪 了更新PDU中包含的方向描述

14、，這樣當(dāng)實(shí)體B在玩 家A屏算上從更新后的位置開(kāi)始新的行走模擬時(shí)， 就不會(huì)出現(xiàn)生硬的拐角，使玩家A屏幕上看到的實(shí) 體B的運(yùn)動(dòng)更加真實(shí)、生動(dòng)。4 結(jié)束語(yǔ)本文通過(guò)對(duì)消息進(jìn)行分類管理和在實(shí)現(xiàn)同步的 關(guān)鍵技術(shù)一DR算法中引入方向預(yù)測(cè)方法，并對(duì)其平 滑方案進(jìn)行改進(jìn)并進(jìn)行了測(cè)試。提高了游戲中同步 的性能，并且改進(jìn)后的算法使得游戲在畫(huà)面的穩(wěn)定 性和真實(shí)性方面取得了較好的效果?？嘉墨I(xiàn)IJJouni Smed, Timo Kaukoranta, and Harri Hakonen. nAspects of networking in puter games”The Electronic Library, Vol.

15、 20, No. 2. 2002:87-972 Jouni Smed9 Timo Kaukoranta, and Harri Hakonen A Review on Networking and Multiplayer Computer Games Turku Center for Computer Science, 454, April 2002.3 The Institute of Electrical and Electronics Engineers IEBE Standard for Distributed Interactive Simulation Application Protocols, Standards Committee on Interactive Simulation (SCIS) of the IEEE Computer Society, September 21, 1995: 123-129.4 Lothar Pan tel Lars C. Wolf. On t