0
0

lockstep 网络游戏同步方案

云风 发表于 2018年08月31日 11:27 | Hits: 606
Tag: 游戏开发

今天想写写这个话题是因为上周我们一个 MOBA 项目抱怨 skynet 的定时器精度只有 10ms (100Hz),无法满足他们项目 “帧同步” 的需求。他们表示他们的项目需要服务器精确的按 66ms 的周期向客户端推送数据,而 skynet 只能以 60ms 或 70ms 的周期触发事件,这影响了游戏的“手感” 。

讨论下来,我认为,这是对所谓“帧同步” 算法有什么误解。我们客户端运行时不应该依赖服务器的准时推送消息才能得到(手感)正确的结果。虽然在 skynet 下你可以写个服务代替底层提供的 timer 来更准确的按 15Hz 发出心跳消息,但我觉得服务器依赖时钟的精确是游戏设计上的错误,提供 “手感” 完全应该是客户端程序的责任。

这篇 blog 就来写写基于 lockstep 的网络游戏同步方案到底是怎么回事。

首先,我认为把 lockstep 翻译成帧同步,还有与之对应的所谓“状态同步” (我在多次面试中听过这个名词),都是对同步算法的错误理解造成的。把自己所理解的算法牵强附会到已有的在欧美游戏先行者中经过实践的方案上。

btw, 前几天和几位做区块链的同学吃饭,饭局上他们对国内区块链社区中名词混乱也是吐槽不已。说是国内流传颇广的中本聪比特币论文的翻译文本中,把 Transaction 错误翻译为交易,导致了众多不看原文的从业技术人概念混乱,对一些概念做有歧义的解读,结果在国内技术社区内简直无法交流。

我更愿意用 lockstep 的本意来翻译这个名词:锁定步进算法。这个术语是从军事语境引入的,用来表示齐步行军,也就是那种阅兵时的阵列,队伍中的所有人都执行一致的动作步伐;对比到机器,就是让网络上所有的机器都同时执行一样的操作,得到一样的结果。执行 lockstep 同步时,其实和时间是无关的,只和动作一致性有关。相信很多同学都参加过军训,经历过苦难的队列练习。训练时枯燥的摆 pose ,一步一步的队列同步,都是相当缓慢的,直到最后才依据哨声或口号进行有节奏的集体行动。

网络游戏发展到今天,从局域网游戏到互联网游戏,其实已经没有再使用纯粹的 lockstep 同步算法了。各个基于 lockstep 的项目都加入了很多细节改进来解决网络波动延迟等问题。本文不想深入讨论这些改进的细节,只想谈一下最基本的 lockstep 是怎样实现的。搞清楚基本原理后,相信每个人都会有很多改进的想法。

lockstep 最早是用于局域网 RTS 游戏的。局域网环境下不用太考虑网络干扰的因素,只用知道网络传输是需要时间的,无法像单机多人游戏环境中,多方可以直接用共享内存状态的方式实时同步。它的朴素想法是用最简单的方式,保证多台机器表现出完全一致的游戏状态即可。

能直接想到的方法就是把实时游戏还原成回合模式,参加游戏的所有玩家都在进行一个一个的回合操作,在每个回合中,大家相互不干扰的下达指令,然后一起亮出自己做了什么操作,接着依据所有人的操作在游戏中进行沙盘推演。这就好比两个人下棋,不像围棋那样你下一手,我再针对你的这手棋应一手;而更像桌游中常见的减少 downtime 的另一种模式,每个人都同时考虑这个回合我要做什么,把指令暗放在沙盘上,等所有人都操作完毕后,规则再自动推演。

1959 年设计的模拟一战的桌面游戏 Diplomacy 就是典型的这种规则(没玩过的同学强烈推荐试一下,有网络版);新一点有权利的游戏版图版也差不多。

为什么我们不觉得星际/横扫千军这类基于 lockstep 算法的 RTS 游戏没有回合感呢?诀窍在于这个内在的回合非常短。我在网上找到一片介绍 Supreme Commander ,横扫千军的精神续作,同步算法的文章:Synchronous RTS Engines And A Tale of Desyncs,它谈到游戏中的实际运算周期,也就是 simulation layer 只有 10 fps ,是远低于用户交互表现层帧率的。

我们可以这样理解,所有玩家都可以在 user layer 下达操作指令,但并不会立刻运行,而是提交到沙盘的指令队列上。在没有服务器时,则将操作以 p2p 方式同步给所有玩家,相当于所有玩家机器上都运行有一个游戏沙盘。沙盘收集完每个回合所有玩家的操作指令后,就向前推演一步。

