帧锁定同步算法

帧锁定算法解决游戏同步

早期 RTS,XBOX360 LIVE游戏常用同步策略是什么?格斗游戏多人联机如何保证流畅性和一致性?如何才能像单机游戏一样编写网游?敬请观看《帧锁定同步算法》

《帧锁定同步算法》转载请注明出处:http://www.skywind.me/blog/archives/131

 

算法概念

该算法普遍要求网速RTT要在100ms以内,一般人数不超过8人,在这样的情况下,可以像单机游戏一样编写网络游戏。所有客户端任意时刻逻辑都是统一的,缺点是一个人卡机,所有人等待。

1.客户端定时(比如每五帧)上传控制信息。
2.服务器收到所有控制信息后广播给所有客户。
3.客户端用服务器发来的更新消息中的控制信息进行游戏。
4.如果客户端进行到下一个关键帧(5帧后)时没有收到服务器的更新消息则等待。
5.如果客户端进行到下一个关键帧时已经接收到了服务器的更新消息,则将上面的数据用于游戏,并采集当前鼠标键盘输入发送给服务器,同时继续进行下去。
6.服务端采集到所有数据后再次发送下一个关键帧更新消息。

这个等待关键帧更新数据的过程称为“帧锁定”
应用案例:大部分RTS游戏,街霸II(xbox360),Callus模拟器。

 

算法流程

客户端逻辑:
1.        判断当前帧F是否关键帧K1:如果不是跳转(7)。
2.        如果是关键帧,则察看有没有K1的UPDATE数据,如果没有的话重复2等待。
3.        采集当前K1的输入作为CTRL数据与K1编号一起发送给服务器
4.        从UPDATE K1中得到下一个关键帧的号码K2以及到下一个关键帧之间的输入数据I。
5.        从这个关键帧到下 一个关键帧K2之间的虚拟输入都用I。
6.        令K1 = K2。
7.        执行该帧逻辑
8.        跳转(1)

服务端逻辑:
1.        收集所有客户端本关键帧K1的CTRL数据(Ctrl-K)等待知道收集完成所有的CTRL-K。
2.        根据所有CTRL-K,计算下一个关键帧K2的Update,计算再下一个关键帧的编号K3。
3.        将Update发送给所有客户端
4.        令K1=K2
5.        跳转(1)

1

服务器根据所有客户端的最大RTT,平滑计算下一个关键帧的编号,让延迟根据网络情况自动调整。

 

算法演示

我根据该算法将街机模拟器修改出了一个可用于多人对战的版本,早期有一个叫做kaillera的东西,可以帮助模拟器实现多人联机,但是并没有作帧锁定,只是简单将键盘消息进行收集广播而已,后来Capcom在PSP和360上都出过街霸的联网版本,但是联网效果不理想。这个算法其实局域网有细就经常使用了,只是近年来公网速度提高,很容易找到RTT<50ms的服务器,因此根据上述算法,在平均RTT=100ms(操作灵敏度1/10秒),情况下,保证自动计算关键帧适应各种网络条件后,就能够像编写单机游戏一样开发网游,而不需状态上作复杂的位置/状态同步。

2

从上图的演示中可以看到,两个模拟器进程都在运行1941这个游戏,两边客户端使用了该算法,将逻辑统一在一个整体中。

3

最后这张图是运行KOF99的效果图,两边完美同步。

 

乐观帧锁定

针对传统严格帧锁定算法中网速慢会卡到网速快的问题,实践中线上动作游戏通常用“定时不等待”的乐观方式再每次Interval时钟发生时固定将操作广播给所有用户,不依赖具体每个玩家是否有操作更新:

1. 单个用户当前键盘上下左右攻击跳跃是否按下用一个32位整数描述,服务端描述一局游戏中最多8玩家的键盘操作为:int player_keyboards[8];

2. 服务端每秒钟20-50次向所有客户端发送更新消息(包含所有客户端的操作和递增的帧号):

update=(FrameID,player_keyboards)

3. 客户端就像播放游戏录像一样不停的播放这些包含每帧所有玩家操作的 update消息。

