Двоичный поиск

Описание поиска

Поиск по своему принципу является методом исключения. Демонстрацию двоичного поиска смотри на этом видео.

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

Далее желательно поставить эмулятор на паузу, затем загружаешь первое сохранение, копируешь из него полностью все байты RAM диапазона $0000-$07FF и вставляешь по тому же месту во второе сохранение. По принципу копирование/вставка байтов похожа на механику загрузки сохранения, то есть ты заменяешь состояние игры на другое.

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

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

Продолжение поиска

Когда ты убедился, что этот способ работает для поиска координат, проверяешь любую из двух половин RAM, которая тебе кажется наиболее вероятной. Половинами будут диапазоны $0000-$03FF и $0400-$07FF. Копируешь одну из них из первого сохранения и вставляешь во второе по тому же месту.

Если же копирование диапазона $0000-$07FF вызвало ошибки, первым делом следует исключить из копирования адреса стека $0100-$01FF, про которые рассказано в подразделе этой статьи.

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

Всего в RAM 2048 адресов в диапазоне $0000-$07FF. Это означает, что практически всегда можно найти адрес с 11-й попытки, каждый раз уменьшая количество адресов вдвое, отсекая лишнюю половину.

Увеличение шансов

Правильные сохранения

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

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

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

Пауза

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

А при вставке без паузы возможно тебе будет проблематично оценить результат двоичного поиска. Для просмотра результата в замедленном режиме пользуйся горячей клавишей Frame Advance.

Высокая точность сохранений

В редких случаях потребуется сохраниться на протяжении кадра в особой временной точке, когда игра еще не успела проверить искомый адрес. Зная код игры, нужно поставить Execute брейкпоинт в том месте, где он будет срабатывать ежекадрово лишь 1 раз за кадр, а после его срабатывания сохраниться.

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

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

Почему поиск не работает

Файл сохранения

Предположим, ты скопировал диапазон $0000-$07FF из первого сохранения во второе, но интересующее тебя игровое событие продолжает повторяться на втором сохранении.

Сохранение хранит в себе множество других технических параметров, относящихся к текущему игровому состоянию. Это не только байты в адресах RAM, но еще и байты в регистрах CPU, PPU и APU, байты в адресах PPU Memory, подключенные PRG банки и различные внутренние тайминги процессора.

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

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

SRAM

Также к RAM могут относиться адреса батарейки в диапазоне $6000-$7FFF, в которых RPG-игры могут сохранять данные прохождения. Если батарейка используется в игре, ее тоже стоит проверить, когда поиск в основной RAM не принес результатов.

Несмотря на то, что SRAM по размеру в 4 раза больше RAM, поиск займет не в 4 раза дольше по времени, а просто на 2 попытки больше.

2 адреса

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

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

По моему опыту, эти 2 адреса будут находиться в пределах нескольких строк друг от друга. 3 и более адресов одновременно я не встречал, но такое теоретически возможно.

Стек

Адреса стека $0100-$01FF задуманы для хранения байтов, отвечающих за адреса возврата из подпрограмм. При ручном изменении этих байтов на сохранении, например при копировании, цепочка возврата из подпрограмм может нарушиться, что приведет к зависанию.

Но в то же время не все адреса стека используются для возврата из подпрограмм. Обычно адреса для подпрограмм находятся в конце стека, около 1/4 части общего диапазона.

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

Зависания

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

Исключением является сохранение на другой сканлинии при использовании Debugger'а. Номер текущей сканлинии можно посмотреть в Debugger'е на паузе эмулятора.

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

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

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

Особый случай

В игре Tecmo Bowl в режиме Season Game, после матча игра записывает статистику этого матча в таблицу. Также есть режим Preseason, в котором статистика во время матча хоть и учитывается в RAM, но по итогу в таблицу не заносится.

В отличие от примера из Battle City, который можно посмотреть на видео, где за продолжение игры/Game Over после подсчета очков отвечает адрес, байт из которого проверяется игрой, в Tecmo Bowl такого простого адреса не существует.

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

Спрайты

Память спрайтов, находящаяся в RAM чаще всего по адресам $0200-$02FF, служит для последующего копирования параметров спрайтов в OAM Memory для отображения их на экране.

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

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

Исходя из этого, в 99% случаев можно полностью игнорировать этот диапазон.

Особый случай

В игре Urban Champion время от времени в окне здания появляется мужик, который бросает вниз горшок с цветком. Изображение состоит из двух спрайтов - горшок и цветок.

Координаты X и Y горшка как объекта хранятся не в отдельных адресах, а непосредственно в той области RAM, которая зарезервирована для спрайтов. Абсолютно любой спрайт требует адреса с Y и X координатами, и как раз эти адреса игра использует для хранения координат объекта. В этой игре они всегда расположены по одному и тому же адресу.

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

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

Рандом

Это, пожалуй, единственные адреса, которые плохо поддаются двоичному поиску. Байты в адресах с рандомом вычисляются исходя из того, какие байты находятся в других адресах RAM.

Например, в игре Castlevania III - Dracula's Curse, даже создав 2 практически идентичных сохранения, в одном из которых после убийства врага выпадает предмет, поиск конкретных адресов может занять слишком много времени. Усложняет ситуацию то, что в этой игре рандом вычисляется в бесконечном цикле в конце кадра.

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

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