继续探讨同步难题…

上一篇文章介绍了帧同步，帧同步是解决网络同步的一个很好的方案，服务端以固定频率向所有客户端广播和指令。但帧同步非常容易受到网络波动影响，我们需要模拟玩家镜像的行为（甚至可能因为等待指令收到而出现卡顿），这对于对网络要求很高的 fps（第一人称射击游戏）、tps（第三人称射击游戏）、qte 判定来说是不可接受的。为什么呢？拿射击游戏来说，如果稍有网络延迟，玩家就难以瞄准目标，或者可能被莫名其妙打死。

什么是状态同步？

状态同步就类似于我们在网络同步系列的第一篇文章中说的直接同步用户的状态。客户端将指令发送给服务端，服务端计算出状态后广播给其他客户端，客户端收到后进行更新。这样虽然会加重服务端的运算负载，但可以有效避免客户端作弊的发生。

当然，我们还可以结合一下分布式运算的想法，将计算压力分摊到客户端上。在这种模式中，客户端将部分指令即时计算成状态之后，将状态发送给其他客户端（其他客户端同理），其他客户端收到后进行更新。这特别适合需要及时看到游戏反馈的射击类游戏，因为如果采用帧同步或者服务器模式（由服务器计算指令）的状态同步的话，数据经由服务端运算再传回各个客户端，会导致较高的延迟从而影响玩家体验，因此这类游戏依赖客户端本地运算的能力（但也正因为如此，分布式状态同步很难防止客户端作弊）。

AOI算法

在一场大逃杀类型的游戏中，单局可能存在数十甚至上百名玩家。这种单局规模较大的游戏如果采用帧同步策略，就需要记录所有玩家的所有指令，这样才能计算出所有玩家镜像正确的行为。当玩家很多的时候，需要同步的指令内容也很多，导致流量和运算成本增大。

但需要注意到：虽然在大逃杀游戏中有很多玩家，但同屏玩家的数量是有限的。如果采用状态同步，客户端只需要关注玩家周围的事物即可，计算量较小，能减轻服务器的压力。我们可以采用AOI（感兴趣区域）算法来实现这一点，例如下图中的红点代表玩家，蓝色范围代表整个战场，则橙色范围代表其感兴趣区域，服务端只需要向红色玩家同步该区域内的状态即可，减少广播量。

我们可以通过一个列表简单的维护玩家 AOI 内的所有实体，当有实体进出玩家 AOI 时会调用回调函数修改列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Entity{
    public int id;
    public float speed;
    public Vector2 pos;
    public List<int> entitys;   // 记录实体id
    // 控制玩家移动
    public void MoveTo(Vector2 target){
        Vector2.MoveTowards(transform.position, target, speed);
    }
    // 获取玩家AOI范围内的实体
    public List<int> GetAOI(){
        return entitys;
    }
    // 有实体进入AOI
    public void OnEnterAOI(int id){
        entitys.Add(id);
    }
    // 有实体离开AOI
    public void OnExitAOI(int id){
        entitys.Remove(id);
    }
}

那么问题来了，我们要怎么知道那些实体在 AOI 里，哪些实体正在进出 AOI 呢？直接遍历所有玩家是一种粗暴的方式，虽然可行但效率低下。九宫格法和四叉树则是业内常用的、效率较高的算法。

九宫格法

九宫格是最容易理解的一种 AOI 算法。我们先将场景划分成小格，格子尺寸依照客户端一屏幕能看到的范围而定，使屏幕最多能够看到 4 个格子。我们可以通过一个二维数组表示地图的格，也可以为格子编写Node类，记录该类的左右界、宽度等信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Grid {
    int GID;            //格子ID
    List<int> entitys;  //当前格子内的实体
}
 
public class GridManger {
    int StartX;     // X区域左边界坐标
    int StartY;     // Y区域上边界坐标
    int AreaWidth;  // 格子宽度(长=宽)
    int GridCount;  // 格子数量
    int[] grids;
    // 通过位置查找GID
    public int GetGIDByPos(float x, float y){
        int gx = ((int)x - StartX) / AreaWidth;
        int gy = ((int)y - StartY) / AreaWidth;
        return gy * GridCount + gx;
    }
}

这样我们就可以根据实体的坐标找到实体位于哪个格子了。通常，我们会划定玩家实体所在格子和四周八个格子组成的范围为玩家的 AOI，每次查找 AOI 内的实体，效率比查找全图更低。当实体离开某个格子时，需要给离开的 AOI 格子发送离开回调、给新的AOI格子内的实体发送进入回调，以维护 AOI 实体。

四叉树

