В середине 1980-х Nintendo Entertainment System (NES) была обязательной к покупке консолью. Лучший звук, лучшая графика и лучшие игры среди всех консолей того времени — приставка расширяла границы возможного. До сих пор такие проекты, как Super Mario Bros., The Legend of Zelda и Metroid считаются одними из лучших игр всех времён.

Прошло более 30 лет после выпуска NES, а классические игры чувствуют себя прекрасно, чего нельзя сказать о железе, на котором они работали. Имея разрешение всего 256x240, консоль NES не могла предоставить играм достаточно пространства. Тем не менее, бесстрашным разработчикам удалось уместить в играх NES потрясающие, незабываемые миры: лабиринтоподобные подземелья The Legend of Zelda, обширные пространства планеты в Metroid, яркие уровни Super Mario Bros.. Однако из-за аппаратных ограничений NES игроки никогда не могли выйти за пределы разрешения 256x240…

До недавнего времени.

Представляю вашему вниманию проект wideNES — новый способ сыграть в классику NES!



wideNES — это новая технология для автоматической и интерактивной разметки игр NES в реальном времени.

Когда игроки движутся по уровню, wideNES записывает экран, постепенно строя карту исследованной части мира. При последующих прохождениях уровня, wideNES синхронизирует игровой процесс на экране со сгенерированной картой, по сути позволяя игрокам видеть больше, «заглядывая» за границы экрана NES! Лучше всего то, что способ разметки игр wideNES абсолютно универсален, что позволяет широкому набору игр NES работать с wideNES без какой-либо настройки!

Но как это всё устроено?

---

Если вы хотите проверить, как работает wideNES, до прочтения статьи, то пожалуйста! ANESE — это написанный мной эмулятор NES, и на текущий момент это единственный эмулятор, в котором реализован wideNES. Однако стоит предупредить, что ANESE не лучший эмулятор NES в мире, с точки зрения как UI, так и точности эмуляции. Большинство возможностей (в том числе включение wideNES) доступно только через командную строку, и хотя многие популярные игры работают отлично, некоторые другие могут вести себя неожиданным образом.

---

Как работает wideNES

Прежде чем углубляться в детали, важно вкратце объяснить, как NES рендерит графику.

Передача пикселей с помощью PPU

Сердцем NES является почтенный процессор MOS 6502. В конце 70-х и начале 80-х 6502 использовались повсюду и работали в таких легендарных машинах, как Commodore 64, Apple II и многих других. Он был дешёв, прост в программировании и достаточно мощен, быть опасным.

Дополнял 6502 в консоли NES мощный графический сопроцессор под названием Picture Processing Unit (PPU). По сравнению с простыми сопроцессорами для работы с видео, использовавшимися в старых системах на основе, PPU стал огромным шагом вперёд с точки зрения удобства использования. Например, за пять лет до выпуска NES, процессор 6502 в Atari 2600 использовался для передачи графических команд сопроцессору для каждой растровой строки, что оставляло процессору совсем мало времени на выполнение игровой логики. Для сравнения: PPU требовалась всего пара команд на кадр, и это давало 6502 достаточно времени для создания интересного и инновационного геймплея.

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

• Разрешение: 256x240 пикселей, 60 Гц
• Работает независимо от ЦП
  
  • Общается с ЦП с помощью ввода-вывода с отображением в память (диапазон адресов 0x2000 — 0x2007)
• 2 слоя рендеринга: слой спрайтов и слой фона
  • Слой спрайтов
    
    • Каждый отдельный спрайт можно располагать в любом месте экрана
    • Отлично подходит для движущихся объектов: игрока, врагов, снарядов
    • До 64 спрайтов размером 8x8 пикселей
  • Слой фона
    
    • Привязан к сетке
    • Отлично подходит для статичных элементов: платформ, больших препятствий, украшений
    • Видеопамяти достаточно для хранения 64x30 тайлов размером 8x8 пикселей
      
      • Настоящее внутренее разрешение 512x240, с окном просмотра 256x240
      • Поддерживает аппаратный скроллинг для изменения окна просмотра 256x240
        
        • Регистр PPUSCROLL (адрес 0x2005) управляет смещением окна просмотра по X/Y

Разобравшись с этим очень кратким обзором, давайте перейдём к самому интересному: как работает wideNES?

Основная идея

