基于消息类型改良的Time Warp网游同步方法

本发明涉及一种Time Warp网游同步方法，特别涉及一种基于消息类型改良的Time Warp网游同步方法，属于网游同步方法技术领域。

最近几十年来互联网技术不断进步，在为人们的生活带来诸多便利的同时，也让人们体验到了互联网为日常休闲娱乐带来的颠覆性变化。网络游戏为广大玩家提供了逼真的网游世界、极致的网游体验，已经成为许多人在工作学习之余的重要休闲活动。近些年来，网络游戏的规模越来越大，网游复杂度越来越高，游戏玩家对网游性能要求也越来越高，网游中游戏玩家结点间需要交互的数据量也大幅增加，然而网游数据包在网络中传输时不可避免的延迟、差错和丢包的现象严重影响网游的同步性能，破坏了网游一致性和网游的公平性，对玩家的游戏体验有极大的制约，对网游状态同步技术的研发改进对于当前网游的研发十分必要。

在网游中游戏玩家会在同一游戏世界里频繁的交流，随着网游规模越来越大，网络固有延迟、丢包和带宽限制等问题严重的影响着网游的同步效果，网游同步问题成为网游开发人员急需解决的问题。相较于其它网游，网络网游中游戏玩家的互动性、竞技性更高，并且需要保证游戏玩家间实时的沟通、协作与竞争，然而网络固有的缺陷直接制约了网游整体体验。基于以上原因如何让大量游戏玩家在同一网游世界中能有流畅的体验成为一款网游最为致命的问题。在计算机网络固有的数据包延迟、差错、不可避免的丢包、带宽资源有限的情况下，对网游同步技术的研究以及探究其在网游实际开发过程中的应用具有广阔的市场空间。

当前网络游戏已经走向大型化和重度化，尤其在网游中最为重要的MMORTS和MMORPG中，网游对象的行为多样性和复杂性逐渐提升，游戏玩家兴趣范围内的游戏玩家数量也会大量增加，这就使得一个游戏玩家需要向其他游戏玩家交互的数据量大幅增加。通过对兴趣结点的管理可减少游戏玩家兴趣范围内结点的数量，但是这对于大量的网络数据交互来说是远远不够的，游戏玩家之间数据交互需要一个高效的方案。

现有技术的Time Warp算法是积极同步算法中最为重要的同步算法，它主要应用在分布式虚拟环境中，Time Warp对于收到的消息直接执行而不去检测消息的正确性，当收到迟到的消息后采用回滚的方式来保证游戏玩家结点状态的同步，Time Warp同步算法不参与同一个网游世界的其他游戏玩家的同步，仅依赖本地时钟进行自我的处理。

Time Warp算法由二部分组成：局部控制机制和全局控制机制。局部控制机制运行于游戏玩家结点的消息处理中，而全局控制机制运行在逻辑控制进程中掌控整个网游逻辑。局部控制机制在游戏玩家客户端中根据时间戳对消息进行排序，同时根据同步后的时钟顺序执行经过排序后的消息。Time Warp算法的关键之处在于每次执行消息前都会保存当前结点的网游状态的快照，即将网游状态进行备份用于之后的回滚。现有技术有海量状态存储技术和增量状态存储技术两种常用的备份方式：一是每个网游客户端中都保持一份状态快照，在接收到迟到的消息时，直接用保存好的快照覆盖掉迟到消息前的最近一个状态，这种备份方式需要保存游戏玩家结点状态的所有信息，所以需要占用很大的内存来存储快照，这种方式适合网游状态间变化大的网游；二是每个游戏玩家结点在执行完消息后，将本次状态改变的数据保存起来，每当收到迟到的消息后利用保存的数据就可以逐层回滚到迟到消息时间戳中前最近的状态，这种备份方式需要保存的数据是状态改变的数据，数据量很小，对存储空间的要求不大，这种方式比较适合状态间改变较小的网游。

当游戏玩家结点接收到迟到的消息，说明该结点处理的消息顺序存在错误，也就是说网游状态发生了不一致，这时Time Warp算法选择回滚到迟到消息前的时刻后，快速执行消息队列中后续被回滚消息，直到执行到正确的时间点，接着恢复正常的消息处理节奏。因为积极同步思想在处理消息前不会做安全检查，所以在迟到数据包中，时间戳后可能已经产生并且广播了一些消息，为保证网游严格的同步性，就需要取消这些已经广播的消息。Time Warp算法采用负消来取消那些连带消息的影响，负消息是原始消息的副本，只是有一个撤销标志位，当其他游戏玩家结点收到负消息后就会在本地触发一个回滚，这样就可以消除因为收到迟到消息而产生的影响，这种采用负消息消除影响的方式可能会导致递归回滚进而产生额外的负消息。例如游戏玩家结点在执行到155ms时收到一个迟到的消息，此消息本该在115ms时执行，根据Time Warp同步算法这时游戏玩家网游状态应该回滚到该迟到消息前最近的状态，即75ms时网游的状态。当网游状态回滚到75ms时的状态后，因为之前已经在135ms和155ms时游戏玩家结点已经产生了两个消息，Time Warp算法此时发送Anti-Message消息来撤销这两个消息对网游状态的影响，在其他游戏玩家接收到负消息后同样会进行相应的回滚。至此回滚操作结束，游戏玩家结点回到正常的执行消息过程。

现有技术Time Warp算法的优势在于无需在收到所有玩家节点消息后才能进行状态更新，提高了游戏的实时性和响应时间。但Time Warp算法的缺陷也非常突出，主要包括：

