[NES] Пишем редактор уровней для Prince of Persia. Глава третья. Первые строчки кода

Глава первая, Глава вторая, Глава третья

Disclaimer

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

Открываем HEX-редактор

Попрыгав между огрызками данных, я обнаружил, что начиная со смещения 0x18010 в ROM-файле, при изменении данных начинает поблочно преображаться первая комната. Но сначала посмотрим на данные:
E0 E0 E0 01 21 01 21 01 14 14 13 13 21 03 00 14 14 14 14 14 14 14 14 14 0E 03 0B 21 01 14 ...
Можно сказать, что эти данные вполне подпадают под то, что мы предполагали ранее. Видны вполне стройные ряды повторяющихся байтов (то есть явно не код) и они, на глаз, не похоже на какие-то шифрованные данные. Попробуем сперва аккуратненько поменять E0 на E1:

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

Осматриваемся

Раз уж один байт отвечает за один блок в комнате, то неплохо было бы понять, за какой тип блока отвечает определенное значение байта. При переборе выясняется, что различных блоков — 32 штуки, причем часть из них рисуют графический мусор, а часть и вовсе рушат игру. Раз блоков 32 штуки, то это значит, что первые 5 бит значения отвечают за тип блока. Меняя оставшиеся три бита в байте, выясняем, что они отвечают за характеристику блока. Например, значение #04 — закрытая решетка, а #24 — открытая.
И, наконец, если перебирать байты за пределами этого 30-байтного блока, убедимся, что меняются и другие комнаты. Вот, правда, порядок у комнат какой-то хаотичный. Такой же хаотичный порядок был и тогда, когда мы меняли единичку в другом блоке данных ранее и принц появлялся то в одной комнате, то в другой. Раскусить нам тогда его, правда, не удалось.

Рассмотрим тот блок поближе. Вспоминаем, что смещение того блока у нас равно 0x18340 и переходим к нему. Ставим вместо единички двойку и принц перескакивает в другую комнату. Попробуем найти эту комнату, редактируя данные в предыдущем блоке. Перебором выясняем, что это следующие 30 байт после первого 30-байтного блока, отвечающего за первую комнату. Следовательно, та единичка — это номер комнаты. А номер комнаты — это номер 30-байтного блока. Отлично, значит комнаты у нас нумеруются, причем нумеруются с единицы.

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

На текущий момент мы знаем, что есть неопределенного размера массив данных, из которых строятся комнаты. Каждая комната описывается блоком размером в 30 байт. После комнат идет некая структура данных с неопределенным размером. Назовем ее «заголовком» уровня. А после… Собственно, как узнать, что идет дальше? Обратимся к тому, что мы уже знаем.

Обустраиваем комнаты

Попробуем посчитать, сколько комнат у нас уместилось между началом и «заголовком», учитывая что одна комната — это 30 байт в этом массиве:
0x182E9 - 0x18010 + 1 = 0x2DA = 730 байт.
На 30 не делится. Тупик? Как бы не так. Попробуем составить схему уровня с номерами комнат. Сделать это пока мы можем только перемещая принца путем изменения первого байта «заголовка». Последовательно двигая его из комнаты в комнату, обнаружим, что он либо оказывается в другой комнате, либо игра не запускается вовсе. Исключим номера, которые дают сбой, а оставшиеся разместим в соответствии с их позицией в игре:

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

Попробуем сопоставить эти комнаты с тем, что у нас есть в нашем массиве. С 1 по 12 комнаты у нас есть на схеме, а вот 13 (а затем 18 и 24) отсутствует. Считаем ее смещение: 0x18010 + 12(первых комнат)*30(размер блока) = 0x18010 + 0x168 = 0x18178.
Переходим и видим:
FF 14 14 14 E1 03...
#FF? А что тогда идет дальше? Идем в комнату 14 и видим, что в ней в левом верхнем углу идут 3 «бетонных» блока, затем платформа, а затем колонна. Очень похоже на то, что первые три «бетонных» блока четырнадцатой комнаты описываются числами #14, платформа — #E1, а колонна — #03. Следовательно, за #FF идет уже описание комнаты №14, а сама комната №13 сократилась до одного байта — #FF. Похоже, что #FF — это некий маркер, означающий, что комната отсутствует. Аналогичная ситуация и для 18, и для 24 комнат.
А вот номеров 25 и выше, судя по всему, уже нет, так как после маркера #FF, который говорит нам, что комнаты №24 нет, идет набор данных, которые ну никак не похожи на предыдущие:
05 00 00 02 06 03 01 00 02 09 00 00...
Можно, конечно, поиграться и с этими числами, но давайте посмотрим на нашу схему.

• Первую комнату окружают комнаты 05 и 02;
• Вторую комнату окружают комнаты 06, 01 и 03;
• Третью комнату окружают комнаты 02 и 09;
• ...

Те же самые числа фигурируют и в найденном массиве. Попробуем угадать.

• Слева от первой комнаты — пятая;
• Слева от второй — шестая;
• Слева от третьей — вторая;

