Проект wideNES — виходимо на межі екрану NES


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

Минуло понад 30 років після випуску NES, а класичні ігри відчувають себе чудово, чого не можна сказати про залізо, на якому вони працювали. Маючи дозвіл всього 256×240, консолі NES не могла надати ігор достатньо простору. Тим не менш, безстрашним розробникам вдалося вмістити в іграх NES чудові, незабутні світи: лабиринтоподібні підземелля The Legend of Zelda, великі простори планети в Metroid, яскраві рівні Super Mario Bros.. Однак через
апаратні обмеження NES гравці ніколи не могли вийти за межі дозволу 256×240…

До недавнього часу.

Презентую вашій увазі проект 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, достатньо буде розглянути їх тільки коротко:

  • Дозвіл: 256×240 пікселів, 60 Гц
  • Працює незалежно від ЦП
    • Спілкується з ЦП за допомогою введення-виведення з відображенням в пам’ять (діапазон адрес 0x2000 — 0x2007)
  • 2 шари
    візуалізації: шар спрайтів і шар фону

    • Шар спрайтів
      • Кожен окремий спрайт можна розташовувати в будь-якому місці екрану
      • Відмінно підходить для рухомих об’єктів: гравця, ворогів, снарядів
      • До 64 спрайтів розміром 8×8 пікселів
    • Шар фону
      • Прив’язаний до сітки
      • Відмінно підходить для статичних елементів: платформ, великих перешкод, прикрас
      • Відеопам’яті достатньо для зберігання 64×30 тайлів розміром 8×8 пікселів
        • Розширення 512×240, з вікном перегляду 256×240
        • Підтримує апаратний скролінг для зміни вікна перегляду 256×240
          • Регістр PPUSCROLL (адреса 0x2005) управляє зміщенням вікна перегляду по X/Y

Розібравшись з цим дуже коротким оглядом, давайте перейдемо до найцікавішого: як працює wideNES?

Основна ідея

В кінці кожного кадру ЦП передає PPU інформацію про зміни. До них відносяться нові позиції спрайтів, нові дані рівнів і, що критично важливо для wideNES, нові зсуву вікна перегляду. Оскільки wideNES працює в емуляторі, то нам дуже просто відстежувати як записуються в регістр PPUSCROLL значення, а значить, неймовірно легко обчислювати, наскільки зрушився екран між будь-якими двома кадрами!

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

Щоб перевірити, чи має ця ідея яку-небудь цінність, я швидко накидав першу реалізацію.

Читайте також  Чистота в майстерні гіка. Частина 1

Компілюємо…
Запускаємо…
Завантажуємо Super Mario Bros….

Вуаля!


Спрацювало!

Начебто…

Інший підхід: чому б не витягувати рівні безпосередньо з ROM-файлів?

Навіть не розглядаючи подробиці реалізації стає очевидно, що ця техніка має серйозне обмеження: повну карту гри можна зібрати тільки тоді, коли гравець самостійно досліджував всю гру.

Що, якщо б був якийсь спосіб вилучення рівнів з сирих ROM чином NES?!

Чи може взагалі існувати така техніка?

Ну, швидше за все немає.

Якщо взяти будь-які дві гри для NES, можна гарантувати, що у них є тільки одне спільне — вони обидві працюють на NES. Все інше може бути абсолютно різним! Така невідповідність — це справжня біда, адже ігор NES по суті є нескінченна кількість варіантів зберігання даних рівнів!

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

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

У wideNES використовується набагато більш простий підхід: замість гадання про те, як гра спакувала дані рівня ROM, wideNES просто запускає гру і стежить за виведеними даними!

Скролінг за межами 255

NES — це 8-бітна система, тобто регістр PPUSCROLL може одержувати тільки 8-бітні значення. Це обмежує максимальне зміщення скролінгу величиною в 255 пікселів, тобто максимальним 8-бітним числом. Немає ніякого збігу в тому, що дозвіл екрана NES одно 240×256 пікселям, тобто 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). Багато гри використовують цю функцію, але пояснення того, навіщо вони це роблять, виходить за рамки цієї статті.

Читайте також  Реалізація вільного переміщення частинок на ReactJS

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

Схоже, що реалізація цього простого правила усунула проблему з SMB3:


…ну, або майже усунула.

Панелі стану — найскладніше

З-за обмежень PPU у будь-який момент на екрані може бути не більше 64 спрайтів; більш того, в будь-який момент часу в кожній растрової рядку може бути не більше 8 спрайтів. Це обмеження не дозволяє розробникам створювати складні HUD з спрайтів і змушує їх використовувати для відображення інформації частині шару фону.

Крім масок, PPU немає простого способу поділу шару фону на ігрову область і область стану. Тому розробники йшли на хитрощі, що призводять до купи неортодоксальнфі способи створення панелей стану…

Для розпізнавання різних типів панелей стану wideNES використовує різні евристики, але для економії часу я розгляну лише одну з самих цікавих: відстеження IRQ посередині кадру (Mid-Frame IRQ tracking).

Mid-Frame IRQ Tracking

На відміну від сучасних GPU з великими внутрішніми буферами кадрів, у PPU взагалі немає буфера кадрів! Для економії місця PPU зберігає сцени як сітку з тайлів 64×32 розміром 8×8 пікселів. Замість попереднього обчислення даних пікселів тайли зберігаються як покажчики на пам’ять 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 застосовується найпростіший з існуючих перцептивних хешей: підсумовування всіх пікселів на екрані!

Читайте також  Що найбільше дратує користувачів, згідно з Google

Він простий, але працює досить непогано!

Наприклад, подивіться, як виділяються переходи між сценами, якщо нанести на графік зміна перцептивного хеша з часом в 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, і зіграйте в них по-новому!

Степан Лютий

Обожнюю технології в сучасному світі. Хоча частенько і замислююся над тим, як далеко вони нас заведуть. Не те, щоб я прям і знаюся на ядрах, пікселях, коллайдерах і інших парсеках. Просто приходжу в захват від того, що може в творчому пориві вигадати людський розум.

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *