В этой статье я попробую рассказать о способе хранения уровней в ROM-памяти картриджей для приставки NES.
Я опишу все основные способы и подробно остановлюсь на наиболее часто используемом (из нескольких десятков исследованных мной игр он встречался практически в каждой).

Данный способ я назвал «блочным» (оговорюсь, что многие термины в статье были придуманы мной, так как материалов на данную тему на русском нет; после исследования нескольких игр я занялся изучением англоязычных материалов и документации к редакторам игр для старых платформ, тогда уже нашлись некоторые аналогии, в таких случаях буду приводить свои термины с объяснением их значения и их английские версии). В качестве примеров я буду приводить уровни из игры «Darkwing Duck», а также других игр компании «Capcom», разобранных мной несколько лет назад.

Я постараюсь пропустить описание использования дизассемблера и техническую часть исследования (если будет интерес, можно сделать на эту тему отдельную статью), а остановлюсь на описании, как именно разработчики хранили данные. Зная, что именно искать, найти это внутри образа ROM станет намного проще. Бонусом я покажу готовый редактор уровней и несколько созданных на нём хаков классических NES-игр.

Итак, начнём описание, как положено исследователям кода, снизу вверх.

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

Я лишь опишу в нескольких предложениях происходящее тут и перейду к более интересным вещам.
Видеопроцессор NES имеет несколько экранных страниц — одна из них отображается на экране. В экранной странице хранятся номера тайлов размером 8x8, которые нужно отобразить (30 рядов по 32 тайла, всего 960 байт) и их атрибуты (дополнительные биты цвета тайлов), на всю страницу уходит 1 килобайт описания, так компактно описывается целый экран. Сами тайлы берутся из знакогенератора (на 256 тайлов размером 8x8 расходуется 4 килобайта памяти, по 16 байт на один тайл), они могут быть расположены как в отдельном видеобанке картриджа, так и копироваться в видеопамять из обычного банка с данными. Для исследователя место их хранения практически не важно. Желающим более подробно разобраться с этой темой могу посоветовать почитать статью от MiGeRa на русском языке

Просмотреть содержимое знакогенераторов видеопроцессора можно с помощью любого эмулятора NES, я буду использовать наиболее продвинутый для исследования игр — FCEUX (на момент написания статьи последняя версия 2.2.2), в нём для этого нужно выбрать пункт меню Debug->PPU Viewer:

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

Как уже упоминалось выше, на описание одного экрана с помощью тайлов уходит 960 байт (30x32 тайлов). Но посмотрите на полную карту первого уровня «Darkwing Duck».

Она состоит из 20 экранов. Если хранить описание всех экранов потайлово, то на сохранение одного уровня уйдёт примерно 18 килобайт, а на всех семи игровых уровней — 131 килобайт. Напоминаю, что это не сама видеопамять в образе игры, а только описание с помощью тайлов видеопамяти игровых экранов! Это больше всего суммарного размера банков данных во всём образе ROM «Чёрного Плаща» (там всего 128 кб суммарно на код и данные и ещё 128 кб на видеобанки). Более того, уровни «Duck Tales 2» содержат до 32 экранов, при том, что образ весит вдвое меньше.

Тут стоит задать себе вопрос, как можно хранить описание экранов экономнее? Что бы вы сделали на месте разработчиков?

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

Сжатие.
Почти не применяется в NES-играх (зато постоянно применяется в играх на Sega Mega Drive и Snes) в основном по причине малого количества доступной оперативной памяти, которая требуется для хранения распакованных данных, а также медленного процессора. Тем не менее, изредка встречается RLE-сжатие
Пример — первая «Contra» (совместно с описанием экранов с помощью блоков, см. дальше 3-й способ про блоки):

Выделенные красным блоки сохранены в образе ROM в виде «7 раз повторить блок с платформой», а синим, соответственно, «3 раза повторить блок с платформой». Можно убедиться в этом, скачав редактор для этой игры.

Стоит заметить, что RLE на NES всё же используют, но не для сжатия описания уровня, а для более подходящих для этого сущностей. Например, сжимают им тайлы, хранящиеся в этом случае в банках данных («Duck Tales 2», та же «Contra»). Распаковка при этом происходит сразу в видеопамять. Также иногда сжимают текстовые данные (подходящими для этого алгоритмами), но для описания уровня на данной платформе это всё же экзотика.

