Я прочитал превосходную книгу Doom Guy Джона Ромеро, которую крайне рекомендую. В девятой главе Джон рассказывает о том, как его поразила увиденная им технология Adaptive Tile Refresh (ATR). Благодаря этому я понял, что пока не анализировал очень важную методику, лежавшую в основе серии игр Commander Keen (CK).

В процессе исследований я выяснил, что ATR использовалась только в первой трилогии CK. Во второй разработчики начали использовать нечто гораздо лучшее.

▍ Краткое введение в EGA

Commander Keen работал во всём своём великолепии на PC, оснащённом картой Enhanced Graphic Adapter (EGA). На этих машинах программирование графики выполнялось при помощи набора регистров для конфигурирования и окна в 64 КиБ памяти, отражаемой^[1] в Video RAM (VRAM) для размещения пикселей. Внутри EGA данные хранятся в четырёх плоскостях, обозначаемых C0, C1, C2 и C3^[2]. Байты берутся из банков контроллером экрана, после чего отправляются на монитор.


Такая архитектура с задействованием четырёх банков может показаться странной, но это был единственный способ обеспечения полосы пропускания, позволяющей угнаться за экраном (ЭЛТ). Достаточно быстрых чипов не было, поэтому проектировщики IBM сделали так, чтобы контроллер (CRTC) параллельно считывал четыре байта.

▍ EGA Mode 0xD

Для генерации пикселей EGA CRTC не ожидает значений RGB. Вместо них он использует систему палитр. Разные режимы обеспечивают различные сочетания разрешений и цветов. В режиме Dh^[3], который используется в играх CK, разрешение составляет 320x200 с 16 цветами^[4].

Стандартная EGA-палитра Commander Keen

В режиме 10h, который в CK НЕ используется, индексы палитр (перья) можно переконфигурировать для использования других цветов (чернил). Каждое перо может указывать на чернила из набора 64 заранее заданных значений.

Пространство цветов EGA (64 значения от 0x00 до 0x3F)

Любопытный факт: в режиме Dh конфигурацию цветов палитры тоже можно менять, но только из стандартных 16 цветов. Именно так в CK реализован грубый эффект затемнения.

▍ EGA Planar Mode

Каждый банк хранит плоскость полубайта (нибла) (4 бита). C0 хранит все младшие биты каждого нибла. C3 хранит старшие биты MSB каждого нибла. И так далее… Например, первый байт в C0 хранит младшие биты восьми первых пикселей на экране.


Для полного экрана требуется 320x200/2= 32000 байтов VRAM. Каждый банк/плоскость хранит 200 строк по 40 байтов каждая.

▍ Проблема, которую решает Adaptive Tile Refresh

Основная проблема, которую решает ATR — это полоса пропускания. Запись 320x200 ниблов (32 КиБ) на кадр — это слишком много для шины ISA. При обновлении целого экрана никак нельзя получить частоту кадров 60 Гц. Если мы запустим следующий код, который просто заполняет все банки, то он будет работать с частотой 5 кадров в секунду.

byte* vram = 0xA0000000L;  

for (int bank_id = 0 ; bank_id < 4 ; bank_id++) {
  select_bank(bank_id);
  for (int i = 0; i < 40 * 200; i++) {
    vram[i] = 0x0;
  }
}

Любопытный факт: знатоки могут сказать, что у EGA есть способы одновременной записи всех четырёх банков. Они могут помочь в очистке экрана, а в случае Wolfenstein 3D — в дублировании столбцов. Но Commander Keen они ничем не помогут.

▍ Как работает Adaptive Tile Refresh

Проще всего разобраться в ATR, создав её с нуля, знакомясь с регистрами EGA по мере необходимости. Давайте начнём с показа статичного изображения. Мы переключим EGA в режим Dh, выберем адрес во VRAM, заполним его ниблами, а затем воспользуемся регистром «CRTC Start», чтобы CRTC знал, откуда начинать чтение.


Любопытный факт: единого регистра адреса начала CRTC нет. Разработчик должен выполнять запись в два регистра, называющиеся «Start Address High» (0CH), и «Start Address Low» (0DH). Для простоты мы будем работать с ними как с единым целым и назовём его CRTC_START.

▍ Плавный вертикальный скроллинг

Теперь мы добавим плавный скроллинг. Наша цель — создать систему, в которой отображаемое на экране изображение можно сдвигать регистром EGA (это малозатратно) без заполнения каждого отдельного пикселя (это затратная операция).

