У середині 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 до генерації мап є повністю узагальненим,
що надає можливість працювати з wideNES для всіх ігор NES прямо з коробки!

Але як він працює?

Якщо Ви бажаєте спробувати додаток wideNES перед тим, як прочитати, як він працює – немає проблем!
ANESE це емулятор NES, який я написав сам,
і у даний час це єдиний емулятор, котрий може імплементувати додаток wideNES.
Хоча заради справедливості скажу, що
ANESE не є кращим емулятором NES як стосовно UI, так і стосовно якості працювання.
Більша частина опцій (включаючи активацію wideNES) є доступною тільки через командний рядок,
і, хоча багато популярних ігор працює добре, деякі з них можуть не працювати так, як очікувалося би.

Як працює wideNES

Перед тим, як закопатися у деталі, важливо коротко обговорити, як система NES візуалізує графіку.

Натиснення пікселів з PPU

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

Процесор 6502 доповнявся потужним графічним спів-процесором, званим Блок Процесування Зображень (PPU, Picture Processing Unit).
За порівнянням з базовими відеоспівпроцесорами у більш стародавних, заснованих на процесорі 6502, системах, PPU був широким кроком у гору.
Наприклад, за півдесятиліття до першого релізу NES, конфігурація Atari 2600 використовувала процесор 6502 для делегування графічних команд для кожноо рядку розгортки її спів-процесора,
залишаючи дуже мало часу для виконування головним процесором власне ігрової логіки. А PPU, з власного боку, вимагає тільки пару команд на один кадр,
залишаючи масу часу для того, щоб 6502 забезпечував цікавий геймплей.

PPU це чарівний чіп, обробляючий графіку так, як жоден сучасний GPU,
і було би потрібно написати цілу серію статтей, щоб дати повне роз’яснення,
як він працює.
Оскільки wideNES вимагає тільки невеличку підмножину функцій PPU, буде достатньо цього короткого огляду:

• Дозвіл: 256x240px @60Hz
• Запускається незалежно від CPU
  • Пов’язується з CPU, використовуючи Відображення Вводу/Виводу У Пам’ять(Memory Mapped I/O) (діапазон адрес 0x2000 – 0x2007)
• 2 Шари Візуалізації: Шар Духів (Рухомих Об’єктів,Спрайтів), і Фоновий Шар
  • Шар Духів
    • Духи можуть бути розміщено у будь-якому місці екрану
    • Відмінно підходить для рухомих об’єктів: персонаж гравця, вороги, снаряди
    • До 64 духів розміром 8x8px
  • Фоновий Шар
    • Замкнутий на сітці
    • Відмінно підходить для статичних елементів: платформ, великих перешкод, декорацій
    • Достатньо пам’яті VRAM для зберігання 64×30 плиток розміром 8x8px
      • Ефективний внутрішній дозвіл 512×240, з портом огляду 256×240
      • Підтримує апаратне прокручування (hardware scrolling, апаратний скролінг)) для змінення порту огляду 256×240
        • Регістр PPUSCROLL (адреса 0x2005) контролює переміщення порту огляду за осю X/Y

З цим неймовірно коротким переглядом графічного процесору, давайте перейдемо до головного питання: як працює wideNES?

Базова Ідея

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

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

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

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

Вуаля!

Це працює!

Схоже на те…

Tangent: Чому не відобути рівні прямо з оперативної пам’яті?

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

Що, якщо існує засіб витягнути рівні з необробленої оперативної пам’яті?!
Може така техніка існувати??

Ні, напевно ні.

Якщо взяти 2 гри зі системи NES, є тільки одна річ, яка є спільною для обох: ці ігри обидві працюють на NES.
Other than that, all bets are off! Ця невідповідність є реальна біль,
оскільки є, за суттю, безмежні шляхи зберігання даних рівня для ігор NES!

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

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

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

Прокручування (скролінг) за межами 255

NES є 8-бітною системою, що означає, що регістр PPUSCROLL приймає тільки 8-бітні значення.
Це обмежує максимальне зміщення при прокручуванні тільки 255-ма пікселами,то є найбільшим 8-бітним числом.
Це не випадково, що дозвіл екрану NES є 240×256 пікселів,
і зміщення розміром у 255px є як-раз-достатньо для прокручування всього екрану.

Але що відбувається, якщо ми прокручуватимемо поза межами 255 пікселів?

По-перше, ігри онулятимуть значення регістру PPUSCROLL. Це роз’ясняє, чому SMB відкидається назад до старту, коли Маріо переміщається занадто далеко управо.

