有哪些应用程序/游戏使用“增量压缩”技术/算法？

Question

我对探索实时多人客户端服务器游戏开发和相关算法感兴趣。许多著名的多人游戏，例如Quake 3或Half-Life 2使用增量压缩技术来节省带宽。

服务器必须不断向所有客户端发送最新的游戏状态快照。总是发送完整快照将非常昂贵，因此服务器只发送上一个快照与当前快照之间的差异。

...很容易，对吧？嗯，我觉得非常难想的部分是如何实际计算两个游戏状态之间的差异。

游戏状态可以非常复杂，并且具有在堆上分配的实体，通过指针相互引用，可能具有数值，其表示因架构而异，等等。

我认为不太可能每种游戏对象类型都有手写的序列化/反序列化/差异计算函数。

---

让我们回到基础知识。假设我有两个用位表示的状态，并且我想计算它们之间的差异：

state0:  00001000100    // state at time=0
state1:  10000000101    // state at time=1
         -----------
added:   10000000001    // bits that were 0 in state0 and are 1 in state1
removed: 00001000000    // bits that were 1 in state0 and are 1 in state1

太好了，我现在有了添加和删除的差异位集，但是...

...差异的大小仍然与状态的大小完全相同。而且我实际上必须通过网络发送两个差异！

从这些差异位集中构建某种稀疏数据结构是否是一种有效的策略？例如：

// (bit index, added/removed)
// added = 0
// removed 1
(0,0)(4,1)(10,0)

// ^
// bit 0 was added, bit 4 was removed, bit 10 was added

这是一种可行的方法吗？

---

假设我已经为我的所有游戏对象类型编写了从/到JSON的序列化/反序列化函数。

我能否以某种方式，自动计算两个JSON值之间的差异，以位为单位？

例如：

// state0
{
    "hp": 10,
    "atk": 5
}

// state1
{
    "hp": 4,
    "atk": 5
}

// diff
{
    "hp": -6
}

// state0 as bits (example, random bits)
010001000110001

// state1 as bits (example, random bits)
000001011110000

// desired diff bits (example, random bits)
100101

如果这样的事情是可能的，那么避免架构相关问题和手写差异计算函数将变得相对容易。

给定两个类似的字符串 A 和 B，是否可能计算出一个字符串 C，它比 A 和 B 都要小，用于表示 A 和 B 之间的差异，并且可以应用于 A 上，得到 B 的结果？

- Vittorio Romeo

---

如果你有一个（多步）撤销/重做机制，你可能可以利用它。 - greybeard

Answer 1

自从你以Quake3为例，我将重点关注在那里的操作方式。你需要先了解的是，在客户端服务器游戏中，“游戏状态”并不是指对象的整个内部状态，包括AI的当前状态、碰撞函数、计时器等等。事实上，游戏的服务器给客户端的远远不止这些。仅仅是对象的位置、方向、模型、模型动画中的帧、速度和物理类型。后两者用于使运动更加平滑，通过允许客户端模拟弹道运动来实现，但仅限于此而已。

每一帧游戏中，大约每秒钟发生10次，服务器会对游戏中所有对象运行物理、逻辑和计时器。然后每个对象调用一个API函数来更新它的新位置、帧等，并更新它是否在这一帧中添加或删除（例如，因为子弹打到了墙上而被删除）。实际上，Quake 3在这方面有一个有趣的bug——如果一个子弹在物理阶段移动并击中了墙壁，它就会被删除，客户端接收到的唯一更新就是被删除了，而不是之前飞向墙壁的状态，所以客户端看到子弹在实际击中墙壁之前的1/10秒内消失在空中。

有了这些小的每个对象的信息，很容易将新信息与旧信息进行差异比较。此外，只有实际更改的对象调用更新API，因此保持不变的对象（例如墙壁或非活动平台）甚至不需要执行此类差异。此外，服务器可以通过在客户端查看对象之前不向客户端发送不可见的对象进一步节省发送信息。例如，在Quake2中，一个级别被分成视图区域，并且如果它们之间的所有门都关闭，则另一个区域（以及其中所有对象）被认为是“不可见”的。

