Главная » Хабрахабр » [Перевод] Извлекаем уровни из Super Mario Bros с помощью Python

[Перевод] Извлекаем уровни из Super Mario Bros с помощью Python

Введение

Для нового проекта мне понадобилось извлечь данные уровней из классической видеоигры 1985 года Super Mario Bros (SMB). Если конкретнее, то я хотел извлечь фоновую графику каждого уровня игры без интерфейса, подвижных спрайтов и т.п.

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

Полный исходный код выложен здесь.
На первом этапе проекта мы изучим язык ассемблера 6502 и написанный на Python эмулятор.

Анализ исходного кода

Реверс-инжиниринг любой программы намного проще, если есть её исходный код, а у нас имеются исходники SMB в виде 17 тысяч строк ассемблерного кода 6502 (процессора NES), опубликованных doppelganger. Поскольку Nintendo так и не выпустила официального релиза исходников, код был создан дизассемблированием машинного кода SMB, с мучительной расшифровкой значения каждой части, добавлением комментариев и осмысленных символьных названий.

Выполнив быстрый поиск по файлу, я нашёл нечто, похожее на нужные нам данные уровней:

;level 1-1
L_GroundArea6:
.db $50, $21
.db $07, $81, $47, $24, $57, $00, $63, $01, $77, $01
.db $c9, $71, $68, $f2, $e7, $73, $97, $fb, $06, $83
.db $5c, $01, $d7, $22, $e7, $00, $03, $a7, $6c, $02
.db $b3, $22, $e3, $01, $e7, $07, $47, $a0, $57, $06
.db $a7, $01, $d3, $00, $d7, $01, $07, $81, $67, $20
.db $93, $22, $03, $a3, $1c, $61, $17, $21, $6f, $33
.db $c7, $63, $d8, $62, $e9, $61, $fa, $60, $4f, $b3
.db $87, $63, $9c, $01, $b7, $63, $c8, $62, $d9, $61
.db $ea, $60, $39, $f1, $87, $21, $a7, $01, $b7, $20
.db $39, $f1, $5f, $38, $6d, $c1, $af, $26
.db $fd

Можно воспринимать этот фрагмент как массив, в котором каждый элемент является байтом. Если вы незнакомы с ассемблером, то я объясню: всё это просто означает «вставить такой набор байтов в скомпилированную программу, а потом позволить другим частям программы ссылаться на него с помощью символа L_GroundArea6».

Поэтому мы исключаем все виды кодирования, позволяющие произвольно размещать блоки на уровне. Первое, что можно заметить — объём данных очень мал (около 100 байтов). Эта подпроцедура в свою очередь вызывает множество других подпроцедур, в конечном итоге вызывая конкретные подпроцедуры для каждого типа объектов, допустимых в сцене (например, StaircaseObject, VerticalPipe, RowOfBricks) для более чем 40 объектов: Немного поискав, я обнаружил, что эти данные считываются (после нескольких операций косвенной адресации) в AreaParserCore.

Сокращённый граф вызовов для AreaParserCore

Метатайл (metatile) — это блок 16x16, из которого составляются фоны игры SMB: Процедура выполняет запись в MetatileBuffer: раздел памяти длиной 13 байтов, представляющий собой один столбец блоков в уровне, каждый байт которого обозначает отдельный блок.

Уровень с прямоугольниками, описанными вокруг метатайлов

Они называются метатайлами, потому что каждый состоит из четырёх тайлов размером 8x8 пикселей, но подробнее об этом ниже.

Однако это означает, что для превращения сырых данных уровня в метатайлы требуется много кода. То, что декодер работает с заранее заданными объектами, объясняет маленький размер уровня: данные уровня должны ссылаться только на типы объектов и их расположение, например «расположить трубу в точке (20, 16), ряд блоков в точке (10, 5), …».

Портирование такого объёма кода для создания собственного распаковщика уровней заняло бы слишком много времени, поэтому давайте попробуем другой подход.

py65emu

Если бы у нас был интерфейс между Python и языком ассемблера 6502, мы могли бы вызывать подпроцедуру AreaParserCore для каждого столбца уровня, а затем использовать более понятный Python для преобразования информации блоков в нужное изображение.

Вот как в py65emu настраивается та же конфигурация памяти, что и в NES: Тут на сцене появляется py65emu — лаконичный эмулятор 6502 с интерфейсом Python.