Наступне – для компенсування 8-бітних обмежень PPUSCROLL ігри оновляють інший регістр PPU: PPUCTRL (адреса 0x2000).
Нижні 2 біта PPUCTRL визначають “початкову точку” поточної сцени з кроком повного кадру. Наприклад: написання значення 1 зміщає порт огляду вправо на 256px,
значення 2 зміщає порт огляду вниз на 240px. Це зміщення PPUCTRL відкладається до регістру PPUSCROLL, дозволяючи прокручувати екран на 512px зліва-вправо,
або на 480px згори-вниз.

Але затримайтеся на секунду, чи достатньо VRAM тільки для 2 екранів рівня? Що відбувається, коли порт огляду прокручується занадто далеко і “прострілює” VRAM?
Для обробки цього випадку, PPU імплементує тактику згортання, так що будь-які розділи вікна перегляду за межами призначеної відеопам’яті будуть просто переноситься на її протилежний кінець.

Ця тактика згортання, у з’єднанні з розумним маніпулюванням регістрами PPUSCROLL та PPUCTRL, дозволяє іграм NES надавати илюзію безмежно довгих/широких світів!
Ліниво завантажуючи більше рівньового простору попереду порту огляду і поступово прокручуючи його, гравці ніколи не розуміють, що вони насправді “бігають по колу” всередині VRAM!

Ця чудова илюстрація з nesdev wiki показує, як Super Mario Bros. використовує ці властивості для илюзії бачимості рівней більш довгих, ніж 2 екрани:

Повернемося до нашого головного питання: як wideNES оброблює прокручування поза межами 256 пікселів?

Чесно кажучи, wideNES повністю ігнорує регістр PPUCTRL, і просто відстежує різницю у значеннях регістру PPUSCROLL між кадрами!

Якщо PPUSCROLL неочіковано стрібає до ~256, це типово показує, що персонаж гравця перемістився вліво/вгору екрану, тоді як неочіковане переміщення значення регістру PPUSCROLL вниз до ~0
означає переміщення персонажа гравця вправо/вниз екрану.

Хоча евристика може виглядати простою — а вона і є простою — вона надійно працює!

Після імплементації евристики ігри Super Mario Bros., Metroid і багато інших ігор розпочали працювати майже ідеально!

Я був повний ентузіазму, і цьому я пішов уперед і завантажив ще одну класичну гру NES classic – Super Mario Bros. 3….

Хмм… Це не добре.

Ігнорування Статичних Елементів Екрану

Багато ігор мають елементи статичного UI на краях екрану. У випадку з SMB3, на екрані є синя колона ліворуч і рядок стану унизу.

За стандартом, wideNES семплює (записуває) 16-пікселевий відступ від країв екрану, що означає семплювання будь-яких статичних елементів поряд з краями екрану! Не добре!

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

Взагалі є 3 різних типи статичних елементів екрану, використованих у іграх NES: HUD-и, Маски і Рядки Стану.

HUD-и – не проблема

Якщо гра накладає HUD поверх рівня, швидше за все, HUD складається з декількох Духів. Приклад: HUD у грі Metroid.

На щастя, ці HUD-и не є проблемою, так як wideNES просто ігнорує Шар Духів на даний момент. Здорово!

Маски – Простіше Простого

PPU має властивість, яка дозволяє іграм маскувати найлівіші 8 пікселів Фонового Шару. Вона активується надаванням 2-го біту регістру PPUMASK (адреса 0x2001).
Хоча ця властивість використовується багатьома іграми, роз’яснення, чому вони роблять так, виходить поза межи цієї статті.

Виявлення активованого стану маски є неймовірно простим: wideNES відстежує значення PPUMASK, і ігнорує найлівіші 8 пікселів у випадку надавання 2-го біту у цьому регістрі!

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

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

Рядки Стану – складна річ

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

За винятком масок, PPU насправді не надає простий спосіб розділити Фоновий Шар між зонами Гри і Стану. За суттю, розробники ігор стали більше творчими,
винаходячи безліч незвичайних шляхів створення Рядків Стану…

wideNES імплементує декілька різних евристичних методів виявлення типів Рядків Стану, але стосовно поточної теми, я оглядатиму один з найцікавіших:
Відстеження Запитів Переривання В Середині Кадру (Mid-Frame Interrupt ReQuest Tracking, Mid-Frame IRQ Tracking).

Відстеження Запитів Переривання В Середині Кадру