В конце каждого кадра ЦП передаёт PPU информацию об изменениях. К ним относятся новые позиции спрайтов, новые данные уровней и, что критически важно для wideNES, новые смещения окна просмотра. Поскольку wideNES работает в эмуляторе, то нам очень просто отслеживать записываемые в регистр PPUSCROLL значения, а значит, невероятно легко вычислять, насколько сдвинулся экран между любыми двумя кадрами!

Хм, а что будет, если вместо отрисовывания каждого нового кадра прямо поверх старого кадра, новые кадры будут отрисовываться с наложением на предыдущий кадр, но смещаясь на текущее значение скроллинга? Тогда со временем на экране будет оставаться всё большая часть уровня, постепенно выстраивая полную картину уровня!

Чтобы проверить, имеет ли эта идея какую-нибудь ценность, я быстро набросал первую реализацию.

Компилируем…
Запускаем…
Загружаем Super Mario Bros.…

Вуаля!


Сработало!

Вроде бы…

---

Другой подход: почему бы не извлекать уровни непосредственно из ROM-файлов?

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

Что, если бы был какой-то способ извлечения уровней из сырых ROM-образом NES?!

Может ли вообще существовать такая техника?

Ну, скорее всего нет.

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

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

Для того, чтобы извлечь данные уровней из ROM, нужно определить, какие части ROM являются кодом (а не данными), а это сделать сложно, потому что нахождение всего кода в двоичном файле эквивалентно проблеме остановки!

В wideNES используется гораздо более простой подход: вместо гадания о том, как игра упаковала данные уровня в ROM, wideNES просто запускает игру и следит за выводимыми данными!

---

Скроллинг за пределами 255

NES — это 8-битная система, то есть регистр PPUSCROLL может получать только 8-битные значения. Это ограничивает максимальное смещение скроллинга величиной в 255 пикселей, то есть максимальным 8-битным числом. Нет никакого совпадения в том, что разрешение экрана NES равно 240x256 пикселям, то есть 255-пиксельного смещения как раз достаточно для скроллинга всего экрана.

Но что происходит при скроллинге дальше 255?

Во-первых, игры сбрасывают регистр PPUSCROLL на 0. Это объясняет, почему SMB переносится к началу, когда Марио сдвигается слишком далеко вправо.

Затем, чтобы компенсировать 8-битные ограничения PPUSCROLL, игры обновляют другой регистр PPU: PPUCTRL (адрес 0x2000). Нижние 2 бита of PPUCTRL задают «исходную точку» текущей сцены в полноэкранных инкрементах. Например, запись значения 1 сдвигает окно просмотра вправо на 256 пикселей, значение 2 сдвигает окно просмотра вниз на 240 пикселей. Смещение PPUCTRL заносится в стек с регистром PPUSCROLL, что позволяет скроллить экран горизонтально в пределах 512 пикселей или вертикально в пределах 480 пикселей.

Но постройте, ведь видеопамяти хватает только на два экрана уровня? Что происходит, когда окно просмотра скроллится слишком далеко вправо и «выходит за пределы» VRAM? Для обработки этого случая PPU реализует свёртку: все части окна просмотра за пределами выделенной видеопамяти просто свёртываются к противоположному краю видеопамяти.

Такое сворачивание в сочетании с умной манипуляцией регистрами PPUSCROLL и PPUCTRL позволяет играм NES создавать иллюзию бесконечно высоких/широких миров! Благодаря ленивой загрузке части уровня за пределами окна просмотра и постепенному скроллингу в неё игроки никогда не понимают, что внутри VRAM они на самом деле «бегают по кругу»!

Превосходная иллюстрация из nesdev wiki показывает, как Super Mario Bros. пользуется этими свойствами для создания уровней длиннее двух экранов:


Вернёмся к обсуждаемому нами вопросу: как wideNES обрабатывает скроллинг за пределами 256?

Ну, если откровенно, wideNES полностью игнорирует регистр PPUCTRL и просто следит за разностью PPUSCROLL между кадрами!

Если PPUSCROLL неожиданно перепрыгивает примерно к 256, что обычно обозначает, что персонаж игрока сдвинулся влево/вверх по экрану, а если он неожиданно перепрыгивает примерно к 0, то это обычно говорит о том, что игрок переместился по экрану вправо/вниз.

Хотя эта эвристика может выглядеть простой — а это так и есть — на самом деле она отлично работает!

После реализации этой эвристики Super Mario Bros., Metroid и многие другие игры заработали почти идеально!

Я был в восторге, поэтому пошёл дальше и загрузил ещё одну классику NES — Super Mario Bros. 3…


Хм… Не очень красиво.

Игнорирование статичных элементов экрана

У многих игр по краям экрана есть статичные элементы UI. В случае SMB3 это столбец в левой части и панель состояния внизу состояния.

По умолчанию wideNES выполняет сэмплирование с 16-пиксельными инкрементами от краёв экрана, то есть сэмплируются все статические элементы по краям! Нехорошо!

Чтобы обойти эту проблему, в wideNES реализованы правила и эвристики, пытающиеся автоматически распознать и замаскировать статические элементы экрана.

В общем случае в играх NES используется три разных типа статических элементов экрана: HUD, маски и панели состояния.

HUD — нет никаких проблем

Если игра накладывает HUD поверх уровня, то есть вероятность, что HUD состоит из нескольких спрайтов. Пример: HUD в Metroid.

К счастью, такие HUD не вызывают проблем, потому что wideNES на текущий момент просто игнорирует слой спрайтов. Отлично!

Маски — проще некуда

У PPU есть функция, позволяющая играм маскировать самые левые 8 пикселей слоя фона. Она активируется заданием второго бита регистра (адрес 0x2001). Многие игры используют эту функцию, но объяснение того, зачем они это делают, выходит за рамки этой статьи.

Распознать включенную маску невероятно просто: wideNES просто следит за значением PPUMASK и игнгорирует самые левые 8 пикселей, когда в регистре задан второй бит!

Похоже, что реализация этого простого правила устранила проблему с SMB3:


…ну, или почти устранила.

Панели состояния — самое сложное

Из-за ограничений PPU в любой момент времени на экране может быть не больше 64 спрайтов; более того, в любой момент времени в каждой растровой строке может быть не больше 8 спрайтов. Это ограничение не позволяет разработчикам создавать сложные HUD из спрайтов и заставляет их использовать для отображения информации части слоя фона.

Кроме масок, в PPU нет простого способа разделения слоя фона на игровую область и область состояния. Поэтому разработчики шли на ухищрения, приводящие к куче неортодоксальных способов создания панелей состояния…

Для распознавания разных типов панелей состояния wideNES использует различные эвристики, но для экономии времени я рассмотрю только одну из самых интересных: отслеживание IRQ посередине кадра (Mid-Frame IRQ tracking).

Mid-Frame IRQ Tracking

В отличие от современных GPU с большими внутренними буферами кадров, у PPU вообще нет буфера кадров! Для экономии места PPU хранит сцены как сетку из тайлов 64x32 размером 8x8 пикселей. Вместо предварительного вычисления данных пикселей тайлы хранятся как указатели на память CHR Memory (память персонажей, Character Memory), в которой содержатся все данные пикселей.

Так как NES разрабатывалась в 80-х, PPU создавался без учёта современных технологий отображения. Вместо одновременного рендеринга полного кадра, PPU выводит видеосигнал NTSC, который должен отображаться на ЭЛТ-экране, выводящем видео пиксель за пикселем, строка за строкой, сверху вниз, слева направо.

Почему всё это важно?

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

Чтобы объяснить, как запись в PPU посередине кадра может создавать панели состояния, я записал сырой дамп среза видеопамяти PPU и CHR Memory для одного кадра SMB3:


Всё выглядит нормально, ничего особенного… но только посмотрите на панель состояния! Она полностью искажена!

Теперь посмотрите на такой же сырой дамп, но сделанный после строки 196…


Да, уровень выглядит ужасно, зато панель состояния выглядит отлично!

Что же здесь происходит?

SMB3 устанавливает таймер для запуска IRQ (прерывания) точно после рендеринга растровой строки 195. В обработчик IRQ он передаёт следующие инструкции:

• Присваиваем PPUSCROLL значения (0,0) (чтобы панель состояния оставалась на месте)
• Заменяем тайловую карту в CHR Memory (приводим в порядок графику панели состояния)

Поскольку остальная часть уровня уже отрендерена, PPU не будет «заново» обновлять кадр. Вместо этого он продолжит рендеринг с этими параметрами, выводя красивую неискажённую панель состояния!

Вернёмся к wideNES: наблюдая за всеми IRQ посередине кадра и запоминая растровую строку, на которой они происходили, wideNES может игнорировать в записи все последующие растровые строки! Если же IRQ происходит в растровой строке выше 240 / 2, то игнорируются все предыдущие строки, потому что раннее прерывание растровой строки означает, что панель состояния может быть наверху экрана.

После реализации этой эвристики Super Mario Bros. 3 заработала идеально!

---

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

---