4. 客户端如果没有update数据了,就必须等待,直到有新的数据到来。

5. 客户端如果一下子收到很多连续的update,则快进播放。

6. 客户端只有按键按下或者放开,就会发送消息给服务端(而不是到每帧开始才采集键盘),消息只包含一个整数。服务端收到以后,改写player_keyboards

————-

虽然网速慢的玩家网络一卡,可能就被网速快的玩家给秒了(其他游戏也差不多)。但是网速慢的玩家不会卡到快的玩家,只会感觉自己操作延迟而已。另一个侧面来说,土豪的网宿一般比较快,我们要照顾。

随机数需要服务端提前将种子发给各个客户端,各个客户端算逻辑时用该种子生成随机数,另外该例子以键盘操作为例,实际可以以更高级的操作为例,比如“正走向A点”,“正在攻击”等。该方法目前也成功的被应用到了若干实时动作游戏中。

 

指令缓存

针对高级别的抽象指令(非前后可以覆盖的键盘操作),比如即时战略游戏中,各种高级操作指令,在“乐观帧锁定”中,客户端任何操作都是可靠消息发送到服务端,服务端缓存在对应玩家的指令队列里面,然后定时向所有人广播所有队列里面的历史操作,广播完成后清空队列,等待新的指令上传。客户端收到后按顺序执行这些指令,为了保证公平性,客户端可以先执轮询行每个用户的第一条指令,执行完以后弹出队列,再进入下一轮,直到没有任何指令。这样在即时战略游戏中,选择 250ms一个同步帧,每秒四次,已经足够了。如果做的好还可以象 AOE一样根据网速调整,比如网速快的时候,进化为每秒10帧,网速慢时退化成每秒4帧,2帧之类的。

————–

PS:可以把整段战斗过程的操作和随机数种子记录下来,不但可以当录像播放,还可以交给另外一台服务端延迟验算,还可以交给其他空闲的客户端验算,将验算结果的 hash值进行比较,如果相同则认可,如果不通则记录或者处理,服务端如果根据游戏当前进程加入一些临时事件(比如天上掉下一个宝箱),可以在广播的时候附带。

(完)

解密:腾讯如何打造一款实时对战手游

2015年以来,手机游戏的市场偏好,逐渐从早期的休闲类、跑酷类、卡牌类游戏,转向重度、操作性更强的ARPG 、FPS、MOBA类游戏。

因此实时对战这一游戏玩法,也逐渐成为了手机游戏的一个核心玩法。

纵观AppStore畅销榜前十的游戏,过半都支持玩家实时的PK或者合作攻关。由于实时对战有玩家之间自发进行强互动的特点,活跃度和社交强度都是比较高,为游戏的用户活跃和流水的提高奠定了坚实的基础。

腾讯的游戏开发团队,很早就观察到实时对战这一核心玩法对游戏生命周期影响的重要性,因此在自研产品方面,加大力度开发围绕实时对战这一核心玩法的游戏,从而诞生了《王者荣耀》、《穿越火线·枪战王者》、《全民超神》、《全民突击》、《天天炫斗》等一大批优秀的作品,其中不乏日活跃过千万的大作。

而早期的休闲类游戏如《全民飞机大战》等,也加入了实时双打等游戏特性,所以现在依然可以经常在AppStore畅销榜前十看到《全民飞机大战》这款游戏的身影。

既然实时对战是一个非常重要的游戏玩法,为什么我们现在看到的许多游戏,都不具备这一的玩法,或者并不是游戏的主要玩法?其中一个重要的原因,就是开发实时对战的功能,在技术上需要有一定的门槛。本文希望能向大家分享腾讯是如何跨过这些门槛,解决实时对战游戏开发的一系列核心技术难题。

游戏数据同步方案

首先我们介绍实时对战手游中最难解决的技术问题——弱网络下的同步问题。

通过对玩家的游戏数据进行观察,发现玩家的游戏环境存在很大差异,不同玩家会使用不同的2G/3G/4G/Wifi网络,不同网络之间的延迟相差很大。另外移动网络质量不稳定,且都是按流量收费,这些都是需要考虑的问题。手机在网络间的切换,又会造成底层网络断线、地址变化等问题,都是常见的情况。这些问题的统一解决手段,最重要的是通盘考虑各种需求,选择一个合理的游戏状态同步模型。

腾讯在大量游戏开发的实践中,总结出三种游戏的同步模型:

 

第一种叫MMOG模式。这种同步模型,在端游时代就使用的非常广泛,特别是MMORPG里面。

它的主要实现要点是:服务器负责计算全部的游戏逻辑,并且广播这些计算的结果,客户端仅仅负责发送玩家的操作,以及表现收到的游戏结果。一般来说,玩家发送一个操作到服务器上,服务器根据玩家操作去修改内存中的游戏世界模型,同时运算游戏世界对这个操作的反应,然后把这些反应都广播给相关的多个客户端,每个客户端负责把这些数据表现出来给玩家看。

这种做法的优点是非常安全,由于整个游戏逻辑都在服务器上,服务器只接受合法的玩家操作,一切都经过既定逻辑的运算。另外一个优点是游戏的逻辑更新很方便,因为主要逻辑都在服务器端。一般的游戏玩法需要更新,游戏开发团队自己更新重启服务器就可以了,无需让千万个手机去下载更新包。

但是这种做法的缺点也很明显,首先就是用户的体验非常依赖网络质量,如果一个用户的网速慢,其他玩家都会发现他在游戏中明显的变卡。

另外一个缺点就是服务器负责了太多的游戏逻辑运算。在动作游戏里,服务器往往需要针对二维或者三维空间进行运算。

最后,使用这种同步方案,由于每个游戏表现都要以数据包发往客户端,所以当一起玩的用户数量较多,这种广播的数据包量就会非常大。

因此根据以上的特点,腾讯一般会在那些同局游戏人数不太多,但讲求玩法变化快和安全性高的游戏中采用这种同步方案。腾讯自研手游中比较著名的《穿越火线·枪战王者》、《全民超神》、《炫斗之王》都是使用这种方案。

关注点 表现
网络延迟 <  100ms
流量 占用较大,同时游戏角色越多占用越大
服务器负载 非常高
安全性 很好,能很方便的做反外挂。

第二种方案叫主机模式。这种同步方案的做法是:以参与对战的一个客户端为“主机”,其他的客户端为“副机”。

游戏逻辑的主要运算由“主机”完成,所有的“副机”把操作指令,通过服务器中转,集中发送给“主机”;“主机”完成游戏运算后,把结果指令再通过服务器中转,广播给所有的“副机”。

这个方案看起来有点奇怪,但是却有很明显的优点:首先是大量的实时动作游戏,其游戏过程的逻辑代码,都是在客户端上开发和运行的。客户端的游戏引擎对于二维、三维空间中的位置运算、碰撞检测等功能,都有很好的支持。

因此把整个游戏逻辑由客户端负责,就能让服务器端无需再开发这部分功能。服务器只负责做转发、广播的操作,所以能承载的人数和第一种方案有数量级上的差别。由于“主机”客户端运行游戏逻辑,所以其体验是最好的,就算“副机”由于网络不佳造成体验下降,对于“主机”来说,只是发现“副机”动作有点迟缓而已。

在以PVE玩法为主的游戏中,用户关注的是自己的体验,不会太在意同伴的准确动作,这种情况下,主机模式就是一种不错的同步方案。腾讯的《全民飞机大战》的双打模式就是采用这种方式,效果相当不错。

关注点 表现
网络延迟 <  400ms
流量 一般,大概为MMOG模式一半
服务器负载
安全性 较差,比较容易通过修改客户端作假

第三种方案叫帧同步模式,又叫“锁步模式”。这种模式用形象的比喻来说,就是把所有参与对战的客户端,看成是排成一列的囚犯。这些囚犯们的左脚都被链子所在一起,因此他们如果要往前走,就只能同时迈步,如果其中某个人走快了,或者走慢了,都会让整队人停下来。

在实现上,一般是以服务器按固定的帧率,来搜集每个客户端的输入,然后把这些输入广播给所有的客户端;由于每个操作指令到达所有客户端的时间(帧)都是一样的,所以每个客户端运算的结果也是一样的,同样的输入就会得到同样的结果。