На відміну від сучасних GPU, які мають великі внутрішні відеобуфери (framebuffers), PPU не має відеобуфреу взагалі! Для зменшення використованого простору,
PPU зберігає сцени як сітку з 64×32 плиток розміром 8×8 пікселів. Замість передчасного обчислення пікселевих даних
плитки зберігаються, як вказівники на символьну память CHR Memory (Character Memory), яка містить збережені піксельні дані.

Оскільки система NES була розробленою у 80-х роках, PPU не мав сучасних технологій обробки візуальної інформації. Замість відображення повного кадру за один раз,
PPU виводить відео у форматі NTSC, який був спроектованим для ЕЛТ-екранів (CRT) і відображає відео піксель за пікселем, рядок розгортки за рядком розгортки, згори вниз, зліва вправо.

Чому це важливе?

Раз вже PPU обробляє кадри згори-униз і рядок-за-рядком,
є можливим посилати до PPU інструкції в середині екрану для створення відеоефектів, у інших ситуаціях неможливих!
Ці ефекти можуть бути такими ж простими, як зміна палітри, або настільки ж складними, як (Ви здогадалися) створення рядка стану!

Щоб роз’яснити, як записи PPU в середині кадру можуть згенерувати Рядки Стану,
я витягнув необроблений дамп шматку VRAM (відеопам’яті) і CHR Memory (символьної памяті) процесору PPU у окремому кадри гри SMB3:

Все виглядає нормально, нічого особливого … крім Рядка Стану! Він повністю спотворений!

Тепер, подивіться на той же необроблений дамп, але витягнутий після розгорткового рядку 196…

Так, рівень виглядає жахливо, але Рядок Стану повністю цілий!

Що відбувається??

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

• Привласнити регістру PPUSCROLL значення (0,0) (забезпечення фіксованого Рядку Стану)
• Замінити мапу плиток (swap the tilemap) у символьної памяті CHR Memory (виправлення графіки Рядку Стану)

Оскільки інша частина рівня є вже обрендереною, PPU не буде “ретроактивно” оновляти кадр. Замість цього, він продовжуватиме обробку зображення з цими новими параметрами,
виводячи красивий, неспотворений Рядок Стану!

Повертаючися до wideNES, відстежуючи Запити Перевивань в середині кадру (mid-frame IRQs) і примічаючи розгортковий рядок, у якому вони виникають,
wideNES може ігнорувати будь-які наступні розгорткові рядки у запису!
Навпаки, якщо IRQ виникає у розгортковому рядку менш ніж 240 / 2, всі попередні розгорткові рядки ігноруються,
тому що ранний запит на переривання розгорткового рядку (scanline IRQ) припускає, що Рядок Стану повинен бути у верху екрану.

З того часу, коли цей евристичний метод використовується, Super Mario Bros. 3 працює ідеально!

Я коротко розглянув бібліотеку Комп’ютерного Бачення OpenCV, щоб виявити рядки стану (і також інші статичні регіони екрану),
але у підсумку вирішив, що вона не є потрібною. Використовування величезної, складної і непрозорої бібліотеки Комп’ютерного Бачення
протистояло би духу додатку wideNES, який намагається спиратися на малі, прості та прозорі правила і евристичні методи досягнення результатів.

Виявлення “Сцен”

Крім декількох примітних прикладів (як Metroid), ігри NES мають тенденцію не розміщатися всередині одного великого та безперервного рівня.
Замість цього, більшість ігор NES є розділеною на менші за розміром окремі “сценки” з дверима або екранами/порталами переходу для переміщення між ними.

Оскільки wideNES не має концепту “сценок”, відбуваються погані речі, коли сцена змінюється…

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

Уффф, це не добре! WideNES повністю переписав останній біт поточного рівня з першим бітом нового рівня!

Зрозуміле, що для wideNES було треба як-небудь виявити, де змінюється сцена. Але як?

Перцептуальне Хешування!

На відміну від криптографічних хеш-функцій, які шукають розкидати введені дані випадковим чином по виходному простору,
перцептуальні хеш-функції прагнуть тримати подібні вхідні сигнали “close” один до іншого у виходному просторі.
Це робить перцептуальні хеши ідеальними для виявлення взаємо подібних образів!

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

Це просто, але працює досить добре!

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

У даний час, wideNES використовує фіксований-поріг між значеннями перцептуального хешу для викликання переходу між сценами, але це знаходиться далеко від ідеалу.
Різні ігри можуть використовувати різні палітри, і існує багато випадків, коли wideNES вважає, що десь є перехід між сценами, а там його немає. У ідеалі,
wideNES є повинним використовувати динамічний поріг, але у цей момент використовується тільки статичний фіксований поріг.