注意,和桌游一样,不行动也是一种操作,即,每个回合都必须严格收集到所有玩家的操作才能推进。至少在局域网中,收集和同步这些操作指令是非常快的。每个玩家在当前回合中可以做的多个指令被打包认为是一个操作(也就是一个回合并不限制只能操作移动一个单位,和 Diplomacy 一样,你可以操作你拥有的所有单位,只要操作不违反游戏本身的规则),然后转发给所有其它玩家;如果有一个中心服务器,则是发给服务器,再由服务器广播给所有人;这个轮回可以远小于 100ms 。而在一个回合结束时刻,沙盘收集到了所有的操作,按规则推演即可。

在表现层,沙盘(也就是每个玩家的客户端程序),可以做足够平滑的动画拟合,正在行军的单位不会因为 100ms 的间隔而间隙停顿,玩家也就不觉得他们在经历一个个不连续的回合了。

我们可以看到,在这个过程中,时间(100ms)对同步过程没有任何关系。只有收集完所有玩家当前回合的操作指令后,沙盘才会推演。正如我们在桌面玩 Diplomacy 时,一个回合吵上一个小时也是正常的,大家都认可我的行动确定了,才翻牌看看到底这个回合发生了什么。

和桌面游戏一样,无限拖延回合行动时间会极大的影响游戏的流畅度。我们不希望开一局 Diplomacy 玩上 8 个小时还无法结束,所以我们会限制每个玩家的决策时间。如果超过大家商定的时间还无法决策就认为你其实是按兵不动。这个时间在桌面游戏中可能是 10 分钟,在 RTS 中就是 100ms 。如果你在这个 100ms 中还没有操作,就认为你当前回合不想操作了。通常我们会考虑网络延迟,把截止时刻放在执行时刻前一点,保证所有人有收到指令的缓冲时间,让客户端能流畅表现。

如果去掉这个回合时间限制,我们来看 RTS ,如果一局游戏整个时长是 10 分钟,以 10Hz 为回合周期,其实一局游戏就是 6000 个回合。按规则,每个人都必须提交 6000 个操作。所以理论上,你以什么频率去提交这 6000 个操作都无所谓,只要每个操作都是合法的即可。如果沙盘推演的时候可以合法的忽略掉无法执行的操作(比如你试图指挥一个已经死掉的单位行动),那么在多人游戏中,每个人机器上都循序执行这 6000 个操作,就可以得到完全确定的结果。

抽象的看一局 8 人参加的 10 分钟 RTS ,就是收集到 6000 组,每组 8 人的操作指令,就得到了这局游戏的确定性结果。这个确定性和每个人每个操作的提交时间是无关的。

但现实中,玩家需要从前面的操作对沙盘推演后的中间状态做出判断,才能做出后续的正确决策,提前发出操作指令是没有任何好处的。而沙盘只有收集到当前回合需要的 8 个操作指令才能向后步进( step )一下,如果有人延迟提交,那么反应在游戏中就是其他人的客户端会卡住等待。这就是我们打星际网络不好时,弹出一个等待框等待某个网络出问题的玩家遇到的情况。

那么,这和回合制游戏的区别又在哪里呢?区别在于,实时游戏虽然内在被分为若干回合,但是和玩家的人机交互上并没有明确的提交一个回合结束的操作。实现(让玩家感觉平滑)的难点也往往在如何确定玩家当前回合的操作是不是做完了。

在 RTS 中,往往允许一个玩家指挥多个单位,手速快的玩家就可以做到单个回合发布多个操作指令。沙盘的推演是等一个回合结束才开始的;如果玩家操作一个单位就算结束的话,那么对下一个单位的操作的执行势必推迟到下个回合(至少延迟 100ms)。但是如果等满 100ms 才汇总过去 100ms 的操作打包成一个回合的指令也会带来问题:最坏情况下,发出一个操作,要最多在本地等待 100ms 然后发出指令,等待回合结束,那么总的操作延迟最大变为 100+n ms ,n 是网络延迟。

但 RTS 游戏在交互上又和回合制游戏有所不同,它不准取消已发出的指令。对于操作单位比较少的 MOBA 类游戏我们又可以这样设计:如果我们已对自己可操作单位下达完指令,无论回合时间有没有到,都认为自己当前回合的操作已经结束。若是一个单位可以有多个技能可以选择时,只需要在规则上给技能加上公共 CD 时间,即释放一个技能后,在一定时间内不准释放下一个技能;这样就从规则上禁止了同一个回合内释放多个技能。