from py65emu.cpu import CPU from py65emu.mmu import MMU # Загрузка ROM программы (т.е. скомпилированного ассемблера) with open("program.bin", "rb") as f: prg_rom = f.read() # Задаём распределение памяти. mmu = MMU([ # Создание 2K ОЗУ, привязываемых к адресу 0x0. (0x0, 2048, False, []), # Привязка ROM программы к 0x8000. (0x8000, len(prg_rom), True, list(prg_rom)) ]) # Создаём ЦП и говорим ему, чтобы он начинал выполнение с адреса 0x8000 cpu = CPU(mmu, 0x8000)

После этого мы можем выполнять отдельные инструкции с помощью метода cpu.step(), исследовать память с помощью mmu.read(), изучать регистры машины с помощью cpu.r.a, cpu.r.pc и т.д. Кроме того, мы можем выполнять запись в память с помощью mmu.write().

Однако его должно быть достаточно для вызова подпроцедуры парсинга, потому что она не использует никаких других аппаратных устройств, кроме ЦП и памяти. Стоит заметить, что это всего лишь эмулятор процессора NES: он не эмулирует другие аппаратные части, такие как PPU (Picture Processing Unit), поэтому его нельзя использовать для эмуляции всей игры.

После завершения этих операций мы используем Python для сборки результата в готовое изображение. План заключается в том, чтобы настроить ЦП так, как показано выше, а затем для каждого столбца уровня инициализировать разделы памяти с входными значениями, требуемыми для AreaParserCore, вызвать AreaParserCore, а затем считать обратно данные столбца.

Но перед этим нам нужно скомпилировать листинг на ассемблере в машинный код.

x816

Как указано в исходном коде, ассемблер компилируется с помощью x816. x816 — это ассемблер 6502 под MS-DOS, используемый сообществом разработчиков самодельных игр (homebrew) для NES и ROM-хакеров. Он замечательно работает в DOSBox.

Вот фрагмент файла: Наряду с ROM программы, который необходим для py65emu, ассемблер x816 создаёт символьный файл, привязывающий символы к расположению их в памяти в адресном пространстве ЦП.

AREAPARSERCORE = $0093FC ; <> 37884, statement #3154
AREAPARSERTASKCONTROL = $0086E6 ; <> 34534, statement #1570
AREAPARSERTASKHANDLER = $0092B0 ; <> 37552, statement #3035
AREAPARSERTASKNUM = $00071F ; <> 1823, statement #141
AREAPARSERTASKS = $0092C8 ; <> 37576, statement #3048

Здесь мы видим, что к функции AreaParserCore в исходном коде можно получить доступ по адресу 0x93fc.

Для удобства я написал парсер символьного файла, который сопоставляет названия символов и адреса:

sym_file = SymbolFile('SMBDIS.SYM')
print("0x".format(sym_file['AREAPARSERCORE'])) # выводит 0x93fc
print(sym_file.lookup_address(0x93fc)) # выводит "AREAPARSERCORE"

Подпроцедуры

Как сказано в представленном выше плане, мы хотим научиться вызывать подпроцедуру AreaParserCore из Python.

Чтобы понять механику подпроцедуры, давайте изучим короткую подпроцедуру и соответствующий ей вызов:

WritePPUReg1: sta PPU_CTRL_REG1 ;записывает содержимое A в регистр 1 PPU sta Mirror_PPU_CTRL_REG1 ;и в его зеркало rts ... jsr WritePPUReg1

Инструкция jsr (jump to subroutine, «перейти к подпроцедуре») добавляет регистр PC в стек и присваивает ему значение адреса, на который ссылается WritePPUReg1. Регистр PC сообщает процессору адрес следующей загружаемой инструкции, чтобы следующая инструкция, выполняемая после инструкции jsr, была первой строкой WritePPUReg1.

Эта команда удаляет сохранённое значение из стека и сохраняет его в регистре PC, что заставляет ЦП выполнить инструкцию, следующую за вызовом jsr. В конце подпроцедуры выполняется инструкция rts (return from subroutine, «возврат из подпроцедуры»).

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

Вот код для выполнения подпроцедуры из Python:

def execute_subroutine(cpu, addr): s_before = cpu.r.s cpu.JSR(addr) while cpu.r.s != s_before: cpu.step() execute_subroutine(cpu, sym_file['AREAPARSERCORE'])

