Character Movement Replication 角色位移同步

玩家2的视角看玩家1的移动是起伏一截一截，并且滞后的
interpolation：内插值，在两个旧的但已知的状态计算
extrapolation：外插值，本质是预测
内插值：但网络随着时间不停地给我信息包时，信息包可以不均匀（由于网络波动等因素），客户端可以根据给的时间将中间值插出来，保证平滑性。如用catmull曲线插值
做内插值时，从服务器来的数据包，要cache到内存，加上一些offset时间，这样在s1和s2之间插值时，有足够的时间等待s3
这样在客户端看到对方的移动是足够的平滑的。
内插值的延迟是会被加剧的
有个问题是，真正在移动的玩家1，如果做跑停跑停的状态，玩家2看到的玩家1可能会把停的状态smooth掉
人眼更倾向于连续的状态
内插值的问题：
1.加剧延迟
2.两个客户端看到的状态是严格不一样的。对于碰撞不敏感的个人移动游戏还可以接受，否则会出现双方产生不同的碰撞视觉效果

外插值：根据现在的速度，加速度，方向，预测未来一段时间，没有任何其他事情发生时，将会处于的位置
当收到一个网络包时，知道我现在已经跟真实状态不同时，如何校准。
如果与此时的网络包校准，追到时，实际上真实世界已经到了另一个状态。因此，要预判别人的动作

换气算法：
我发现我在点p，速度v，加速度a，在t0收到网络包，告知真实位置在p0，速度是v0，加速度a0。
经过一个固定时间tb，我的新的真实位置pb，等于当前的收到包告知的真实当前位置p0加上真实当前速度v0，加上真实当前加速度a0的时间平方的一半（牛顿第一第二定理）
此时客户端自身的移动预测轨迹是p，v，a确定的。次轨迹在tb时间后的预测位置是pt
此时需要一条曲线让客户端自身的移动预测位置pt能追上真实预测位置pb
需要对速度进行插值，在tb时间是，客户端速度v追上真实速度v0
同时对位置进行插值，如果没有收到新包时，自身的p，v本身也会收到自身的a影响，走到自身复制的pt位置（如上图红线），因为收到了新包，所以知道在t时间后会在新的真实pb位置（如上图绿线）。线性的在两个位置之间依次进行插值（如上图蓝线，即客户端真实展现的运动轨迹）

这样处理的好处在于，不会看到物体的位置瞬间变换，是逐步追上目标点的位置。并不符合动力学，实际就是对位置进行生硬的插值



碰撞问题：虽然可以检测到两辆车已经发生碰撞，但位置是外插值进来的，会发现车直接插进另一辆车里面。server发现两个刚体已经穿插时，很多物理引擎会给两个刚体一个很大的力来推开。导致实际上不是很重的碰撞直接弹飞了。
不同的游戏需要不同的策略

一个简单的思想：在客户端提前进行物理的检测，如果检测发生碰撞，会把位置同步的权利从网络同步和外插值的算法切换回物理引擎的算法。一段时间后再切回（如看门狗是1秒之后）。则在这1秒内完全交给本地的client的物理来结算。
有个问题是，因为输入的不同会导致不同客户端物理模拟的结果不同。这里面有很多很难的trick。
总结：做外插值时，需要考虑各种各样的边界情况
内插值：多用于fps，moba游戏。会应用在玩家会经常进行各种瞬移，或者突然有很大的加速度（注意，赛车这种其实加速度并不大，真正加速度大的是controller，即玩家自己。因为需要角色灵活有响应感。这实际上都是反物理的，几乎都是瞬移）。内插值相对比较稳定（外插可能看到其他人穿墙又来回，可以本地做物理检测解决）

外插值：适合整个运动符合物理学规律的，如开船开车的游戏

真实游戏里，可能会把两种算法结合到一起。在角色移动时，使用内插，保证安全性。上了载具后，又使用外插

Hit Registration 命中判定

难题1:敌人在哪。灰色真实位置，半透明是服务器位置，然后是客户端看到的位置

难点2:对方不停移动，怎样算打中。以及我看到对方在掩体外，但对方实际在掩体内
在一个网络不确定的环境下，让所有的客户端对是否命中目标达成共识（不是真实）
解决方法：
第一种，客户端决定，hit detection
第二种，服务器处理，hit-registration

客户端判定的游戏，大地图，许多玩家，如PUBG，非常动态非常复杂的世界（可以拆屋子，有大量破坏），如战地

就是一个hitscan，去扫描一下能否打中。
3种弹道：
1.速度无限快的直线，开枪的瞬间就判定直线位置
2.有飞行轨迹的直线
3.抛物线
客户端3种都行，只以本地看到的为准，非常准确，符合人的直觉。都是射击手感比较好的游戏

服务器会做一个验证，但是验证通常不会特别麻烦，客户端会发送开枪的位置，及击中的目标，击中的位置给服务器和服务器记录的自身的位置做验证，是否距离过远。如果符合距离，验证射击直线上是否有障碍物。
真实游戏，如守望先锋，服务器以受击者的位置（上图黄圈），周围红框的范围，只要打中这个box，就判定打中。除此还有一些其他的防外挂判定

如果选择客户端判定检测，服务器很多的校验只是做一些基本情况的验证。

优点：
1.高效，很多计算在客户端做完
2.准确
缺点：
1.非常不安全，客户端或者网络包被破解会有很多外挂
2.lag switches：客户端主动断开网络，则没有新的网络包接收，客户端的敌人就会暂时停住。此时射击敌人，然后1s或者0.5s后，重连网络。因为服务器没有判定客户端掉线。服务器会收到一个相对真实的射击消息
3.客户端检测，弹药可以无限，进行无限的射击判定
服务器判定
最基本的问题：服务器看到的人位置会比客户端看到的人位置更快（服务器人已经跑进掩体，客户端并没有），客户端无法对移动的真实位置进行锁定
延迟补偿
当服务器收到客户端一个开枪的消息时，知道客户端射击的位置，方向。服务器不会用现在的受击者的状态做判定。会把状态的时钟返回退，退回一个延迟的时钟，以当时的受击者状态做判定。
即服务器根据延迟，算法猜测客户端射击瞬间时客户端的世界是什么状态。
因此服务器要对世界在每一个tick时将state做一个快照，保存一段时间，形成一个buffer，来对不同延迟的客户端进行处理
fps很多时候不止网络延迟，内插值还会延迟一段时间，才得到对方的位置
服务器时间需要减掉网络延迟(Packet Latency)，以及客户端的内插值延迟(Client View Interpolation Offset) （即上图蓝色box）
红色box是客户端本地看到的状态

根据不同算法，内插值还是外插值，需要单独的处理延迟补偿。甚至本地可能用了物理检测
服务器检测问题
掩体问题：
1.我认为我躲进了掩体，但是由于延迟在对方客户端我仍为躲进掩体，服务器是以开枪人的世界做判定。我仍被击中
2.我已经在掩体后，观察别人。因为延迟的原因，其实已经看到别人，但因为我的位置仍未同步过去，在对方世界里，我仍在掩体后，无论是以发现还是射击作为收益，都会有先手优势。网络延迟越大，优势越大。

职业的fps射击比赛，会选择用局域网，控制延迟足够小

攻击前摇：攻击加起手动作，几帧的动作(50ms/100ms)能有效降低在网络波动，延迟情况下导致的客户端和服务器状态不同步延迟
因此很多动作游戏，建议做攻击的前摇，为网络延迟争取时间

虽然是服务器做命中检测，但是可以客户端也做命中的判定，如果命中，可以先播放击中的特效。只是纯粹的受击效果展示，真实的伤害结算仍以服务器计算为准

MMOG Network Architecture MMOG网络架构

MMO：很多玩家在一个世界online在一起，MMORPG，MMOFPS，MMOMOBA
游戏子系统
User management：玩家管理器
Matchmaking：匹配系统
Trading system：交易系统
Social system：社交系统
Data storage：数据系统
。。。

简易架构：
连接层：login，gateway。管理用户链接
服务层：各种玩家服务
数据层：各种DB

Login Server：https，完成链接，验证账号密码
Gateway：网关服务，把服务器内外网隔绝开，用户永远只跟gateway交流，gateway负责和内部的角色服务器，大厅服务器。。。去talk。类似防火墙 。验证客户端发送的所有信息的合法性，有效性，包括拦截一些攻击。玩家的链接的加密解密，数据解压缩都在Gateway。通常会用户数量增长越开越多
大厅：多数时候作为一个缓冲池，让玩家在等待例如matchmaking的时候，彼此间能够被管理起来。有时不一定要有真实的场景，可以是个虚拟大厅

管理所有玩家的真正属性、数据。包括玩家的邮件，装备，道具

有非常重的金融属性，保证绝对的安全性，原子性。每一笔交易全部可以rollback。保证任何情况下，做的每一个transaction，都能被准确记录下来，不用担心出现异常数据
有时候会变成一个独立的server。邮件，聊天有自己专门的server。一个单一的server在很多人在一起操作时，可能会炸掉
不仅要考虑玩家间的ranking值，还要考虑彼此间的延迟，尽可能把延迟相近的玩家匹配在一起，保证大家的体验是一致的。
一般开黑的玩家会被扔到一个单独的池子匹配



3类数据存储方式：
1.关系数据库：如mysql。实际上在网游的海量数据下，采用的一般是分布式的数据架构。同时写的时候会写到很多个并行的数据表里，确保写的效率足够高。万一有一个服务器挂掉，数据不会丢掉
2.非关系数据库：访问速度更快，更轻量的数据库，如mongoDB。很多大量的log信息，或者一些临时的state，不需要特别及时，复杂的查询，但又希望访问。
3.内存数据库：如redis。许多服务器同时在跑，可能产生很多的游戏的中间数据，需要一个效率非常高，能够管理数据，但不需要特别重的读写磁盘，只需要在内存中保存下来


