什么 application/game 状态 "delta compression" techniques/algorithm 确实存在？
What application/game state "delta compression" techniques/algorithm do exist?
我有兴趣探索实时多人客户端-服务器游戏开发和相关算法。许多著名的多人游戏，例如 Quake 3 或 Half-Life 2 使用 delta compression 技术来节省带宽。
服务器必须不断向所有客户端发送最新的游戏状态快照。总是发送完整的快照会非常昂贵，因此服务器 只发送上一个快照和当前快照之间的差异。
...容易吧？好吧，我觉得很难思考的部分是如何实际计算两个游戏状态之间的差异。
游戏状态可能非常复杂，在堆上分配的实体通过指针相互引用，可以具有表示因架构而异的数值，等等。
我很难相信每个游戏对象类型都有手写的 serialization/deserialization/diff-calculation 函数。
让我们回到基础。假设我有两个状态，用位表示，我想计算它们的差异：
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
这是一种可能有效的方法吗？
假设我设法为所有游戏对象类型编写 serialization/deserialization 函数 from/to 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 并且可以 applied to A to结果得到 B?
比较位时，存储每个个变化位的位置是否有效取决于变化了多少位。在 32 位系统中，每个位置占用 32 位，因此只有在 32 位中更改少于 1 时才有效。但是，由于更改的位通常是相邻的，因此如果以更大的单位（例如字节或字）进行比较会更有效。
请注意，您比较位的方法仅在位的绝对位置不变时才有效。但是，如果在中间插入或删除了一些位，您的算法将看到几乎 inserted/removed 位置之后的每一位都发生了变化。为了缓解这种情况，您将计算最长的公共子序列，因此只有 A 或 B 中的位是 inserted/removed.
但是比较 JSON 对象不必按位进行。 （如果必须的话，这与比较两个位串是一样的。）比较可以在更高级别进行。计算两个任意 JSON 对象的差异的一种方法是编写一个函数，该函数接受 A 和 B 以及：
- 如果参数类型不同，return "A is changed to B".
- 如果参数是相同的基本类型，return如果它们相同则没有，否则，return "A is changed to B".
- 如果两个参数都是字典，则键只在A中的元素是删除的元素，键只在B中的元素是添加的元素。对于key相同的元素，递归比较。
- 如果两个参数都是数组，计算A和B的最长公共子序列（两个元素是否相等也可以用递归函数来判断），只在A或B中找到元素，所以，只有元素A 中的元素是删除的元素，仅 B 中的元素是添加的元素。或者不相等的元素也可以递归比较，但我能想到的唯一有效的方法是有一种方法（比如记录ID）来识别A中的哪个元素对应于B中的哪个元素，并比较一个元素与相应的元素。
也可以使用最长公共子序列计算两个字符串之间的差异。
我建议退后一步，环顾四周，以找到可能更好的解决方案。
正如您所提到的，游戏状态可能非常复杂且庞大。所以智能压缩（差异、紧凑的序列化形式等）不太可能有帮助。最终，将需要传输非常大的差异，因此游戏体验会受到影响。
为了让故事简短，我建议查看两个数字（link 将提供来源）。
您可以将用户操作转化为函数调用，这将改变游戏状态：
或者你可以创建一个相应的 command/action 并让你的命令执行器异步处理它改变状态：
看起来差异很小，但第二种方法允许您：
- 通过为用户操作引入队列来避免任何竞争条件并安全地更新状态
- 处理来自多个来源的操作（您只需要将它们正确排序）
我刚刚描述了 Command Pattern，这可能非常有帮助。它给我们带来了 computed state 的想法。如果命令行为是确定性的（因为它应该是）为了获得一个新的状态，你只需要一个前一个和一个命令。
因此，具有初始状态（每个玩家都相同，或在游戏开始时转移）只需要其他命令来执行状态增量。
我将使用预写和命令记录作为示例（假设您的游戏状态在数据库中），因为几乎相同的问题正在解决并且我已经尝试提供 detailed explanation:
这种方法还允许简化状态恢复等，因为与 generate new state, compare to the previous one, generate diff, compress diff, send diff, apply diff 序列相比，动作执行可能真的更快。
无论如何，如果您仍然认为发送差异比较好，请尝试让您的状态足够小（因为您将至少有两个快照）和小且易于读取的内存占用。
在那种情况下，diff 过程将生成稀疏数据，因此任何流压缩算法都可以轻松产生良好的压缩因子。顺便说一句，确保您的压缩算法不需要更多内存。最好不要使用任何基于字典的解决方案。
Arithmetic coding, Radix tree 可能会有所帮助。以下是您可以开始的想法和实施：
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;
}
最后一句话：不要公开状态，不要传输它，而是计算它。这种方法将更快，易于实施和调试。
既然您已经使用 Quake3 作为示例，我将重点介绍那里的工作方式。首先你要明白，客户端-服务器游戏中的"game state"并不是指对象的整个内部状态，包括AI的当前状态、碰撞函数、计时器等。游戏的服务器实际上给客户端的东西少了很多。只是对象的位置、方向、模型、模型动画中的帧、速度和物理类型。后两者用于通过允许客户端模拟弹道运动来使运动更平滑，但仅此而已。
游戏中的每个帧，大约每秒发生 10 次，服务器为游戏中的所有对象运行物理、逻辑和计时器。然后每个对象调用一个 API 函数来更新它的新位置、帧等，以及更新它是在这个帧中添加还是删除（例如，一个镜头因为撞墙而被删除）。实际上，Quake 3 在这方面有一个有趣的错误 - 如果射击在物理阶段移动并撞到墙上，它就会被删除，并且客户端收到的唯一更新被删除，而不是之前飞向墙壁的更新，所以客户看到镜头在真正撞到墙上之前 1/10 秒消失在半空中。
有了这些每个对象的小信息，就可以很容易地区分新信息和旧信息。此外，只有实际更改的对象才会调用更新 API，因此保持不变的对象（例如墙壁或非活动平台）甚至不需要执行这样的差异。此外，服务器可以通过不向客户端发送对象来进一步保存已发送的信息，这些对象在客户端出现之前是不可见的。例如，在 Quake2 中，一个关卡被划分为多个视图区域，如果一个区域（以及其中的所有对象）之间的所有门都关闭，则该区域（以及其中的所有对象）被认为与另一个区域"out of view"。
请记住，服务器不需要客户端有完整的游戏状态，只需要一个场景图，这需要简单得多的序列化，绝对不需要指针（在 Quake 中，它实际上保存在一个静态的-大小的数组，这也限制了游戏中对象的最大数量。
除此之外，还有 UI 玩家的生命值、弹药等数据。同样，每个玩家只会收到发送给他们自己的生命值和弹药，而不是服务器上每个人的。服务器没有理由共享该数据。
更新：
为了确保获得最准确的信息，我仔细检查了代码。这是基于 Quake3，而不是 Quake Live，所以有些事情可能会有所不同。发送到客户端的信息本质上封装在一个称为 snapshot_t. This contains a single playerState_t for the current player, and an array of 256 entityState_t 的结构中，用于可见游戏实体，以及一些额外的整数和一个表示 "visible areas".[=21= 位掩码的字节数组。 ]
entityState_t依次由22个整数、4个向量和2条轨迹组成。 "trajectory" 是一种数据结构，用于表示对象在没有任何反应时通过 space 的移动，例如弹道运动，或直线飞行。是2个整数，2个向量，1个枚举，概念上可以存储为一个小整数。
playerState_t 稍微大一点，包含大约 34 个整数、大约 8 个大小从 2 到 16 不等的整数数组和 4 个向量。这包含从武器的当前动画帧到玩家物品栏到玩家发出的声音的所有内容。
由于使用的结构具有预设大小和结构，因此制作一个简单的手动 "diff" 函数，比较每个成员，对于每个成员来说相当简单。但是，据我所知，entityState_t 和 playerState_t 只是全部发送，而不是部分发送。唯一 "delta"ed 是发送哪些实体，作为 snapshot_t.
中实体数组的一部分
虽然快照最多可包含 256 个实体，但游戏本身最多可包含 1024 个实体。这意味着从客户端的角度来看，在单个帧中只能更新 25% 的对象（任何更多都会导致臭名昭著的 "packet overflow" 错误）。服务器简单地跟踪哪些对象进行了有意义的移动，并发送这些对象。它比执行实际差异要快得多 - 只需发送自身调用 "update" 且位于玩家可见区域位掩码内的任何对象。但从理论上讲，手写每个结构的差异并不会那么难。
为了团队健康，虽然 Quake3 似乎没有这样做，所以我只能推测它是如何在 Quake Live 中完成的。有两种选择：发送所有 playerState_t 结构，因为它们最多有 64 个，或者在 playerState_t 中添加另一个数组以保持团队 HP，因为它只有 64 个整数。后者的可能性更大。
为了保持对象数组在客户端和服务器之间同步，每个实体都有一个从 0 到 1023 的实体索引，它作为消息的一部分从服务器发送到客户端。当客户端收到一个包含 256 个实体的数组时，它会遍历该数组，从每个实体中读取索引字段，并在其本地存储的实体数组中更新读取索引处的实体。
我有兴趣探索实时多人客户端-服务器游戏开发和相关算法。许多著名的多人游戏，例如 Quake 3 或 Half-Life 2 使用 delta compression 技术来节省带宽。
服务器必须不断向所有客户端发送最新的游戏状态快照。总是发送完整的快照会非常昂贵，因此服务器 只发送上一个快照和当前快照之间的差异。
...容易吧？好吧，我觉得很难思考的部分是如何实际计算两个游戏状态之间的差异。
游戏状态可能非常复杂，在堆上分配的实体通过指针相互引用，可以具有表示因架构而异的数值，等等。
我很难相信每个游戏对象类型都有手写的 serialization/deserialization/diff-calculation 函数。
让我们回到基础。假设我有两个状态，用位表示，我想计算它们的差异：
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
这是一种可能有效的方法吗？
假设我设法为所有游戏对象类型编写 serialization/deserialization 函数 from/to 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 并且可以 applied to A to结果得到 B?
比较位时，存储每个个变化位的位置是否有效取决于变化了多少位。在 32 位系统中，每个位置占用 32 位，因此只有在 32 位中更改少于 1 时才有效。但是，由于更改的位通常是相邻的，因此如果以更大的单位（例如字节或字）进行比较会更有效。
请注意，您比较位的方法仅在位的绝对位置不变时才有效。但是，如果在中间插入或删除了一些位，您的算法将看到几乎 inserted/removed 位置之后的每一位都发生了变化。为了缓解这种情况，您将计算最长的公共子序列，因此只有 A 或 B 中的位是 inserted/removed.
但是比较 JSON 对象不必按位进行。 （如果必须的话，这与比较两个位串是一样的。）比较可以在更高级别进行。计算两个任意 JSON 对象的差异的一种方法是编写一个函数，该函数接受 A 和 B 以及：
- 如果参数类型不同，return "A is changed to B".
- 如果参数是相同的基本类型，return如果它们相同则没有，否则，return "A is changed to B".
- 如果两个参数都是字典，则键只在A中的元素是删除的元素，键只在B中的元素是添加的元素。对于key相同的元素，递归比较。
- 如果两个参数都是数组，计算A和B的最长公共子序列（两个元素是否相等也可以用递归函数来判断），只在A或B中找到元素，所以，只有元素A 中的元素是删除的元素，仅 B 中的元素是添加的元素。或者不相等的元素也可以递归比较，但我能想到的唯一有效的方法是有一种方法（比如记录ID）来识别A中的哪个元素对应于B中的哪个元素，并比较一个元素与相应的元素。
也可以使用最长公共子序列计算两个字符串之间的差异。
我建议退后一步，环顾四周，以找到可能更好的解决方案。
正如您所提到的，游戏状态可能非常复杂且庞大。所以智能压缩（差异、紧凑的序列化形式等）不太可能有帮助。最终，将需要传输非常大的差异，因此游戏体验会受到影响。
为了让故事简短，我建议查看两个数字（link 将提供来源）。
您可以将用户操作转化为函数调用，这将改变游戏状态：
或者你可以创建一个相应的 command/action 并让你的命令执行器异步处理它改变状态：
看起来差异很小，但第二种方法允许您：
- 通过为用户操作引入队列来避免任何竞争条件并安全地更新状态
- 处理来自多个来源的操作（您只需要将它们正确排序）
我刚刚描述了 Command Pattern，这可能非常有帮助。它给我们带来了 computed state 的想法。如果命令行为是确定性的（因为它应该是）为了获得一个新的状态，你只需要一个前一个和一个命令。
因此，具有初始状态（每个玩家都相同，或在游戏开始时转移）只需要其他命令来执行状态增量。
我将使用预写和命令记录作为示例（假设您的游戏状态在数据库中），因为几乎相同的问题正在解决并且我已经尝试提供 detailed explanation:
这种方法还允许简化状态恢复等，因为与 generate new state, compare to the previous one, generate diff, compress diff, send diff, apply diff 序列相比，动作执行可能真的更快。
无论如何，如果您仍然认为发送差异比较好，请尝试让您的状态足够小（因为您将至少有两个快照）和小且易于读取的内存占用。
在那种情况下，diff 过程将生成稀疏数据，因此任何流压缩算法都可以轻松产生良好的压缩因子。顺便说一句，确保您的压缩算法不需要更多内存。最好不要使用任何基于字典的解决方案。
Arithmetic coding, Radix tree 可能会有所帮助。以下是您可以开始的想法和实施：
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;
}
最后一句话：不要公开状态，不要传输它，而是计算它。这种方法将更快，易于实施和调试。
既然您已经使用 Quake3 作为示例，我将重点介绍那里的工作方式。首先你要明白，客户端-服务器游戏中的"game state"并不是指对象的整个内部状态，包括AI的当前状态、碰撞函数、计时器等。游戏的服务器实际上给客户端的东西少了很多。只是对象的位置、方向、模型、模型动画中的帧、速度和物理类型。后两者用于通过允许客户端模拟弹道运动来使运动更平滑，但仅此而已。
游戏中的每个帧，大约每秒发生 10 次，服务器为游戏中的所有对象运行物理、逻辑和计时器。然后每个对象调用一个 API 函数来更新它的新位置、帧等，以及更新它是在这个帧中添加还是删除（例如，一个镜头因为撞墙而被删除）。实际上，Quake 3 在这方面有一个有趣的错误 - 如果射击在物理阶段移动并撞到墙上，它就会被删除，并且客户端收到的唯一更新被删除，而不是之前飞向墙壁的更新，所以客户看到镜头在真正撞到墙上之前 1/10 秒消失在半空中。
有了这些每个对象的小信息，就可以很容易地区分新信息和旧信息。此外，只有实际更改的对象才会调用更新 API，因此保持不变的对象（例如墙壁或非活动平台）甚至不需要执行这样的差异。此外，服务器可以通过不向客户端发送对象来进一步保存已发送的信息，这些对象在客户端出现之前是不可见的。例如，在 Quake2 中，一个关卡被划分为多个视图区域，如果一个区域（以及其中的所有对象）之间的所有门都关闭，则该区域（以及其中的所有对象）被认为与另一个区域"out of view"。
请记住，服务器不需要客户端有完整的游戏状态，只需要一个场景图，这需要简单得多的序列化，绝对不需要指针（在 Quake 中，它实际上保存在一个静态的-大小的数组，这也限制了游戏中对象的最大数量。
除此之外，还有 UI 玩家的生命值、弹药等数据。同样，每个玩家只会收到发送给他们自己的生命值和弹药，而不是服务器上每个人的。服务器没有理由共享该数据。
更新：
为了确保获得最准确的信息，我仔细检查了代码。这是基于 Quake3，而不是 Quake Live，所以有些事情可能会有所不同。发送到客户端的信息本质上封装在一个称为 snapshot_t. This contains a single playerState_t for the current player, and an array of 256 entityState_t 的结构中，用于可见游戏实体，以及一些额外的整数和一个表示 "visible areas".[=21= 位掩码的字节数组。 ]
entityState_t依次由22个整数、4个向量和2条轨迹组成。 "trajectory" 是一种数据结构，用于表示对象在没有任何反应时通过 space 的移动，例如弹道运动，或直线飞行。是2个整数，2个向量，1个枚举，概念上可以存储为一个小整数。
playerState_t 稍微大一点，包含大约 34 个整数、大约 8 个大小从 2 到 16 不等的整数数组和 4 个向量。这包含从武器的当前动画帧到玩家物品栏到玩家发出的声音的所有内容。
由于使用的结构具有预设大小和结构，因此制作一个简单的手动 "diff" 函数，比较每个成员，对于每个成员来说相当简单。但是，据我所知，entityState_t 和 playerState_t 只是全部发送，而不是部分发送。唯一 "delta"ed 是发送哪些实体，作为 snapshot_t.
虽然快照最多可包含 256 个实体，但游戏本身最多可包含 1024 个实体。这意味着从客户端的角度来看，在单个帧中只能更新 25% 的对象（任何更多都会导致臭名昭著的 "packet overflow" 错误）。服务器简单地跟踪哪些对象进行了有意义的移动，并发送这些对象。它比执行实际差异要快得多 - 只需发送自身调用 "update" 且位于玩家可见区域位掩码内的任何对象。但从理论上讲，手写每个结构的差异并不会那么难。
为了团队健康，虽然 Quake3 似乎没有这样做，所以我只能推测它是如何在 Quake Live 中完成的。有两种选择：发送所有 playerState_t 结构，因为它们最多有 64 个，或者在 playerState_t 中添加另一个数组以保持团队 HP，因为它只有 64 个整数。后者的可能性更大。
为了保持对象数组在客户端和服务器之间同步，每个实体都有一个从 0 到 1023 的实体索引，它作为消息的一部分从服务器发送到客户端。当客户端收到一个包含 256 个实体的数组时，它会遍历该数组，从每个实体中读取索引字段，并在其本地存储的实体数组中更新读取索引处的实体。