Код сохраняет текущее значение регистра указателя стека (s), эмулирует вызов jsr, а затем выполняет инструкции, пока стек не вернётся к исходной высоте, что происходит только после возврата первой подпроцедуры. Это будет полезно, потому что теперь у нас есть способ прямого вызова подпроцедур 6502 из Python.

Нам нужно сообщить процедуре, какой уровень мы хотим отрендерить и какой столбец нам нужно парсить. Однако мы кое о чём забыли: как передавать входные значения для этой подпроцедуры?

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

Valgrind для NES?

Чтобы найти способ для определения входных значений AreaParserCore, я использовал в качестве примера инструмент memcheck для Valgrind. Memcheck распознаёт операции доступа к неинициализированной памяти благодаря хранению «теневой» памяти параллельно с каждым фрагментом настоящей выделенной памяти. Теневая память записывает, выполнялась ли запись в соответствующую реальную память. Если программа выполняет считывание по адресу, в который никогда не выполняла записть, то выводится ошибка неинициализированной памяти. Мы можем запустить AreaParserCore с таким инструментом, который сообщит нам, какие входные данные нужно задать, прежде чем вызывать подпроцедуру.

На самом деле написать простую версию memcheck для py65emu очень легко:

def format_addr(addr): try: symbol_name = sym_file.lookup_address(addr) s = "0x{:04x} ({}):".format(addr, symbol_name) except KeyError: s = "0x{:04x}:".format(addr) return s class MemCheckMMU(MMU): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self._uninitialized = array.array('B', [1] * 2048) def read(self, addr): val = super().read(addr) if addr < 2048: if self._uninitialized[addr]: print("Uninitialized read! {}".format(format_addr(addr))) return val def write(self, addr, val): super().write(addr, val) if addr < 2048: self._uninitialized[addr] = 0

Здесь мы обернули блок управления памятью (MMU) py65emu. Этот класс содержит массив _uninitialized, элементы которого сообщают нам, выполнялась ли когда-нибудь запись в соответствующий байт эмулируемой ОЗУ. В случае возникновения неинициализированного считывания выводится адрес неверной операции считывания и имя соответствующего символа.

Вот какие результаты даёт MMU в обёртке при вызове execute_subroutine(sym_file['AREAPARSERCORE']):

0x0728 (BACKLOADINGFLAG):
Uninitialized read! Uninitialized read! 0x0741 (FOREGROUNDSCENERY):
Uninitialized read! 0x0742 (BACKGROUNDSCENERY):
Uninitialized read! 0x075f (WORLDNUMBER):
Uninitialized read! 0x074e (AREATYPE):
Uninitialized read! 0x0727 (TERRAINCONTROL):
Uninitialized read! 0x0743 (CLOUDTYPEOVERRIDE):
Uninitialized read! 0x074e (AREATYPE):
...
0x0743 (CLOUDTYPEOVERRIDE):
Uninitialized read!

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

mmu.write(sym_file['WORLDNUMBER'], 0) # Номер мира минус 1
mmu.write(sym_file['AREANUMBER'], 0) # Номер уровня минус 1
execute_subroutine(sym_file['LOADAREAPOINTER'])
execute_subroutine(sym_file['INITIALIZEAREA']) metatile_data = [] for column_pos in range(48): execute_subroutine(sym_file['AREAPARSERCORE']) metatile_data.append([mmu.read_no_debug(sym_file['METATILEBUFFER'] + i) for i in range(13)]) execute_subroutine(sym_file['INCREMENTCOLUMNPOS'])

Код записывает первые 48 столбцов уровня World 1-1 в metatile_data, используя подпроцедуру IncrementColumnPos для увеличения внутренних переменных, необходимых для отслеживания текущего столбца.

А вот содержимое metatile_data, наложенное на скриншоты из игры (байты со значением 0 не показаны):

Очевидно, что metatile_data явно соответствует информации фона.

Графика метатайлов

(Чтобы посмотреть конечный результат, можно сразу перейти к разделу «Соединяем всё вместе».)

Описанные ниже этапы придуманы благодаря анализу исходников и чтению документации с потрясающей Nesdev Wiki. Теперь давайте разберёмся, как превратить полученные числа метатайлов в настоящие изображения.