由于玩家不需要明确的下达 idle 一个回合的指令,通常 idle 这种不操作是用超时机制自动触发的。我们一般把 idle 指令的自动执行时刻点放在上一个回合结束时刻点后延大约半个回合周期即可。这个时间点不必特别精确。假设是 50ms ,那么在收到上个回合的信息,推演出沙盘的下个步骤 50ms 后,如果从最后一个发出的指令到这一刻,这段时间内没有操作,就发出 idle 操作。

这样,下一个操作的执行延迟最长就是 150ms :因为如果你在 idle 操作发出后立刻做了一个操作,那么必须等 50 ms ,沙盘向前推进一步(你的操作是 idle ),然后再等 100ms ,你这个操作才被确认执行。

针对传统的 lockstep 算法,通常是这样实现的:设定一个逻辑周期,通常是 100ms ,和渲染表现层分开。

玩家在客户端的操作会被延迟确认。我们可以给没有操作设定延迟时长,从 0 到 50ms (一半的回合周期)。当收到回合确认同步信息(即所有玩家当前回合的操作指令)后,找到指令队列中延迟时间最短的那个时间,设置超时时长。超时后,把指令队列作为下个回合的操作指令打包发出。

如果至少有一个 0 操作延迟的动作,那么就会在收到上个回合确认后,立刻发出。如果没有任何操作,那么最多会再等待 50ms 发出一个 idle 操作作为当前回合的操作指令。

这个 10Hz 的逻辑周期,并不是由收到网络信息包驱动的,而是采用客户端内在的时钟稳定按 100ms 的心跳步进。网络正常的情况下,客户端会在逻辑心跳的时刻点之前就收到了所有其它玩家当前回合的操作指令;因为如果玩家在频繁交互,大部分动作都是 0 延迟的,会在上个回合时刻点就发出了;如果玩家没有操作,也会在 50ms 前发出操作;在网络单向延迟 50 ms ( ping 值 100ms)之下,是一定能提前获知下个回合沙盘要如何推演的。

也就是说,若网络条件良好,每当逻辑周期心跳的那一刻,我们已经知道了所有人会做些什么。在逻辑层下,沙盘上所有单位都是离散运动的;我们确定知道在这个时刻,沙盘上的所有单位处于什么状态:在什么位置、什么移动速度、处于什么状态中…… 。对于表现层,只需要插值模拟逻辑确定的时刻点之间,把两个离散状态变为一个连续状态,单位的运动看起来平滑。

当网络条件不好时,我们也可以想一些办法尽可能地让表现层平滑。例如,在下个回合的逻辑时刻点 20ms 之前再检查一次有没有收齐数据,如果没有,就减慢表现层的时间,推迟下个逻辑时刻点。玩家看起来本地的表现变慢了,但是并没有卡住。如果网络状态转好,又可以加快时钟赶上。

如果实在是无法收到回合操作指令,最粗暴且有效的方法是直接弹出一个对话框,让本地游戏暂停等待。当同步正常(也就是收到了那个网络不好的玩家上个回合的操作指令后),再继续。如果玩家掉线或网络状态差到无法正常游戏而被踢下线,那么则可以在规则上让系统接管这个玩家,然后让剩下的玩家继续,之后的回合不再等待这个玩家的操作指令。

从上面的描述我们可以清楚的看到,lockstep 的核心其实是按回合锁定游戏进程,逐步推演。时钟周期对游戏规则其实并不重要,超时机制的存在是客户端用来解决如何确定当前回合要提交的多少操作而设定的;而模拟层的心跳周期则影响了表现层如何把离散状态拟合成连续状态。

那么,基于 lockstep 的同步方案一定要基于每个客户端计算操作,通过这些操作达到完全一致状态么?

并不是。

基于操作和对操作的一致性计算,达到每个客户端有一致的结果;这种实现方法仅仅只是因为早期的 RTS 游戏没有中心服务器,且操作本身的占用带宽比较小而已。

如果我们有一个权威主机,所有客户端把操作发往这个主机,由它来计算,然后把当前回合的计算结果:沙盘上每个单位的状态变化广播给所有客户端,一样可以得到一致的结果。算法还是基于 lockstep 的,仅仅只是传输的数据不同。客户端没有收到下一个 step 的状态前,依然不能推进游戏进程。区别在于,客户端收到了其他人的操作,自己演算这些操作引起的后果;还是信任权威服务器算好的结果。

