Pokemon Yellow - это карманная вселенная со своими правилами. В ней можно покупать и продавать предметы, тренировать покемонов, побеждать других тренеров но нельзя менять правила самой игры. Нельзя построить себе дом, поменять музыку или даже переодеться. Точнее, так было задумано. На самом деле есть последовательность валидных команд (типа перемещения из одного места в другое и манипуляций с предметами), которая позволяет превратить игру в Pacman, тетрис, Pong, MIDI-проигрыватель и что угодно ещё.

Существует спидран Felipe Lopes de Freitas (p4wn3r), в котором Pokemon Yellow проходится за 1 минуту 36 секунд. Этот спидран основан на следующем хаке: в норме инвентарь игрока ограничен 20 предметами. Но есть баг, который позволяет игнорировать это ограничение и обращаться с памятью, расположенной сразу после инвентаря, как будто бы это был список предметов. Соответственно, стандартные манипуляции с предметами позволяют эту память переписывать. Спидраннер использует эту возможность, чтобы заставить дверь из стартовой комнаты переносить его на финальную локацию, в которой ему остаётся только выслушать поздравления.

Когда я впервые увидел этот спидран и понял, что памятью Gameboy можно манипулировать с помощью одного только списка предметов, безо всяких внешних инструментов, я решил посмотреть, получится ли у меня усовершенствовать приёмы p4wn3r. Вот что получилось:

Gameboy это восьмибитный компьютер. Соответственно, всё происходящее в игре результат того, что исполняется некая последовательность однобайтовых команд. Например, последовательность[62 16 37 224 47 240 37 230 15 55] в местных машинных кодах означает, что надо выяснить, какие кнопки нажаты в данный момент, и записать результат в регистр A. Можно создать программу, которая будет читать ввод с кнопок и записывать куда-нибудь в память исполняемый код, а потом передавать ему управление. Если удастся каким-то образом засунуть такую программу (назовём её программой ввода) в память и заставить Gameboy её исполнить то я выиграл, потому что теперь я могу исполнять произвольный код (скажем, тетрис) вместо Pokemon Yellow.

Во-первых, как написать такую программу? Восьмибитными числами представлены не только правила, но и состояние игры (инвентарь, список покемонов, имя главного героя и т.п.) Инвентарь хранится вот так:

item-one-id         (0-255)item-one-quantity   (0-255)item-two-id         (0-255)item-two-quantity   (0-255)...

Упомянутая выше подпрограмма для чтения кнопок хранится в той же последовательности битов, что и следующий набор предметов:

lemonade     x16guard spec.  x224leaf stone   x240guard spec.  x230parlyz heal  x55

Так что если нам удастся собрать нужные предметы в нужном количестве и порядке то получится код программы ввода. Правда, его с самого начала нужно писать так, чтобы он состоял только из валидных ID и количеств предметов. Это не так-то просто, потому что предметов в игре немного, а многие машинные инструкции состоят из 2-3 битов. Та версия программы, на которой я остановился, состоит из 92 бит; примерно половина из них не делает ничего полезного и вставлена только для того, чтоб код был ещё и корректным списком предметов.

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

Поехали!

Я начинаю с того, что называю своего противника Lp/k. Эти символы в своё время превратятся в предметы и будут перемещены на указатель функции, чтобы я мог исполнить программу ввода. Но сперва её надо записать, так что я начинаю забег так же, как и p4wn3r: перезапускаю игру при сохранении, чтобы сломать список покемонов. После этого я меняю местами 8 и 10 покемона, что ломает список предметов и позволяет мне манипулировать предметами после 20-го (то есть соответствующей областью памяти). С помощью этих манипуляций я выставляю скорость текста на максимум и переключаю свою дверь на магазин Celadon Dept. store. p4wn3r в этот момент переключил её на Зал славы и выиграл, но мне неинтересен спидран как таковой.

Поэтому я не останавливаюсь, а выкладываю из своего поломанного инвентаря в сундук множество глитчевых предметов 0x00, которые мне ещё пригодятся. Потом я забираю из сундука зелье, что вызывает переполнение счётчика предметов с 0xFF на 0x00 и восстанавливает мой инвентарь. Зелье при этом, правда, исчезает. После этого я забираю 255 0x00-предметов и отправляюсь в магазин. Там я продаю 2 0x00 за 414925 монет каждый, что позволяет мне купить следующие предметы:

+-------------------+----------+|##| Item           | Quantity |+--+----------------+----------+|1 | TM02           |  98      ||2 | TM37           |  71      ||3 | TM05           |   1      ||4 | TM09           |   1      ||5 | burn-heal      |  12      ||6 | ice-heal       |  55      ||7 | parlyz-heal    |  99      ||8 | parlyz-heal    |  55      ||9 | TM18           |   1      ||10| fire-stone     |  23      ||11| water-stone    |  29      ||12| x-accuracy     |  58      ||13| guard-spec     |  99      ||14| guard-spec     |  24      ||15| lemonade       |  16      ||16| TM13           |   1      |+--+----------------+----------+

