一种基于感知模型的Timewarp算法

《一种基于感知模型的Timewarp算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2010年6月沈阳航窄工业学院学报第27卷第3期JournalofShenyangInstituteofAeronauticalEngineeringJun．2010V01．27No．3文章编号：1007—1385(2010)03—0041—05一种基于感知模型的Timewarp算法石祥滨王晓晖刘芳(沈阳航空航天大学计算机学院，辽宁沈阳110136)摘要：针对MMOG同步算法中状态回卷效率低的问题，提出一种基于感知模型的Timewarp算法。该算法采用基于视觉行为特征的感知模型，根据感知模型中不同

2、层次对一致性的要求程度的不同和对象对游戏状态的影响度，对未过时的迟到事件进行综合分析与过滤，仅对一部分迟到事件执行状态回卷。实验结果证明，该算法能减少回卷次数并降低通信量，从而提高游戏的交互性与可玩性。关键词：MMOG；Timewarp算法；感知模型；回卷中图分类号：TP393文献标识码：A随着计算机技术的飞速发展和人们娱乐需求的提高，网络游戏已进入了MMOG(MassivelyMuhiplayerOnlineGame，大型多人在线游戏)时代，游戏规模日益庞大。由于MMOG以Intemet为依托，

3、固有的网络延迟，带宽差异及UDP传输机制，可能使数据包乱序或延迟到达目的节点，从而导致事件以不同顺序被执行，引起玩家之间游戏状态不一致。传统的MMOG基于C／S模式，服务器集中控制所有游戏事件，维护了状态的一致性，但C／S模式存在单点失败和带宽瓶颈问题⋯。P2P结构作为一种分布式计算模式可以很好地解决单点失败和瓶颈问题悼J，但这种结构中玩家节点各自进行游戏状态计算与更新加重了MMOG中的一致性问题，从而需要对游戏状态短期不一致进行回卷修复。因此状态修复的效率对同步算法的性能有重要影响。目前网络游戏

4、中的同步算法主要有TSS算法和Timewarp算法两类。TSS算法p1通过维护一定数量的游戏状态拷贝来检测并修复不一致。该算法通过真实状态而不是迟到事件来检测是否发生不一致，减少了回滚次数，但是该算法限制了迟到事件的延迟上限，且需要大量的事件计算，耗费很大的内存。Timewarp算法【41通过比较接收事收稿日期：2009—11—13基金项目：辽宁省教育厅科学技术研究项目(项目编号：2008558)；沈阳市科学技术计划(项目编号：1091185—1—00)；航空一集团航空科学基金(项目编号：2008

5、ZC54008)。作者简介：石祥滨(1963一)，男，辽宁普兰店人，教授，主要研究方向：分布式系统、网络游戏、数据库技术，E—mail：目cb@syiae．edu．cIl。件的时间戳与状态队列中的最大保存时间来检测与修复不一致。该算法对所有迟到事件都执行状态回卷修复，消耗过多的计算时间，可能引起画面停顿与回退现象，影响游戏的流畅感，使其失去应有的可玩性。所以需要对迟到事件进行过滤，减少不必要的状态回卷。在Timewarp算法的基础上，引入了基于视觉行为特征的感知模型和对象影响度，根据事件在感知模型

6、中的所属层次，及事件对象的影响度来判定未过时迟到事件是否引发回卷修复。从而减少了回卷次数，提高了游戏的交互性与可玩性。1Timewarp算法的基本原理Timewarp算法H1是一种乐观同步算法，它由两部分组成：局部控制机制和全局控制机制。基本思想是节点定期对游戏状态进行快照，如果收到一个迟到事件，并且该事件时间戳之后的事件已被执行，即事件执行顺序被打乱，此时发起回卷；游戏状态会回卷到迟到事件之前最近的正确状态，接着重新执行事件队列中迟到事件及其时间戳值以后的所有事件。由于需要定期进行状态存储，占用

7、大量内存，因此每隔一段时间进行内存的回收。由全局控制机制维护一个全局虚拟时间GVT(GlobalVirtualTime)用于检验哪些内存可以被安全的回收。Timewarp算法在不同游戏体系结构中实现方式不同。C／S结构中，服务器根据所有玩家事件计算当前游戏状态并发送给玩家节点，玩家节点通过服务器发回的更新信息来获取游戏的最新42沈阳航空工业学院学报第27卷状态。当服务器端发生事件丢失或迟到时，只在服务器端进行回卷检测与修复，就能保证玩家间游戏状态的～致性。而在P2P结构中，当玩家触发事件时，直接发

8、送事件给其他玩家。每个玩家根据接收到的事件进行计算得到最新的游戏状态，并保存全局游戏状态的拷贝，当事件丢失或迟到时，玩家节点需要自行检测与修复。在MMOG中，一系列事件不同的处理J颐序可能得到不同的游戏结果。为保证玩家之间游戏状态一致，需要在不可靠连接条件下保证事件在各个节点以一致的顺序进行处理。当有迟到事件到达节点时，为保证事件处到顷序一致，需要发起回卷。然而并不是所有迟到事件都会导致游戏状态不一致，例如与本地玩家角色无直接操作的事件等。2基于感知模型的Timewarp算法为了对