第一，Time Warp算法在每次执行消息时都会保存网游状态的快照，然而如果快照的频率太快的话，会增加内存的消耗，一般处理该问题的方法是采用周期性保存快照的方式，这降低了快照的频率同时也减少了内存的消耗，但采用周期性快照的方式会导致回滚发送时不能准确的回滚到正确的位置，这将会扩回滚的范围，回滚范围扩大导致的代价可能会大于内存消耗带来的代价；

第二，Time Warp算法在每一个执行新消息是都会保存当前状态的快照，占用大量的内存，所以必须及时对内存进行回收。为确定哪些内存可以释放，引入GVT，GVT是以下两个时钟中最小时间戳：一是游戏玩家结点消息队列中最小的时间戳；二是正在网络传输的全部消息中最小的时间戳，早于GVT的所有快照占用的内存都可以被回收，但Time Warp算法在执行消息时不会检测其正确性，当检测到迟到的消息后采用回滚来保持网游的一致性，然而回滚可能会导致递归回滚和内存的大量占用，从而降低网游实时性与系统性能；

第三，现有技术的Time Warp算法主要应用在分布式虚拟环境中，Time Warp对于收到的消息直接执行而不去检测消息的正确性，当收到迟到的消息后采用回滚的方式来保证游戏玩家结点状态的同步，Time Warp同步算法不参与同一个网游世界的其他游戏玩家的同步，仅依赖本地时钟进行自我的处理，游戏响应性的感受不好，可能出现网游画面和网游数据不一致的情况，游戏过程中有感觉到明显的画面抖动，玩家的游戏体验不好；

第四，网游中游戏玩家间网游状态同步的积极同步算法，按照一定的规则执行游戏玩家间交互的数据包来更新网游状态，保证网游状态的一致性。在积极同步算法中最重要的为基于消息回滚的Time Warp同步算法，该算法在执行每个消息前都会保存当前网游状态的快照用来状态回滚，由于每执行一个消息都会对当前状态进行快照，会导致网游占用很大的内存，算法采用积极的态度，游戏玩家结点收到迟到的消息后进行状态回滚，那么在网络环境不理想的时候必然会导致网游的频繁回滚，本发明基于动态周期对Time Warp算法进行改良，基于网游消息分类对Time Warp算法进行改良，改良后的算法对不同的消息采用不同的处理策略，在保证网游交互性和一致性的同时尽可能降低网游因为快照导致的内存占用率。

本发明提供的基于消息类型改良的Time Warp网游同步方法，针对网游同步问题出现的原因作了详细的分析，对Time Warp积极同步算法进行了详尽的分析，该算法能够保证网游的响应性，但状态快照引起的高内存占用率和频繁的状态回滚导致了算法的性能较低。本发明针对Time Warp算法频繁状态回滚和大量的资源占用等缺点，对Time Warp算法基于消息类型和网络环境状况二方面进行了改良，网游中的消息按重要程度分为重要消息和非重要消息，本发明对Time Warp同步算法针对二种消息类型提出了不同的处理策略，通过实验进一步验证了改良后的Time Warp同步算法性能得到有效的提升，网游的实时性和一致性得到平衡。

为达到以上技术效果，本发明所采用的技术方案如下：

基于消息类型改良的Time Warp网游同步方法，基于消息类型对Time Warp算法进行改良，提出基于实时网络状态的消息处理策略，算法改良后，当网络状态比较差时，采用基于动态周期更新的Time Warp算法有效降低消息的迟到率；基于非重要消息的特征，本发明对Time Warp同步算法中的非重要消息处理策略进行的改良，如果非重要消息迟到首先检查该消息是否已经被过期，如果该消息已经被其它消息过期,则将该被过期的消息抛弃，否则进行回滚；Time Warp算法改良后大幅减少网游状态的回滚次数和消息的迟到率，减少网游快照次数和对内存的占用，使网游的实时性和一致性得到平衡；

本发明对Time Warp算法改良总结为：针对网游中重要消息和非重要消息对网游状态的影响程度不同，对两种消息采取不同的同步策略，当网络状态良好时，对网络进行定时评价，当网游中出现大量消息迟到时，改变消息处理策略，采取动态周期同步的方式对网游状态进行更新，游戏玩家结点收到迟到的重要消息时立即对网游状态进行回滚，而当游戏玩家结点收到迟到的非重要消息时，首先判断消息是否已经被其后的消息过期，如果是则直接抛弃，否则才会对网游状态进行回滚；

改良后的Time Warp算法的消息处理过程为：当游戏玩家结点收到其它结点的网游时间时，首先根据时间戳判断该消息是否已经迟到，如果消息已经迟到，首先更新用来对网络进行评价的数据集，接下来判断该消息是否为重要消息，如果是非重要消息，则检查该消息是否被过期，如果已经被其他消息过期将该消息抛弃，不对网游状态进行回滚，如果该消息为重要消息或为未被过期的非重要消息则对网游状态进行回滚，接着将网游状态快速更新到当前时钟对应的位置；如果该消息没有迟到，判断本评价周期是否结束，如果已经结束，则根据本周期中消息的迟到数，丢失数来判断本评价周期中消息的失常率；如果消息失常率超过临界值则下个评价周期采用动态周期Time Warp算法处理网游消息，动态周期的长度根据本周期的失常率通过计算获得；如果失常率低于临界值则采用传统的Time Warp算法处理网游消息；如果本评价周期没有结束，则继续采用本周期初决定好的同步策略处理网游消息；在本地结点处理网游消息时，采用Head Reckoning平滑技术对角的运动做平滑处理，在利用收到的消息更新完网游状态后，采用Head Reckoning位置预测技术对角的运动进行预测。

基于消息类型改良的Time Warp网游同步方法，进一步的，本发明提出基于TimeWarp算法对网游中消息处理方法改良，改良后的算法对于消息延迟设定一个延迟极限临界值Csill，当网络延迟小于该值时代表当前网络状态良好，此时采用传统Time Warp算法处理消息，游戏玩家结点在收到消息后立即更新状态，只有当收到迟到的消息后进行状态回滚；在网络状态良好时，游戏玩家结点的操作消息在短时间内到达其他结点，这时消息的迟到率很低，网游的回滚次数很少，游戏玩家结点只需要保存很短时间内网游状态的快照即可满足回滚要求；

当网络延迟大于Csill时，当前网络状态较差，这时会导致大量消息不能及时到达游戏玩家结点，导致大量的回滚操作；此时采用基于动态周期的快照和网游状态更新策略，动态周期的周期值根据网络状态来决定，周期更新即每当游戏玩家结点收到新的消息时不进行处理，而是在本周期结束时对网游当前状态进行快照并对本周期内收到的消息进行统一更新；采用周期同步的方式避免每执行一个消息就对网游状态进行一次快照，而是每一个周期对网游状态进行一次快照，显著降低网游的内存占用率；采用周期同步后，因为新的消息到达游戏玩家结点不需要进行及时更新，降低网游消息延迟率和回滚率。

基于消息类型改良的Time Warp网游同步方法，进一步的，对于Time Warp算法中消息的改良中，网络状态的好坏需要每隔一定时间进行量化；每隔一段时间对网络状态进行评价，通过测量特定时间间隔W内游戏玩家的消息丢失率来判断网络状态，游戏玩家结点为每个消息添加一个编号，统计丢失的消息数；当网络状态良好时采用固定周期W对网络进行量化的方法对网络状态进行评价，当网络丢包率高时，说明网络状态较差，相反当网络丢包率较低时，说明网络状态较好，网络中的丢包率作为评价网络状态的重要参考；

本发明算法的改良只限于本地独立处理消息并对网游状态进行更新，将量化周期中丢失和迟到的消息统称为失常消息，假设Mlost表示本周期内本游戏玩家结点发送给其他游戏玩家结点数据包中丢包的数量，Mlate表示本周期内本游戏玩家结点收到的消息中迟到消息的数量，Msum表示本周期内本游戏玩家结点收到的消息和发送消息的总数，本周期消息的消息失常率Qabnormal计算方法为式1：

通过式1得出当前周期内网络状态的量化结果，Qabnormal越小表示当前网络状态越好，Qabnormal越大表示当前网络的状况越差。

基于消息类型改良的Time Warp网游同步方法，进一步的，通过网络丢包和迟到消息对网络状态进行评价，当网络状态良好的时候，采用在固定周期W中，根据丢包和迟到消息计算出本周期中消息失常率，当计算结果为本周期Qabnormal＜Csill时，表示网络仍然良好，数据包可以及时达到其他游戏玩家结点，消息的延迟率很低，不会出现较多的网游状态回滚，这时只需保存较短时间内的网游状态快照即可满足可能的网游回滚；当Qabnormal＞Csill时，表示网络的状况较差，这时必然会出现大量消息延迟导致频繁的网游状态回滚；为避免频繁的网游状态回滚，一旦计算得到的Qabnormal大于Csill游戏玩家结点立即采用周期执行收到消息的方法对网游状态进行更新；采取动态周期算法后，下个周期的长度根据本周期的Qabnormal值进行调整，Qabnormal值越大，周期越长；当计算得到本周期的Qabnormal小于Csill时采用传统Time Warp算法对网游状态进行更新；当网络状态较差时，根据本周期Qabnormal调整下个周期的长度，当Qabnormal增大时，延长同步周期，当Qabnormal减小时，缩短同步周期；

当消息失常率Qabnormal超过Csill，Time Warp算法采用动态周期状态更新，动态同步周期W的值通过消息失常率计算，动态周期值计算如式2：

其中，Zmin为网游中游戏玩家结点中最短路径的延迟，Zmax为网游中游戏玩家结点中最长路径的延迟，Qabnormal为本周期的消息失常率，Csill为采用传统Time Warp算法能保持良好效果的消息最大失常率，F＝2，3，4。

基于消息类型改良的Time Warp网游同步方法，进一步的，在网游世界中，虚拟的网游对象分为以下几种：预设定对象、非玩家控制角以及游戏玩家操作的角，预设定对象是网游世界中不参与网游内容的对象，非玩家控制角为计算机控制的网游对象，游戏玩家角是网游玩家控制的角，游戏玩家可以控制它移动、攻击、防守等操作并与其他游戏玩家进行交互，游戏玩家角是网游中最重要的对象，游戏玩家角的行为引发网游消息的发生，同时游戏玩家角的属性随着游戏玩家间的交互发生变化，从而影响游戏的结果；

根据网游角的行为对网游状态的影响程度对网游消息进行分类，将网游消息分为两类：重要消息和非重要消息，重要消息是必然会影响网游状态的消息，该消息可能会改变网游中玩家的状态，也可能直接改变网游的结局，游戏玩家角的操作消息为重要消息，保证重要消息能安全传输到游戏玩家结点非常重要；网游中除了重要消息其它都为非重要消息，非重要消息对网游的状态不会有太大影响，非玩家控制角产生的消息大部分为非重要消息，所以非重要消息不需要及时传输给其他游戏玩家，只需保证一定时间内可以将非重要消息同步给其他游戏玩家来保证网游画面状态一致；

基于重要消息和非重要消息对网游重要性的不同，针对两类消息进行不同的处理，对TimeWarp算法进行改良，在改良算法中寻求在保证网游流畅性和较高响应性的前提下，减少网游状态的回滚和因为快照而导致的高内存占用。

基于消息类型改良的Time Warp网游同步方法，进一步的，基于网游消息分类对Time Warp算法的改良：重要消息对网游状态有直接的影响且具有不可替代性，所以当重要消息迟到时，直接对网游状态进行回滚；非重要消息是网游中对网游状态很小或基本不造成影响的消息，这类消息中对网游状态产生的作用很快就被后序消息的作用覆盖掉的为过期消息，对于过期的非重要消息，游戏玩家结点选择直接抛弃而不做处理，避免无谓的网游状态回滚。

基于消息类型改良的Time Warp网游同步方法，进一步的，定义消息过期：假设一个游戏玩家结点按照时间戳收到消息的序列为H＝{q1，q2，q3…qn|qi∈R}，R为网游中全局范围内所有可能的消息，假设qi和qj是游戏玩家结点1收到的来自游戏玩家结点2产生的两个连续非重要消息，[qi,qi+1,…qj-1,qj]执行后网游的状态为Xj，[qi+1，qi+2…qj-1,qj]执行后网游的状态为Xj'，如果Xj＝Xj'，那么认为消息qi对网游状态产生的影响完全可以被消息qj覆盖，称消息qi被消息qj过期，表示为qi∈qj，此时消息qi是否执行对网游状态已无关紧要；如果游戏玩家1准时收到非重要消息qj并且执行后，收到了迟到的非重要消息qi，此时不需要对网游状态进行回滚，降低网游的回滚率。

基于消息类型改良的Time Warp网游同步方法，进一步的，根据消息过期的定义，判断消息qi是否被消息qj过期，需要得到qi与qj间全部的消息序列，网游依赖的互网络存在不可避免的延迟与丢包问题，不能保证期间所有的消息都能到达目的结点，而且消息是否过期的判断是在所有消息到达后进行，这对于实时性要求极高的网游来说显然达不到要求；

假设Object(qi)＝Ui，Object(qj)＝Uj，Ui表示消息qi操作的对象集合，Uj表示消息qj操作的对象集合，如果存在qi∈qj，即qi消息对网游状态带来的影响完全可以被qj所覆盖，那么qi消息操作的对象的集合必定是qj操作对象的子集，即Ui∈Uj，如果消息qi与消息qj之间存在一个消息qk对qj的操作集合产生影响使得Ui∩Uj≠Ui，那么qi∈qj就不成立，通过这种方式可以快速判断qi对网游状态的影响是否能被消息qj覆盖。

基于消息类型改良的Time Warp网游同步方法，进一步的，网络游戏中，非玩家控制角、游戏玩家1和游戏玩家2同处一个兴趣区域，非玩家控制角在网游中保持简单的直线运动，W1时刻所在位置为Z1，状态为X1，产生并广播第一个非重要消息q1，经过很短时间的加速运动在W2时刻到达位置Z2，此刻状态为X2，产生并广播第二个非重要消息q2；如果在非玩家控制角运动的过程中没有其他消息发生改变非玩家控制角状态的话，游戏玩家1和游戏玩家2在收到这两个消息后，由于W1与W2之间的时间差很小，游戏玩家几乎感觉不出来，可以用消息q2代替消息q1更新网游状态；如果在非玩家控制角移动的过程中游戏玩家1对非玩家控制角的运行轨迹进行了改变，那么为在游戏玩家1和游戏玩家2画面中完整呈现真实的网游状态，消息q2就不能代替q1，即q2不能过期q1；

如果在网游中，结点收到的很多非重要消息都能够被过期，网游会出现大量的重要消息被丢弃，只执行最新的非重要消息，对于网游中网游对象的移动而言，大量的消息被丢弃会直接导致网游对象短时间内移动距离过大，对于游戏玩家而言就会造成网游画面的抖动；在实际应用中需要对非重要消息的过期水平进行评价，在抛弃过期消息的同时保证游戏玩家的网游体验。假设网络网游中非重要消息qi∈qj，消息qj完全可以覆盖消息qi对网游状态产生的影响，但是为保证游戏玩家画面的稳定性，qi与qj时间差应小于人的视觉感知消息，Wi、Wj分别为qi、qj产生的时间，如果|Wi-Wj|

基于消息类型改良的Time Warp网游同步方法，进一步的，针对消息类型的改良：基于网游中的非重要消息的特征，即被过期的非重要消息的效果可被新的消息代替，重要消息的特征，即重要消息不可以被其它消息代替且对网游状态有决定性作用；对Time Warp同步算法改良如下：当消息准时到达结点时即当网络良好时，采用传统Time Warp同步算法对消息处理的方式，收到消息时保存当前网游快照后，执行该消息来更新网游状态；当网络状态差时，采用动态周期同步对网游状态进行备份和更新；当游戏玩家结点收到的消息迟到时，如果该消息为重要消息，则采取状态回滚措施；如果该消息为非重要消息迟到时采用以下的处理策略：基于当前结点对消息进行过期判断，如果当前消息已经被产生于同一结点的新消息过期，则直接将该非重要消息抛弃，无需对网游状态进行回滚；如果当前迟到消息不能被其它消息过期，则采用状态回滚的方式确保游戏玩家间网游状态的一致。

与现有技术相比，本发明的贡献和创新点在于：

第一，由于现有技术的Time Warp同步算法，由于频繁的状态回滚和大量的内存占用严重影响着网游同步效果，本发明针对以上两方面对Time Warp算法提出了改良，一是将网游中的消息分为重要消息和非重要消息，部分非重要消息可能很快被其他消息过期，即一部分非重要消息即使丢失也不会对网游状态有所影响，当游戏玩家结点收到过期的非重要消息直接将其抛弃，这样可以降低网游的回滚次数；二是当网络状态良好时，网游消息可以及时抵达游戏玩家结点，消息迟到率较低，采用现有技术的Time Warp算法可以保证网游的响应性，网络状态较差时则采用动态周期同步策略，可以有效降低网游消息迟到率的同时减少了网游状态快照保存次数，即降低了网游快照对内存的占用，提高网游实时性与系统性能，在实际应用中有很高的利用价值；