З цим новим евристичним методом wideNES ефективно визначає вхід Сімону до замку у Castlevania і відповідно перемикається на свіжий інтер’єр.

І з цим кроком фінальний великий шмат пазлу за ім’ям wideNES знайшов собі місце.

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

Що тепер відбуватиметься з wideNES?

wideNES складається з двох окремих частин: Ядро wideNES , яке є набором правил/евристичних методів, закладених у підставу технології працювання додатку,
і конкретної імплементації wideNES всередині емулятору ANESE.

Поліпшення ядра wideNES

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

Виявлення статичних екранних елементів також вимагає більше праці. Наприклад,
Megaman IV має запит переривання в середині кадру (mid-frame IRQ), але в його немає рядку стану,
що веде wideNES до помилкового ігнорування значної частини ігрового поля.
У той час, як цей окрема проблема може бути усунутою через деяке мануальне налагодження,
було б краще використовувати більш інтелектуальну евристику.

Декілька ігор NES прокручуває екран “унікальними” чинами. Яскравий приклад цього це The Legend of Zelda,
яка використовує PPUSCROLL для горизонтального прокручування, але вертікаьно прокручує екран з допомогою зовсім іншого регістру – PPUADDR.
Zelda є дуже популярною назвою,
і цьому wideNES імплементую евритиску тільки для Zelda.
Також існують і інші ігри з подібними режимами “унікального” прокручування екрану, які також вимагають особливих евристичних методів.

Було б корисно мати який-небудь спосіб “зшивати” однакові сцени. Наприклад, якщо хтось проходить Рівень 1 грі Super Mario Bros.,
але вибірає трубу, щоб дойти до підземної схованки з монетами, wideNES створюватиме дві окремі сцени для Рівня 1:
Сцену А – частину рівня до точки, де Маріо входить до зони х монетами,
і сцену Б – частину рівня з точки, де Маріо виходить з труби до флагштоку.
Якщо гра в дальшнішему перезавантажується і Рівень 1 переігривається без входження до труби,
wideNES елементарно оновлятиме Сцену А, щоб отримати повністю пройдений рівень, але залишатиме Сцену Б у “завислому” стані

Нарешті, wideNES повинен відстежувати переходи між сценами і зберігати ці дані. З цими даними було б можливо побудувати графік переходов між сценами,
дозволяючи генерувати “світові мапи” для ігор, які не є складеними з єдиного, величезного світу.

Поліпшення імплементації wideNES у емуляторі ANESE

У даний час реалізація праці wideNES можлива тільки у середовищі ANESE, емуляторі системи NES, який я написав сам.
ANESE є дуже, дуже спартанським емулятором,
з більшостю опцій, схованих поза флагами CLI, і з тільки одним встановленим UI – простим оверлеєм вибору файлів (file-picker overlay)!
Він дуже далеко, далеко від рівня “production ready.”

Хоча, окрім UI, ANESE та wideNES могли б обидва поліпшити сумісність та ефективність.
ANESE був першим великим емулятором, який я написав, і це помітно!

Є досить багато проблем сумісності, з деякими іграми, які працюють неправильно/ не запускаються взагалі.
На щастя, це відбувається тому що ANESE не є дійсно добрим емулятором,
а не тому що wideNES є поганим додатком.
Принципи, на яких спирається wideNES, є перевіреними і надійними, і дозволяють легко імплементовати додаток у інших емуляторах!

Стосовно ефективності ANESE та wideNES є не самі найвеликіші, і навіть деякі відносно потужні ПК можуть іноді падати у продуктивності ніжче 60fps!
Є багато оптимізацій, які повинні бути імплементовані до ANESE та wideNES.
Окрім загальних поліпшень ядра ANESE,
потрбін поліпшення у тому, як wideNES записуває кадри, відображає (рендерінг) мапи, і семплює хеши.

Висновок

Незважаючи на те, що я обговорив тут головні аспекти працювання додатку wideNES, є багато менш значних технічних питань для обговорення.
Наприклад, wideNES зберігає мапу істинного хешу кожного кадру і значення його прокруток (скролінгу),
які використовуються для відтворення сцен “повторного входу”.
Ця особливість, і також багато інших, є детально прокоментованими на ресурсі для wideNES,
який є доступним на сторінці проекту wideNES.

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

Спробуйте wideNES самостійно, і скажіть мені, що Ви думаєте! Завантажіть ANESE,
запустіть Super Mario Bros., або The Legend of Zelda, або Metroid, і трохі розважіться!

Посилання на оригінал статті: wideNES – Peeking Past the Edge of NES Games
Автор статті: Daniel Prilik
Автор перекладу: Alvetari