什么应用/游戏状态"增量压缩"技术/算法确实存在？

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

太好了,我现在有了added和removed diff的bitsets - 但是......

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

一个有效的策略实际上是从那些diff位集构建某种稀疏数据结构吗？例:

// (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

如果这样的事情是可能的,那么避免依赖于体系结构的问题和手写差异计算功能将是相当容易的.

给定两个串甲和乙彼此相似,是可以计算的字符串Ç其在尺寸上大于较小甲和乙,即表示之间的差甲和乙可以和施加到甲得到乙在结果？

Answer 1

由于您使用了 Quake3 作为示例，因此我将重点介绍其中的工作方式。您需要了解的第一件事是，与客户端-服务器游戏相关的“游戏状态”并不指对象的整个内部状态，包括AI的当前状态、碰撞函数、计时器等。游戏的服务器实际上给客户的东西少了很多。只是对象位置、方向、模型、模型动画中的框架、速度和物理类型。后两者用于通过允许客户端模拟弹道运动来使运动更加平滑，但仅此而已。

游戏中的每个帧（每秒大约发生 10 次），服务器都会为游戏中的所有对象运行物理、逻辑和计时器。然后，每个对象调用 API 函数来更新其新位置、帧等，以及更新是否在此帧中添加或删除它（例如，由于撞到墙上而被删除的镜头）。实际上，Quake 3 在这方面有一个有趣的错误 - 如果一个镜头在物理阶段移动并撞到墙壁，它就会被删除，并且客户端收到的唯一更新是被删除，而不是之前飞向墙壁的飞行，因此，在真正撞到墙壁之前，客户会看到镜头在 1/10 秒内消失在半空中。

有了这些关于每个对象的信息，就可以很容易地区分新信息和旧信息。此外，只有实际发生变化的对象才会调用更新 API，因此保持不变的对象（例如墙壁或不活动的平台）甚至不需要执行此类差异。此外，服务器可以通过不向客户端发送在客户端可见之前不可见的对象来进一步节省发送的信息。例如，在 Quake2 中，一个关卡被划分为多个视图区域，如果一个区域（及其内部的所有对象）之间的所有门都关闭，则该区域（及其内部的所有对象）将被视为“在另一个区域的视图之外”。

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

除此之外，还有玩家的生命值、弹药等用户界面数据。同样，每个玩家只会收到自己的生命值和弹药，而不是服务器上每个人的生命值和弹药。服务器没有理由共享该数据。

更新： 为了确保我获得最准确的信息，我仔细检查了代码。这是基于 Quake3，而不是 Quake Live，所以有些事情可能会有所不同。发送到客户端的信息本质上封装在一个名为 的结构中snapshot_t。playerState_t其中包含当前玩家的单个数据、entityState_t可见游戏实体的 256 个数组，以及一些额外的整数，以及表示“可见区域”位掩码的字节数组。

entityState_t依次由 22 个整数、4 个向量和 2 个轨迹组成。“轨迹”是一种数据结构，用于表示物体在没有发生任何事情时在空间中的运动，例如弹道运动或直线飞行。它是 2 个整数、2 个向量和 1 个枚举，概念上可以存储为一个小整数。

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

由于使用的结构具有预设的大小和结构，因此制作一个简单的手动“diff”函数，比较每个成员，对于每个成员来说都是相当简单的。然而，据我所知，entityState_t并且playerState_t只是完整发送，而不是部分发送。唯一“增量”的是发送哪些实体，作为实体数组的一部分snapshot_t.

虽然快照最多可以包含 256 个实体，但游戏本身最多可以包含 1024 个实体。这意味着从客户端的角度来看，在单个帧中只能更新 25% 的对象（任何更多的对象都会导致臭名昭著的“数据包溢出”错误）。服务器只是跟踪哪些对象进行了有意义的移动，然后发送这些对象。它比执行实际差异要快得多 - 只需发送任何本身调用“更新”的对象，并且位于玩家的可见区域位掩码内。但从理论上讲，手写的每个结构差异不会那么难制作。

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

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