第二，网游中游戏玩家间网游状态同步的积极同步算法，按照一定的规则执行游戏玩家间交互的数据包来更新网游状态，保证网游状态的一致性。在积极同步算法中最重要的为基于消息回滚的Time Warp同步算法，该算法在执行每个消息前都会保存当前网游状态的快照用来状态回滚，由于每执行一个消息都会对当前状态进行快照，会导致网游占用很大的内存，算法采用积极的态度，游戏玩家结点收到迟到的消息后进行状态回滚，那么在网络环境不理想的时候必然会导致网游的频繁回滚，本发明基于动态周期对Time Warp算法进行改良，基于网游消息分类对Time Warp算法进行改良，改良后的算法对不同的消息采用不同的处理策略，在保证网游交互性和一致性的同时尽可能降低网游因为快照导致的内存占用率，在计算机网络固有的数据包延迟、差错、不可避免的丢包、带宽资源有限的情况下，本发明对网游同步技术的研究改进具有广阔的市场应用空间；

第三，本发明基于消息类型对Time Warp算法进行改良，当网络状态比较差时，采用基于动态周期更新的Time Warp算法可有效降低消息的迟到率。基于非重要消息的特征，对Time Warp同步算法中的非重要消息处理策略进行的改良，如果非重要消息迟到首先检查该消息是否已经被过期，如果该消息已经被其它消息过期,则将该被过期的消息抛弃，否则进行回滚。Time Warp算法改良后，大幅减少网游状态的回滚次数和消息的迟到率，更为重要的是能减少网游快照次数和对内存的占用，改良后的算法使网游的实时性和一致性得到平衡，是一种具备显著创新性，且优势突出的网游同步方法；

第四，本发明提供的基于消息类型改良的Time Warp网游同步方法，游戏过程中对网游响应性的感受好，没有明显的卡顿感；没有察觉到网游画面和网游数据不一致的情况，游戏过程中没有感觉到明显的画面抖动，消息等待处理的时间短，消息的迟到数少，网游状态回滚次数明显减少，玩家的游戏体验明显变好。

图1是本发明Time Warp周期同步原理示意图。

图2是本发明针对重要消息处理改良后Time Warp算法处理流程图。

图3是基于动态周期和消息类型改良后Time Warp消息处理流程图。

下面结合附图，对本发明提供的基于消息类型改良的Time Warp网游同步方法的技术方案进行进一步的描述，使本领域的技术人员可以更好的理解本发明并能予以实施。

本发明基于消息类型对Time Warp算法进行改良，由于重要消息的丢失或延迟到达必定会导致网游状态的不一致，确保重要消息能够准时安全到达游戏玩家结点对于网游状态同步十分重要，网络的固有延迟和丢包，所以本发明提出基于实时网络状态的消息处理策略，算法改良后，当网络状态比较差时，采用基于动态周期更新的Time Warp算法可有效降低消息的迟到率。网络游戏中有大量的非重要消息，这些消息对网游状态影响很小且对网游状态产生的作用很快就被后序消息的作用覆盖掉。基于非重要消息的以上特征，本发明对Time Warp同步算法中的非重要消息处理策略进行的改良，如果非重要消息迟到首先检查该消息是否已经被过期，如果该消息已经被其它消息过期,则将该被过期的消息抛弃，否则进行回滚。Time Warp算法改良后，大幅减少网游状态的回滚次数和消息的迟到率，更为重要的是能减少网游快照次数和对内存的占用，改良后的算法使网游的实时性和一致性得到平衡。

本发明对Time Warp算法改良总结为：针对网游中重要消息和非重要消息对网游状态的影响程度不同，对两种消息采取不同的同步策略，当网络状态良好时，对网络进行定时评价，当网游中出现大量消息迟到时，改变消息处理策略，采取动态周期同步的方式对网游状态进行更新，游戏玩家结点收到迟到的重要消息时立即对网游状态进行回滚，而当游戏玩家结点收到迟到的非重要消息时，首先判断消息是否已经被其后的消息过期，如果是则直接抛弃，否则才会对网游状态进行回滚。本发明对改良后的Time Warp算法的改良了测试，结果表明优化后的算法在保证网游一致性的同时，显著降低了网游中消息的迟到率和网游状态回滚次数。

一、基于网络状态对Time Warp算法的改良

本发明提出基于Time Warp算法对网游中消息处理方法改良，改良后的算法对于消息延迟设定一个延迟极限临界值Csill，当网络延迟小于该值时代表当前网络状态良好，此时采用传统Time Warp算法的思想处理消息，游戏玩家结点在收到消息后立即更新状态，只有当收到迟到的消息后进行状态回滚。在网络状态良好时，游戏玩家结点的操作消息可以在短时间内到达其他结点，这时消息的迟到率很低，网游的回滚次数很少，游戏玩家结点只需要保存很短时间内网游状态的快照即可满足回滚要求。保证网络状态良好时，网游状态的一致性和网游的交互性。

当网络延迟大于Csill时，因为当前网络状态较差，这时会导致大量消息不能及时到达游戏玩家结点，从而导致大量的回滚操作。此时采用基于动态周期的快照和网游状态更新策略，动态周期的周期值根据网络状态来决定，周期更新即每当游戏玩家结点收到新的消息时不进行处理，而是在本周期结束时对网游当前状态进行快照并对本周期内收到的消息进行统一更新。采用周期同步的方式可避免每执行一个消息就对网游状态进行一次快照，而是每一个周期对网游状态进行一次快照，这显著降低网游的内存占用率。采用周期同步后，因为新的消息到达游戏玩家结点不需要进行及时更新，可降低网游消息延迟率和回滚率。如图1所示，当本地时钟执行到165ms的消息时，收到应该在145ms执行的迟到消息，这时会因为消息迟到而导致网游状态回滚。当采用周期同步后，虽然在145ms执行的消息要晚于在165ms执行的消息到达，但周期同步不会在接收到消息时立刻执行，而是在本周期结束时执行，即在180ms会将本周期所有的消息按照时间戳的顺序执行。所以尽管消息没有按照顺序到达，也不会导致网游状态回滚。

(一)量化网络环境状况

对于Time Warp算法中消息的改良中，网络状态的好坏需要每隔一定时间进行量化。每隔一段时间对网络状态进行评价，通过测量特定时间间隔W内游戏玩家的消息丢失率来判断网络状态。游戏玩家结点为每个消息添加一个编号，以便统计丢失的消息数。对于Time Warp算法重要消息改良中，当网络状态良好时采用固定周期W对网络进行量化的方法对网络状态进行评价。在实际应用中，网络的丢包率与网络状态有直接的关系，当网络丢包率高时，说明网络状态较差，相反当网络丢包率较低时，说明网络状态较好。所以网络中的丢包率可作为评价网络状态的重要参考。Time Warp算法中消息迟到也意味着网络存在一定的拥塞，消息的迟到率可作为量化网络状态的一个参考。

Time Warp同步算法不参与同一个网游世界的其他游戏玩家状态同步，仅依赖本地时钟进行自我的处理。算法的改良同样只限于本地独立处理消息并对网游状态进行更新，本发明将量化周期中丢失和迟到的消息统称为失常消息，假设Mlost表示本周期内本游戏玩家结点发送给其他游戏玩家结点数据包中丢包的数量，Mlate表示本周期内本游戏玩家结点收到的消息中迟到消息的数量，Msum表示本周期内本游戏玩家结点收到的消息和发送消息的总数。那么本周期消息的消息失常率Qabnormal计算方法为式1：

通过式1得出当前周期内网络状态的量化结果，Qabnormal越小表示当前网络状态越好，Qabnormal越大表示当前网络的状况越差。

(二)基于动态周期的改良

通过网络丢包和迟到消息对网络状态进行评价，当网络状态良好的时候，采用在固定周期W中，根据丢包和迟到消息计算出本周期中消息失常率。当计算结果为本周期Qabnormal＜Csill时，表示网络仍然良好，数据包可以及时达到其他游戏玩家结点，消息的延迟率很低，不会出现较多的网游状态回滚，这时只需保存较短时间内的网游状态快照即可满足可能的网游回滚。当Qabnormal＞Csill时，表示网络的状况较差，这时必然会出现大量消息延迟导致频繁的网游状态回滚。为避免频繁的网游状态回滚，一旦计算得到的Qabnormal大于Csill游戏玩家结点立即采用周期执行收到消息的方法对网游状态进行更新。采取动态周期算法后，下个周期的长度根据本周期的Qabnormal值进行调整，Qabnormal值越大，周期越长。当计算得到本周期的Qabnormal小于Csill时采用传统Time Warp算法对网游状态进行更新。

当网络状态较差时，根据本周期Qabnormal调整下个周期的长度，当Qabnormal增大时，适当延长同步周期，当Qabnormal减小时，适当缩短同步周期。由于网游玩家对游戏的交互性要求很高，如果网游状态更新周期设置的太大，就会明显降低游戏玩家对网游的直观体验。基于网游的交互性和响应性的考虑，周期长度的取值不应该过大，为保证网游的交互性将网游交互临界值Wmax设置为同步周期上限。同步周期同样不能太小，如果周期太小会退化成传统的Time Warp算法，将周期最小值Wmin设置为网游世界中各个游戏玩家结点间最长路径需要的最小延迟。

当消息失常率Qabnormal超过Csill，Time Warp算法采用动态周期状态更新，动态同步周期W的值通过消息失常率计算，动态周期值计算如式2：

其中，Zmin为网游中游戏玩家结点中最短路径的延迟，Zmax为网游中游戏玩家结点中最长路径的延迟，Qabnormal为本周期的消息失常率，Csill为采用传统Time Warp算法能保持良好效果的消息最大失常率，F＝2，3，4。

网络延迟是导致网游同步问题产生的根源，本发明针对网络实时状况提出对网游中消息处理策略的改良。改良后的算法在网络状态比较差时，采用动态周期Time Warp算法执行游戏玩家结点收到的消息对网游进行更新，可减少网游状态的回滚率，同时可减少网游状态快照对内存的占用。当采用动态周期Time Warp算法处理消息时，如果消息的网络延迟，仍然使游戏玩家消息在超过动态周期长度后到达游戏玩家结点，则采用回滚的方式回滚到上个网游状态，并重新计算下个动态周期的长度。其中有一点需要指出，在回滚后需要将网游快速执行到当前正确的物理时间，以保证正常的状态更新。采用动态周期性同步的Time Warp算法，游戏玩家结点收到的消息不能立即执行，会在一定程度上降低游戏玩家的操作响应时间。而当网络状态良好时，采用传统的Time Warp算法可以在保证游戏玩家的网游体验的同时，维持网游玩家间网游状态的高度一致。改良后的Time Warp算法原理如图2所示。

二、网游消息分类

在网游世界中，虚拟的网游对象分为以下几种：预设定对象、非玩家控制角以及游戏玩家操作的角。预设定对象是网游世界中不参与网游内容的对象，非玩家控制角为计算机控制的网游对象，游戏玩家角是网游玩家控制的角，游戏玩家可以控制它移动、攻击、防守等操作并与其他游戏玩家进行交互。游戏玩家角是网游中最重要的对象，游戏玩家角的行为引发网游消息的发生，同时游戏玩家角的属性随着游戏玩家间的交互发生变化，从而影响游戏的结果。

