В моей третьей статье про NES-игры я покажу техники, используемые для создания игровых движков, а именно реализацию скроллинга экрана, переключение банков памяти, организацию списка объектов, устройство системы анимаций персонажей, функции обновления игровых объектов (и обработку столкновений), устройство главной карты. Чтобы не быть голословным в описаниях, я буду приводить дизассемблированный код из конкретных игр (любимый всем «Darkwing Duck», с отсылками к «Chip & Dale» и «Duck Tales»), без него в этой статье не обойтись. В качестве примера рассматривается движок от «Capcom», на модификациях которого работает как минимум пара десятков игр.

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

Для исследования будет использоваться встроенный в эмулятор FCEUX дизассемблер, а также известный дизассемблер IDA для работы с базой кода (можно обойтись и без него, воспользовавшись блокнотом и ручкой). Вот здесь(цикл «Документация к FCEUd») есть несколько статей по использованию отладчика. Идея поиска известна, наверное, любому, кто занимался реверс-инжинирингом — нужно найти в памяти любой адрес, назначение которого известно и относится прямо или косвенно к исследуемой функциональности, и установить на этот адрес точку остановки в отладчике. Дальше исследователь запускает игру, ожидает, когда точка остановки сработает и изучает код, который привёл к срабатыванию, получая таким образом информацию о том, что происходит у игры «под капотом». Далее будут приводится примеры исследования работы движка.

Реализация скроллинга экрана

Если игра имеет больше одного экрана на уровень, то при приближении игрока к его границам необходимо постоянно обновлять картинку. Можно запустить игру «Darkwing Duck» в эмуляторе, загрузить первый уровень и открыть окно просмотра экранных страниц Debug->Name table viewer. Если теперь идти вправо по одному шагу и наблюдать изменения в этом окне, то можно заметить, что игра обновляет по 2 блока (2x2 тайла каждой, всего 8 тайлов видеопамяти) каждый шаг ЧП:


(На этот раз для разнообразия я буду использовать скриншоты из хаков игр)

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

Можно проверить, как устроен скроллинг технически. Для этого в отладчике надо установить точку остановки на запись в видеопамять на диапазон адресов $2007-$23BF (опция PPU MEM в отладчике) в момент, когда уровень уже загружен. Дальше запускается игра, и ЧП отправляется вперёд для того, чтобы скроллинг сработал и эмулятор остановил игру и показал окно отладчика:

ROM:C119 loc_C119:; CODE XREF: ROM:C137
ROM:C119 LDA $360,X
ROM:C11C BMI locret_C139
ROM:C11E STA byte_2006
ROM:C121 LDA $361,X
ROM:C124 STA byte_2006
ROM:C127 LDY $362,X
ROM:C12A
ROM:C12A loc_C12A:; CODE XREF: ROM:C132
ROM:C12A LDA $363,X
>ROM:C12D STA byte_2007
ROM:C130 INX
ROM:C131 DEY
ROM:C132 BPL loc_C12A
ROM:C134 INX
ROM:C135 INX
ROM:C136 INX
ROM:C137 BNE loc_C119

Общение с видеопамятью в NES происходит через адресное пространство процессора, адрес $2006 служит для адресации, а адрес $2007 — для чтения и записи значений в память. Тогда можно понять логику работы кода выше — это функция чтения записей о том, откуда, куда и сколько байт скопировать в видеопамять из оперативной памяти. Сами записи начинаются с адреса $360 и имеют такой формат:
COPY_TO_VIDEO_REC|стоп байт 0xFF, где COPY_TO_VIDEO_REC = (адрес_записи_в_видеопамять, сколько байт копировать, байты для копирования).

Дальше точка остановки переставляется на запись в область 0x360-0x36F, в которой хранятся эти данные и отладчик показывает большую функцию скролла по адресу $DB40-$DD09 (457 байт). Функция многоцелевая и используется во всех видах скроллинга в игре (вправо, вверх, вниз), в ней много ветвлений в зависимости от установки различных бит. На входе функции — значение скроллинга персонажа в ячейках $23 и $25 (двухбайтовое).
Дальше я пропущу часть исследования (оно заключается в перестановке точек остановки и проверке откуда приходят данные изначально и каким трансформациям подвергаются) и выложу граф функции трансформации:



Как видно по графу, я не разбирал всю функцию, а сосредоточился на её нижней части — по адресу $140 и дальше в оперативной памяти находятся выбранные индексы блоков из тех макроблоков, которые будут отображены на экране, а затем, из этого ряда данных составляются записи для копирования в видеопамять (ряд 0x360), этого достаточно, чтобы понять устройство именно скроллинга, верхняя же часть описывает трансформацию координат и выборку данных о номере активного экрана в образе ROM.

В других движках устройство похожее — существует ряд адресов для копирования и ряд для хранения индексов макроблоков, иногда расположенный по тому же адресу.

Конфиги уровней и переключение банков памяти

Разбираясь с потоком данных об уровне всё дальше, можно прийти к исходным местам их хранения — месту записи их в образе ROM. Часто записи о данных всех уровней сгруппированы вместе и называются конфигами уровней.
Для примера, конфиги уровней и дверей для игры «Chip & Dale»:
Описание дверей (25 записей)

1E673 - индекс экрана в раскладке.
1E68B - Y экрана.
1E6A3 - X экрана.
1E6BB - номер блока графики для фона.
1E6D3 - номер блока графики для объектов.
1E6EB - номер используемой палитры.
1E703 - номер второй палитры (влияет на объекты типа Вжика и Рокки и и используется для блинка).
1E71B - побитовое описание блинка цветов (из первой и второй палитры).
1E734 - позиция появления игроков Y.
1E74C - позиция появления игроков X.

Описание уровней (15 записей)

101B2, 101A3 - указатели на старшие байты координаты X объектов (номера экранов).
101D0, 101C1 - указатели на младшие байты координаты X объектов (позиция на экране).
101EE, 101DF - указатели на старшие байты координаты Y объектов (номера экранов).
1020C, 101FD - указатели на младшие байты координаты Y объектов (позиция на экране).
1022A, 1021B - указатели на тип объектов.
10248, 10239 - указатели на данные о направлении скролла для каждой линии высоты уровня.
1E201  - индекс в описании больших блоков уровня (совпадают для пар уровней).
1E26A - номер трека на уровне.
1E2A6, 1E297 - указатели на раскладку (форма уровня).
1E2C4, 1E2B5 - указатели на описание (направление скролла + номер двери).
1E210 - номер в раскладке стартовой комнаты.
1E23D - номер блока графики для объектов (8x=enemy gfx, 9x=tile gfx).
1E24C - номер блока графики для фона (8x=enemy gfx, 9x=tile gfx).
1E25B - номер палитры, используемой на уровне.
1E279 - номер второй палитры, используемой на уровне.
1E288 - побитовое описание блинка цветов (из первой и второй палитры).
1E22E - размер по высоте раскладки уровня.
1E21F - размер по ширине раскладки уровня.

Отсюда у наблюдательных читателей возникает вопрос, почему все указатели занимают всего два байта, ведь с помощью 16 бит можно адресовать всего 64 кб памяти, а размер образов ROM бывает и намного больше? Ответ — в NES для обхода этого ограничения используются специальные микросхемы в картриджах, которые управляют подключением разных банков памяти, мапперы. Они определяют, из какого именно банка памяти ROM будет производится чтение при обращении к адресному пространству процессора, отвечающему за чтение из ROM. Про указатели на NES можно почитать в статье cah4e3'а.

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

Из такой архитектуры следуют два возможных способа распределения данных по банкам — либо хранить все данные одного уровня в одном банке, либо хранить все наборы данных одного типа в одном банке (макроблоки в одном, блоки в другом, экраны в третьем). В различных движках встречается как первый, так и второй подход. В «Capcom» чаще всего хранят данные одного уровня в одном банке — в «Mega Man 4», например, даже все указатели на блоки и макроблоки одинаковы, то есть при переключении банков данные маппятся на одни и те же адреса в адресном пространстве процессора. Даже при этом, однако, переключение банков осуществляется несколько раз за кадр, то есть нужные данные всё равно разбросаны по разным местам образа ROM.