这就好像:其他玩家通过网络,把操作手柄接到你的手机。这种同步方案,是传统单机-局域网游戏中最常用的。

这种同步模型的最大优点是:强一致性。每个客户端的表现是完全一样的,非常适合高度要求操作技巧的游戏。由于广播的仅是玩家的操作,所以数据量很少。不管游戏中的角色数、状态量有多大、多复杂,都不会影响广播的数据量。

但是这个方案也有缺点:对所有玩家的延迟都有要求,一般来说要求在50毫秒以内。如果有一个客户端网络卡了,所有的客户端都要停下来等,大家在玩《星际争霸》就见识过:一个玩家断线,全部玩家的游戏都暂停。腾讯游戏中的《王者荣耀》、《全民突击》由于竞技性非常强,所以采用了这种方案。

另外在帧同步模式中,数据同步的频率较高,网络延迟越小越好。由于TCP的滑动窗口机制和重传机制,导致延时无法控制,因此帧同步一般采用udp进行网络传输,但udp又会衍生出可靠性问题,对于客户端,如果某些udp包没有收到,就会出现丢帧的情况,所以这里我们自己研发了一套《可靠UDP传输》的协议,应用在《王者荣耀》项目。关于《可靠UDP传输》的相关技术介绍,后续会作为专题继续分享给大家。

关注点 表现
网络延迟 <  50ms
流量 很小
服务器负载
安全性 差,游戏逻辑主要依赖客户端

安全问题

游戏外挂,一直是国内游戏市场的痼疾。在实时对战的游戏中,常见的有修改客户端代码运行时逻辑、协议破解,以及脚本代替玩家行为等外挂。对此,我们花了很大力气,从游戏的内部结构上,对抗这些破坏游戏性的行为。现在比较常用的手段有四种:

第一种是服务器驱动。在同步模型中的”MMOG模型”中,游戏逻辑都由服务器控制,所以外挂能攻击的空间比较小,这是最好的对抗外挂的方法。由于逻辑全部在服务器上运算,所以外挂几乎无法从游戏逻辑中得到任何好处,只能在降低玩家操作难度上想办法。

但是这种方案的代价也是高昂的:服务器需要保存整个游戏世界的模型,并演算所有的AI逻辑,这让服务器消耗大量内存和CPU,增加了服务器端代码的复杂性。

第二种是MonoSvr抽查回放。这种方法是在第一种服务器驱动方案上的一种简化:客户端还是会上传所有的游戏操作,但服务器并不完全的演算整个战斗逻辑,仅对容易被外挂攻击的部分,进行验证。

服务器上仅保留部分世界模型即可,从而降低了服务器的运算量。客户端并不需要等待服务器的命令回复,就可以先按自己的逻辑去运行,所以体验上有更好的表现。如果服务器发现了作弊,会事后惩罚相关的帐号。这种做法也有漏洞:因为那些没有被抽查到的客户端,或没有被验证的逻辑,都可能是外挂攻击的漏洞。

第三种是柔性反外挂。这种方法的校验更加简单,仅仅在服务器上保留了一批预设的校验规则。这些规则可能是核算玩家的收益和付出是否合理、一些重点操作是否符合规则……。

这种方案服务器的压力非常的轻。由于验算的过程大大的加快了,玩家的体验也会很好。不过这种方法的漏洞更加多,一旦外挂熟悉了这些预设的校验规则,就很容易进行针对性的攻击。

第四种是举报系统。这种方法简单来说就是人民战争,让玩家发起举报请求,然后服务器再搜集模拟被举报者的行为证据,进行针对性的验证和惩罚。但这种民不举官不究的做法,很容易被有意识的互刷所利用。这种方案有一定的漏报几率,因此往往是作为其他几种验证机制的后备机制,一起使用。

以上四种,在腾讯的游戏中,往往都是结合起来使用。在实时对战游戏中,我们除了要关注验证的准确性外,同时还需要平衡游戏体验。因此往往需要在很多地方做妥协,但是只要我们有足够多的手段复合使用,真正的漏网之鱼还是很少的。