根据网游角的行为对网游状态的影响程度对网游消息进行分类，将网游消息分为两类：重要消息和非重要消息。重要消息是必然会影响网游状态的消息，该消息可能会改变网游中玩家的状态，也可能直接改变网游的结局，游戏玩家角的操作消息为重要消息，保证重要消息能安全传输到游戏玩家结点非常重要。网游中除了重要消息其它都为非重要消息，非重要消息对网游的状态不会有太大影响，非玩家控制角产生的消息大部分为非重要消息。所以非重要消息不需要及时传输给其他游戏玩家，只需保证一定时间内可以将非重要消息同步给其他游戏玩家来保证网游画面状态一致。

基于重要消息和非重要消息对网游重要性的不同，针对两类消息进行不同的处理，从而对Time Warp算法进行改良。在改良算法中寻求在保证网游流畅性和较高响应性的前提下，减少网游状态的回滚和因为快照而导致的高内存占用。

三、基于网游消息分类对Time Warp算法的改良

由于重要消息对网游状态有直接的影响且具有不可替代性，所以当重要消息迟到时，直接对网游状态进行回滚。非重要消息是网游中对网游状态很小或基本不造成影响的消息，这类消息中对网游状态产生的作用很快就被后序消息的作用覆盖掉的为过期消息。对于过期的非重要消息，游戏玩家结点可以选择直接抛弃而不做处理，这么做有两个好处，一是可以在一定程度上避免资源浪费，二是对于迟到并且已经过期非重要消息，该方式避免了无谓的网游状态回滚。

(一)定义消息过期

假设一个游戏玩家结点按照时间戳收到消息的序列为H＝{q1，q2，q3…qn|qi∈R}，R为网游中全局范围内所有可能的消息，假设qi和qj是游戏玩家结点1收到的来自游戏玩家结点2产生的两个连续非重要消息，[qi,qi+1,…qj-1,qj]执行后网游的状态为Xj，[qi+1，qi+2…qj-1,qj]执行后网游的状态为Xj'，如果Xj＝Xj'，那么认为消息qi对网游状态产生的影响完全可以被消息qj覆盖，称消息qi被消息qj过期，表示为qi∈qj，此时消息qi是否执行对网游状态已无关紧要。如果游戏玩家1准时收到非重要消息qj并且执行后，收到了迟到的非重要消息qi，此时不需要对网游状态进行回滚，可以降低网游的回滚率。

根据消息过期的定义，判断消息qi是否被消息qj过期，需要得到qi与qj间全部的消息序列，但网游依赖的互网络存在不可避免的延迟与丢包问题，不能保证期间所有的消息都能到达目的结点，而且消息是否过期的判断是在所有消息到达后进行，这对于实时性要求极高的网游来说显然达不到要求。假设Object(qi)＝Ui，Object(qj)＝Uj，Ui表示消息qi操作的对象集合，Uj表示消息qj操作的对象集合。如果存在qi∈qj，即qi消息对网游状态带来的影响完全可以被qj所覆盖，那么qi消息操作的对象的集合必定是qj操作对象的子集，即Ui∈Uj。如果消息qi与消息qj之间存在一个消息qk对qj的操作集合产生影响使得Ui∩Uj≠Ui，那么qi∈qj就不成立，通过这种方式可以快速判断qi对网游状态的影响是否能被消息qj覆盖。

网络游戏中，非玩家控制角、游戏玩家1和游戏玩家2同处一个兴趣区域，非玩家控制角在网游中保持简单的直线运动，W1时刻所在位置为Z1，状态为X1，产生并广播第一个非重要消息q1，经过很短时间的加速运动在W2时刻到达位置Z2，此刻状态为X2，产生并广播第二个非重要消息q2。如果在非玩家控制角运动的过程中没有其他消息发生改变非玩家控制角状态的话，游戏玩家1和游戏玩家2在收到这两个消息后，由于W1与W2之间的时间差很小，游戏玩家几乎感觉不出来，可以用消息q2代替消息q1更新网游状态。如果在非玩家控制角移动的过程中游戏玩家1对非玩家控制角的运行轨迹进行了改变，那么为在游戏玩家1和游戏玩家2画面中完整呈现真实的网游状态，消息q2就不能代替q1，即q2不能过期q1。

如果在网游中，结点收到的很多非重要消息都能够被过期，网游会出现大量的重要消息被丢弃，只执行最新的非重要消息，对于网游中网游对象的移动而言，大量的消息被丢弃会直接导致网游对象短时间内移动距离过大，对于游戏玩家而言就会造成网游画面的抖动。在实际应用中需要对非重要消息的过期水平进行评价，在抛弃过期消息的同时保证游戏玩家的网游体验。假设网络网游中非重要消息qi∈qj，消息qj完全可以覆盖消息qi对网游状态产生的影响，但是为保证游戏玩家画面的稳定性，qi与qj时间差应小于人的视觉感知消息，Wi、Wj分别为qi、qj产生的时间，如果|Wi-Wj|

(二)针对消息类型的改良

基于网游中的非重要消息的特征，即被过期的非重要消息的效果可被新的消息代替，重要消息的特征，即重要消息不可以被其它消息代替且对网游状态有决定性作用。对Time Warp同步算法改良如下：当消息准时到达结点时即当网络良好时，采用传统TimeWarp同步算法对消息处理的方式，收到消息时保存当前网游快照后，执行该消息来更新网游状态；当网络状态差时，采用动态周期同步对网游状态进行备份和更新；当游戏玩家结点收到的消息迟到时，如果该消息为重要消息，则采取状态回滚措施；如果该消息为非重要消息迟到时采用以下的处理策略：基于当前结点对消息进行过期判断，如果当前消息已经被产生于同一结点的新消息过期，则直接将该非重要消息抛弃，无需对网游状态进行回滚；如果当前迟到消息不能被其它消息过期，则采用状态回滚的方式确保游戏玩家间网游状态的一致。