Организация списка объектов

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

• При появлении врага на экране замедлить время и проверить его X,Y координаты или другие параметры (Меню Tools->Ram Search...). Так обнаруживается, что параметры врагов на экране для «Darkwing Duck» в RAM хранятся столбиками 0x580 (для первого объета, 0x581 для второго, 0x582 — для третьего и т. д.) — направление движения объекта, 0x5A0 — оставшееся здоровье и т.п. Среди них можно обнаружить и номер объекта
• Засечь счётчик объектов, которые появляются на экране. Он увеличивается на 1 при появлении следующего объекта. Его, кстати, можно увидеть без поиска в памяти, а с прямо глядя в оперативную память (в FCEUX это удобно благодаря фиче подветки недавно изменённых ячеек (меню Tool->Hex Editor):
  
  
  Ячейка 0x70 увеличивается одновременно с появлением на экране нового объекта (и в «Darkwing Duck», и в «Chip & Dale»).
  
• В играх с начислением очков за убийство врагов можно поставить точки остановки на увеличение счётчика очков и так выйти на функцию начисления очков, которая также использует данные о номере врага для рассчёта количества
• Другие способы, ограниченные только фантазией исследователя

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

1 уровень — 0x10315-0x10347
2 уровень — 0x10438-0x10473
3 уровень — 0x10584-0x105C7
6 уровень — 0x106A0-0x106D5
4 уровень — 0x10816-0x10865
5 уровень — 0x10962-0x109A0
7 уровень — 0x10A89-0x10AC2

После некоторых экспериментов по коррапту данных в окрестности этих адресов становится понятна и их структура — перед списком самих объектов лежат 4 массива такой же длины, с пара координат X и Y объектов. Старший байт указывает координату экрана, на которой появляется объект, а младший — координату самого объекта на экране. Таким образом, полностью на описание позиции и типа объекта уходит по 5 байт.
Также становится понятно, что объекты в списке должны быть отсортированы в том порядке, в котором они будут появляться на экране, так как в движке существует процедура, которая проверяет появление следующего объекта в списке, и только потом увеличивает счётчик на 1 и проверяет следующий объект. Если он находится сзади игрока (а скроллинга назад в игре нет), то он не появится на экране никогда. Существуют ещё несколько особенностей движка, касающихся списка объектов, которые нужно учитывать при сортировке объектов, например, после входа в двери счётчик обнуляется и движок ищет первый подходящий по координате Y экрана объект в списке, начиная с первого. Это позволяет строить уровни с несколькими альтернативными переходами, которых не было в оригинальной игре.

В других движках устройство списка объектов очень похожее, иногда встречаются особенности, такие как кодирование одной из координат объекта одним байтом (либо домножая его на константу, либо используя фиксированный адрес в качестве базы для целого набора объектов, например, в «Duck Tales 2») или переменная длина записей в списке объектов (пример — «New Ghostbusters 2», там для врагов хранятся координаты, тогда как для дверей дополнительно ещё и комната, в которую будет совершён переход).

Раскодировка всех типов объектов для «Duck Tales»: gist.github.com/spiiin/5524555

Устройство системы анимаций

Номер объекта является не просто константой, а индексом в массиве записей о всех объектах.
Точка остановки на запись по диапазону адресов 0x05A4 — 0x05AF (в нём хранятся номера объектов на экране) показывает место, откуда загружаются характеристики объектов:

LDA (06), y.  [cpu addr 0x8C57->rom addr 0x10C67] -  4 байта описания (жизни)
LDA (04), y.  [cpu addr 0x8AB3->rom addr 0x10AC0] -  4 байта описания (характеристики)

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

1-й байт - тип объекта.
2-й байт - номер функции поведения объекта (некоторые объекты могут разделять одну и ту же функцию поведения).
3-й байт - начальный номер анимации объекта.
4-й байт - дополнительное поле - статус объекта или второй номер анимации.

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

Каждая анимация состоит из нескольких кадров и времени, которое она проигрывается:

Формат анимации:
{
  1 байт -  кол-во кадров N.
  1 байт. таймер.
  N байт - номера кадров.
}

По таймеру кадр переключается на следующий:

Формат кадра:
{
  количество тайлов в кадре
  индекс описания координат
  номера тайлов (через 1. тайл - аттрибуты тайла)
}

(Массив кадров разделён в образе ROM на две части из-за большого размера, чтобы разделить его на разные банки).

Вывод всех тайлов кадра на экран осуществляется стандартными для NES средствами — видеопроцессор помимо экранных страниц может отрисовывать на экране тайлы (размером 8x8) в произвольных местах экрана, подробнее о выводе спрайтов на экран статья, раздел «Спрайты. Контроллер DMA.».

Подобная система анимаций применяется в играх «Darkwing Duck», «Chip & Dale», «Duck Tales» (первые части, в «Chip & Dale 2» и «Duck Tales 2» своя система), «Little Mermaid», «Tale Spin», «Mega Man» (со второй по пятую части), «Mighty Final Fight».
Для редактирования анимаций можно воспользоваться редактором CadEditor или утилитой Capcom Sprite Assembler:

Функции обновления игровых объектов

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

Поиск номера функции обновления можно посмотреть в предыдущем разделе, дальше необходимо исследовать ячейки памяти, в которых хранятся текущие параметры объекта. Для «Darkwing Duck» это:

4D0 - стадия (сторожит/следует за ЧП/стреляет/спит/бежит etc.).
420 - номер анимации
580 - направление движения
5A0 - оставшееся здоровье (80, если объект бессмертный)
410 - кадр анимации
430 - таймер между кадрами анимации
400 - флажки (направление движения, мерцание, присутствие на экране, etc.)
и другие.

Дальше следует кропотливая работа по пониманию логики работы каждой функции объектов (сложно обычно только для первых двух-трёх, дальше всё повторяется).
Для примера, код функции обновления первого врага «Чёрного Плаща», Робота: gist.github.com/spiiin/14197bc6b8889a0dd4f0

Робот имеет две фазы, в первой («Патрулирование») он не покидает своего поста и ходит в небольшом радиусе от него, иногда останавливаясь, чтобы покрутить головой в поисках Чёрного Плаща. Если расстояние до игрока уменьшится до 32 пикселей, или здоровье Робота уменьшится, то он переходит в фазу «Атака», в которой он начинает двигаться в ту сторону, с которой находится игрок, причём меняет направление только при условии попадания в тупик, из которого не может выбраться прыжком.

Особенных инструментов для создания своих объектов нету, необходимо переписывать код, желательно влезая в ограничение по размеру на функцию обновления. Однако это не мешает созданию таких фантастических хаков как «Rockman Minus Infinity».

Устройство главной карты

Бонусом будет небольшой раздел про устройство главной карты. Для неё в «Darkwing Duck» используется не блочный, а описательный способ (про способы хранения данных см. первую статью цикла).
При этом для изменения карты, кроме разбора способа хранения (который я пропущу, чтобы не перегружать статью ассемблерным кодом), необходимо написать ещё и способ сохранения карты обратно в образ ROM. Описательный способ хранения подразумевает, что из карты выбрасываются все цепочки нулей, а вместо них перед каждой цепочкой данных указывается адрес, с которого он начинается, чтобы было понятно, куда вписать данные в карту:



Код запаковщика на C#: gist.github.com/spiiin/8738491

Теперь можно добавить карту в редактор:



… и, например, переселить Чёрного Плаща из Сен-Канара в другой город:

Послесловие

Тем, кому этого мало, могу предложить продолжать самостоятельное исследование движка, или изучать разобранный откомментированный код движка «Mega Man 4», похожего на «Darkwing Duck». Оттуда можно почерпнуть некоторые сведения, не разобранные в статье, например, устройство звукового движка или устройство спецэффектов, таких как, анимация фона переключением палитр, и другие.

Если кого-то заинтересуют другие аспекты устройства движков игр, добро пожаловать в комментарии, попробую помочь разобраться.