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

    Глава первая, Глава вторая, Глава третья, Глава четвертая, Глава пятая, Эпилог

    Disclaimer

    В детстве, как и у многих, родившихся в 80-х, у меня была приставка Dendy. Клон японской FamiCom, подаренный нам добрыми китайцами, и распространяемый небезызвестной Steepler, раскрасил в яркие цвета детство многих из поколения 80-х. Раз за разом, проходя полюбившиеся мне игры вдоль и поперек, находя все возможные секреты (причем, зачастую, без книжек с громкими заголовками в духе «Секреты и прохождения 100500+1 игр», ценность которых стремилась к нулю), мне хотелось играть в них еще и еще, но с новыми уровнями, новыми секретами и новыми возможностями.

    Некоторые игры предусматривали встроенный редактор уровней (например, Battle City, Fire'n'Ice aka Solomon's Key 2), но большинство из них, разумеется, таковой возможности не предоставляли. Хотелось сыграть (естественно!) в новый Super Mario Bros (о, как я любил и ненавидел китайцев, выпустивших картридж 99...9 in 1, в котором были уровни A-1, B-1,… Z-1, которые невозможно было пройти, или которые представляли собой дубли оригинальных уровней, но с измененными текстурами), Duck Tales 1, 2 и многие другие.

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

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

    Различного рода ресурсы по NES и ее эмуляции не очень охотно поддавались моему пониманию и я так и оставался где-то на уровне нуба.

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

    Начал я… Впрочем, перед тем, как я начну рассказывать далее, предостерегу:
    Не рекомендуется лезть под кат профессионалам. Там рассматриваются «живодерские» методы новичка! Работа Вашей нервной системы может быть необратимо нарушена! Я предупредил.


    Вникаем в суть

    Глядя на набор байтов в HEX-редакторе и набор неизвестных мне на тот момент инструкций процессора 6502, я загрустил. Вся эта картина ровным счетом ничего не проясняла. Но, глаза боятся, а руки делают. Начинаем изучать то, что есть.

    NES-заголовок

    Это первое, что лежит на поверхности. С него и начнем.
    Заголовок имеет размер в 16 байт, где помимо сигнатуры имеется техническая информация о ROM-файле. ROM-файл сам по себе — это совокупность данных и технической информации в одном файле. Заглянем внутрь заголовка.
    4E 45 53 1A 08 00 21 00 00 00 00 00 00 00 00 00
    4 байта: Сигнатура NES->;
    1 байт: Количество 16 кБ PRG-ROM банков;
    1 байт: Количество 8 кБ CHR-ROM банков;
    2 байта: Флаги;
    1 байт: Количество 8 кБ PRG-RAM банков;
    2 байта: Флаги;
    Оставшийся хвост — нули.

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

    Из заголовка мы выясняем, что у нас Mapper #2 (байт с номером маппера составляется из половинок шестого и седьмого байтов) и 8 16 кБ PRG-ROM банков. Все остальное отсутствует.

    Из документации следует, что PRG-ROM банки — это собственно код + произвольные данные, которые будут использованы непосредственно CPU. CHR-ROM банки — это данные для видеоподсистемы (PPU). CPU к ним непосредственно обратиться не может.
    Как же мы получаем изображение, если у нас нет ни одного CHR-ROM? Очень просто: в PRG у нас хранятся данные, которые все время копируются в память PPU. Неудобно? Да. Но над этими данными у нас, в некотором смысле, больше власти.

    Далее мы выясняем, что Mapper #2 на самом деле подразумевает несколько различных мапперов, одинаковых по функциональности, но различаемых по структуре: UNROM и UOROM, объединенных по названию в UxROM. Разница лишь в количестве PRG-ROM банков: в первом 8 банков, во втором — 16. Для любого из них последний банк фиксирован в конце оперативной памяти ($C000-$FFFF), а оставшиеся 7 (или 15 для второго случая) могут переключаться в область памяти $8000-$BFFF.
    Это все техническая информация, которая, на данный момент ни о чем толковом нам не говорит.

    Запасаемся консервами

    Итак, мы можем разбить ROM-файл на 9 составляющих: Заголовок и 8 банков. Заголовок редактировать смысла нет, т.к. там хранится информация для программы-эмулятора, а как редактировать банки мы не знаем. Во-первых, в банках нет какой-либо строгой структуры (как, например, в PE-формате, где код и ресурсы лежат в своих секциях) и данные могут быть перемешаны хаотично с кодом. Может нам и вовсе не повезло и данные для построения уровней формируются исполняемым кодом.

    Но, пока прикинем варианты, как бы мы могли достать то, что нам нужно из цельных кусков бинарной каши:
    1. Самый сложный, но и самый универсальный: последовательный реверс кода отладчиком. С помощью этого метода мы точно доберемся до того, что нам нужно, по пути получая бонусы в виде дополнительной информации о том, как построен код. Минусы очевидны: на реверс мы потратим уйму времени, но это еще полбеды, ведь мы пока еще ничего не знаем, а значит на изучение ассемблера и различных «трюков» программирования на нем мы потратим 90% времени. Т.е. КПД будет около 10%. Мало;
    2. Изучение оперативной памяти, а затем отладка по точкам останова обращения к памяти (рассмотрим чуть ниже). Этот способ уже лучше. Памяти для изучения у нас сравнительно немного: из 64 кБ имеющейся памяти у нас половина уходит на банки из ROM-файла, половина от этой половины — либо зарезервировано, либо используется портами IO. И, наконец, оставшаяся половина бьется еще пополам. Одна половина — это порты IO для PPU (их немного, но они зеркалируются на всю эту половину), а вторая делится на четыре части по 2 кБ. Первая часть — собственно оперативка, используемая кодом, а оставшиеся три — зеркала первой части. Таким образом, на изучение у нас остается 2 кБ памяти, которую вполне можно изучить глазами прямо наживую. КПД способа повыше, т.к. мы будем иметь перед глазами живые данные, которые мы можем менять прямо во время выполнения и смотреть тут же на результат;
    3. Изучение считанных данных. В момент перехода на другой уровень или перехода в другую комнату изучаем данные, которые были считаны из ROM-файла. Как мы помним, в Prince of Persia каждый уровень делится на комнаты, между которым он бегает;
    4. «Живодерский» способ — «Брутфорс»: последовательно меняем по одному байту, скриншотим результат, а зачем изучаем кучу скриншотов.


    Запасаемся необходимым количеством материала и приступаем к его изучению. Изучать будем в обратном порядке: от простого для изучения (достаточно посмотреть скриншоты) до сложного (изучаем листинги отладчика).

    Вооружимся инструментами:
    • Любимый ЯП для написания вспомогательный утилит. Может быть какой угодно. Я использовал C++ в составе VS2010;
    • Эмулятор с отладчиком. Я использовал версии из разных веток FCEUX-эмулятора. FCEUX и FCEUXDSP. У первого простенький топорный отладчик, который умеет совсем простые вещи. У второго очень мощные инструменты по отладке и изучению памяти, но он, к сожалению, часто падал, поэтому в простых случаях я прибегал к первому;
    • Любой шестнадцатеричный редактор. Я использовал WinHEX, который позволяет, не сохраняя файл, запустить его на выполнение (редактируем любой байт и жмем Ctrl+E).
    • Для справки по коду можно использовать IDAPro с загрузчиком NES. Можно использовать загрузчик от cah4e3. Но чудес от нее не ждите, т.к. банки в процессе выполнения меняются динамически, и правильный код будет только из последней банки.

    Перед тем, как приступать, посмотрим на то, что же такое UxROM:
    Вообще говоря, Mapper — это с точки зрения эмулятора алгоритм, а с точки зрения железа некий контроллер, который занимается переключением банков в памяти.
    Во-первых: Зачем он это делает?
    Во-вторых: Как он это делает?

    На первый вопрос ответ простой: оперативной памяти, которую может адресовать процессор, немного — всего 64 кБ, причем туда надо впихнуть не только код и данные, но и порты ввода/вывода, а так же кучу других вещей (вроде энергонезависимой памяти, куда сохраняются промежуточные результаты некоторых игр). Нашли простое решение: по мере выполнения кода не все данные в памяти требуются для работы, поэтому их можно просто исключить, а на их место поставить более важные в данный момент времени. Рядом с ROM-памятью на картридже поставили контроллер, который по команде в адресную память отображает нужный кусок. В зависимости от сложности игры эти контроллеры различались своей начинкой. Китайцы же это дело вовремя подхватили и напридумывали много разных (адекватных и не очень) мапперов. Благодаря этому у нас появилось большое количество многоигровок.

    Во втором вопросе мы рассмотрим только работу маппера UxROM, так как остальные нам сейчас неинтересны. Маппер берет последний банк (#07 или #0F), помещает его по адресам $C000-$FFFF и больше не трогает. Все остальные банки включаются по мере надобности после записи (в общем случае) по любому адресу из пространства $C000-$FFFF номера банка (#00-#06 или #00-#0E). Но правильно это делается следующим образом: по адресу $FFF0+N записывается N, где N — номер банка, и в итоге по адресам $8000-$BFFF мы видим содержимое нужного банка.

    Рубим банку топором. Способ №4.

    Для этого была написана небольшая утилита, которая меняла один байт (простой инкремент: Byte++), сохраняла в отдельный файл, далее запускала в эмуляторе полученный ROM, выполняла скриншот и закрывала эмулятор.
    Разумно было бы сократить количество скриншотов, т.к. изучить over 130.000 скриншотов даже бегло было бы сложно.

    Поскольку у нас только PRG-ROM банки, то в каких-то из них наверняка хранятся и тайлы, которые нам неинтересны. Их мы и попробуем исключить.
    Берем любой тайловый редактор, открываем в нем ROM-файл. Я использовал Tile Layer Pro — это довольно таки древняя программа, но дело свое знает. Выглядит она примерно так (на скриншоте тайлы из игры Final Fantasy). В статусной строке окна программы указано смещение каждого тайла. Мы можем прокрутить окно с данными до того момента, где очевидно заканчиваются тайлы и начинаются «мусорные» с точки зрения графики данные. Прокрутив, выясняем, что первые две банки — это графика. Их мы пропускаем и остается 6 банков. Уже «всего» 96 кБ. Сложно, но все же полегче.

    Ну что ж. Как этим способом мы найдем нужные нам данные? Очень просто: бегло просматривая скриншоты мы увидим, что на некоторых из них у нас последовательно меняются блоки в комнатах. Комната состоит из 10х3 блоков, соответственно на 30 скриншотах подряд у нас должны (но не обязаны!) будут изменяться рядом стоящие блоки на какие-нибудь другие: например, «бетонный» блок может поменяться на колонну или что-нибудь еще.

    Запускаем утилиту по перебору где-нибудь в сторонке, а сами приступим к изучению считанных из ROM данных.

    Режем крышку банки тесаком. Способ №3.

    Этот способ аналогичен предыдущему, но мы существенно сокращаем объем данных для изучения. Как?
    В FCEUXDSP есть инструмент, который сохраняет считанные данные в соседний файл. Между нажатиями кнопок Start и Pause считанные данные помещаются в файл ровно в то место, в котором они хранятся в оригинальном. Таким образом, мы можем открыть диалог фиксации данных, нажать Start, в игре перебежать из одной комнаты в другую, нажать Pause, и так же как и в предыдущем пункте, изучить зафиксированные данные. Этих данных будет существенно меньше. По сути сам код нам покажет то, на что следует обратить внимание. А перебрать сотню-другую байт труда не составит даже вручную.

    На этом я предлагаю сделать паузу, сходить на кухню, заварить кофе и открыть документацию по инструкциям процессора 6502.
    Перед тем, как воспользоваться способом №2, не помешало бы ознакомиться с врагом.

    Собираем микроскоп для изучения содержимого. Не так страшен черт, как его малюют.

    Процессор 6502 имеет всего 56 документированных инструкций, поэтому чашки кофе хватит, чтобы хотя бы бегло с ними ознакомиться.
    Так как сходу разобраться в коде будет сложно, то я придумал для изучения простой Си-подобный язык, в который легко можно будет переводить ассемблерную простыню.

    Для начала выделим несколько моментов из документации:
    1. Адресация может быть непосредственная регистр<->память (IMM): LDA $00; STA $00;
    2. Прямая с участием индексных регистров: регистр<->память+INDEX: LDA $0000, X; STA $0000, Y;
    3. Косвенная с участием индексных регистров: регистр<->указатель+INDEX: LDA ($00), X; STA ($00),Y;

    В косвенной адресации процессор извлекает из двух ячеек (в пределах первой страницы памяти $00-$FF) 16-битный указатель, прибавляет к нему значение индексного регистра, и затем уже работает с ячейкой по полученному таким образом адресу.

    Отсюда составим следующие соглашения по псевдокоду:
    • Переменные обозначим как $XXXX (где XXXX — ее адрес);
    • Прямую адресацию обозначим как #XXXX[Y] (где XXXX — адрес, от которого адресуем). Аналог: *((char*) (XXXX+Y)) = A;
    • Косвенную адресацию обозначим как $XXXX[Y] (полная аналогия с массивами в Си);
    • Все процедуры у нас имеют одинаковый вид: char sub_XXXX() { }. Так как в NES нет каких-либо соглашений по передаче аргументов, то аргументов у нас не будет. Какие-либо данные, как правило, передаются либо через регистры, либо через переменные.
    • Регистры имеют оригинальные имена (A, X, Y).
    • Восьмибитные числа будем записывать как #XX в HEX

    Возьмем простой код переключения банков:
    $F2D3:84 41		STY $0041 = #$00
    $F2D5:A8		TAY
    $F2D6:8D D1 06		STA $06D1 = #$06
    $F2D9:99 F0 FF		STA $FFF0,Y @ $FFF0 = #$00
    $F2DC:A4 41		LDY $0041 = #$00
    $F2DE:60		RTS
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    

    Попробуем перевести построчно:
    char switch_bank() // передаем номер включаемого банка в регистре A
    {
        $0041 = Y; // сохраняем Y
        Y = A;
        $06D1 = A; // сохраняем номер включаемого банка
        #FFF0[Y] = A; // включаем банк путем записи в порт $FFF0+N числа N (где N - номер включаемого банка)
        Y = $0041; // восстанавливаем содержимое Y
        return A;
    }
    


    Теперь возьмем код посложнее:

    ;; процедура копирования тайла из оперативной памяти в память PPU
    $F302:20 D3 F2		JSR $F2D3
    $F305:8E 06 20		STX $2006 = #$41
    $F308:A9 00		LDA #$00
    $F30A:8D 06 20		STA $2006 = #$41
    $F30D:A2 10		LDX #$10
    $F30F:A0 00		LDY #$00
    $F311:B1 17		LDA ($17),Y @ $020E = #$03
    $F313:8D 07 20		STA $2007 = #$00
    $F316:C8		INY
    $F317:D0 F8		BNE $F311
    $F319:E6 18		INC $0018 = #$02
    $F31B:CA		DEX
    $F31C:D0 F1		BNE $F30F
    $F31E:4C 10 D0		JMP $D010
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    


    Первый этап перевода:
    char sub_F302()
    {
                sub_F2D3(); // switch bank. Bank counter in A register
              // $2006 – PPU Address register
              // $2007 – PPU data write
              // В $2006 записываем адрес в видеопамяти 
              // (старший байт, затем младший)
              // 2007 после чего в регистр записываем данные
              // в PPU. После каждой записи адрес PPU
              // автоматически увеличивается на 1.
                $2006 = X; // старший байт адреса 
                $2006 = #00 // младший байт адреса 
                X = #10;
    label_F30F:
                Y = #00;
    label_F311:
              // в ячейках $0017:$0018 лежит указатель 
              // , на данные, которые будем записывать в PPU
                $2007 = $0017[Y];
                Y++;
                if ( Y != #00 ) goto label_F311;
                $0018++;
                X--;
                if ( X != #00 ) goto label_F30F;
                return sub_F2D3(#05);  // включаем 5-ый банк
    }
    


    И последний этап перевода:
    void WriteDataIntoPPU(char Bank, char PPULine)
    {
                switch_bank(Bank); // switch bank.
                PPUADDRESS = PPULine; // старший байт адреса 
                PPUADDRESS = #00; // младший байт адреса 
                for(X = #10; X > 0; X--)
                {
                            for(Y = #00; Y <= #FF; Y++)
                            {
                                        PPUDATA = $Tiles[Y];
                            }
                            $Tiles += #100; // переходим на следующую строку 
                }
                return switch_bank5();
    }
    

    В два простых этапа мы переписали сложночитаемый (для новичка) ассемблерный листинг в понятный код. Я не рассматривал процедуру switch_bank5, там банальный код присвоения регистру A числа #05, а затем вызов процедуры переключения банка sub_F2D3. Для выработки автоматизма при переводе кода в читаемый мне хватило пары-тройки процедур, далее все становится намного проще. После того, как у меня скопилось с десяток 5-7 кБ текстовых файлов, переводить код уже стало попросту не нужно — все стало происходить само собой в голове.

    Переходим к букетно-конфетному периоду

    Во второй главе мы познакомимся с последними двумя способами и более глубоко проникнем в загадочный мир NES. Хочу сказать, что в итоге мы сможем найти искомые данные путем комбинирования первых трех способов. Четвертый же отбросим за очевидными минусами.

    Предполагая появление вопросов «А зачем описывал его?» отвечу сразу: при исследовании любого предмета хороши все способы, которые могут дать результат. В нашем случае, этот способ может пригодиться как изучение черного ящика путем тыканья в него иголками, не влезая в дебри кода: какая-нибудь точка да даст свой результат. Этот способ обладает очевидными преимуществами брутфорса. Так или иначе на что-нибудь наткнемся.
    • +71
    • 28.6k
    • 7
    Share post

    Comments 7

      +3
      Ждём продолжения!
      С такой любовью к играм в GameDev не тянет?
        +3
        На самом деле, ковыряние сподвигалось сильным чувством ностальгии и любопытством «А как оно там — внутри?». Пока я от GameDev далек.
        Продолжения планирую каждый день выпускать. Сперва хотел в рамках одной статьи (казалось бы такую простую вещь) описать, но в итоге оказалось так много текста, что пришлось разбить на главы. И их получилось прилично. :-)
        +2
        Интересный момент из истории Prince of Persia: изначально разработчик планировал выпустить его на двух дискетах, на одной из которых, кроме прочих ресурсов и магии, должен был располагаться как раз редактор уровней, но по ходу работы и количество изначальных уровней было урезано и редактор выкинут. Сделано это было исключительно для того, чтобы сэкономить место и сделать игру более интересной и захватывающей за счёт дополнительных анимаций, испытаний и персонажей (вспомним, например, скелет на одном из уровней), а не просто набором бесцельных прыжков по уровням с одинаково выглядящими соперниками (которых, к слову, по началу вовсе не было: беги себе и умирай на штырях). Всё это, конечно, касается исключительно версии под Apple II, портами же занимались сторонние разработчики (хотя, под DOS портирование немного контролировалось Джорданом).

        P.S. Всё это вольный пересказ дневника разработчика, которой крайне советую к прочтению — отличный взгляд на IT индустрию конца 80х и … мотивация при работе над собственным проектом, особенно, если последний делается в одиночку.
          +3
          После упоминания марио и непроходимые уровни не могу не запостить старый баян:
          www.youtube.com/watch?v=in6RZzdGki8
            0
            А вот интересно, что такое «банка» в текущем контексте?
              0
              Банка — здесь это «кусок» памяти определенного рода (в данном случае PRG-ROM Bank). Вообще, по-английски Bank, но у нас решили называть «Банка».
                –3
                Это был немного сарказм. Я к тому и писал, что они вроде как называются «банк», а не «банка». И ссылка на 7-й пункт правил.
                У «нас» – это у кого?

            Only users with full accounts can post comments. Log in, please.