Spiiin's blog

Предыдущая часть

Duck Tales 2 - одна из технически наиболее продвинутых игр Capcom на NES.

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

Работа алгоритма понятна без дизассемблера, но архив разбит на 4 части (это сделано, потому что 1/4 часть видеопамяти общая для всех банков - там хранятся шрифт игры и стандартные для всех уровней объекты - бочки и сундуки), так что для сборки видеобанка надо написать логгер, который отследит начала частей архива в ROM. После небольшого анализа кода выясняется, что процедуру распаковки можно остановить по адресу PC == $CFC0. В этот момент в ячейках оперативной памяти хранится:
$67-$68 - адрес считывания данных.
$69 - банк считывания данных.
$6A-$6B - адрес записи в видеопамять.
$6C - первый считанный байт архива (символ повтора).

Для сбора информации о архивах можно использовать Lua-скрипт, который будет логгировать вызовы процедуры распаковки и копировать содержимое ячеек памяти в файл.
Основа Lua-скрипта универсальная и подходит для логгирования данных под любой поддерживающий скрипты эмулятор (требуется модуль binio).
https://gist.github.com/spiiin/88f80daaac6ab6bf5822

Чтобы со старта попасть в секретный бонусный уровень, можно в момент выбора уровня записать по адресу $С8 номер уровня 5.

Теперь надо последовательно запустить все уровни, чтобы получить лог с адресами архивов.
https://gist.github.com/spiiin/8a5107f473b42cb17c62
(если процедура декомпрессии не вызывается достаточно долго, в логах ставится разделитель, это позволяет разделять архивы конкретных уровней).

Область видеопамяти, в которую сохраняются фоны уровня - 0x0000 - 0x1000 (4 килобайта). По логу видно, что некоторые участки памяти после первичной распаковки частично переписываются другими.

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

def compress(repeatSym, data): 
  res = [chr(repeatSym)]
  grps = ["".join(grp) for num, grp in itertools.groupby(data)]
  for grp in grps: if len(grp)<3: res.extend(grp) else: res.append(chr(repeatSym))
  res.append(chr(len(grp)))
  res.append(grp[0])
  res.append(chr(repeatSym))
  res.append(chr(0))
  return res

Полный текст модуля.

Кроме используемых банков в игре есть неиспользуемый архив с графикой белки-летяги (найден Ti_):

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

Алгоритм эффективного упорядочивания тайлов заключается в склеивании концов тайлов с одинаковыми байтами (один тайл видеопамяти на NES кодируется 16 байтами, для таких массивов и надо считать повторы байт в голове и хвосте массива). Так получатся более длинные цепочки из повторяющихся байт, а, следовательно, повысится эффективность сжатия. Получается бонус в 10-20 байт.

Суть алгоритма:

• Находим для всех массивов, какой длины у него есть “торчащие” голова и хвост из одинаковых элементов. Получаем массив из туплов - голова, хвост, индекс элемента.
• Выбираем самую лучшую пару для соединения - ищем, какие голова и хвост могут образовать самую длинную цепочку
• Соединяем два элемента массива в один - склеиваем голову и хвост, получаем элемент с новыми концами.
  Запоминаем также, какая пара элементов была склеена - храним список того, какие именно элементы были соединены.
• Повторяем шаг 2 до тех пор, пока это возможно - пока будут находится пары элементов, у которых значение головы первого элемента пары совпадает со значением хвоста второго элемента.

• Когда таких пар не нашлось - список невозможно дальше склеивать, теперь проходим по нему слева направо и восстанавливаем все списки индексов элементов - это лучшая последовательность для сжатия её алгоритмом RLE.

  https://gist.github.com/spiiin/2ca831a508605c1706c3

  Результаты переноса видеопамяти из игры Duck Tales в Duck Tales 2: