增进平滑移动效果的DeadReckoning算法

1、.32.电大理工总第228期2006年8月.32.电大理工总第228期.32.电大理工总第228期增进平滑移动效果的Dead Reckoning算法任广伟辽宁广捨电視大学（沈阳110034） 9 网络游戍中一个最常见的阿题就是&联网自身存在的延时问題，当新數据包剑来的时候，游戏界面上 的角色就会产生抖动现象.解决这个问题的聂重要的方法就是Dead Reckoning算法.本文对传统的DR算法进行了改 进，在其平滑机制中引入了 三次多数”方法，并在3D游戏中引入了方向預测方法.改进后的算法在性能和游戏真实.32.电大理工总第228期性方面取得了杖好的效果.关M Dead Reckoning 算法

2、 平滑技术0 引言MMOG（大型多人在线游戏，Massively Multiplayer Online Games）中存在的最主要的问题就 是延迟问题，这意味着在信息到达接收方之前需要 -定的时间。虽然有一些技术方法能够减少或者限 制这些延迟，但是有一些延迟是永远都不会消失的。 对于网络游戏来说，其最吸引人的地方是多人的交 互性和协作性，视听觉效果的作用已经退到次要的 位置。由于MM0G中存在着不可避免的延迟问题， 怎样提高游戏的一致性和响应性避免由于网络延迟 而产生的玩家界面不一致的问题，就成了网络游戏 平台研究的首要问题。虽然目前运行的游戏中也 采用了一些方法来保证玩家界面的-致性，但是在

3、 性能和效果方面都存在着一些问题。本文所做的研究正是针对这方面问题。传统的 DR算法是美国国防部为了解决军事模拟中存在的 延迟问题而提出的。主要用于解决同步过程中带宽 占用过大和服务器压力过大的问题。同样，在网络 游戏同步中也存在着类似的问题。所以在本文中， 对传统的DR算法进行了研究，并对其进行了改进。 改进后的算法在游戏预测方法中引入了方向预测算 法，并且对传统DR算法中的平滑算法进行了改进， 使其更适合在线游戏。而且，改进后的算法在性能 和视觉效果方面取得了很大的改善。.1 相关工作1.1网络游戏同步机制中存在的问题由于网络传输中存在的延迟现象，基于C/S结 构下的网络游戏的同步在保证客

4、户端响应本地用户 指令流畅的情况下，没法有效的保证同步的及时性 和有效性。当新数据包到来的时候，游戏角色会产 生抖动。同时，对网络带宽和服务器的压力也很大。 通常的解决办法包括：增加包发送的频率，通过压 缩减少包的大小,最殖要的就是DR（Dead reckoning） 算法。DR算法游戏中的DR算法由两部分组成：位置预测和平 滑移动。位置预测：用于减少在游戏中延迟产生的 影响，这种技术尽力猜测对象将要采取的行动，按 照位置预测公式推算实体的移动位置.这样就可以 避免每次玩家移动都发送一个更新包，减少了对网 络带宽和服务器的压力。平滑移动：用于在玩家接 收到更新包以后玩家实体从初始位置平滑移动到

5、更 新后的位置。但是，当前的DR算法所采用的平滑算 法存在着一些缺陷，由于没有考虔玩家速度的更新， 玩家实体移动到新位置后的移动方向看起来会很不 真实，影响游戏的真实性。而且，当前的DR算法没 有考虑玩家实体位置方向的预测，无法更真实的表 现实体的自身的旋转等信息。2 増进平淆移动效果的DR算法增进平滑移动效果的DR算法主要由三部分组 成：位置预测，方向预测和平滑移动。2.1位置预测，位置预测是DR算法用于推测实体下一步将要移 动到的位置的公式，文中的位置预测方案采用了传 统的DR算法中的位置预测方法，即：P=P0+V0AtP=Po+V0At+l/2AoAt2使用这两个公式可以计算推测出在At

6、时间后， 实体将要处于哪个位賈。2.2方向预测方案方向预测用于推算实体自身的偏移、旋转等移 动。引入了方向预测以后，实体自身的运动状态更 加丰富，这样玩家感受到的游戏更加真实、可信。在时间 t+At 时，world coordinate 变换为 body coordinate的方向矩阵为：Rk-b = DRlR0w.bdead reckoning矩阵的计算方法把时间S的实体的body coordinate变换为时间 to+At的实体的body coordinate的矩阵定义为：DRX1yos( | 3 | At)w qt/ | Q | 2+cos( | 3 I t)Isin | 3 I tQ/

7、 I 3 I因为上面用到的角速度是body coordinate中的 速度，而角速度是用Euler (world coordinate)角度 来表示的，所以下面要给出一些转换公式：World coordinate (Euler)角速度转变为 body coordinate角速度的公式：3 产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平滑移动三次参数方法提供了一个最现实的