这两者的区别已经和 lockstep 算法无关了。两种方法,玩家都不能对规则作弊。每个操作时序都是确定的,即每个回合你做了什么似无法抵赖的。基于操作的演算,你无法把一次攻击操作对敌人造成的伤害从 100 改成 1000 造成对手死亡;因为其他玩家会认为你的运算结果和他们的不一致,造成游戏无法推演下去;这种不一致发生时,大家如何知晓?一般的做法是每个人的客户端同时计算出每个回合的所有单位的状态的一个 hash 值,如果发现自己算的和别人的不一致,就表示不一致。如果没有修改客户端的话,这一版是客户端本身的 bug 造成的。对于基于权威服务器的演算,客户端只有表现结果的职责,更无法改变结果。

不过,基于操作一致性演算的方案,前提是要保证这些操作在每台设备上从上一个状态计算到下一个状态必须是完全一致的,这样才不会让玩家玩的时候看到的沙盘状态差之毫厘失之千里。这也必须让每个客户端拥有完整的沙盘信息。如果游戏规则有战争迷雾的话,虽然按规则,玩家不可以看到迷雾中的敌方单位,但是沙盘演算又无法缺失这些信息,所以实质上,迷雾中的敌方单位运动每个客户端都是可知的。玩家想作弊的话,可以轻易的在自己的客户端上打开所有迷雾。

如果采用单个权威服务器运算的方法,这个服务器知道所有玩家可以看到哪些单位不可以看到哪些单位的行为;它在每个回合广播状态时,就可以有选择的只通知那些可知信息,就能解决战争迷雾作弊问题。

这种方式的缺点是,服务器运算负担较大,且对带宽要求更高。不像前者,即使设立一个中心服务器,也仅仅做一些转发操作的工作就够了。

和 lockstep 对应的同步方式是什么呢?我认为核心点在于要不要 lock 。

就是客户端表现的时候,是否必须收集齐所有玩家的回合指令才允许向后推延。多数 MMORPG 就没有那么严格的一致性要求。服务器只需要在游戏沙盘变化后,把新的状态同步给客户端,为了减少带宽要求,这个同步频率也不必严格限制为固定周期。而客户端则不用严格等待服务器的步进,无论服务器有没有新的状态下发,也自行推测(或不推测,保留前一个状态)和模拟游戏沙盘。当服务器下发新状态时,修正客户端的表现即可。

如同本文最前所述,现在已经没有太多网络游戏遵循严格意义的 lockstep 同步来实施了。一般都可能针对网络波动和延迟做一些优化。最终很可能会是一个杂合方案。

例如,你可以做这样一个优化来解决网络不稳定的问题:让权威服务器有权利自行做无操作超时,而不必等待客户端发出超时 idle 指令。

即,如果服务器超过一段时间没有收到某个客户端发过来的指令,就认为它当前回合不操作,并打包整个回合所有玩家指令(或指令计算后的状态结果)广播;如果事后这个客户端的操作晚到,扔掉即可。这样就不会因为有人突然网络断开连接无法发出当前回合的指令,而让所有人都卡住。

但对应的客户端就要做一些处理,不可以认为自己发出的指令一定会被执行,而是以服务器下发的为准。发现自己的指令被取消,就做一些弥补:有些可以自动重发,有些则明确在交互界面上通知玩家。

对于格斗游戏那种,逻辑帧率很高的游戏类别,如何基于 lockstep 做同步?

以我玩的比较多的 DOA 为例,它的内在帧率是 60fps 。这类游戏都有明确的出招帧率表,DOA5LR 甚至在训练模式都明确标出来。

如果按传统的 lockstep ,每个逻辑帧都需要双方确认才能继续,那么在互联网上肯定运行不了。受光速所限,在一定距离外,互联网物理上就无法保证 16ms 的 ping 值。16 ms 只够光信号在 2400 km 的距离上跑一个来回,这个距离在地球表面轻易可以超过。

所以格斗游戏每个招式都有起手时间和恢复时间。比如以 DOA 里霞的 P (拳为例) 这个属于比较快的招式,它的帧数为 9(2)13 ,就是起手有 9 frame ,有 2 frame 的击中判定,然后有 13 frame 的恢复时间无法发出新招。这个 9 frame 在 60fps 下就是 150ms 足够应付一般的网络延迟了。

