by AKara 2010-09-07 @ http://blog.csdn.net/akara @ akaras(at)163.com
---------------------------------------------------------------------
和MMORPG不同，实时动作型网络游戏 追求操作的响应要求极高(<150ms)。
动作型网络游戏的制作人希望做到单机游戏的体验，网络游戏的服务。
网络指令在多客户端间的同步算法，从原理上来说，围绕两种特性的取舍而定：
* 牺牲局部实时性 ：某程度的互等待，保证各客户端间指令集在指定时间段一致。
* 牺牲局部一致性 ：容许客户端本机先行模拟，等待后续指令到达纠正。(DR)
网络的存在导致鱼与熊掌不可兼得，所以现在市面上的动作网络游戏都有
如下的妥协和折衷实现：
* 在客户端本机上算大量关键运算来保证手感
* 玩法上对直接进行的决定性互动的要求不高
* 接受时不时网络延迟导致等待的缺点来维持复杂精确的玩法
* 策划维持可玩性的底线下对一些一致性的要求求减低
实时性需求非常高的网络游戏，舍是一种关键艺术。
FPS，赛车，RTS，泡泡堂/QQ堂，模拟器联网等类型的网络游戏在一定程度上
都有以上的一个或多个取舍抉择。
---------------------------------------------------------------------
在很多实时同步的网络游戏中，都用到UDP而不是MMORPG中的TCP进行
非关键消息的同步(更有些赛车类型的游戏可能直接起用p2p网络互联)：
非关键消息允许丢包，可对物体状态做客户端预测补偿；UDP甚至可方便地穿墙；
所以UDP比TCP在这种情况下更合适。Dead Reckoning是常用的客户端
预测的技术，而更细节的客户端预测对不同类型的游戏而言有不同的扩展。
这方面的技术在之前的HalfLife / Quake3 / CounterStrike等UDP中心
服务器做动作认证的FPS游戏中应用得比较成熟。
虽然觉得真正的p2p网状互联的动作同步不适合网游(一致性和防外挂考虑)，
但观察了几个游戏后发现泡泡堂，跑跑卡丁车，QQ飞车，名将三国等一些游戏
确实不同程度上使用网状p2p(有些在公共场景组队就启用p2p进行位置同步)，
而且有些的收发包分别都达到20个/秒的量，几乎赶上渲染帧率的一半。
直观的猜想是它们玩家间动作显示上具实时性，但关键交互结果是不具实时性的。
而道具的使用大部分都提倡 范围化 和 时延化 ，以减少网络延迟的影响。
这样可以简单地提高udp发包频率和数量，客户端尽情模拟后拉扯：
如果大家不作弊，如果平均每秒接到的包够多，简单插值和预测一下自然很平滑。
而关键的属性改变，战场物品掉落，死亡，胜利等，则用非实时的中心服务器
信息保证保证结果唯一性。
虽然如此，还是觉得p2p的体系应该有一定的peer间同步法则。
之前没了解过p2p体系的同步知识，所以先查阅了一些比较容易找到的paper，
所描述的分布式状态同步算法大致有如下几种。
---------------------------------------------------------------------
Lockstep Synchronization
最直观同步方案：任何peer的action要得到其他所有peer的同意才能发起。
见下图：
如果使用非网状的p2p模型，提供peer master来做统一状态运算，
那lockstep模型便成为严格的帧同步模型，这是大多RTS，模拟器联网，
以及一些提供建主机后连接的休闲动作游戏采用的同步模型；通过频繁
对时，便可以像编写串行单机指令一样来进行多个peer的事件指令同步。
lockstep原是*用语，指犯人列队步行时的同步串链式行进，非常形象。
最初并非设计用于游戏，而是军方的军事互动仿真程序。IEEE DIS标准指出：
100-300ms的双程总延时，对军事性互动仿真模拟是可接受的。而根据一些统计，
第一人称射击游戏中的玩家双程延迟普遍在50-300ms的区间内。
而如果玩家都在一个LAN内进行p2p连接通信，双程延迟可能控制在20ms以内。
优点：简单易实现，不会出现任何的不一致性。
在延迟小(round-trip < 100ms)且稳定的环境下非常合适。
在实时性要求不高的玩法(比如回合制玩法)中也非常合适。
缺点：游戏节奏受最慢的peer影响巨大。一人卡机，所有人受影响。
恶意的peer可以用伪造大延迟的方式来获得好处，从而破坏游戏公平性。
---------------------------------------------------------------------
Bucket Synchronization
见下图：
原paper很长，这里只按照个人理解编排步骤：
(原文是彻底分布式的网状p2p，为方便理解，下面将player B称为peer master，
并假设它负责对时任务，以省掉NTP对时系统的理解过程)
1. 设定最大容忍延迟值为 PlayoutDelay(如120ms)。
PlayoutDelay为：peer master执行指令N的时刻 - 远程peer的指令N发出时刻所对应的bucket时间段起始时间
2. 设定游戏时间轴上每隔BucketFrequency(如40ms)归一个新bucket来存放动作指令。
3. 开始游戏前，peer master发送对时命令给所有peer进行对时。
4. 因为peer master知道所有peer的平均延迟 AvgLag，那它执行步骤3后，
延迟 AvgLag 时间后，开始游戏逻辑。
5. peer master自身发出的操作指令，虽然不需要经过网络，但也需要强行延迟
投递到Ti对应的bucket中，其中：
Ti = 当前时刻所属bucket时间段的起始时间 + PlayoutDelay
6. 如果peer master接到一个动作指令，但：
peer master当前时间 - 动作指令携带的发送时间 > PlayoutDelay
那peer master会直接丢弃这个动作指令(也就是将超时到达的指令当作无效)
7. 如果peer master接到的动作指令不超过上述6中描述的范围，那会把这个指令
放入Ti所对应的bucket中，其中：
Ti = 指令包携带的发送时间戳所在的bucket时间段起始时间 + PlayoutDelay
8. 每个bucket对应的时间段末端，peer master执行这个bucket中所有的指令，
将结果状态更新到画面。
9. 因为有网络的存在，可能某些bucket中没有指令，原版MiMaze游戏实现是不处理。
但paper中提供了基于Dead Reckoning的预测状态显示方法。
10. 游戏过程中，peer master以某种时间间隔作频率进行各peer对时，
保证将各peer机器时间的误差控制在一个可接受范围内。
优点：不依赖最慢peer来决定游戏流畅度。流畅度是维持在平均预定义水平的。
缺点：对超过MaxLag的指令做丢弃。除了原paper中的3D吃豆人迷宫式游戏这种
经过特殊剪裁的游戏，动作游戏对延迟玩家的操作做丢弃，似乎很难想象。
---------------------------------------------------------------------
TimeWrap Synchronization
它是一个基于某些状态支持回滚(rollback)的同步算法。有点类似HL的做法。
简言之，就是对每个操作指令的执行后保存一个状态快照(snapshot)，
各个peer按照自己的预测先行显示，但在发生一致性冲突的情况下，
回滚到上一个状态，并重新将指令序列在基于回滚后的快照的基础上再
执行一次，以获得正确的当前状态。
---------------------------------------------------------------------
Trailing State Synchronization
对TimeWrap Synchronization的一种改进。TimeWrap方案中建立snapshot是
以指令数量(1或少量几个指令)间隔为单位；而TSS方案则以某种延迟值(100ms)
间隔为单位对游戏做snapshot(比如100ms前做一个，200ms前做一个...)。
当发生一致性冲突时，寻找最远需要开始计算的snapshot，并将该snapshot到
现在为止的时间内的指令重新执行，得到正确的最新状态。
---------------------------------------------------------------------
参考文章：
<<Minimization of Latency in Cheat-Proof Real-Time Gaming by Trusting Time-Stamp Servers>>
<<End-to-end transmission control mechanisms for multiparty interactive applicatins on the Internet>>
<<Dead Reckoning: Latency Hiding for Networked Games>>
<<An Efficient Synchronization Mechanism for Mirrored Game Architectures>>
---------------------------------------------------------------------