Видно, что числа 5, 6 и 2 стоят на кратным числу 4 местах. Значит, окружение одной комнаты описывается структурой из четырех байт, причем первый из них — это номер комнаты слева. Исходя из карты уровня, видно, что оставшиеся три байта описывают комнаты справа, сверху и снизу. Причем, если комната отсутствует, то на соответствующем месте будет стоять 0. Число этих структур ровно 24, после которых начинается «заголовок» уровня. Раз так, значит мы можем построить максимум 24 комнаты (потом, изучая код, в этом убедимся).

Зовем стражу!

В прошлый раз мы нашли массив указателей на некие структуры данных, которые мы назвали «заголовками». Причем при чтении массива в качестве индекса использовался удвоенный порядковый номер уровня. Значит следующие два байта в этом массиве — это указатель на такую же структуру, но второго уровня. Изучим и ее:
Массив указателей:D9 82 61 86 91 89 ....

• Первый уровень: D9 82 -> $82D9 -> смещение в файле 0x182E9;
• Второй уровень: 61 86 -> $8661 -> смещение в файле 0x18671;
• ...

Нас там встречают такие данные:
05 0D FF 1E 9E ... (забавно, здесь тоже после первых трех байт опять идут числа, заканчивающиеся на 0x0E)

Здесь уже первое число #05, значит принц стартует в комнате с порядковым номером 5. А вот следующие два байта уже не нули.
Если поиграться с ними, то выясним, что #0D — это позиция принца в комнате. Всего возможных позиций 10х3=30, где 10 — ширина комнаты, а значит #0D=13 — это позиция 3x1, то есть он будет находится на месте четвертого блока слева и на месте второго сверху. Следующий байт со значением #FF — его направление: если #FF, то он развернется и будет смотреть влево, если не #FF, то останется смотреть вправо. Странно только то, что в первом уровне он не меняет своего положения. Но это мы выясним позже.

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

Вернемся в первый уровень и запишем #02 (как в прошлый раз) в четвертое поле. Стражник появился совсем рядом с принцем. Ставим #03. Появился, но уже подальше. Перебирая значения вплоть до #1D, убеждаемся в том, что этот байт отвечает за позицию стражника. Но когда ставим 0x1E он пропадает. Но 0x1E = 30 в десятичном представлении, а значит, если мы выставим предельное значение позиции, то это будет означать, что стражника в комнате нет. Судя по всему, оставшиеся байты отвечают за стражников в других комнатах. То есть следующий байт отвечает за присутствие стражника во второй комнате, затем — в третьей и так далее. Впрочем, это подтверждается простой проверкой. Также проверкой выясняется, что за позицию стражника отвечают только первые 5 бит значения, оставшиеся 3 бита не используются, как бы мы их не крутили.

Собираем всех вместе: Строителей, архитекторов и стражников

Итого, у нас есть следующие структуры данных:

• «Кирпичи», из которых строятся комнаты. Структура нефиксированного значения;
• Схема расположения комнат. Фиксирована по длине (4x24 байта);
• Маленькая структурка, описывающая как и где будет появляться принц (3 байта) — «заголовок» уровня;
• Структура, описывающая расположение стражников по комнатам (24 байта).

Но вот ведь что неудобно: тот указатель, что у нас есть (из массива указателей) ведет нас на «заголовок», а значит смещение начала уровня нам придется считать. Давайте взглянем в отладчик и посмотрим, как оно считается.
Нам известно, что начало у нас находится по смещению 0x18010, значит в памяти оно будет находится аккурат по адресу $8000. Но банков у нас несколько, поэтому будем отслеживать только нужный. Считать его номер мы не будем, мы просто скажем отладчику, что нас интересует чтение по адресу $8000, причем первый байт должен быть равен #E0 (первый блок в первой комнате первого уровня):

Первый же останов привет нас к процедуре:

$C0F6:20 C7 C0	JSR $C0C7
$C0F9:A5 52	LDA $0052 = #$00
$C0FB:18	CLC
$C0FC:65 6D	ADC $006D = #$00
$C0FE:85 0E	STA $000E = #$00
$C100:A5 53	LDA $0053 = #$00
$C102:65 6E	ADC $006E = #$80
$C104:85 0F	STA $000F = #$80
$C106:8C 0B 04	STY $040B = #$03
$C109:A0 00	LDY #$00
$C10B:B1 0E	LDA ($0E),Y @ $8000 = #$E0    ;; <<<<< останов
$C10D:AC 0B 04	LDY $040B = #$03
$C110:60	RTS

В ячейках $0E:$0F мы имеем адрес $8000. Туда он попал из знакомых нам ячеек $6D:$6E, к которым добавились значения из ячеек $52 и $53. В ячейках $52, $53 сейчас нули, поэтому нас интересует, как в $6D:$6E попали числа #00 и #80.
В самом начале процедуры видим вызов другой процедуры по адресу $C0C7. Залезем туда:

$C0C7:20 D5 C0	JSR $C0D5
$C0CA:BD 3A EB	LDA $EB3A,X @ $EB3A = #$00
$C0CD:85 6D	STA $006D = #$00
$C0CF:BD 3B EB	LDA $EB3B,X @ $EB3B = #$80
$C0D2:85 6E	STA $006E = #$80
$C0D4:60	RTS