Рисование на чистом холсте.
Данный подход подразумевает то, что большая часть экрана остаётся чистой, поэтому описывать её не надо. Описывается только по каким координатам должны быть нарисованы конкретные объекты. Яркий пример такого подхода — игры серии «Марио»:




При таком подходе в памяти хранятся записи, которые расшифровываются в виде «нарисовать по координатам X,Y объект ЯЩИК». (Вместо «ЯЩИК» может быть любой игровой объект). Всё остальное пространство остаётся залито фоновым цветом и тратить драгоценные байты на его описание не нужно. Получается, что на одну такую запись расходуется всего 3 байта, а на одном экране будет нарисовано всего 5-6 объектов. Конечно, нужно потратить ещё несколько десятков байт на описание самих объектов, но это не идёт ни в какое сравнение с тем, чтобы хранить почти килобайт данных при описании всего экрана тайлами. А если вы присмотритесь к скриншотам повнимательнее, то узнаете страшную тайну «Super Mario Bros.» Облако и куст — это один и тот же объект, но нарисованный с разной палитрой. На что только не пойдут разработчики ради экономии нескольких байт.

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

Блочный
Основной и самый часто встречаемый способ экономии места для сохранения данных об игровых уровнях — блочный, при котором уровень описывается не тайлами 8x8, а большими единицами данных. Сами единицы данных (блоки) могут быть разного размера — самый часто встречаемый для NES размер в 2x2 тайла, т.е. размер блока 16x16 пикселей (в играх на Sega Mega Drive часто встречаются и блоки размером 4x4 тайлов). При этом сами блоки могут быть организованы в большие структуры — макроблоки (2x2 блока, 32x32 пикселей в большинстве случаев).


В левой части картинки показано объединение четырёх тайлов в один блок, в правой части — объединение четырёх блоков в один макроблок луны из первого уровня «Darkwing Duck».
Из скриншота должен быть понятен основной принцип объединения.

Примечание: ромхакеры часто называют блоки «Tiles», а макроблоки — «Tile Sprite Assembly (TSA)», что создаёт путаницу в понятиях тайла как символа/иконки в знакогенераторе и тайла как объединения нескольких других тайлов в одну структуру (TSA первого уровня и второго). Поэтому я позволю себе сохранить введённые мной названия.

В разных играх могут быть разные, но похожие системы блоков и макроблоков. В «Batman» размер макроблока — 2x1, за счёт чего фон выглядит менее блочным, во «Flintstones: Rescue Dino and Hoppy» макроблоки огромны (по 16 блоков), а в «New Ghostbusters 2» нету макроблоков, а комнаты составлены из обычных блоков. Принцип не меняется — уровень сохраняется как массив из чисел, кодирующий номера больших по размеру структур, составленных из более маленьких.

Например, описание первого экрана первого уровня в «Darkwing Duck» начинается в образе ROM по адресу 0x10 (это самое начало образа после 16 байт заголовка). Первые 8 байт — это первая строка экрана, 8 номеров макроблоков, которые будут отображены первыми, можете попробовать изменить их вручную, запустить игру, начать первый уровень и посмотреть результат. Следом описывается вторая строка, третья и так далее, один экран занимает 8 строк, дальше следует описание второго экрана. Описание экранов может идти не в том порядке, в котором они будут встречаться в игре. В каком-то смысле сами игровые экраны тоже можно представить огромными структурами из 8x8 макроблоков, из которых лепится сам уровень (весь уровень в этом случае называется «раскладкой»(англ. layout) игровых экранов). Экран не обязательно может иметь размер 8x8, зачастую встречаются экраны размером 8x6, верхняя и нижняя строка используются игрой для отрисовки интерфейса.

Часто можно увидеть на экране тайлы, которые ни при каких обстоятельствах не могут быть отображены игрой из-за особенностей движка (либо из-за ограничений скроллинга, либо из-за особенностей программирования, например, в «Tiny Toon Adventures» на уровнях ввысоту «съедается» половина макроблока на стыке двух экранов). В некоторых играх нету разделения на экраны, и весь уровень описывается одной большой матрицей индексов макроблоков.

