Какие методы/алгоритмы дельта-сжатия состояния приложения/игры существуют?

Я бы предложил отступить на секунду и осмотреться, чтобы найти потенциально лучшее решение.

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

Для краткости предлагаю рассмотреть два рисунка (ссылка на источник будет дана).

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

Или вы можете создать соответствующую команду/действие и позволить исполнителю вашей команды обработать ее, изменяя состояние асинхронно:

Может показаться, что разница довольно мала, но второй подход позволяет вам:

• чтобы избежать каких-либо условий гонки и безопасно обновлять состояние, введя очередь для действий пользователя.
• обрабатывать действия из нескольких источников (нужно только правильно их отсортировать)

Я только что описал Шаблон команды, который может оказаться очень полезным. Это подводит нас к идее computed state. Если поведение команд детерминировано (как и должно быть), чтобы получить новое состояние, вам просто нужно предыдущее состояние и команда.

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

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

Такой подход также позволяет упростить восстановление состояния и т. д., потому что выполнение действия может быть действительно быстрее по сравнению с последовательностью generate new state, compare to the previous one, generate diff, compress diff, send diff, apply diff.

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

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

Арифметическое кодирование, Основное дерево, скорее всего, поможет. Вот и идея и реализация, с которой можно начать:

  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;
}

Последнее слово: не раскрывайте состояние, не передавайте его, а вместо этого вычисляйте. Такой подход будет быстрее, проще в реализации и отладке.

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

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

Но сравнение объектов JSON не обязательно должно происходить побитно. (Если необходимо, это то же самое, что сравнивать две битовые строки.) Сравнение может происходить на более высоком уровне. Один из способов вычислить разницу между двумя произвольными объектами JSON — написать функцию, которая принимает A и B и:

• Если аргументы имеют разные типы, верните «A изменено на B».
• Если аргументы имеют один и тот же примитивный тип, ничего не возвращать, если они одинаковы, в противном случае возвращать «A изменено на B».
• Если оба аргумента являются словарями, элементы, чьи ключи находятся только в A, удаляются, а чьи ключи находятся только в B, добавляются. Для элементов с одинаковым ключом сравнивайте рекурсивно.
• Если оба аргумента являются массивами, вычислить самую длинную общую подпоследовательность A и B (равенство двух элементов также можно проверить с помощью рекурсивной функции) и найти элементы только в A или B. Таким образом, элементы только в A удаляются , добавляются элементы только в B. Или, может быть, неравные элементы также можно сравнивать рекурсивно, но единственный эффективный способ, о котором я могу думать, требует наличия способа (например, записи идентификаторов) для определения того, какой элемент в A соответствует какому элементу в B, и сравнить элемент с соответствующим элементом.

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