В начале видим вызов знакомой нам процедуры sub_C0D5 (которая возвращает нам в регистре X удвоенный порядковый номер уровня), а затем чтение из последнего банка. Считаем по выработанному нами правилу: $EB3A+0x10010=0x1EB4A

Смотрим:
00 80 31 83 9B 86 C1 89 ...
Точно. Указатели на наши «кирпичи». Если полазить в окрестности этого кода, то увидим три подобные процедуры — они идут практически друг за другом. Две из них мы видели, а третья (0x1EB82) обращается к массиву, который ведет на структуру размещения комнат.

Вроде все собрали? Как бы не так.

Открываем двери

В принципе, мы можем отстроить уровень с фундамента и по самую крышу, но как же быть с решетками? Ими же надо уметь управлять. Попробуем изучить их поведение.

Помещаем принца в комнату №5, так как в ней сразу две решетки и аж три кнопки. Одна из них закрывает решетку, а две другие — открывают. Тут у меня возник ступор: как бы я мог связать кнопки с решетками, будучи разработчиком?

Начнем с того, что мы можем сейчас сделать — подвинуть кнопку или решетку и посмотреть на эффект.
Первая решетка после перемещения перестала открываться. Кнопка при перемещении тоже перестала работать. А вот если поменять местами две кнопки («высокую» и «низкую»), то «низкая» кнопка (на изображении она на две позиции левее «высокой», на которой стоит принц, — ее не видно) стала открывать, а «высокая» закрывать. Значит, позиции (как и раньше, будем вести отсчет с нуля, а комнаты с единицы) кнопок и решеток однозначно связаны, но как? Я выписал эти позиции в столбик и получил такую табличку:
Button Room - Button Position : Door Room - Door Position
05 - 02 : 05 - 09 — «низкая» кнопка закрывает вторую решетку.
05 - 04 : 05 - 05 + 05 - 09 — первая «высокая» кнопка открывает обе решетки.
05 - 08 : 05 - 09 — вторая «высокая» кнопка открывает только вторую решетку.

Размышляя над этой таблицей, я как-то машинально залез в HEX-редактор и решил посмотреть еще раз на «заголовок» уровня. Вопреки моим ожиданиям, после окончания массива, размещающего по комнатам стражников, начинался не второй уровень, а массив еще каких-то данных. Второй же уровень начинался сразу за ними.
05 02 01 05 09 05 04 00 05 09 05 04 00 05 05 05 08 00 05 09 ...
Байты практически в точности повторяли мои записи в таблице, только вместо двоеточия стояли либо 00, либо 01. Учитывая то, что напротив первой записи у меня стоит слово «закрывает», а напротив остальных «открывает», то легко видеть, что 00 — говорит о том, что в этой связке решетка будет открываться, а 01 — закрываться. Проверка показала, что так оно и есть. Теперь мы нашли еще и механиков, отвечающих за механизм открытия дверей.

Редактор

Что ж, редактор почти готов? Достаточно взять три смещения, определить из них указатели на три структуры (Комнаты, геометрия уровня и «заголовок») и в редакторе отобразить. Как бы не так.

Алгоритм размещения комнат довольно прост: начиная с начальной комнаты мы «опрашиваем» рекурсивно соседние комнаты, размещая их по координатной сетке. Первая комната у нас будет находится в точке (0,0), комната слева — в точке (-1, 0), комната снизу — в точке (0, 1) и так далее. Затем мы берем «самую отрицательные» координаты X и Y, и их абсолютные значения прибавляем к координатам всех комнат. Таким образом, мы получим карту всего уровня.

Все хорошо, но на 10 уровне алгоритм выбрасывает исключение: мол, комната №1 ссылается на комнату №3, а комната №3, в свою очередь, ссылается на 00, что говорит о том, что над ней нет никаких комнат. В игре мы тоже никак не можем попасть «под» комнату №1 (с нее начинается 10 уровень).
Примерно зарисовав комнату №3 стало понятно, что это та самая стартовая комната, с которой начинается игра. В ней нам предлагают пойти вправо и начать игру заново, или же влево, где мы набираем пароль и попадаем в соответствующий уровень.
У комнаты №3 есть соседка — комната №12. И таки да, в ней как раз стоит бутылка и дверь выхода.

Таким образом, нам в редакторе достаточно будет учесть эти комнаты, и выполнить отрисовку карты уровня.

nesprinced

Мы вплотную подошли к написанию редактора. У нас есть практически все, чтобы заниматься строительством. Нам остается только выяснить, как правильно преобразовать подземелье в дворец и наоборот. Внешний вид мы менять умеем, а цвет — пока нет.

Над именем редактора я долго не задумывался: есть PrincEd, который для DOS-версии, а у нас NESPrincEd, который для NES-версии.
На этом этапе я думал, что достаточно теперь написать оболочку и редактор готов. Как же я тогда ошибался… И в четвертой главе, которая называется «Он сам бежит! Или скелет в шкафу», мы в этом убедимся.

Автор: loginsin

Источник