Как дельта-сжатие уменьшает объем данных, передаваемых по сети?

Во многих играх используется метод дельта-сжатия, чтобы снизить загружаемую информацию. Я не понимаю, как этот метод на самом деле снижает нагрузку на данные?

Например, скажем, я хочу отправить позицию. vector3Например, без дельта-сжатия я посылаю точную позицию объекта (30, 2, 19). С дельта-сжатием я отправляю vector3с меньшими номерами (0.2, 0.1, 0.04).

Я не понимаю, как это снижает загрузку данных, если оба сообщения vector3- 32-битные для каждого числа с плавающей запятой - 32 * 3 = 96 бит!

Я знаю, что вы можете преобразовать каждое число с плавающей точкой в ​​байт, а затем преобразовать его обратно из байта в число с плавающей точкой, но это вызывает ошибки точности, которые видны.

Есть моменты, когда вы не можете избежать отправки полного состояния игры - например, при загрузке сохраненной многопользовательской игры или когда требуется повторная синхронизация. Но отправки полного состояния обычно можно избежать, и именно здесь начинается дельта-кодирование . Как правило, это все, что касается дельта-сжатия; Ваш пример на самом деле не описывает эту ситуацию. Причина, по которой дельта-сжатие даже упоминается, заключается в том, что наивные реализации часто отправляют состояние, а не дельты, потому что обычно состояние - это то, что хранит любая реализация наивной игры. Дельты - это оптимизация.

С дельтами вы никогда не отправите позиции юнитов, которые вообще не двигались . Это дух этого.

Представьте, что мы годами были друзьями по переписке, и я потерял память (и после прочтения отбросил все ваши письма). Вместо того, чтобы просто продолжать серию писем, как обычно, вы должны написать мне всю историю своей жизни в одном большом письме, чтобы я наверстал упущенное.

В вашем конкретном случае может (в зависимости от вашей кодовой базы) быть возможно использовать меньшее количество битов для кодирования дельт, в отличие от больших битовых диапазонов, необходимых для отправки полного состояния. Скажем, мир имеет много километров в поперечнике, вам может понадобиться 32-разрядное число с плавающей запятой, чтобы точно кодировать позиции, скажем, сантиметр в данной оси. Однако, учитывая максимальную скорость, применимую к объектам, которая может составлять всего пару метров на тик, это может быть выполнимо всего за 8 бит (2 ^ 8 = 256, так что достаточно для хранения максимум 200 см). Конечно, это предполагает фиксированное использование, а не использование с плавающей запятой ... или некоторый тип пополам / четверти с плавающей запятой, как в OpenGL, если вы не хотите суеты с фиксированной запятой.

Вы ошиблись дельтой. Вы смотрите на дельту отдельных элементов. Вы должны думать о дельте всей сцены.

Предположим, у вас есть 100 элементов в вашей сцене, но только 1 из них перемещен. Если вы отправите 100 векторов элементов, 99 из них будут потрачены впустую. Вам действительно нужно только отправить 1.

Теперь предположим, что у вас есть объект JSON, в котором хранятся все ваши векторы элементов. Этот объект синхронизируется между вашим сервером и вашим клиентом. Вместо того, чтобы решать "так и так двигаться?" Вы можете просто сгенерировать следующий тик игры в объекте JSON, создать diff tick100.json tick101.jsonи отправить этот diff. На стороне клиента вы применяете diff к вектору вашего текущего тика, и все готово.

Делая это, вы используете многолетний опыт в обнаружении различий в тексте (или двоичном коде!) И вам не нужно беспокоиться о том, чтобы что-то пропустить самостоятельно. Теперь, в идеале, вы также должны использовать библиотеку, которая делает это за кулисами, чтобы вам было еще проще, как разработчику.

Очень часто другой механизм сжатия сочетается с дельта-кодированием, как, например, арифметическое сжатие.

Эти схемы сжатия работают намного лучше, когда возможные значения сгруппированы предсказуемо. Дельта-кодирование сгруппирует значения около 0.

Вы в целом правы, но упускаете один важный момент.

Сущности в игре описываются многими атрибутами, из которых позиция только одна .

