Исследование формата карты уровней NES-игры «Jackal»
В статье будет описан нестандартый способ поиска данных об уровнях в NES-играх — с помощью последовательного изменения всех данных в образе и исследования последствий («коррапт» в терминах ромхакеров). Для примера я покажу, как найти данные об уровнях в игре «Jackal» для NES и добавить один из её уровней в редактор CadEditor. Данный способ позволяет исследовать любую игру с блочной структурой уровней (почти любую игру на NES), без знания ассемблера X8502, требуются только начальные навыки работы со скриптовыми языками (Lua и Python).ТеорияИдея метода заключается в том, чтобы изменить поочерёдно по одному все байты в игре и посмотреть, при изменении каких из них уровень внешне изменился. Руками делать это очень долго, поэтому необходимо задействовать вспомогательные инструменты, а именно встроенный в эмулятор FCEUX скриптовый язык Lua, о его возможностях и ограничениях будет сказано ниже.Кроме того, некоторую сложность представляет процесс проверки результата — изменённый образ ROM необходимо загрузить в эмулятор, а затем довести игру до момента запуска первого уровня. Причём просто загрузить уже готовое сохранение эмулятора, сделанное на оригинальном образе, в момент после начала уровня нельзя — данные из образа уже попадут в видеопамять и RAM, и первый экран уровня останется неизменённым, визуально отличить его от оригинала будет невозможно. Поэтому необходимо либо записать в эмуляторе FCEUX повтор всех нажатий клавиш, который приводит игру от момента стартового экрана к запуску уровня (это делается с помощью меню File→Movie→Record Movie…), либо же поступить проще — сделать сохранение непосредственно в момент загрузки уровня. После нажатия кнопки «Start» в главном меню игры, перед началом уровня, изображение на экране на несколько мгновений затемняется, в это время и происходит создание первого игрового экрана уровня. Чтобы получить сохранение в нужный момент, можно замедлить время в несколько раз (меню NES→Emulation Speed→Speed Down, рекомендую настроить горячие клавиши в меню Config→Map Hotkeys, чтобы удобно ускорять/замедлять игру с клавиатуры). Необходимо дождаться начала затемнения экрана и в этот момент (до появляния игрового появления игрового экрана) сохранить игру (допустим в слот 1, комбинацией клавиш Shift + F1). Также для дальнейшей работы необходимо засечь, на каком фрейме было сделано сохранение и на каком фрейме в итоге появился игровой экран (включить отображение текущего кадра-фрейма на экране можно с помощью пункта меню Config→Display→Frame Counter). Это понадобится для того, чтобы сделать скриншот экрана уровня в тот момент, когда он уже будет создан, чтобы не снять раньше чёрный экран.
На скриншоте данные об уровня загружаются из образа в память в момент между фреймами 454 и 560.Таким образом, алгоритм для поиска данных об уровнях будет выглядеть так:
Запускаем изменённый ROM в эмуляторе Загружаем подготовленное заранее на оригинальном образе ROM сохранение (в момент загрузки данных из образа в видеопамять, чтобы получить изменённый уровень на экране). Ждём отмеренное количество кадров (для этого мы засекали значение Frame Counter в момент, когда на экране появляется изображение). Делаем скриншот экрана. Повторяем процесс для следующей версии изменённого образа ROM. Анализируем сделанные скриншоты (в имени сделанного скриншота необходимо указать адрес байта, который был изменён, чтобы было понятно, какое именно изменение привело к тому, что данные на экране изменились). В большинстве случаев изображение на экране не изменится, иногда его не будет вообще, так как в некоторых версиях образов ROM мы неизбежно сломаем код игры, иногда на экране будет странная каша из тайлов, конечная цель — найти ту версию, в которой на экране будет изненён только один макроблок (напоминаю ещё раз, экраны уровней в NES составлены из макроблоков). Когда такой скриншот будет найдет, станет понятно, по какому именно адресу хранится массив номеров блоков, описывающих экраны.Встроенный в эмулятор язык LUA позволяет оперировать памятью и регистрами процессора, однако он предназначен для работы с уже загруженным образом ROM картриджа, поэтому в нём нет операций ни по загрузке изменённых версий образов ROM, ни по изменению самого образа после загрузки, однако с помощью него можно реализовать шаги 2,3,4 алгоритма.Остальное в первой версии автоматического корраптера я решил с помощью языка Python. Однако в той версии было несколько серьёзных недостатков — несколько тысяч сгенерированных образов ROM занимали много места, эмулятор постоянно запускался из командной строки как отдельное приложение и закрывался, из-за чего на него переключался фокус, так что работать на машине с запущенным скриптом было неудобно, как и закрыть его в ходе работы. Поэтому для статьи я решил добавить нужный функционал в модули LUA, чтобы изменять байт внутри образа ROM прямо из эмулятора.
Создание инструментов К счастью, исходный код эмулятора FCEUX доступен, так что можно скачать исходники и добавить свои модификации.Находим функцию для чтения байта из образа ROM (файл fceu.cpp, функция FCEU_ReadRomByte) и добавляем аналогичную версию для записи:
//новоеvoid FCEU_WriteRomByte (uint32 i, uint8 value){ if (i < 16 + PRGsize[0]) PRGptr[0][i - 16] = value; else if (i < 16 + PRGsize[0] + CHRsize[0]) CHRptr[0][i - 16 - PRGsize[0]] = value;}
Дальше «пробрасываем» возможность вызывать эту функцию из LUA (файл lua_engine.cpp): static int rom_writebyte (lua_State *L) { FCEU_WriteRomByte (luaL_checkinteger (L,1), luaL_checkinteger (L,2)) return 1;} static const struct luaL_reg romlib [] = { {«readbyte», rom_readbyte}, {«readbytesigned», rom_readbytesigned}, // alternate naming scheme for unsigned {«readbyteunsigned», rom_readbyte}, {«writebyte», rom_writebyte}, //новая функция {«gethash», rom_gethash}, {NULL, NULL}};
Таким образом, мы получили возможность изменять байты данных из скриптов и избавились от необходимости создавать и загружать тысячи разных версии образов ROM.Следующий этап — научить LUA анализировать скриншоты, перед сохранением их. Для этого нужно вместо стандартного сохранения скриншота в файл функцией gui.savescreenshot () оставить его в памяти с помощью функции gui.gdscreenshot (), а дальше проверить, не был ли уже сделан такой же скриншот (для этого придётся хранить хеши всех уже сделанных скриншотов), и сохранять на диск только уникальные. Это позволит не хранить тысячи одинаковых скриншотов, в которых изменение одного байта никак не повлияло на первый экран игры.Для сохранения скриншотов я использовал библиотеку gd (скомпилированную версию можно взять здесь или собрать из исходников самому), распакованные файлы нужно положить в папку с собранным эмулятором. Для подсчёта хешей я воспользовался небольшой хитростью — прокинул функцию рассчёта из самого эмулятора (там она использовалась для рассчёта контрольных сумм образов ROM):
//файл lua_engine.cppstatic int calchash (lua_State *L) { const char *buffer = luaL_checkstring (L, 1); int size = luaL_checkinteger (L,2); int hash = CalcCRC32(0, (uint8*)buffer, size); lua_pushinteger (L, hash); return 1;} static const struct luaL_reg emulib [] = { //часть кода пропущена //… {«readonly», movie_getreadonly}, {«setreadonly», movie_setreadonly}, {«print», print}, // sure, why not {«calchash», calchash}, {NULL, NULL}};
Скрипт коррапта и его использование Теперь подготовительная работа наконец-то закончена и можно написать LUA-скрипт для коррапта образов (если комментарии в конце строк не отображаются полностью, можно посмотреть откомментированные скрипты на гитхабе, ссылка в конце статьи): --загружаем библиотеку gdrequire «gd» --начальный адрес для коррапта (сразу от заголовка образа ROM)START_ADDR = 0×10 --конечный адрес для коррапта (зависит от маппера, на котором сделан картридж, можно просто выставить размер файла) END_ADDR = 0×20010 CUR_ADDR = START_ADDR --конечный номер кадра, после которого нужно сделать скриншот (когда игровой экран уже отображается для игрока, номер замерен для созданного сохранения) FRAME_FOR_SCREEN = 7035 --тестовое значение, которым будет записано вместо байта игры WRITE_VALUE = 0×33 --шаг, с которым будет производиться коррапт, для экономии времени поиска --(изменять каждый байт на экране не нужно, на экране может отображаться большое количество макроблоков, достаточно обнаружить хотя бы один из них). STEP = 8 --таблица для сохранения хешей всех уникальных скриншотовshas = {} --запомнить значение, которое будет испорчено корраптом, чтобы потом его восстановитьlastValue = rom.readbyte (START_ADDR) --загрузить предварительно заготовленное сохранение из ПЕРВОГО слота (нумерация слотов в эмуляторе начинается с 0, а в LUA — с 1). s = savestate.create (2) savestate.load (s) while (true) do --если экран загрузился и уже отображается if (emu.framecount () > FRAME_FOR_SCREEN) then --сохранить скриншот в памяти local gdStr = gui.gdscreenshot (); --подсчитать его хеш local hash = emu.calchash (gdStr, string.len (gdStr)); --если такого скриншота ещё не было if (not shas[hash]) then print («Found new screen »…tostring (hash)); local fname = string.format (»%05X», CUR_ADDR)…».png»; local gdImg = gd.createFromGdStr (gdStr); --сохранить скриншот на диск с указанием в имени адреса изменённого байта gdImg: png (fname) shas[hash] = true; end; --восстановить значение предыдущего байта rom.writebyte (CUR_ADDR, lastValue); CUR_ADDR = CUR_ADDR + STEP; --коррапт следующего байта lastValue = rom.readbyte (CUR_ADDR); rom.writebyte (CUR_ADDR, WRITE_VALUE); --снова загрузка сохранения, чтобы дать возможность игре загрузить из нового образа данные в память s = savestate.create (2) --отображение прогресса savestate.load (s) gui.text (20,20, string.format (»%05X», CUR_ADDR)); --когда все адреса будут обработаны, остановить эмулятор if (CUR_ADDR > END_ADDR) then emu.pause (); end end; --проматываем эмуляцию до следующего кадра emu.frameadvance (); end;
Для запуска эмулятора со скриптом можно воспользоваться командным файлом такого содержания: fceux -turbo 1 -lua corrupt.lua «Jackal (U) [!].nes»(Ключ turbo позволит запустить эмулятор в максимально ускоренном режиме).Скрипт у меня на машине обрабатывает все данные за 8 минут. Если будет работать слишком долго, можно увеличить шаг STEP на больший, до 64 на экран, а также сделать более точное сохранение игры, в котором время между кадром запуска и кадром, на котором нужно делать скриншот, будет минимальным.Несколько рекомендаций по настройке скрипта под разные игры: данные о экранах часто начинаются с начала банков (по адресам, кратным 0×2000 или 0×4000), эти зоны можно исследовать подробнее; если в образе ROM есть видеобанки (CHR-ROM), их можно не исследовать, так как в них хранится исключительно видеопамять. Видеобанки находятся всегда в конце образа ROM, их количество также можно посмотреть в заголовке (первые 16 байт образа ROM).
Для игры «Jackal» скрипт находит 235 уникальных скриншотов, на которых предствлен широкий спектр всевозможных графических глитчей. Однако интерес представляют скриншоты, сделанные с образов с изменёнными байтами по адресам 0×105С8, 0×105D8, 0×105E8: 
Из них понятно, что:
Игра использует систему макроблоков размером 2×2 блока (4×4 тайла). Экраны описываются линиями по 16 макроблоков в ширину (разница между двумя соседними адресами). Линии хранятся в образе ROM в порядке снизу вверх. Что можно сделать с полученными данными? Например, подготовить картинки всех макроблоков уровня, что использовать их в блочном редакторе CadEditor для создания редактора карты уровня.Для этого надо слегка переписать скрипт коррапта так, чтобы он записывал все возможные значения байта по адресу, который приводит к изменению блока на экране (например, 0×105C8) и делал скриншоты всех блоков. Полный текст скрипта приводить не буду, он есть в архиве-примере в конце статьи (corrupt_byte.lua). К сожалению, библиотека gd не предназначена для удобной обработки частей картинок, поэтому для «выкусывания» из скриншота картинки макроблока и объединения их для удобства в одну длинную «ленту» пришлось написать ещё один скрипт на Python (с установленной библиотекой PIL для обработки картинок):
# -*- coding: utf-8 -*-import Imagedef cutBlock (pp): im = Image.open (pp) #загрузить скриншот в любой графический редактор, чтобы посмотреть координаты начала блока X = 96 Y = 96 #вырезать из скриншота блок по заданным координатам imCut = im.crop ((X, Y, X+32, Y+32)) imCut.save (»_» + pp) for x in xrange (256): cutBlock (r»%03d.png»%x) BLOCK_COUNT = 102MAX_BLOCK_COUNT = 256imBig = Image.new («RGB», (32*MAX_BLOCK_COUNT,32))for x in xrange (BLOCK_COUNT): im = Image.open (»_%03d.png»%x) imBig.paste (im, (32*x,0,32*x+32,32))#увеличение размера макроблока до 64×64, требование для использования с редактором CadEditorimBig64 = imBig.resize ((MAX_BLOCK_COUNT*64,64)) imBig64.save («outStrip.png»)
Добавление игры в редактор уровней Осталась последняя часть — необходимо создать конфигурационный файл для редактора CadEditor, который бы использовал полученную картинку. В нём в качестве скриптового языка используется C# (При помощи библиотеки CSScript).По скринам рассчитываем начало линии в карте макроблоков — если адрес 0×105C8 меняет 4-й макроблок в линии, то за первый отвечает адрес 0×105C5. Дальше создаём шаблонный конфиг: using CadEditor; using System; using System.Collections.Generic; using System.Drawing; public class Data{ /*вычисляем правильный адрес поочерёдно сдвигая границы линий вверх и вниз до тех пор, пока в «окне» не окажется правильная карта уровня. От стартового адреса 0×10625 отступаем 96 линий вверх. 1 — количество игровых экранов на уровне, 16×96 — размер в байтах одного игрового экрана */ public OffsetRec getScreensOffset () { return new OffsetRec (0×10625 — 16×96, 1, 16×96); } public int getScreenWidth () { return 16; } //устанавливаем ширину экрана public int getScreenHeight () { return 96; } //задаём высоту экрана public int getBigBlocksCount () { return 256; } //подкючаем стрип с картинками макроблоков public string getBlocksFilename () { return «jackal_1.png»; } //выключаем подредакторы макроблоков и врагов, которые для данной игры не реализованы public bool isBigBlockEditorEnabled () { return false; } public bool isBlockEditorEnabled () { return false; } public bool isEnemyEditorEnabled () { return false; }}
Загруженная в редактор карта уровня с таким конфигом выглядит странно, хотя и напоминает реальную: 
После изучения результата оказывается, что линии экрана размером 16×8 макроблоков хранятся в порядке снизу вверх, но сами экраны — сверху вниз, из-за чего получается, что каждые 8 линий экрана переставлены местами. К счастью, в редакторе имеется большое количество методов, которые позволяют задать, как именно будет загружен из образа ROM уровень. В данном случае нужно задать две специальные функции, которые будут управлять тем, как именно будет читаться номер макроблока из карты и, соотвественно, как он будет записываться редактором обратно.
//Указание редактору использовать специальную функцию для получения номера макроблока из//карты и записи обратноpublic GetBigTileNoFromScreenFunc getBigTileNoFromScreenFunc () { return getBigTileNoFromScreen; } public SetBigTileToScreenFunc setBigTileToScreenFunc () { return setBigTileToScreen; } public int getBigTileNoFromScreen (int[] screenData, int index) { int w = getScreenWidth (); int noY = index / w; noY = (noY/8)*8 + 7 — (noY%8); //трансформация Y-координаты макроблока int noX = index % w; return screenData[noY*w + noX]; } public void setBigTileToScreen (int[] screenData, int index, int value) { int w = getScreenWidth (); int noY = index / w; noY = (noY/8)*8 + 7 — (noY%8); //трансформация Y-координаты макроблока int noX = index % w; screenData[noY*w + noX] = value; }
Всё, теперь карта отображается правильно и можно перерисовать геометрию уровня: 
Метод поиска применим почти ко всем NES-играм, можете воспользоваться скриптами из архива с примером для исследования ваших любимых игр! Кроме того, с некоторыми модификациями метод применим и для платформ «Sega Mega Drive» и «SNES» (отличие в том, что модифицировать надо не сам образ ROM, а оперативную память приставки, зачастую распакованная карта уровня хранится в ней).
В следующей статье я покажу на примере какой-нибудь игры устройство игровой логики и методы поиска игровых объектов, чтобы отобразить и расставить их на карте.
Ссылки: Архив с примеромОткомментированные скрипты