请记住，服务器不需要客户端拥有完整的游戏状态，只需要一个场景图，这需要更简单的序列化，并且绝对没有指针（在Quake中，它实际上保存在一个单一的静态大小数组中，这也限制了游戏中对象的最大数量）。

除此之外，还有用于玩家健康状况、弹药等的UI数据。同样，每个玩家只会收到他们自己的健康和弹药，而不是服务器上所有人的。服务器没有必要共享这些数据。 更新: 为了确保获取最准确的信息，我通过代码进行了双重检查。这是基于Quake3而不是Quake Live，因此有些事情可能会有所不同。发送到客户端的信息实质上封装在称为snapshot_t的单个结构中。其中包含一个用于当前玩家的playerState_t和一个包含256个可见游戏实体的entityState_t数组，以及一些额外的整数和表示“可见区域”位掩码的字节数组。

entityState_t是由22个整数、4个向量和2个轨迹组成的。 "轨迹"是一种数据结构，用于表示物体在空间中移动时的状态，例如弹道运动或直线飞行。它包含2个整数、2个向量和一个枚举，可以概念上存储为一个小整数。

playerState_t稍微大一些，包含大约34个整数，大约8个整数数组，每个数组的大小从2到16不等，以及4个向量。这包括从武器的当前动画帧到玩家的库存，再到玩家正在发出的声音的所有内容。

由于使用的结构具有预设的大小和结构，因此对于每个成员，制作一个简单的手动“diff”函数进行比较相当简单。但是，据我所知，entityState_t和playerState_t仅以其完整形式发送，而不是部分发送。唯一进行“delta”的是发送的实体，作为snapshot_t中的实体数组的一部分。

虽然快照最多可以包含256个实体，但游戏本身最多可以包含1024个实体。这意味着从客户端的视角来看，每帧只有25％的对象可以更新（任何更新超过此数量会导致臭名昭著的“封包溢出”错误）。服务器只是跟踪哪些对象具有有意义的移动，并发送它们。这比执行实际的差异要快得多-仅需发送任何调用其自身的“update”的对象，且在玩家可见区域位掩码内。但理论上，手写的每个结构差异并不会更难。

对于团队健康状况，虽然Quake3似乎没有这样做，因此我只能推测在Quake Live中如何完成。有两个选择：要么发送所有playerState_t结构，因为最多只有64个，要么在playerState_t中添加另一个数组以保持团队HP，因为它只有64个整数。后者更有可能。

为了让客户端和服务器之间的对象数组保持同步，每个实体都有一个从0到1023的实体索引，并作为消息的一部分从服务器发送给客户端。当客户端接收到256个实体的数组时，它会遍历数组，从每个实体读取索引字段，并在本地存储的实体数组中更新读取索引处的实体。

- SlugFiller

---

非常有趣的信息。我有一些额外的问题，希望你能回答（或帮助我找到答案）：1）根据你的回答，似乎健康/弹药和其他状态不是同步的 - Quake 3如何处理这些数据？我能在Quake Live的HUD上看到我的队友的健康状况。，2）存储在静态数组中的对象＃500在服务器上与客户端上的对象＃500同步吗？，3）差异实际上是如何计算的？是否有手写函数来计算每种对象类型的差异？ - Vittorio Romeo

如果您需要我回答中的任何额外信息，请告诉我。 - SlugFiller

Answer 2

我建议先退后一步，寻找潜在的更好解决方案。正如你所提到的，游戏状态可能非常复杂和庞大。因此，智能压缩（差异、紧凑的序列化形式等）不太可能有所帮助。最终，将需要传输非常大的差异，游戏体验将受到影响。

为了简化故事，我建议查看两个图表（源链接将提供）。

您可以将用户操作转换为函数调用，从而改变游戏状态：

或者您可以创建一个相应的命令/操作，并让您的命令执行器异步处理更改状态。

可能看起来差别很小，但第二种方法允许您：

• 通过为用户操作引入队列，避免任何竞态条件并安全更新状态
• 处理来自多个来源的操作（您只需要正确排序它们）

我刚才描述了命令模式，这可能非常有帮助。 它将我们带到了计算状态的思路。 如果命令行为是确定性的（应该是这样的），为了获得新状态，您只需要先前的状态和命令。

因此，只需要其他命令即可进行状态增量，拥有初始状态（对于每个玩家都相同，或在游戏开始时传输）。