Какие атрибуты? Не нужно слишком много думать, в сетевой игре это может включать:

• Позиция.
• Ориентация.
• Текущий номер кадра.
• Информация о цвете / освещении.
• Прозрачность.
• Модель для использования.
• Текстура для использования.
• Спецэффекты
• И т.п.

Если вы выберете каждый из них в отдельности, вы, безусловно, можете сделать так, чтобы, если в каком-либо конкретном кадре его нужно было изменить, он должен быть передан в полном объеме.

Однако не все эти атрибуты изменяются с одинаковой скоростью .

Модель не меняется? Без дельта-сжатия оно должно быть передано в любом случае. С дельта-сжатием это не должно быть.

Положение и ориентация - два случая, которые более интересны, и обычно состоят из 3 поплавков в каждом. Между любыми заданными двумя кадрами существует вероятность того, что только 1 или 2 из каждого набора из 3 поплавков могут измениться. Двигаться по прямой? Не вращается? Не прыгать? Это все случаи, когда без дельта-сжатия вы должны ретранслировать полностью, но при дельта-сжатии вам нужно только ретранслировать то, что изменяется.

Вы правы, что простое вычисление дельты само по себе, с результатом, сохраненным в той же структуре данных размера, что и операнды и переданной без какой-либо дальнейшей обработки, не сохранит трафик.

Однако есть два способа, которыми хорошо спроектированная система, основанная на дельтах, может сэкономить трафик.

Во-первых, во многих случаях дельта будет равна нулю. Вы можете разработать свой протокол так, чтобы, если дельта была нулевой, вы вообще не отправляли его. Очевидно, что в этом есть некоторые накладные расходы, поскольку вы должны указать, что вы отправляете или не отправляете, но в целом это, вероятно, будет большой победой.

Во-вторых, дельты обычно будут иметь гораздо меньший диапазон значений, чем исходные числа. и этот диапазон будет сосредоточен на нуле. Это может быть использовано либо путем использования меньшего типа данных для большинства дельт, либо путем передачи всего потока данных через алгоритм сжатия общего назначения.

Хотя большинство ответов говорят о том, что дельта-кодирование сводится только к отправке изменений в состояние в целом, есть еще одна вещь, называемая «дельта-кодирование», которая может использоваться в качестве фильтра для уменьшения объема данных, которые необходимо сжать в полном состоянии. Обновите также, что может быть, из-за чего возникла путаница в вопросе.

При кодировании вектора чисел вы можете в некоторых случаях (например, целые числа, перечисления и т. Д.) Использовать кодирование переменной байта для отдельных элементов, а в некоторых из этих случаев вы можете еще больше уменьшить объем данных, который требуется каждому элементу. если вы храните его как текущие суммы или как минимальное значение, а также разницу между каждым значением и этим минимумом.

Например, если вы хотите кодировать вектор, {68923, 69012, 69013, 69015}вы можете дельта-кодировать его как {68923, 89, 1, 2}. Используя тривиальное кодирование переменной байта, где вы сохраняете 7 бит данных на байт и используете один бит, чтобы указать, что есть еще один байт, каждому из отдельных элементов в массиве потребуется 3 байта для его передачи, но версия с дельта-кодированием потребует только 3 байта для первого элемента и 1 байт для остальных элементов; в зависимости от типов данных, которые вы сериализуете, это может привести к довольно впечатляющей экономии.

Однако это скорее оптимизация сериализации, а не то, что обычно подразумевается, когда мы говорим о «дельта-кодировании», когда речь идет о потоковой передаче произвольных данных как части игрового состояния (или видео или тому подобного); другие ответы уже адекватно объясняют это.

Стоит также отметить, что алгоритмы сжатия лучше справляются со своей задачей. В других ответах упоминается, что либо большинство ваших элементов остаются одинаковыми между двумя состояниями, либо значения изменяются незначительно. В обоих этих случаях применение алгоритма сжатия к разнице вашего вектора чисел дает вам значительную экономию. Даже если вы не применяете никакой дополнительной логики к вектору, например, удаляете элементы 0.