Давайте начнём с плавного вертикального скроллинга. Если мы распределим больше памяти, чем отображается, то создадим во VRAM виртуальный экран. Мы можем добавить 16 строк выше и 16 строк ниже. Вместо 40x200 = 8000 байтов на плоскость мы теперь используем 40 x 232 = 9280 байтов на плоскость.


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


Чтобы переместить отображаемое изображение на одну строку вниз, можно просто уменьшить значение в регистре CRTC_START на 40 байтов.


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

▍ Плавный горизонтальный скроллинг

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

Поначалу кажется, что мы не можем использовать тот же трюк, потому что все строки хранятся во VRAM одна за другой (между ними нет пространства). Но у EGA есть регистр, позволяющий создавать отступы между строками. Присвоив регистру OFFSET значение 2, мы добавляем 16 байтов отступа, что даёт нам 16 лишних пикселей слева и 16 пикселей на виртуальном экране^[5].


Однако этого недостаточно, чтобы скроллинг был плавным. Если мы изменим адрес начала CRTC, то должны будем помнить, какие ниблы хранятся в плоскостях. Увеличение CRTC_START на 1 перемещает экран горизонтально на 8 пикселей. Скроллинг получается дёрганным, а не плавным.

Последний регистр, используемый в ATR, называется «Horizontal Pel Panning» (мы будем называть его PEL). Он получает 4 бита, чтобы приказывать CRTC пропускать до 7 битов от CRTC_START, прежде чем использовать ниблы. Именно это нам и нужно для плавного горизонтального скроллинга.

Каждое движение влево или вправо выполняется при помощи изменения регистра CRTC_START (на значение coordinate/8). Тогда движение можно точно настраивать при помощи регистра PEL (на значение coordinate%8).

▍ «Встряска» при завершении виртуального экрана

Итак, мы создали виртуальный экран во VRAM, позволяющий выполнять 16 плавных перемещений на один пиксель по обеим осям при помощи только регистров EGA. Но что произойдёт, когда мы достигнем конца? Именно здесь начинается инновация, от которой Джон Ромеро на полчаса потерял дар речи.

Как объяснял Джон Кармак^[6], после достижения конца виртуальный экран необходимо сбросить. Это не может быть перерисовывание целого экрана, потому что оно займёт 200 мс и снизит частоту обновления до 5 кадров в секунду. Эта операция, которую knolo
в своём прекрасном объяснении назвал «jolt» («встряска»)^[7], требовала совместной работы с дизайнерами игры.

Уровни CK созданы из тайлов размером 16x16. При рисовании тайлов художниками система сборки выдавала им уникальный ID. Дизайнер уровней создавал карту, располагая ID тайлов в 2D-редакторе. Движок CK отслеживает, какие ID тайлов находятся на виртуальном экране. Так как движок выполняет «встряску» с размерностью тайлов, он может чрезвычайно быстро определять, что изменилось на экране, сравнивая ID.

До «встряски»

Обратите внимание, что до «встряски» CRTC начинает с низа виртуального экрана. Отображаемое на экране изображение не меняется между «до» и «после». Однако виртуальный экран «заново центрируется».

После «встряски»

▍ Необходима помощь дизайнера карт

Для выполнения «встряски» движок сравнивает ID каждого тайла в текущем состоянии виртуального экрана и в нужном, заново центрированном состоянии. Для совпадающих тайлов никаких действий выполнять не нужно, они полностью пропускаются. Дополнительную нагрузку на CPU вызывают только несовпадающие тайлы, потому что они требуют перезаписи во VRAM.

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

На показанном ниже скриншоте Commander Keen 1 игрок плавно перемещается вправо, пока не закончится виртуальный экран. Происходит «встряска» на 16 пикселей влево. Мы видим, что перезаписано только небольшое количество тайлов.

До

После

Разность

Из 250 тайлов изменилось всего 40 (показаны розовым). Величина перерисовки составляет всего 16% от полного экрана.

▍ Спрайты

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

▍ Двойная буферизация/занимаемся математикой

Чтобы избежать визуальных артефактов, вся система дублируется при помощи двух буферов кадров. Пока изображение считывается CRTC, другое может быть записано в другое место во VRAM. Каждый буфер использует (320 + 32) * (200 + 32) * 4 / 8 = 40832 байта. При двойном буфере общая величина составляет 40832 * 2 = 81664 байта. Это намного больше, чем стандарт, заданный первой графической картой IBM EGA. Но это не проблема.

Только первая плата IBM EGA имела в составе 64 КиБ, это был неуклюжий монстр с кучей дискретных компонентов, требовавший дочерних плат для расширения VRAM.

