В процессе разработки прототипа игры evacuation-simulator возникла необходимость сохранять и передавать уровни, созданные во встроенном редакторе, но ввиду того, что игра является статическим веб приложением, сохранять уровни на сервере не было возможности. Единственным решением оказалось сохранять всю информацию об устройстве уровня непосредственно в url - ссылку на этот уровень.
Данные уровня состоят из нескольких массивов координат - массив стен, массив стрелок, массив людей и тд. Все массивы содержат координаты, при этом все объекты, кроме людей, находятся в сетке, а значит, координаты целые, и относительно небольшие(от 0 до 14), а люди располагаются по координатам в пикселях в игровом пространстве (от 0 до 700).
Сначала передадим уровень как есть - закодировав его в json, после чего переведя в base64, и передав в url параметр. Но при таком способе достаточно большой уровень(на котором будет производиться тестирование далее) занимает 6216 символов.
Первый самый простой способ уменьшения размера - использование бинарного формата, в качестве которого был взят protobuf. Одно из важных его преимуществ, 7-битное кодирование, которое представляет целые числа до 128 одним байтом, числа до 128 * 128 двумя байтами и тд, один бит байта тут используется для определения, является ли данный байт конечным, или далее следует ещё один. В итоге, простое использование protobuf уменьшает размер тестируемого уровня до 2130 символов (почти в 3 раза).
Стоит отметить, что применение встроенных в JavaScript функций для кодирования в base64 работают для строк, но не для байтовых последовательностей, так что пришлось использовать стороннюю реализацию (в слегка модифицированном виде), способную работать с Uint8Array.
Но protobuf имеет один существенный недостаток - при использовании message с полями x и y для кодирования точек, каждое значение в protobuf имеет перед собой идентификатор - ключ, по которому определяется, к какой части сообщения принадлежит значение. В итоге, перед каждой координатой располагается индекс массива, в котором хранится точка, и индекс, указывающий, x или y координатой является значение. Такое кодирование добавляет два байта системной информации к каждой координате, которые в большинстве случаев занимают 1 байт.
Решением этой проблемы стала ручная сериализация - все массивы координат упаковывались в массив чисел, в следующем простом формате
[<len1>,<x1>,<y1>,<x2>,<y2>,<x3>,<y3>...,<len2>,<x1>,<y1>,<x2>,<y2>,<x3>,<y3>...]
Сперва идёт длина массива, затем его элементы, затем длина следующего, и так с каждым исходным массивом. После чего получившаяся последовательность упаковывалась в protobuf, но уже как массив чисел, с которым он умеет работать, не предваряя каждое значение дополнительным идентификатором; теперь от protobuf мы получили только преимущество 7-битного кодирования. Размер уровня стал 720 символов, что уже приемлемо для хранения в url.
Теперь, если вывести последовательность байт, которые мы получили после кодирования в protobuf, получится последовательность такого вида:
[5, 3, 143, 3, 135, 3, 172, 3, 87, 145, 5, 57, 135, 5, 155, 1, 212, 4, 170, 1, 212,
4, 189, 1, 212, 4, 213, 1, 212, 4, 156, 1, 236, 4, 172, 1, 241, 4, 191, 1, 245, 4,
152, 1, 138, 5, 176, 1, 141, 5, 204, 1, 135, 5, 137, 2, 217, 4, 137, 2, 248, 4,
135, 3, 222, 4, 135, 3, 239, 4, 138, 3, 142, 5, 134, 2, 164, 4, 167, 2, 172, 4,
130, 3, 166, 4, 199, 3, 186, 4, 231, 3, 238, 4, 175, 4, 132, 5, 239, 4, 136, 5,
238, 4, 220, 4, 211, 4, 200, 3, 247, 4, 201, 3, 212, 4, 212, 1, 135, 5, 214,
1, 244, 4, 241, 1, 212, 4, 228, 2, 247, 4, 247, 2, 67, 248, 2, 85, 238, 2,
55, 160, 2, 91, 161, 2, 58, 240, 1, 90, 240, 1, 157, 2, 174, 1, 233, 2, 152,
1, 255, 2, 153, 1, 0, 1, 4, 9, 3, 6, 2, 1, 2, 13, 2, 70, 1, 14, 2, 14, 3,
14, 5, 14, 6, 14, 7, 14, 8, 14, 9, 14, 10, 14, 11, 14, 12, 14, 13, 14, 13,
2, 12, 2, 11, 2, 1, 2, 2, 2, 3, 2, 4, 3, 5, 3, 7, 3, 8, 3, 9, 3, 10, 3, 5,
6, 6, 6, 7, 6, 8, 6, 9, 6, 5, 10, 6, 10, 7, 10, 8, 10, 9, 10, 4, 7, 4, 9, 4,
14, 4, 10, 5, 12, 8, 11, 5, 11, 6, 11, 6, 12, 7, 12, 1, 9, 1, 7, 2, 7, 1, 3,
1, 4, 2, 4, 13, 4, 12, 4, 13, 3, 9, 11, 10, 11, 12, 13, 13, 13, 12, 12, 13,
12, 1, 11, 2, 11, 12, 7, 13, 7, 12, 9, 13, 9, 2, 13, 7, 4, 8, 4, 5, 4, 4, 4,
63, 1, 13, 5, 13, 9, 13, 14, 13, 14, 12, 14, 11, 14, 10, 14, 9, 14, 8, 14, 7,
14, 6, 14, 5, 14, 4, 14, 3, 14, 2, 0, 1, 4, 2, 11, 2, 0, 3, 1, 4, 0, 5, 0, 6,
1, 5, 1, 6, 0, 7, 1, 7, 1, 8, 1, 9, 1, 10, 0, 11, 1, 11, 1, 12, 4, 6, 4, 7,
11, 6, 11, 8, 11, 7, 4, 8, 4, 9, 11, 9, 5, 7, 5, 8, 5, 12, 5, 11, 9, 12, 9,
11, 3, 5, 3, 6, 3, 7, 3, 8, 1, 3, 12, 5, 12, 7, 11, 12, 12, 9, 12, 10, 12,
4, 2, 4, 3, 13, 2, 12, 11, 13, 7, 3, 6, 3]
Можно заметить, вначале байты чередуются - маленькое значение с произвольным, а после какого-то значения все становятся маленькими. Это связано с описанной в начале статьи структурой уровня - вначале идут координаты людей, старший байт которых довольно маленький, а младший может иметь любое значение. Затем массивы стен, стрелок и огня в координатах сетки - значения от 0 до 14.
Универсальным способом сжатия таких неравномерно распределённых данных является энтропийное кодирование. Одним из самых простых таких алгоритмов является код Хаффмана. Поскольку распределение всегда остаётся примерно одинаковым, нет необходимости передавать таблицу кодов вместе с уровнем, её можно один раз статически сгенерировать, после чего использовать и для кодирования, и для декодирования уровней.
Для этих целей был специально составлен уровень, забитый различными предметами примерно в тех пропорциях, в которых они используются в реальности, но в сильно больших количествах. На этом уровне собиралась частотная статистика встречаемости байтов. После генерации таблицы, и применения её на тестовом уровне, получаем размер около 485 символов.
Вывод
Как видно, простой json файл с числовыми данными, при некоторых усилиях получилось сжать почти в 13 раз. Более того, возможно ещё большее сжатие, в частности, можно было применить более эффективный вариант энтропийного кодирования, такой как арифметический код, который при правильно подобранном частотном алгоритме, мог бы cжать данные ещё в некоторое количество раз.