版本更新问题

手机游戏的版本更新问题由来已久,让用户升级手机上的程序是非常不容易的。经常会出现以下问题:

  • 手机内存小,更新的过程较容易崩溃;

  • 移动设备的网络环境很不稳定。经常下载到一半,用户走出了wifi范围或者进了电梯,网络中断了。

  • 应用商店的版本审核。什么时候能审核通过往往不能预测,对于紧急的BUG来说更是远水救不了近火。

然而,实时对战游戏由于强调竞技性,所以玩法逻辑常常需要进行小的调整优化。并且实时对战的玩法内容需要持续更新,所以经常都需要更新很多程序,在现有的条件下,如果只是简单的按部就班发版本,估计玩家早就跑光了。

从一些自研游戏发版本时的运营数据来看,如果在游戏内进行资源更新,可以做到99.5%以上的成功率的。但是,如果要发布一个程序包版本的更新,成功率往往就会跌至90%以下。

所以每次发布版本,一些游戏的在线人数会下降10%,这对于游戏运营来说,是一个巨大而持久的损失。因此,热更新技术是现在的主流版本更新方式。把程序代码,以脚本来编写,然后使用一个优秀的脚本解析器来运行,就能让程序代码以文本资源的形式,和图片、声音等其他游戏资源一样更新下载了。

我们自己开发了一个xLua执行库,这个库能在Unity3D引擎中运行lua脚本,并且其执行的效率非常高,还能无缝的在脚本中调用游戏引擎的API。这样,我们就可以尽量少的发布新的程序版本,大部分的游戏内容玩法调整,都使用lua脚本更新来实现。

由于使用了资源更新的方式来更新游戏,现在游戏的更新成功率普遍可以达到99.8%左右,并且避免了应用商店的审核,使iOS和Android用户同时玩上游戏的最新版本。

玩家实时沟通

在传统的端游中,玩家在游戏过程中往往会通过键盘打字沟通。后来有一些第三方语音聊天软件,充当了游戏过程中实时沟通的工具。在实时对战的游戏中,和队友的配合往往是游戏的重要乐趣来源,因此实时的沟通非常重要。

所谓的“开黑”,就是表示一个沟通良好的游戏伙伴小组,一起和其他玩家对战,顺畅的沟通能带给玩家巨大的竞技优势。然而,在手机游戏中,屏幕一般都比较小,不可能有空间来让玩家打字输入,况且如此激烈的实时战斗,也没有时间去慢慢的打字。因此自然很多人想到像PC上一样,运行一些实时聊天的语音软件,来辅助游戏沟通。

但是手机操作系统和Windows不一样,在手机上运行的后台软件,除了会严重降低手机运行性能外,还可能被操作系统暂停和关闭。所以游戏+语音工具的路子是走不通的。这时,就需要游戏开发团队,为玩家在游戏中,直接提供实时语音的服务。

 

腾讯自研的两款大作《王者荣耀》、《穿越火线手游》为了改善玩家在PVP对战时的沟通体验,率先使用了腾讯内部的实时游戏语音服务。从上线后玩家反馈的效果来看,这一功能对维持用户活跃非常有价值。

从运营统计数据来分析,有30%的玩家会主动说话,每人单局的语音会超过30秒,累计用过语音的玩家超过85%——这些数据都说明了语音服务是实时对战游戏玩家需要的功能。所以腾讯后续在所有32款对战游戏中,都加入了游戏实时语音服务。后面腾讯也会开放出这一技术为所有游戏开发者服务。

结束语

实时对战游戏的核心技术难点,主要是解决数据同步问题及弱网络下玩家的游戏体验优化。没有一款通用模型可以用于所有游戏,根据自己游戏的模型,设计出合理的游戏架构,才能让游戏的PVP体验趋于完美。

 

转载自: http://mp.weixin.qq.com/s?__biz=MjM5MDI5MjAyMA==&mid=402528028&idx=1&sn=50b90cadc10d545865ebd6897fc6a6c0&scene=23&srcid=03191karOzdEnKKkG78DqeSR#rd