MMOG网络同步算法揭秘（QQ幻想）

sea_bug

概述

　　游戏发展从单机游戏到局域网游戏再到mmog（Massive multiplayer online game， 即大型多人在线游戏），越来越强调玩家之间的互动。mmog形成互动的前提是游戏中的所有玩家认为他们是在同一个游戏世界中，然而这个同一个游戏世界真的存在吗？答案是否定的，实际上，从不同的维度看，mmog中存在3种不同世界：

　　真实世界，也就是mmog服务器推演的游戏世界；

　　玩家自己的世界，是真实世界在玩家自己角度的一个映射；

　　其他玩家的世界，也就是真实世界在其他玩家角度的一个映射。

　　连接这3种世界的就是网络，如何通过网络同步这些世界之间的数据？网络存在延时，每个用户的上行/下行带宽有限制，服务器端和客户端计算资源有限，不同mmog类型对于网络同步的要求也是不一样的（例如FPS类型的mmog要求延时尽量短），总之，我们应该根据限制条件和不同mmog类型的特点选择合适的网络同步算法。

　　QQ幻想是腾讯自主研发的第一款Q版2D即时MMOG，公测时最高同时在线用户数达到66万，是国内非常优秀的一款资源MMOG。本文讨论QQ幻想网络同步相关思路和算法。

网络同步基本算法

　　MMOG网络同步需要考虑玩家及NPC移动信息同步、视野信息同步及其他状态信息同步，这些信息同步中以移动同步设计最为关键。

设计要点

　　客户端发出移动请求并附带寻路信息；

　　客户端发出移动请求的同时，自己立即移动所控制的玩家；

　　服务器验证路径信息，如果合法则合并存储路径并将路径转发给视野中的其他相关玩家，如果不合法则返回移动位置矫正消息给客户端将其拉扯到server所认为的位置；



　　玩家的移动速度由服务器控制并通知给相关玩家；

　　服务器每隔一定时间按照所存储的路径和玩家当前速度以及最后一次移动的时间改变其位置；

　　在一些特定处理时，例如移动速度改变、与距离相关的操作等，服务器立即计算并改变玩家的位置。

　　客户端和服务器之间存在网络延时，为解决网络延时带来的同步问题，QQ幻想中引入了移动消息序列号和路径补偿机制。

移动消息序列号机制

　　当服务器的位置调整协议还没有到达客户端时，网络上仍然有客户端发过来的移动请求消息，而影响服务器逻辑处理。在QQ幻想中通过每个移动同步消息携带一个序列号来解决此问题

　　服务器发送位置调整协议后，会将接收序列号做个较大幅度的变更，此后收到的移动请求消息如果序列号不同步则直接丢弃；

　　位置调整协议消息会带有调整后的序列号，这样客户端收到后也更新自己的移动起始序列号。

路径补偿机制

　　由于客户端和服务器之间存在网络延时，当服务器收到客户端请求包验证通过后进行路径合并时，有两种情况：



　　假设黑线段是服务器存储的上一次路径，绿线段是最新收到的路径信息，在原路径的(x1,y1)上改变路径。第一种情况是服务器上玩家的位置在(x2,y2)，没有到达(x1,y1)，这时只需要把新的路径合并进来就可以。第二种情况就是服务器上玩家的位置在(x3,y3)，超过了(x1,y1)，这时需要把多行走的距离折算到新的路径上，这种情况指的就是服务器的路径补偿，当然补偿的距离应该用速度和时间的乘积计算更准确。

同步算法的改进

　　上述的移动同步算法并不是QQ幻想的最终版本，在中国存在多家网络服务提供商（ISP），跨ISP通信时，网络丢包率和延时都比较大；当玩家跨ISP进行游戏时，例如网通接入的用户在电信的服务器上进行游戏，由于则被服务器验证路径失败而导致的回扯现象特别严重。

　　这个问题主要的原因是当玩家跨ISP进行游戏时，我们发现在服务器端特别容易出现粘包现象：



　　在客户端虽然发送的移动请求有一定的时间间隔，在服务器端收到这个请求时由于网络延时或网络丢包，其间隔与客户端可能不一致。当服务器端只以收到消息包的时间作为请求发生的时间，进行条件判定时会导致一些问题。例如服务器端由于频率限制等原因默认有一个客户端的最小移动请求间隔，如果两个移动请求之间的间隔比这个间隔还小，则认为非法，发出位置调整协议消息调整客户端玩家的位置，出现回扯。

　　一种解决方式是增加客户端的参考时间戳。客户端的参考时间戳是指客户端发出请求时服务器端对应的映射时间，也就是说客户端角度的世界与服务器的真实世界应该存在一个时间上的映射关系，如果网络延时不变，客户端角度的世界t1时间发生的事件在服务器端真实世界发生的时间是t1'，则客户端角度的世界t1+Δt时间发生的事件在服务器端真实世界发生的时间是t1'+Δt。

　　那么，如何建立这个时间映射关系呢？一般采用的方式就是使用客户端和服务器之间的对时机制。也就是在客户端和服务器建立连接后，使用特殊的对时消息交互获取一个时间上的映射关系。