基于动态周期和消息类型改良后Time Warp消息处理流程如图3所示。

四、Time Warp同步算法改良实验与结果分析

(一)实验场景

在Unity3D中建立一个网游场景，六台客户端分为二组，该场景中有三个网游角，和三个非玩家控制角，每当网游角经过非玩家控制角时，非玩家控制角的正面会转向该角。每组三个客户端，第一组采用Time Warp算法，第二组采用本发明改良后的Time Warp算法对收到网游消息进行处理。该网游场景大小为280*280，角可在地图允许的范围内运动，角的运动没有限制，游戏玩家通过键盘上的W、A、S、D和鼠标间的配合控制角的运动，每个客户端利用Head Reckoning技术对角的运动轨迹进行预测。角在地图中移动的过程中通过鼠标左键选中其他角同时按下键盘上的Q键完成对其他角的攻击，角的攻击次数不做限制，为保证网游的平衡，角1秒钟最多攻击1次。该网游场景中游戏玩家控制的角产生的消息均为重要消息，非玩家控制角产生的消息为非重要消息。为保证实验结果的可靠性，二组游戏玩家同时在同一网络环境下进行游戏，网游过程持续50分钟以上，消息交互量在6000次以上。通过统计实验中在相同网络情况下二种算法中消息的迟到率和网游状态的回滚次数，对二种算法进行比较。

(二)算法性能评价指标

本次实验的目的在于验证改良后的Time Warp同步算法是否能在保证网游状态一致性的前提下，减少网游消息迟到数与网游状态的回滚次数以及网游的内存占用率。所以需要对网游的性能有客观，准确的评价。本发明提出以下评价指标。

1.主观评价指标包括：一是实验人员在游戏过程中对网游响应性的感受，是否会出现明显的卡顿感；二是实验人员在网游过程中是否察觉到网游画面和网游数据不一致的情况；三是实验人员在游戏过程中是否感觉到明显的画面抖动，及抖动发生的频率是否能接受。

2.客观的评价指标包括：一是消息等待处理的时间，基于动态周期的Time Warp算法的消息处理时间会出现波动；二是消息的迟到数，Time Warp算法频繁的消息迟到，导致频繁的网游状态回滚和网游快照对内存的大量占用，所以消息的迟到严重影响着网游的同步性能；三是网游状态的回滚次数，基于消息类型的Time Warp算法会对网游状态进行选择回滚，避免大量的网游状态回滚。

(三)实验结果分析

实验在局域网中完成，将18台客户机分为两组。第一组采用传统的Time Warp同步算法，第二组采用本发明改良后的Time Warp同步算法。通过实验人员的主观切身感受和客观的各个指标对每种算法的表示进行客观评价。为保证实验的严密性，二组客户端除采用的消息处理算法外其它一切指标都相同。保证网游实验结果具有可靠性和说服力，网游进行时间保证在60分钟以上，且消息的交互量在18000次以上。为保证网游中游戏玩家的正常体验，两组都采用Head Reckoning客户端状态预测，对网游中角的运动进行预测。

实验1：实验目的：对比二个算法在消息处理响应时间和消息的迟到数目，以便评价基于动态周期改良后的Time Warp算法与传统算法的性能改良效果。实验结果：采用传统Time Warp算法的实验人员表示在实验的过程中出现了频繁的画面抖动，在一定程度上影响了实验人员对网游的体验，网游流程度和响应性一般。采用本发明基于动态周期改良的Time Warp算法的实验人员表示，游戏过程没有出现频繁的画面抖动，偶尔会出现响应不及时的问题，但整体在可接受的范围内。结论：采用基于动态周期的Time Warp算法能有效降低网游中消息的迟到数，网游的流畅性能可以得到保证。

实验2：实验目的：对比两个算法在网游中消息迟到数目，网游状态的回滚次数，以及网游对内存的占用率，以便评价基于消息分类回滚改良的Time Warp算法与传统算法的性能改良效果。实验结果：两组实验人员都未感觉到明显的卡顿，采用基于消息分类改良的Time Warp的实验人员表示网游的过程中没有出现过频繁的画面抖动，网游整体感觉好。采用传统Time Warp算法的实验人员表示网游的过程中出现了频繁的画面抖动，非常影响网游体验。表明改良后的Time Warp算法保持网游状态快照的次数在一定程度上有所减少，对内存的占用有一定程度上的降低。

改良后的Time Warp算法的消息处理过程总结为：当游戏玩家结点收到其它结点的网游时间时，首先根据时间戳判断该消息是否已经迟到，如果消息已经迟到，首先更新用来对网络进行评价的数据集，接下来判断该消息是否为重要消息，如果是非重要消息，则检查该消息是否被过期，如果已经被其他消息过期将该消息抛弃，不对网游状态进行回滚，如果该消息为重要消息或为未被过期的非重要消息则对网游状态进行回滚，接着将网游状态快速更新到当前时钟对应的位置。如果该消息没有迟到，判断本评价周期是否结束，如果已经结束，则根据本周期中消息的迟到数，丢失数来判断本评价周期中消息的失常率。如果消息失常率超过临界值则下个评价周期采用动态周期Time Warp算法处理网游消息，动态周期的长度可以根据本周期的失常率通过计算获得。如果失常率低于临界值则采用传统的Time Warp算法处理网游消息。如果本评价周期没有结束，则继续采用本周期初决定好的同步策略处理网游消息。在本地结点处理网游消息时，采用Head Reckoning平滑技术对角的运动做平滑处理，在利用收到的消息更新完网游状态后，采用Head Reckoning位置预测技术对角的运动进行预测。