我将使用写前日志和命令日志作为示例（假设您的游戏状态在数据库中），因为解决的问题几乎相同，我已经尝试提供详细说明：

这种方法还可以简化状态恢复等操作，因为与“生成新状态、与先前状态进行比较、生成差异、压缩差异、发送差异、应用差异”序列相比，动作执行可能会更快。

无论如何，如果您仍然认为发送差异更好，请确保状态足够小（因为您将至少拥有两个快照），并具有小且易于读取的内存占用量。

在这种情况下，差分过程将生成稀疏数据，因此任何流压缩算法都将轻松产生良好的压缩因子。顺便说一句，确保您的压缩算法不需要更多的内存。最好不要使用任何基于字典的解决方案。 算术编码，基数树可能会有所帮助。以下是一个您可以开始使用的想法和实现：

  public static void encode(int[] buffer, int length, BinaryOut output) {
    short size = (short)(length & 0x7FFF);

    output.write(size);
    output.write(buffer[0]);

    for(int i=1; i< size; i++) {
        int next = buffer[i] - buffer[i-1];
        int bits = getBinarySize(next);

        int len = bits;

        if(bits > 24) {
          output.write(3, 2);
          len = bits - 24;
        }else if(bits > 16) {
          output.write(2, 2);
          len = bits-16;
        }else if(bits > 8) {
          output.write(1, 2);
          len = bits - 8;
        }else{
          output.write(0, 2);
        }

        if (len > 0) {
            if ((len % 2) > 0) {
                len = len / 2;
                output.write(len, 2);
                output.write(false);
            } else {
                len = len / 2 - 1;
                output.write(len, 2);
            }

            output.write(next, bits);
        }
    }
}

public static short decode(BinaryIn input, int[] buffer, int offset) {
    short length = input.readShort();
    int value = input.readInt();
    buffer[offset] = value;

    for (int i = 1; i < length; i++) {
        int flag = input.readInt(2);

        int bits;
        int next = 0;
        switch (flag) {
            case 0:
                bits = 2 * input.readInt(2) + 2;
                next = input.readInt(bits);
                break;
            case 1:
                bits = 8 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 2:
                bits = 16 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 3:
                bits = 24 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
        }

        buffer[offset + i] = buffer[offset + i - 1] + next;
    }

   return length;
}

最后的建议： 不要暴露状态，也不要传递它，而是计算它。这种方法将更快、更易于实现和调试。

- Renat Gilmanov

Answer 3

比较位时，存储每个更改的位的位置是否高效取决于更改的位数。在32位系统中，每个位置占用32位，因此仅当少于32位中的1位更改时才有效率。但是，由于更改的位通常是相邻的，如果您以更大的单元（例如字节或字）进行比较，则效率会更高。

请注意，仅当位的绝对位置不发生变化时，才能使用比较位的方法。然而，如果在中间插入或删除了一些位，您的算法将看到插入/删除位置之后几乎每个位都被更改了。为了缓解这种情况，您需要计算最长公共子序列，使得A或B中仅有插入/删除的位。

---

但是，比较JSON对象不一定要按位进行。(如果必须的话，它与比较两个位串相同。)比较可以在更高层次上进行。计算两个任意JSON对象之间差异的一种方法是编写一个函数，该函数接受A和B，并且：

• 如果参数具有不同类型，则返回“A已更改为B”。
• 如果参数具有相同的基本类型，则如果它们相同则什么都不返回，否则返回“A已更改为B”。
• 如果两个参数都是字典，则只包含在A中的键的元素被删除，而只包含在B中的键的元素被添加。对于具有相同键的元素，请进行递归比较。
• 如果两个参数都是数组，则计算A和B的最长公共子序列(也可以通过递归函数检查两个元素是否相等)，并找到仅在A或B中的元素。因此，在A中仅存在的元素被删除，在B中仅存在的元素被添加。或者，也可以通过递归地比较不相等的元素，但我所能想到的唯一有效的方法需要有一种方法(如记录ID)来标识哪个元素在A中对应于哪个元素在B中，并将一个元素与相应的元素进行比较。

---

两个字符串之间的差异也可以使用最长公共子序列来计算。

- user4098326