Как узнать из каких структур (макроблоков) состоит уровень конкретной игры?
Для этого нужно найти описание уровня внутри образа ROM с помощью дизассемблера или другим способом и изменить один или несколько байт в этом описании, чтобы посмотреть, что произойдёт на экране:



На картинках — примеры разных размеров макроблоков в разных играх (2x2 тайла в «Chip & Dale 2», 4x4 тайла в «Jungle Book», 4x8 тайлов в «Flintstones Surprise of Dinosaur Peak»).

Ещё раз — всё в уровнях игр на NES описывается блоками (ну, и макроблоками). При этом описание макроблоков чаще всего состоит просто из индексов отдельных блоков (при размере макроблока 2x2 — 4 индекса блока, всего 4 байта, для «Чёрного Плаща» слева-направо и сверху-вниз), а вот описания блоков включают в себя дополнительную информацию — цвет всего блока и его характеристику, является ли блок фоном, платформой, на которой можно стоять, подбираемым предметов или шипами, которые наносят урон и т.п. Разумеется, встречаются игры, в которых данное правило не соблюдается (например, в «Ninja Cats» цвет задаётся сразу для всего макроблока, а в «Chip & Dale 2» информация о типе блока закодирована просто в самом его номере). Другое отличие — порядок хранения частей макроблоков в памяти, они могут идти последовательно (4 байта на описание первого макроблока, затем 4 байта на описание следующего и т.д. зачастую по 256 штук на уровень), либо же хранится отдельно (например, в «Tiny Toon Adventures» сначала хранятся все левые верхние кусочки макроблоков, за ним все левые правые кусочки, потом нижние левые и правые четвертинки соответственно).

Однако общие принципы блочного построения соблюдаются везде, что позволяет, во-первых, быстро находить похожие структуры в разных играх, во-вторых, изучать, в каких играх использовались похожие движки. Так, например, уровни «Darkwing Duck» с точностью до указателей на наборы блоков и макроблоков соотвествуют таковым в игре «Tale Spin» (хотя сам движок взят из «MegaMan 4», в котором наборы блоков и макроблоков были разделены по разным банкам, но с сохранением одинаковых указателей на них), и очень похожи на уровни «Chip & Dale» (отличия только в способах хранения вспомогательной информации уровня — в том, как записывается способ скроллинга экранов и кодов дверей между комнатами). Вторые же «Chip & Dale» сделаны совсем по другому, экраны в них описываются не макроблоками, а обычными блоками размером 2x2, и поэтому описание занимается намного больше места, так что сами экраны на уровнях регулярно повторяются, хотя благодаря дизайнерской работе неподготовленный игрок этого не замечает (в первой зоне первого уровня, например, циклически повторяются всего 3 экрана).

Исследуя игры, я писал для proof-of-concept программу CadEditor, которая отображала бы уровни из образов ROM так, как они выглядят в ходе прохождения игры на консоле.

Со временем она обрастала функционалом редактора, и ромхакеры даже сделали с её помощью несколько замечательных хаков (в основном на «Capcom»-классику), а также с десяток демок.

Вот одно из прохождений хака «Darkwing Duck In Edoropolis»:


Текущая версия редактора позволяет изменять уровни для 50 игр на платформы NES и Sega Mega Drive (для многих игр только по одному уровню, и часто требуется «доработка напильником», так что потребуются знания в ромхакинге).

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

Надеюсь, данная статья позволит желающим немного разобраться в том, как были устроены уровни в старых играх (кстати, не только для NES, но и для остальных приставок с тайловой графикой — Sega Mega Drive, SNES, GBA и другие). Если у читателей возникнет интерес, могу написать ещё несколько статей похожей тематики, например: технический процесс поиска данных об уровнях (с помощью дизассемблера либо скриптов коррапта файлов), отличия в устройстве уровней для сеговских игр, устройство систем анимаций персонажей, поиск объектов на уровнях или создание вспомогательных инструментов для исследования.

Ссылки:
Исходники редактора
Тема на форуме с обсуждением редактора