Эти предметы я раскладываю в инвентаре в таком порядке, чтобы получилась моя первая программа ввода. Первая потому что написать окончательную версию программы ввода внутри игры у меня не получилось. Та, которую я собираю из предметов, умеет читать только кнопки A, B, start и select. Каждый фрейм игры она пишет 4 бита в определённую область памяти; собрав 200 с лишним байт, она исполняет то, что написала. С помощью этой программы я пишу следующую, которая читает уже все 8 кнопок и пишет произвольное число байтов в произвольную область памяти, а потом исполняет код по произвольному адресу. Эта программа, в свою очередь, используется для загрузки третьей, которая делает всё то же самое, но ещё и выводит записываемый код на экран.

Закончив с кодом первой программы, я отправляюсь в Celadon mansion (это не критично, мне просто нравится локация). Там я снова меняю местами сломанных покемонов и ломаю инвентарь. Проскроллив до имени своего противника, я выкидываю предметы до тех пор, пока имя не окажется на указателе функции. Как только я закрываю меню, программа ввода исполняется, и я могу заливать следующую программу.

Инфраструктура

Всё видео было записано ботами, а сам я к Gameboy (точнее, к эмулятору) даже не притрагивался. Ниже краткое описание инфраструктуры, которую я создал для этого проекта. Исходники доступны в http://hg.bortreb.com/vba-clojure

Прежде всего, мне нужен был программный доступ к эмулятору, так что я скачал vba-rerecording. Поверх него я написал низкоуровневый интерфейс на C, к которому я смогу обращаться из Java через JNI. Этот интерфейс позволяет обращаться к базовым функциям эмулятора: прогнать один фрейм игры или один тик часов Gameboy, обратиться к любому адресу памяти или регистру. Кроме того, он позволяет выгрузить состояние эмулятора в объект Java или загрузить его обратно.

Поверх JNI я написал обёртку на clojure, так что в итоге у меня получился функциональный интерфейс к vba-rerecording. Этот интерфейс работает с состоянием эмулятора как с иммутабельным объектом и позволяет делать в функциональном стиле всё то, что интерфейс на C позволял делать в императивном. С помощью этого интерфейса я написал функции, которые принимают на вход состояние эмулятора, находят и исполняют последовательность команд, которая приведёт к желаемому эффекту. Из этих функций я собрал высокоуровневые функции, которые выполняют в игре задачи типа перемещения и покупки предметов. Вот, например, код для перемещения кратчайшим путём из магазина покемонов в Viridian City в лабораторию Оака:

(defn-memo viridian-store->oaks-lab  ([] (viridian-store->oaks-lab       (get-oaks-parcel)))  ([script]     (->> script          (walk [                                                                                                                                                                                                                                       ])          (walk-thru-grass           [      ])          (walk [                                                ])                          (do-nothing 1))))

А вот функция, которая находит кратчайшую последовательность команд для переноса нужных предметов в сундук:

(defn-memo hacking-10  ([] (hacking-10 (hacking-9)))  ([script]     (->> script          begin-deposit          (deposit-held-item 17 230)          (deposit-held-item-named :parlyz-heal 55)          (deposit-held-item 14 178)          (deposit-held-item-named :water-stone 29)          (deposit-held-item 14 32)          (deposit-held-item-named :TM18 1)          (deposit-held-item 13 1)          (deposit-held-item 13 191)          (deposit-held-item-named :TM02 98)          (deposit-held-item-named :TM09 1)          close-menu)))

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

Мне особенно пригодились глитч-предметы 0x00 и 0xFF. 0x00 стоит почти половину максимально возможного числа денег, и всего двух хватило на то, чтоб купить все необходимые предметы. К тому же 0x00 это NO-OP, который я могу вставлять куда угодно, чтобы подогнать программу под требования инвентаря. 0xFF имеет другое полезное свойство. В норме игра объединяет стеки предметов: если купить, например, покеболл, а потом ещё один покеболл, то инвентарь будет выглядеть вот так:

pokeball x2

Но если где-то перед тем в списке предметов есть 0xFF, то эта функция отключается, что позволяет мне получить вот такой инвентарь:

pokeball x1pokeball x1pokeball x1

Так что я вставляю в самое начало инвентаря 0xFF и больше об этом не беспокоюсь.

Полезная нагрузка, которую я залил в Gameboy, это тоже последовательность программ. Я создал упрощённый формат MIDI, имплементировал его в машинных кодах GameBoy, и перевёл в свой формат мелодию с http://www.everyponysings.com/. В полезной нагрузке последней программы ввода содержится как сам MIDI-файл, так и интерпретатор. Картинка устроена так же я перевёл PNG-файл в Gameboy-совместимый формат и добавил код, который её показывает. И картинку, и мелодию загружает последняя программа ввода, так что исходники можно увидеть на экране эмулятора (или скачать с http://hg.bortreb.com/vba-clojure).