May. 2nd, 2017

spiiin: (Default)
Felix The Cat - одна из немногих игр для NES, использующая сжатие данных описания уровня.

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

Уровень состоит из блоков 2x2 (с аттрибутами палитры и физики). Блоков используется 128.

Все подуровни описываются одним массивом, это необязательно в движке, но, видимо, так было удобнее разработчикам). Каждая вертикальная линия описывается отдельно, уровень описывается как массив указателей на линии, если линия полностью повторяет предыдущую, просто используется указатель на эту линию. Повторение линий активно используется, где-то 40-50% линий - повторы. Также в указателях на линии несколько бит используются для кодирования объектов.

Линии сжимаются с помощью алгоритма RLE, после чего из сжатых пар (количество повторов блока, номер блока для повтора) образуется словарь и повторы заменяются на слова из словаря. Обычные блоки имеют индексы от 0x00 до 0x7F, слова из словаря нумеруются от 0x80 и дальше, до 124 слов в словаре.

Последние 4 значения 0xFC-0xFF используются для задания второй формы сжатия. Она устроена интереснее и используется на уровнях с мозаичным фоном (например, узоры на стенах пирамид на уровнях 2-2 и 2-3).
В этом случае в начале линии может использоваться команда из двух байт (номер_базовой_линии, кол-во блоков из базовой линии). На уровне используется 4 базовые линии (их номера кодируются от 0xFC до 0xFF), которые описывают зацикленную мозаику. Первые несколько блоков берутся из этой линии, а затем нижняя часть дорисовывается обычным способом.
Пример таких начал линий на скриншоте:



На нём выделены рамками повторяющиеся базовые линии.

Эти три приёма (индексирование линий, RLE-словарь и базовые линии) позволяют сжимать уровни размером в 18 килобайт до 4-5 килобайт.

Tags:

Profile

spiiin: (Default)
spiiin

September 2017

S M T W T F S
     1 2
34 567 89
101112131415 16
17181920212223
24252627282930

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 19th, 2017 11:37 am
Powered by Dreamwidth Studios