PPU консоли NES способен в общем рендерить 64 разных цвета, однако чёрный цвет несколько раз дублируется (подробности см. Чтобы понять, как рендерить каждый метатайл, нам сначала нужно поговорить о цветовых палитрах NES. в Nesdev):

Каждый уровень Mario может использовать для фона только 10 из этих 64 цветов, разделённых на на 4 четырёхцветных палитры; первый цвет всегда одинаков. Вот четыре палитры для World 1-1:

Давайте теперь рассмотрим пример номера метатайла, представленный в двоичном виде. Вот номер метатайла тайла камней с трещинами, который является землёй уровня World 1-1:

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

MetatileGraphics_Low:
.db <Palette0_MTiles, <Palette1_MTiles, <Palette2_MTiles, <Palette3_MTiles

MetatileGraphics_High:
.db >Palette0_MTiles, >Palette1_MTiles, >Palette2_MTiles, >Palette3_MTiles

Сочетание этих двух массивов даёт нам 16-битный адрес, который в нашем примере указывает на Palette1_Mtiles:

Palette1_MTiles:
.db $a2, $a2, $a3, $a3 ;vertical rope
.db $99, $24, $99, $24 ;horizontal rope
.db $24, $a2, $3e, $3f ;left pulley
.db $5b, $5c, $24, $a3 ;right pulley
.db $24, $24, $24, $24 ;blank used for balance rope
.db $9d, $47, $9e, $47 ;castle top
.db $47, $47, $27, $27 ;castle window left
.db $47, $47, $47, $47 ;castle brick wall
.db $27, $27, $47, $47 ;castle window right
.db $a9, $47, $aa, $47 ;castle top w/ brick
.db $9b, $27, $9c, $27 ;entrance top
.db $27, $27, $27, $27 ;entrance bottom
.db $52, $52, $52, $52 ;green ledge stump
.db $80, $a0, $81, $a1 ;fence
.db $be, $be, $bf, $bf ;tree trunk
.db $75, $ba, $76, $bb ;mushroom stump top
.db $ba, $ba, $bb, $bb ;mushroom stump bottom
.db $45, $47, $45, $47 ;breakable brick w/ line
.db $47, $47, $47, $47 ;breakable brick
.db $45, $47, $45, $47 ;breakable brick (not used)
.db $b4, $b6, $b5, $b7 ;cracked rock terrain <--- This is the 20th line
.db $45, $47, $45, $47 ;brick with line (power-up)
.db $45, $47, $45, $47 ;brick with line (vine)
.db $45, $47, $45, $47 ;brick with line (star)
.db $45, $47, $45, $47 ;brick with line (coins)
...

Данные форматированы в 4 записи на строку, поэтому наш пример метатайла ссылается на двадцатую строку, помеченную комментарием cracked rock terrain. При умножении индекса метатайла на 4 он становится индексом этого массива.

Эти идентификаторы передаются непосредственно в PPU консоли NES. Четыре записи этой строки на самом деле являются идентификаторами тайлов: каждый метатайл состоит из четырёх тайлов размером 8x8 пикселей, выстроенных в следующем порядке — верхний левый, нижний левый, верхний правый и нижний правый. Идентификатор ссылается на 16 байтов данных в CHR-ROM консоли, а каждая запись начинается с адреса 0x1000 + 16 * <идентификатор тайла>:

0x1000 + 16 * 0xb4: 0b01111111 0x1000 + 16 * 0xb5: 0b11011110
0x1001 + 16 * 0xb4: 0b10000000 0x1001 + 16 * 0xb5: 0b01100001
0x1002 + 16 * 0xb4: 0b10000000 0x1002 + 16 * 0xb5: 0b01100001
0x1003 + 16 * 0xb4: 0b10000000 0x1003 + 16 * 0xb5: 0b01100001
0x1004 + 16 * 0xb4: 0b10000000 0x1004 + 16 * 0xb5: 0b01110001
0x1005 + 16 * 0xb4: 0b10000000 0x1005 + 16 * 0xb5: 0b01011110
0x1006 + 16 * 0xb4: 0b10000000 0x1006 + 16 * 0xb5: 0b01111111
0x1007 + 16 * 0xb4: 0b10000000 0x1007 + 16 * 0xb5: 0b01100001
0x1008 + 16 * 0xb4: 0b10000000 0x1008 + 16 * 0xb5: 0b01100001
0x1009 + 16 * 0xb4: 0b01111111 0x1009 + 16 * 0xb5: 0b11011111
0x100a + 16 * 0xb4: 0b01111111 0x100a + 16 * 0xb5: 0b11011111
0x100b + 16 * 0xb4: 0b01111111 0x100b + 16 * 0xb5: 0b11011111
0x100c + 16 * 0xb4: 0b01111111 0x100c + 16 * 0xb5: 0b11011111
0x100d + 16 * 0xb4: 0b01111111 0x100d + 16 * 0xb5: 0b11111111
0x100e + 16 * 0xb4: 0b01111111 0x100e + 16 * 0xb5: 0b11000001
0x100f + 16 * 0xb4: 0b01111111 0x100f + 16 * 0xb5: 0b11011111