Клоны EGA, которые начали появляться примерно в 1986-1987 годах, были основаны на интегрированных чипсетах (например, Chips & Technologies), и подавляющее большинство из них имело на плате 256 КиБ. Когда вышел Commander Keen, количество карт EGA с менее чем 256 КиБ было настолько мало, что им можно было пренебречь. — VileR (источники: ^[8], ^[9])

Любопытный факт: как управлять 256 КиБ VRAM, имея окно всего в 64 КиБ? Это не проблема, потому что каждый банк содержал 64 КиБ. CPU всё равно мог «видеть» всё при помощи регистра маски (выбора) плоскости.

▍ Лучше, чем Adaptive Tile Refresh: Drifting

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

Commander Keen 1, 2 и 3

В Commander Keen 1, 2 и 3 мы видим характерные повторяющиеся паттерны, требуемые для реализации ATR, но во второй трилогии, состоящей из Commander Keen 4, 5 и 6, их нет. Это наиболее заметно в начальном лесу CK 4, где не повторяется ничего, кроме подземных частей.

Commander Keen 4, 5 и 6

Как разработчикам это удалось? Джон Кармак намекнул на ответ в своём посте в Twitter за 2020 год^[11].

«Во второй трилогии Keen использовался более хитрый трюк — мы просто продолжали смещаться и перерисовывать передний край, позволив экрану возвращаться назад на краю окна 64 КиБ.» — Джон Кармак

Более подробное объяснение приведено в интервью с Лексом Фридманом за 2022 год^[12].

«Наконец, я задал вопрос, что на самом деле происходит, когда ты выходишь а край [памяти VRAM]?

Если ты берёшь начало [CRTC] и начинаешь двигаться, постепенно подбираясь к тому, что должно быть низом окна памяти. [...] Что случится, если я начну с 0xFFFE в самом конце блока на 64 КиБ? Оказывается, просто произойдёт перенос наверх блока.

Я подумал: о, это ведь всё упрощает. Можно просто скроллить экран в любую сторону, и всё, что тебе придётся отрисовывать — это просто одна новая строка тайлов.

И всё сработало. У нас больше не было проблемы наличия полей одинакового цвета. Что бы ты ни делал, можно создавать полностью уникальный мир и просто отрисовывать новую полосу.» — Джон Кармак

Вот и объяснение. ATR усовершенствовали, не добавив функции, а убрав одну из них. Без «встряски» адрес начала CRTC «дрейфует» в пространстве VRAM, пока не прокрутит пространство банков в 64 КиБ. Так как это происходит с обоими элементами двойного буфера, они дрейфуют с одинаковой скоростью и никогда не накладываются друг на друга. В большинстве случаев это работало, не вызывая проблем.

«Это очень просто, при этом система работает и она быстрее. Мы не видели в ней никаких минусов.

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

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

У меня была сложная ситуация. Мне что, нужно проверять каждую из этих [КАРТ SUPER VGA]? В то время ведь с ними происходил настоящий дурдом: было около двадцати разных производителей видеокарт, и каждый реализовал свою нестандартную функциональность немного по-своему. Мне нужно было или нативно программировать все эти карты, или бросить это дело. Я выбрал лёгкое решение — когда игрок доходит до края экрана, я закрывал глаза на задержку и просто копировал весь экран наверх». — Джон Кармак

Скорее всего, из-за этой методики невозможно было хранить во VRAM тайлы и спрайты (чтобы использовать быстрый метод копирования из VRAM во VRAM по 32 бита, популяризированный Майклом Абрашем). Но поскольку в каждом кадре отрисовывать нужно не так много, вероятно, это не имеет значения.

▍ Сноски

1. Распределение памяти EGA [0xA000:0000, 0xA000:FFFF].
2. IBM, Enhanced Graphics Adapter: 16/64 Color Graphics Modes (Mode 10).
3. Dh == 0xD, но написание с суффиксом H ощущается более олдскульным.
4. EGA: Video Memory Layouts.
5. Michael Abrash's Graphics Programming Black Book, Chapter 23.
6. The trick behind the scrolling in the first Commander Keen...
7. What is 'Adaptive Tile Refresh' in the context of Commander Keen?
8. PC Tech Journal Oct 1986, part 1.
9. PC Tech Journal Nov 1986, part 2.
10. Commander Keen in Keen Dreams source code.
11. The second Keen trilogy used a better trick.
12. The secret to Commander Keen: Side scrolling explained.

Telegram-канал с розыгрышами призов, новостями IT и постами о ретроиграх ????️