8、方式来创建 个dead reckoning路径。这是因为我们在三次参数 方法中考虑了起点的付酥速度和终点的付置速度。 其产生的结果是：采用三次参数方法的对象的运动 没有急进的现象产生，除非是延迟特别严重的情况 下。(1)三次参数方法使用三次参数方法来创建路径是一些简单的代 数竽式。首先考虑输入的四个(x, y, z)数对。第 一个数对代表了对象的起始位賈(Po)。类似的，第三 个数对表示数据的更新位置(P2)。通常，为了实现更 好的同步，拟采用终点位置后的一点预测位置P3,P3是实体以更新速度运行T时间后的位置。然后让 实体以一个较快的速度Vs=( P-Po)/T移动到P3点，同 时，把P3点

9、作为第四个数对。最重要的数对就是第 二个和第三个：它们代农对象的速度。第二个数 对用來计算以对象现在的速度，在.(.时间之后这个 对象将在哪里出现。第三个数对是更新位置，同时 以对象的更新速度运动。A.下面就足用来创建曲线的参数等式x=At3+Bt2+ct+Dy=Et3+Ft2+Gt+H zslP+J+Kt+L t是时间变量。它的范围从最初点0到终点T。B描述参数方程中的系数变量的解法 给定n个互异节点心及对应的函数值yi= f(xWQ,若以Xi(i=l,n)为节点的插值多项式 为：y=C+C2X+”+CnXi求该多项式的系数Ci(i=l,!)即为三次参数方 程中的系数。 应用Vandermo

10、nde矩阵的方法求得，-k=lk=l rn jbk=b 如i&+s 如1, k=n-l , ，1C 一旦这些等式被创建了，下一步就是要决定在 游戏中怎么实现它。下面的方法是很简单和有效的。 允许一个对象遵循物理法则移动(根据速度 和加速度)。 当一个数据包到达的时候开始创建到下一个 位置的曲线。 曲线上的数对1和数对2可以通过使用现在 的位置和速度来找到。Coord 1 = XoidCoord2 = xoid + voW 数对3和数对4更难获得。他们取决于更新 数据包的速度。如果在从位置1到位置4的过程中 有新的PDU到达，那么我们定义它为NewPackage。 对数对4来说，使用新数据包来计

11、算在T秒之后的 最终位置。同样的信息也nJ以被用来计算在新时间的对象的速度。Coord3 = Coord4 - (Vp + 叶小)Coord4 = Xpactet + Vpacket +0.5*这个方法联合了 dead reckoning算法的两种形 式：立方抖动方法和二次方程移动方法。这样结果看 起来更加现实。 让这个对象沿着这条曲线走时间To 曲线的末端，再从第一步重新开始。这样结果看起来就会像下面的一样平滑hiHf.li Smoothing path3 改进后平滑纂法的性館分析本小节主要对同步机制算法进行简单的性能分 析，并对同步机制中采用的平滑算法在游戏中取得 的视觉效果进行测试。平滑

12、算法效果图如下，wnrr to xarrlinear” 方式quadratic”方法三次方法Fig.2i Performance analysis of smoothing method m the algorithm 2中平淆方的性誼分析在“poim-tspoim”方法中，实体被简单的从旧 位置拖拽到更新后的位Eo采用这种方法实现很 简单，但是对实体的每一次移动都要发送一个更新 包，对本来就很紧张的带宽来说是一个很大的压力： 同时在玩家的屏幕上，实体也是一跳一跳的前进的, 给人一种很不真实的视觉效果。在“linear”方法中，实体以一条直线路径运动 到更新厉的位置上。使用这种方法，实体的每一

13、次 更新运动都是按直线方式运动的，这样实体B在玩 家A屏幕上移动起来变得非常的不现实，经常会出 现很生便的拐角。在“quadratic”方法中，实体以二次方路径的形 式运动到更新后的位置上。使用这种方法，可以使B 在玩家A屏幕上的移动变得比较的有人性化一些。 但是该方法的考虑也足不周全的，仅仅只考虎了初 始位置到更新位置的方向，而没有考虑新的PDU包 中的方向描述，那么实体B从更新位置开始模拟行 走的时候，仍然是会出现比较牛硬的拐角，在“三次参数”方法中，实体按照三次参数方 程的路径形式从初始位置运动到更新位置上。在此 种方法中不仅考虑了路径的运动形式，而且还考堪 了更新PDU中包含的方向描述

14、，这样当实体B在玩 家A屏算上从更新后的位置开始新的行走模拟时， 就不会出现生硬的拐角，使玩家A屏幕上看到的实 体B的运动更加真实、生动。4 结束语本文通过对消息进行分类管理和在实现同步的 关键技术一DR算法中引入方向预测方法，并对其平 滑方案进行改进并进行了测试。提高了游戏中同步 的性能，并且改进后的算法使得游戏在画面的稳定 性和真实性方面取得了较好的效果。考文献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