我们可以这样看,你在 DOA 里所发出的任何技能动作,这个动作是否可以发生,是由前述某个 frame 所决定的。而这个动作在击中判定时是否有击中,同样也是前述某 frame 的确定状态所确定了。

假设我们允许 9 frames 也就是 150ms 的最大延迟,那么本地客户端只需要确定当前帧向过去 9 frame 的对方状态,就能知道现在的呈现 frame 的交互结果。例如本地渲染在第 100 frame ,这个时候,我输入了一个技能,如果确定的逻辑 frame (即对手反馈回来的他的 frame ),只要在 91 frame 之后,我都能知道我当前的输入是否成功。如果可以输入这个招式,我的本地只要马上表现我操作的角色做对应的动作就可以了,这样就能保证手感。而对手,可以根据已确认的过去某帧的状态去猜测现在的状态;多数情况下是准确的,因为实际上格斗游戏你来我往的交互节奏并不高。客户端还可以根据接下来收到的对手的操作,不断地修正画面。也就是在网络对战时,客户端其实同时在计算两个状态,一个根据已经收到的对手的操作,算出一个过去的确定状态,一个是根据过去的状态推演出的当前的状态。

所谓手感,就是让我操作的角色立刻反应出我刚刚的操作,根据游戏规则,我当下能做出的操作是由过去一个时刻敌我状态所能决定的,所以一旦符合规则,那么动作一定可以发出;所以不会有事后发生歧义需要回滚的情况。而对手在我的显示器上的画面呈现,在招式起手阶段是滞后于真实情况的,但会随着时间推移而迅速弥补上。

如果网络状态不好,可能发生的情况就是当前的画面进度超出了逻辑确定帧能确保的范围,那么客户端就可以零界点快到时,开始降低渲染帧率,看起来就是在放慢动作;极端情况下让画面静止卡住等待。

总之,整个游戏的每一帧游戏画面,对于我方控制的角色,状态是一直确定的,敌方是不断跟进模拟的;但对于整个游戏进程来说,每一帧的双方状态都是确定的,只不过这个确定状态并非实时表现在画面上。画面有所超前。

对于格斗游戏来说,一局 3 分钟,60fps ,也就是双方各提供 10800 个操作,只要保证每个操作都是规则下有效的,那么就一定能得到每一帧确定的结果。

为什么服务器的 timer 精度对游戏的表现没有影响?

这是因为,如果是无权威服务器结构,即使有一个中心服务器,它的职责也仅仅是负责转发每个客户端的操作序列,无关时间。收到即转发。

如果是权威服务器结构,那么服务器保证的是在一个较长时间段内执行了固定次数的逻辑帧即可,这些逻辑帧是在什么时刻执行的并不那么重要。因为 lockstep 同步要的是准确的状态序列,客户端利用这个序列呈现每个 step 的画面。流畅度是由客户端时钟保证的,而非由服务器推送的包驱动。影响服务器的包抵达的时刻的因素很多,有服务器内部处理的时刻,也有网络传输因素。甚至,抛开网络不谈,即使是单机游戏,从 CPU 处理数据到液晶屏上显示出来,其精度误差也可能超过 10ms (液晶屏的刷新率为 60 Hz ),保证业务处理时刻的时间准确性在 10ms 以下是没有太大意义的。

保证手感这件事,只有在客户端用一个精确的时钟去控制,服务器尽可能的保证在这个时刻到达前,当前 step 的数据推送到,而客户端精准的在这个时刻处理,并拟合呈现层的画面,才能确保客户端的流畅。

权威服务器若有额外逻辑,比如 MOBA 战场上指挥一些 NPC 单位,这些额外的操作也应该用 frame 来驱动,而非时钟。即,要实现成在第 300 frame 时刷出一个 NPC ,而不能实现成在第 30 秒时刷出一个 NPC 。服务器大致保证一秒步进 10 个 frame 就够了,而不需要精确的保证这些 frame 在准确的时刻发生。对于游戏规则来说,只有每个 frame 发生了什么,而和真实时间是完全解耦的。

客户端只需要把逻辑帧略微向服务器时刻之后 shift 很短一点时间,在网络通畅时,完全能保证在每个逻辑帧抵达之前就收到了服务器下发的信号。即使是上面 60fps 的格斗游戏类别也不例外。

原文链接: https://blog.codingnow.com/2018/08/lockstep.html

0     0

评价列表(0)