Вот пример в Python:

import numpy as np
import zlib
import json
import array


state1 = np.random.random(int(1e6))

diff12 = np.r_[np.random.random(int(0.1e6)), np.zeros(int(0.9e6))]
np.random.shuffle(diff12) # shuffle so we don't cheat by having all 0s one after another
state2 = state1 + diff12

state3 = state2 + np.random.random(int(1e6)) * 1e-6
diff23 = state3 - state2

def compressed_size(nrs):
    serialized = zlib.compress(array.array("d", nrs).tostring())
    return len(serialized)/(1024**2)


print("Only 10% of elements change for state2")
print("Compressed size of diff12: {:.2f}MB".format(compressed_size(diff12)))
print("Compressed size of state2: {:.2f}MB".format(compressed_size(state2)))

print("All elements change by a small value for state3")
print("Compressed size of diff23: {:.2f}MB".format(compressed_size(diff23)))
print("Compressed size of state3: {:.2f}MB".format(compressed_size(state3)))

Что дает мне:

Only 10% of elements change for state2
Compressed size of diff12: 0.90MB
Compressed size of state2: 7.20MB
All elements change by a small value for state3
Compressed size of diff23: 5.28MB
Compressed size of state3: 7.20MB

Если ваша позиция хранится в vector3, но фактическая сущность может перемещаться только на несколько целых чисел за раз. Тогда отправлять его в байтах будет лучше, чем отправлять в целых числах.

Текущая позиция: 23009.0, 1.0, 2342.0 (3 числа с плавающей запятой)
Новая позиция: 23010.0, 1.0, 2341.0 (3 числа с плавающей запятой)
Дельта: 1, 0, -1 (3 байта)

Вместо того, чтобы отправлять точную позицию каждый раз, мы отправляем дельту.

Дельта-сжатие - это сжатие дельта-кодированных значений. Дельта-кодирование - это преобразование, которое производит различное статистическое распределение чисел. Если распределение благоприятно для выбранного алгоритма сжатия, оно уменьшает количество данных. Он очень хорошо работает в такой системе, как игра, в которой сущности перемещаются лишь незначительно между двумя обновлениями.

Допустим, у вас есть 100 объектов в 2D. На большой сетке 512 x 512. Для примера рассмотрим только целые числа. Это два целых числа на одну сущность или 200 чисел.

Между двумя обновлениями все наши позиции меняются на 0, 1, -1, 2 или -2. Было 100 экземпляров 0, 33 экземпляра 1 и -1 и только 17 экземпляров 2 и -2. Это довольно часто. Мы выбираем кодирование Хаффмана для сжатия.

Дерево Хаффмана для этого будет:

 0  0
-1  100
 1  101
 2  110
-2  1110

Все ваши 0 будут закодированы как один бит. Это всего лишь 100 бит. 66 значений будут закодированы как 3 бита, и только 34 значения - как 4 бита. Это 434 бита или 55 байтов. Плюс небольшие накладные расходы, чтобы спасти наше дерево картирования, так как дерево крошечное. Обратите внимание, что для кодирования 5 чисел необходимо 3 бита. Мы обменяли здесь возможность использовать 1 бит для «0» для необходимости использовать 4 бита для «-2».

Теперь сравните это с отправкой 200 произвольных чисел. Если ваши сущности не могут быть на одной плитке, вам почти гарантировано, что вы получите плохое статистическое распределение. В лучшем случае было бы 100 уникальных чисел (все на одном X с разными Y). Это как минимум 7 бит на число (175 байт) и очень сложно для любого алгоритма сжатия.

Дельта-сжатие работает в особом случае, когда ваши сущности меняются незначительно. Если у вас много уникальных изменений, дельта-кодирование не поможет.

Обратите внимание, что дельта-кодирование и сжатие используются и в других ситуациях с другими преобразованиями.

MPEG разбивает изображение на маленькие квадраты, и если часть изображения перемещается, сохраняются только движение и изменение яркости. В фильме с частотой 25 кадров в секунду очень мало изменений между кадрами. Опять дельта кодирование + сжатие. Лучше всего подходит для статических сцен.