大量玩家时，服务器采用分布式架构。
主要都是一些服务器的开发

负载均衡



一致性哈希
服务器和player都用一个哈希算法，算出一个0-2的32次方的值，将数域分布成一个环，服务器也分布在一个环。所有的玩家数据，逆时针方向找到最近的server作为存储
如果s2服务器被释放掉，s2服务器的数据，逆时针顺沿存储到s3
注意，哈希算法设计的要使服务器分布的尽可能均衡

Bandwidth Optimization 带宽优化

带宽优化的意义：数据量过大，会产生拥塞，造成延迟。延迟过大时，有些网关会主动掐断
带宽计算：
n 玩家的数量，f 更新频率，s 更新的数据包体大小


数据压缩
最常用的一种数据压缩方法：将浮点数转成定点数。如果世界不是特别大，用一个16位的定点数可以精确到以厘米位单位的位置
为了配合这种方法，会对游戏地图进行分区。每个区不会特别大，以便于定点数存储位置

只更新玩家相关的object，不需要同步全地图
把世界分成一个个静态zone，将玩家放在zone里

如果世界是开放的，不希望有传送门的概念，这试验AOI
以我为中心，我只关注我周围的object
最简单的AOI：定义一个半径，在整个世界里进行一个query

对空间划格子：
只关注我周围3x3的格子，形成一个AOI列表。当有entity进入或离开zone，通过event更新。同理我进入或离开一个zone，也会notify其他人。
本质是空间换时间



十字链表法
假设空间是2D分布，以x轴为方向，所有的object排个序，再沿着y轴排个序。
如果我的AOI是150m，在x轴上，前后各走150m，得到一群id，在y轴上同样操作。同时满足x轴与y轴的id就是AOI里的entity。
当有任何物体在移动时，会去notify其他人，更新各自的AOI
PVS：根据所在的位置，预先生成好了visiblity的set，不在pvs里的object不关注。对空间分割感更强的游戏更实用
降低server传递数据的频率，尤其对于近战游戏，近处的object同步频率高，远处的object同步频率低

Anti-Cheat 反作弊

直接修改游戏主体，修改内存，破解客户端
破解底层sdk
劫持网络包，发生假消息
作弊方式：查内存，定位内存中的敏感数据。修改数据


反作弊：
加密客户端，运行时再解密。“给客户端加壳”。现在的这种方式几乎都被破解
内存混淆：高度敏感中的数据，在内存中加密，使用的瞬间解密读取
作弊方式：修改本地的文件资源。例如fps游戏，把资源改成发光的材质
反作弊：客户端不停地算本地文件的哈希值，上传哈希值到服务器进行对比校验
作弊方式：网络包劫取


反作弊：
加密网络包：
1.对称算法加密：客户端与服务器共享一个密钥，根据密钥通讯。客户端可能被破解，暴露密钥。
2.非对称算法加密：客户端拥有一个公钥，服务器有一个私钥。 速度较慢，成本较高。一般只登录时使用一次。当网络建立好，用加密的方式把对称的钥匙传递给客户端。接下来服务器与客户端的通讯用一次性的对称加密钥匙
作弊方式：软件注入

反作弊软件：扫描内存中游戏的签名，如果内存中被注入一些奇怪的代码，或者checksum，哈希值不对。检查内存是否被更改过
作弊方式；ai作弊。 比较难防
监察者模式：检查到可疑视频，上传给监察者，让其他玩家打分管理，有主观因素。不准确。是与技术无关的反作弊方法

通过大数据的深度学习，去判定玩家的行为模型。正常玩家的模型是有pattern的
在内存中扫描已知的外挂程序。对商业性质的外挂有较好的判断

Build a Scalable World

开放世界的构建分成3种模型
1.zoning：将世界分成一个个zone
2.instancing：副本
3.replication：将世界分成很多个虚拟的层

玩家的分布是不均匀的，所以zone是动态的划分的。一般用四叉树

玩家跨边界：每个角色的AOI有关注的半径，zone之间会做一个边界，一个角色到边界时，另一个zone的玩家需要能看到边界的角色
只要一个entityA在zoneA的border区里，会在zoneB做一个对应的ghost entityA，虽然真正的entityA在zoneA里，但是zoneB的玩家仍然能看见。只不过真正的逻辑，行为仍由entityA去处理
跨越边界的瞬间，本来在zoneA的实体entityA，把数据迁移一下，将zoneB里的ghostA变成entityA，将zoneA里的entityA变成ghostA。
实际做的时候，会有一个缓冲区，设定一个阈值，穿过边界一段距离后才迁移数据，避免边界线来回跑
每一个character扔到多个游戏的镜像去处理，其他层的玩家对于本层的玩家都是ghost