九宫格算法需要一次性开辟出所有的网格，无论格子中是否存在一定数量的玩家。当一次性出现陈千上万的网格，对服务端的资源浪费可想而知。类似的算法与灯塔算法亦是如此。当然也有一些算法对此做了优化但终有取舍，例如四叉树。四叉树算是一种比较完备的 AOI 算法，也是在二维图片中定位像素的唯一适合的算法。

四叉树的优势相比九宫格有两点：

  1. 当玩家数量比较少的时候，节省了节点的分配的内存
  2. 当玩家数量比较多的时候，能保持每个节点内的玩家数量均衡，但整个树的内存体积和九宫格体积应该是差不多的，因为一样要存那么多个玩家数据进去

仲裁权问题

仔细观察下图所示的临界情况：

在这个情况中，假设：

  1. 下方的玩家向上走了一步，向服务端发送“向上一步、夺旗”的状态；
  2. 上方的玩家在接收到这个状态之前向下走了一步，向服务端发送“向下一步、夺旗”的状态。
  3. 此时两个玩家的状态都变成了“夺旗”，到底谁获得了胜利呢？

这就涉及到状态同步的仲裁权问题。两个玩家都在竞争“仲裁权”，我们需要结合具体的信息（例如状态更新的时间）进行公平公正的仲裁。有两种可行的思路：

强一致性

服务器模式就是一种强一致性的方式，因为只存在一个逻辑仲裁点（服务器），这从根本上避免了冲突。两个用户把指令发送到服务器上，服务器根据指令发送的时间戳判断哪个玩家先夺得旗帜。

而在分布式模式中，不同客户端仅对单一状态进行仲裁，两个客户端不能仲裁同一个状态，这样就可以实现仲裁权的分割。只不过这个做法比较理想化，不符合联机游戏的特征、存在扩展风险。

弱一致性

在弱一致性方法中，我们首先要对所有一致性做一个区分：哪些是核心一致性，哪些是非核心一致性？

  • 核心一致性：可能影响双方的状态采用单点仲裁处理、异步交互（如：fps游戏中是否命中、赛车游戏中的道具），这部分需要放在服务端上进行计算。

    • 单点逻辑仲裁对操作响应的延迟很敏感。
    • 比较慢，因为需要服务器计算后合包再发送给各个客户端，这中间存在时延。因此更适合对核心仲裁延迟相对不敏感的情况（比如fps的命中判定并不是立刻判定完成的，但结合“子弹存在飞行时间”等ux因素，对玩家的体验影响并不太大）。
    • 一致性有容错空间。

  • 非核心一致性：仅对自身有影响的状态采用仲裁分割、延迟同步（如：赛车游戏中自身位置、fps游戏中的位置等），这部分可以分布式处理。

    • 对于物理、3D这些比较复杂的运算，如果全部交给服务端将对其造成较大的计算负荷，因此这部分状态判定可以交由客户端本身进行处理。

但在射击游戏中，有时为了保证玩家体验，会采取“主动方优先”的策略，将仲裁权交给主动方。例如一个玩家对另一个玩家开枪，玩家A发出“开枪，命中玩家B”的状态、玩家B发出“未命中玩家B”的状态时，听从玩家A。

fps的回溯判定

fps对于精度的判断要求很高，在存在服务器状态延迟、射击指令延迟的时候应该怎么准确的进行命中仲裁呢？此时服务器需要回溯射击发生当时的状态，进行判断。

在上图所示的例子中，蓝色玩家在射击时向服务器发送了射击指令，经过延迟服务器收到后计算出橙色玩家已经走到了下面的位置、子弹飞到了右侧的位置，此时子弹和橙色玩家并没有接触。

但这样我们就可以直接判断子弹没有命中橙色玩家吗？显然是不行的，因为我们不知道子弹飞行的过程中是否击中了橙色玩家，因此需要做“回溯判定”的操作。服务器会采用一些高效的逐帧检查，直到检测出命中/不命中。

优点与缺点

优点

- 支持更多玩家和更长时间的运行
- 服务器模式下更安全（不容易作弊）
- 断线重连更快
- 实时性更好
- 适合小规模状态/可划分子系统（适用于fps/赛车/三消等）
- 较小的计算量
- 输入延迟低，因为本地就计算好状态了

缺点

  • 大规模状态时同步的数据也大
  • 流量大
  • 分布式计算/复杂逻辑的一致性难以协调，导致后期维护成本高
  • 不好实现回放
  • 实现复杂

参考资料

百万在线：大型游戏服务端开发（罗培羽）
https://gameinstitute.qq.com/course/detail/10242
https://www.youxituoluo.com/528021.html