Распознавание «сцен»

За исключением нескольких выдающихся примеров (например, Metroid), игры для NES обычно не проходят в пределах одного огромного, неразрывного уровня. Напротив, большинство игр NES разделено на множество мелких независимых «сцен» с дверями или экранами перехода между ними.

Так как в wideNES нет концепции «сцен», при смене сцен происходят нехорошие вещи…

Например, вот первый переход со сцены Castlevania, где Саймон Бельмонт входит в замок Дракулы:


Ого, всё плохо! wideNES полностью переписал последнюю часть уровня первым экраном нового уровня!

Очевидно, что wideNES нужен какой-то способ распознавания смены сцен. Но какой?

Перцептивное хэширование!

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

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

Он прост, но работает довольно неплохо!

Например, посмотрите, как выделяются переходы между сценами, если нанести на график изменение перцептивного хэша со временем в The Legend of Zelda:


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

После реализации этой новой эвристики wideNES успешно распознаёт вход Саймона из Castlevania в замок и соответствующим образом создаёт новый холст.


И этим решением мы поставили на место последний крупный кусок паззла wideNES.

Реализовав простейшую сериализацию, я наконец смог запустить игру для NES, сыграть в несколько уровней и автоматически сгенерировать карты уровней!

Что ждёт wideNES в будущем?

wideNES состоит из двух отдельных частей: ядра wideNES, которое является самими правилами/эвристиками, лежащими в основе технологии, и конкретной реализации wideNES внутри эмулятора ANESE.

Усовершенствование ядра wideNES

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

Также требуется дополнительная работа над распознаванием статических элементов экрана. Например, в Megaman IV есть IRQ посередине кадра, но нет панели состояния, из-за чего wideNES ошибочно игнорирует солидную часть игрового поля. Хотя этот конкретный случай можно исправить ручной настройкой, лучше всё-таки использовать более умные эвристики.

Некоторые игры для NES выполняют скроллинг экрана «уникальными» способами. Одним из самых заметных примеров является The Legend of Zelda, в которой для горизонтального скролла используется PPUSCROLL, но для вертикального скролла применяется совершенно другой регистр — PPUADDR. Zelda — это довольно популярная игра, поэтому wideNES реализует эвристику специально для Zelda. Есть и другие игры с похожими «уникальными» режимами скроллинга, для которых тоже понадобятся индивидуальные эвристики.

Было бы полезным найти какой-то способ «сшивания» идентичных сцен. Например, если пользователь играет в Super Mario Bros. Level 1, но залезает в трубу, чтобы попасть в подземную пещеру с монетами, то wideNES создаст две отдельные сцены для Level 1: сцену A, уровень до того момента, когда Марио заходит в зону с монетами, и сцену B, уровень, с момента, когда Марио выходит из трубы и до флагштока. Если игра затем перезапускается и Level 1 переигрывается без захода в трубу, то wideNES просто обновит сцену A, в которой будет карта полного уровня, но сцена B «оборвётся».

И наконец, wideNES должен отслеживать переходы между сценами. Без этих данных невозможно будет построить граф переходов между сценами для генерации карт мира игр, не состоящих из единого большого мира.

Улучшение реализации wideNES в ANESE

На текущий момент wideNES реализован только в написанном мной эмуляторе NES под названием ANESE. ANESE — это очень спартанский эмулятор: большинство опций скрыто за флагами CLI, а единственным реализованным UI является простейший оверлей выбора файла! Он ещё чрезвычайно далёк от уровня «продакшена».

Кроме отсутствия UI, ANESE и wideNES не помешали бы улучшения в совместимости и скорости. ANESE — первый написанный мной эмулятор, и это заметно!

В нём довольно много проблем с совместимостью — многие игры работают некорректно или не запускаются вообще. К счастью, несовершенство ANESE не означает того, что wideNES — это плохая технология. wideNES построен на основе проверенных принципов, которые легко будет реализовать в других эмуляторов!

С точки зрения скорости ANESE и wideNES неидеальны, и даже на относительно мощных PC производительность иногда может падать ниже 60fps! В ANESE и wideNES нужно реализовать множество оптимизаций. Кроме общего улучшения ядра ANESE, нужно усовершенствовать в wideNES запись кадров, рендеринг карты и сэмплирование хэшей.

Заключение

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

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

Попробуйте использовать wideNES и расскажите о своих ощущениях! Скачайте ANESE, запустите Super Mario Bros., The Legend of Zelda или Metroid, и сыграйте в них по-новому!