0x1000 + 16 * 0xb6: 0b10000000 0x1000 + 16 * 0xb7: 0b01100001
0x1001 + 16 * 0xb6: 0b10000000 0x1001 + 16 * 0xb7: 0b01100001
0x1002 + 16 * 0xb6: 0b11000000 0x1002 + 16 * 0xb7: 0b11000001
0x1003 + 16 * 0xb6: 0b11110000 0x1003 + 16 * 0xb7: 0b11000001
0x1004 + 16 * 0xb6: 0b10111111 0x1004 + 16 * 0xb7: 0b10000001
0x1005 + 16 * 0xb6: 0b10001111 0x1005 + 16 * 0xb7: 0b10000001
0x1006 + 16 * 0xb6: 0b10000001 0x1006 + 16 * 0xb7: 0b10000011
0x1007 + 16 * 0xb6: 0b01111110 0x1007 + 16 * 0xb7: 0b11111110
0x1008 + 16 * 0xb6: 0b01111111 0x1008 + 16 * 0xb7: 0b11011111
0x1009 + 16 * 0xb6: 0b01111111 0x1009 + 16 * 0xb7: 0b11011111
0x100a + 16 * 0xb6: 0b11111111 0x100a + 16 * 0xb7: 0b10111111
0x100b + 16 * 0xb6: 0b00111111 0x100b + 16 * 0xb7: 0b10111111
0x100c + 16 * 0xb6: 0b01001111 0x100c + 16 * 0xb7: 0b01111111
0x100d + 16 * 0xb6: 0b01110001 0x100d + 16 * 0xb7: 0b01111111
0x100e + 16 * 0xb6: 0b01111111 0x100e + 16 * 0xb7: 0b01111111
0x100f + 16 * 0xb6: 0b11111111 0x100f + 16 * 0xb7: 0b01111111

Он отделён от PRG-ROM, в котором хранится код программы. CHR-ROM — это фрагмент памяти read-only, к которому может получать доступ только PPU. Поэтому приведённые выше данные отсутствуют в исходном коде и их нужно получать из дампа ROM игры.

16 байта для каждого тайла составляют 2-битный тайл размером 8x8: первый бит — это первые 8 байтов, а второй — вторые 8 байтов:

21111111 13211112
12222222 23122223
12222222 23122223
12222222 23122223
12222222 23132223
12222222 23233332
12222222 23111113
12222222 23122223

12222222 23122223
12222222 23122223
33222222 31222223
11332222 31222223
12113333 12222223
12221113 12222223
12222223 12222233
23333332 13333332

Выполняем привязку этих данных к палитре 1:

…и объединяем куски:

Наконец мы получили отрендеренный тайл.

Соединяем всё вместе

Повторив эту процедуру для каждого метатайла, мы получим полностью отрендеренный уровень.

И благодаря этому нам удалось извлечь графику уровней SMB с помощью Python!


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

На основе здравого смысла: выращиваем DevOps с нуля

Накануне DevOps Conf Russia 2018 мы поговорили с техническим директором «Учи.ру» Алексеем Ваховым об этапах развития платформы, о том, какие инструменты они используют и насколько там все DevOps-ово. Работал разработчиком C++ в огромных системах (десятки миллионов строк кода). Алексей Вахов ...

[Перевод] Руководство по Node.js, часть 3: хостинг, REPL, работа с консолью, модули

Перед вами третья часть перевода руководства по Node.js. Сегодня мы поговорим о выборе хостинга для Node.js-проектов, о том, как работать с Node.js в режиме REPL и как запускать скрипты с аргументами, о взаимодействии с консолью и о модулях. [Советуем почитать] ...