　　服务器会对客户端的参考时间戳进行检查，以解决一些同步相关外挂带来的安全问题，例如会检查这个时间戳必须是递增的，时间戳之间的间隔必须大于最小的请求间隔等等。

总结

　　网络同步是MMOG设计中非常关键的一环，同步设计中视野管理、带宽管理、安全性等问题本文限于篇幅没有逐一展开，抛砖引玉，希望能激发同行对此话题更多的交流和碰撞。

来自：腾讯大讲堂

gantleman

使用路径补偿？不敢苟同。这显然把简单问题复杂化。
对于服务器校验，客户端进入了不能进入的区域，
必然要触发强制措施，例如移动到主城，或判定死亡。
网络延迟，服务器预测客户端路径就更扯淡。
这个应该是每个单独的客户端单独预测其他客户端高速移动的物体。
服务器只存储一个相对较旧但确定的位置，
如果有事件被触发，例如对高速移动的物品释放技能。
服务器只要根据确定的位置和移动的速度得到一个估计的位置，
然后判断技能是否被集中即可。
我要没记错的话tcp协议根本不存在丢数据的问题。
这篇文章的作者对一些基础技术掌握存在盲区，
导致他会对一些根本不可能发生的事情过度担忧。
为了解决这些他过度担忧的问题，又扯进来一大坨其他的没必要的问题。

nut799

学习了，
看 提到使用了移动消息序列号机制 。那么qq幻想是使用了 udp而非 tcp协议咯？是这样子吗？因为tcp是可以保证发送序列的顺序的。

gantleman

好吧如果一开始就用udp相当于给自己挖了一个坑，
udp说白了就是一个ip协议简单封装，是否断线，封包是否完整，是否假冒，都要服务器和客户端再校验。
先要在udp的基础上封装一个和tcp一样可信任网络层，如果是这样的为什么不一开始就用tcp。
难道还很自信自己封装的东西比tcp还要安全可靠，那典型的就是在重复造轮子，跟自己写map,list是一个道理。

nut799: Re:MMOG网络同步算法揭秘（QQ幻想）

学习了，
看 提到使用了移动消息序列号机制 。那么qq幻想是使用了 udp而非 tcp协议咯？是这样子吗？因为tcp是可以保证发送序列的顺序的。

上线王

gantleman: Re: Re:MMOG网络同步算法揭秘（QQ幻想）

好吧如果一开始就用udp相当于给自己挖了一个坑，
udp说白了就是一个ip协议简单封装，是否断线，封包是否完...

前些年一个暴雪的开发团队请我去对一个游戏项目做评估,其中,对"用udp相当于给自己挖了一个坑"的观点感觉十分亲切 [em9]

ps:lz这个是自己写的吗?

nut799

这里有一篇文章 ，很有意思，Why you should never use TCP to network a multiplayer game.
http://gafferongames.com/networking-for-game-programmers/udp-vs-tcp/

gantleman

真的不需要知道过去一秒钟发生的事情吗？
过去一秒钟其他人给你丢了个**，在你这没有显示可能么？
我相信服务器发给客户端的包都是有用有的。
即使赛车类游戏还有轨迹同步的需求，也不可能每次把所有轨迹都同步发下去，
如果每次都是把开始到最新的轨迹都发送一次哪确实丢一两次包是没有问题。

nut799: Re:MMOG网络同步算法揭秘（QQ幻想）

这里有一篇文章 ，很有意思，Why you should never use TCP to network a multiplayer game.
http://gaff...

sjinny

nut799: Re:MMOG网络同步算法揭秘（QQ幻想）

这里有一篇文章 ，很有意思，Why you should never use TCP to network a multiplayer game.
http://gaff...

这个文章下面的评论里有一种观点我是认同的：
对于大多数网游来说，只要不是FPS，那么使用TCP是合适的，这里的合适是指综合考虑了收益和代价的。

gantleman

FPS别人打你一枪，包丢了，怎么办？
服务器判定你死亡，包丢了，怎么办？
任何有逻辑上下文关系的通信都不会容忍丢包吧？
反正，如果一个游戏可以容忍丢包，那服务器就是可有可无的，
如果服务器是可有可无哪就不是网游。
udp速度带来的那点收益完全可以忽略不计。

sjinny: Re: Re:MMOG网络同步算法揭秘（QQ幻想）


这个文章下面的评论里有一种观点我是认同的：
对于大多数网游来说，只要不是FPS，那么使用TCP是合适的，这里的合适是指综合考虑了收益和代价的。

nut799

继续讨论，周末了 ，放假：
文章里解释不使用tcp的最大原因是：当tcp发现有丢包的时候，就会停止发送数据，重新发送丢失的包，这样子当丢包 发生的时候，会导致数据敏感的包不能及时送达。这样子就影响了游戏的流畅性（用户感受上）
虽然使用udp,文章后面 描述了如何在udp上面封装一层机制，使之可信赖。在对方收到的包中包含有自己发送的包的id,
当觉察到丢包发生（后续收到的包中没有之前出去包成功的id）时，并不停止发送后面数据 ，而是将丢失的包 重新设id,重新发送。
所以 用udp是可以解决丢包问题的。