[Примечание переводчика: перевод первой части этой статьи уже есть ^[1] на Хабре, но её автор почему-то не завершил работу.]

Рендерер Quake III

Рендерер Quake III стал эволюционным развитием рендерера Quake II с аппаратным ускорением: классическая часть построена на архитектуре «двоичного разбиения»/«потенциально видимых наборов», но добавлены два новых заметных ключевых аспекта:

• Система шейдеров, построенная поверх фиксированного конвейера OpenGL 1.X. Это было большим достижением для 1999 года. Она обеспечивала большое пространство для инноваций в эру до повсеместно распространённых сегодня вершинных, геометрических и фрагментных шейдеров.
• Поддержка многоядерной архитектуры: клиент-серверная модель OpenGL блокирует некоторые методы и система потоков частично решает эту проблему.

Архитектура

Рендерер полностью содержится в renderer.lib и статично связан с quake3.exe:

Общая архитектура повторяет Quake Classic: в ней используется знаменитое сочетание BSP/PVS/карт освещения:

• Предварительная обработка:
  1. Дизайнер игры создаёт с помощью QRadiant .map и сохраняет его.
  2. q3bsp.exe разрезает карту двоичным разбиением пространства (BSP). Я писал об этом в обзоре рендерера Quake1.
  3. Из BSP генерируется система порталов: я писал об этом в статье об инструменте Doom3 Dmap ^[2].
  4. q3vis.exe использует систему порталов и генерирует PVS (потенциально видимый набор) для каждого листа. Каждый PVS сжимается и хранится в файле bsp, как описано в предыдущей статье.
  5. Система порталов очищается.
  6. q3light.exe вычисляет освещение для каждого полигона на карте и сохраняет результат как текстуры карт освещённости в файле bsp.
  7. На этом этапе все предварительно рассчитанные данные (PVS и карты освещения) хранятся в файле .bsp.
• Время выполнения:
  1. Движок загружает карту и bsp.
  2. Когда необходима визуализация:
  3. Движок разархивирует PVS для текущего листа и определяет, что видимо на самом деле.
  4. Для каждого полигона он с помощью мультитекстурирования сочетает карту освещения с цветом.

Этап мультитекстурирования и карт освещения чётко заметен, если изменить движок и отображать только одно или другое:

Текстура, нарисованная дизайнером уровня/художниками:

Карта освещения, сгенерированная q3light.exe:

Окончательный результат при соединении с помощью мультитекстурирования во время выполнения:

Архитектура рендеринга была рассмотрена Брайаном Хуком (Brian Hook) на Game Developer Conference в 1999 году. К сожалению, видео с GDC Vault ^[3] уже недоступно! [Зато оно есть на youtube ^[4].]

Шейдеры

Система шейдеров построена поверх фиксированного конвейера OpenGL 1.X, а потому очень затратна. Разработчики могут программировать модификации вершин, но также и добавлять проходы текстур. Это подробно рассмотрено в библии шейдеров Quake 3 Shader bible:
^[5]

Многоядерный рендерер и SMP (симметричная многопроцессорность)

Многим неизвестно, что Quake III Arena была выпущена с поддержкой SMP ^[6] с помощью cvariable r_smp. Фронтэнд и бекэнд обмениваются информацией через стандартную схему Producer-Consumer. Когда r_smp имеет значение 1, рисуемые поверхности попеременно сохраняются в двойной буфер, расположенный в ОЗУ. Фронтэнд (который называется в этом примере Main thread (основным потоком)), попеременно выполняет запись в один из буферов, в то время как из другого выполняет чтение бекэнд (в этом примере называемый Renderer thread (потоком рендерера)).

Пример демонстрирует, как всё работает:

t0-t1:

• Main thread решает, что отрисовывать, и записывает поверхности в surfacebuffer1.
• Для потока Renderer thread нет данных, поэтому он заблокирован.
• Поток GPU thread тоже ничего не делает.

t1-t2: повсюду начинаются процессы:

• Поток Main thread решает, что будет видимо в следующем кадре. Он записывает поверхность в буфер surfacebuffer2: это типичный пример двойной буферизации.
• Тем временем, поток Renderer thread выполняет вызов OpenGL и терпеливо ждёт, пока поток GPU thread не скопирует всё в надёжное место.
• Поток GPU thread считывает поверхность оттуда, куда указывает Renderer thread.

Заметьте, что в t2:

• Renderer thread всё ещё передаёт данные в GPU: используется SurfaceBuffer1.
• Main thread завершил запись в SurfaceBuffer2… но не может начать запись в SurfaceBuffer1: он заблокирован

Этот случай (когда Renderer thread блокирует Main thread) очень часто возникает при игре в Quake III:
Продемонстрируем ограничение блокировки одного из методов OpenGL API.

После t2:

• Как только Renderer thread заканчивает с SurfaceBuffer1 (t3), он начинает закачивать поверхности из SurfaceBuffer2.
• Как только он разблокируется (в t3), Main thread начинает работать в следующем кадре, записывая в SurfaceBuffer1.
• В такой конфигурации GPU почти никогда не простаивает.

Примечание: синхронизация выполняется через Windows Event Objects ^[7] в winglimp.c ^[8] (часть с ускорением SMP внизу).

Сетевая модель

Сетевая модель Quake3 — это, без всяких сомнений, наиболее элегантная часть движка. На низком уровне Quake III по-прежнему абстрагирует обмен данными с модулем NetChannel, впервые появившимся в Quake World ^[9]. Самое важное, что нужно понять:

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

Поэтому в результате движок использует UDP/IP: в коде нет следов TCP/IP, потому что «надёжная передача» создаёт недопустимую задержку. Сетевой стек был улучшен двумя взаимоисключающими слоями:

• Шифрование с использованием заранее переданного ключа.
• Сжатие с помощью заранее вычисленного ключа Хаффмана.

Но самый удивительный дизайн находится на стороне сервера, где элегантная система минимизирует размер каждой датаграммы UDP и компенсирует ненадёжность UDP: история снапшотов генерирует дельта-паркеты с помощью самоанализа памяти.

Архитектура

Сторона клиента в сетевой модели довольно проста: клиент каждый кадр отправляет серверу команды и получает обновления состояния игры. Сторона сервера немного более сложна, потому что она должна передавать общее состояние игры на каждый клиент с учётом потерянных пакетов UDP. Этот механизм содержит три основных элемента:

• Master Gamestate — это общее, истинное состояние вещей. Клиенты отправляют свои команды в Netchannel. Они преобразуются в event_t, которые изменяют состояние игры при получении сервером.
• Для каждого клиента сервер хранит 32 последних состояния игры, отправляемых по сети в циклическом массиве: они называются снапшотами. Массив циклически перемещается с использованием знаменитого трюка с двоичной маской, о которой я рассказывал в статье о Quake World Network (элегантные решения ^[9]).
• У сервера также есть «пустое» состояние, котором каждое поле имеет значение 0. Оно используется для дельта-снапшотов, у которых нет «предыдущих состояний».

Когда сервер решает отправить клиенту обновление, он использует по порядку все три элемента, чтобы сгенерировать сообщение, которое потом передаётся через NetChannel.

Интересный факт: хранение такого количества состояний игры для каждого игрока занимает большой объём памяти: по моим измерениям, 8 МБ для четверых игроков.

Система снапшотов

Чтобы понять систему снапшотов, приведу пример со следующими условиями:

• Сервер отправляет обновление клиенту Client1.
• Сервер пытается передать состояние, которое имеет четыре поля, клиенту Client2 (три целочисленных значения для position[X], position[Y], position[Z] и одно целочисленное значение для здоровья).
• Связь осуществляется через UDP/IP: эти сообщения довольно часто теряются в Интернете.

Кадр 1 сервера:

Сервер получил несколько обновлений от каждого клиента. Они повлияли на общее состояние игры (зелёного цвета). Настало время передать состояние клиенту Client1:

Чтобы сгенерировать сообщение, сетевой модуль ВСЕГДА делает следующее:

1. Копирует общее состояние игры в следующий слот истории клиента.
2. Сравнивает его с другим снапшотом.

Именно это мы видим на следующем изображении.

1. Общее состояние игры (Master gamestate) копируется с индексом 0 в историю Client1: теперь оно называется «Snapshot1».
2. Поскольку это первое обновление, в истории Client1 правильных снапшотов, поэтому движок использует пустой снапшот «Dummy snapshot», в котором все поля обнулены. Это приводит к ПОЛНОМУ обновлению, потому что каждое поле отправляется в NetChannel.

Важнее всего здесь понять то, что если в истории клиента нет правильных снапшотов, то движок берёт для генерирования дельта-сообщения пустой снапшот. Это приводит к полному обновлению, отправляемому клиенту в 132 битах (каждому полю предшествует битовый маркер ^[10]): [1 A_on32bits 1 B_on32bits 1 B_on32bits 1 C_on32bits].

Кадр 2 сервера:
Давайте теперь переместимся немного в будущее: вот второй кадр сервера. Как мы видим, каждый клиент отправил команды, и все они повлияли на общее состояние игры Master gamestate: Client2 переместился по оси Y, поэтому теперь pos[1] равно E (синего цвета). Client1 тоже отправил команды, но, что более важно, он подтвердил получение предыдущего обновления, поэтому Snapshot1 был помечен как подтверждённый («ACK»):

Выполняется тот же самый процесс:

1. Общее состояние игры копируется в следующий слот истории клиента: (индекс 1): это Snapshot2
2. На этот раз у нас в истории клиента есть правильный снапшот (snapshot1). Сравниваем эти два снапшота

В результате по сети пересылается только частичное обновление (pos[1] = E ). В этом заключается красота такого дизайна: процесс всегда одинаков.

Примечание: поскольку каждому полю предшествует битовый маркер ^[10] (1=изменилось, 0=не изменилось), для частичного обновления из примера выше используется 36 бит: [0 1 32bitsNewValue 0 0].

Кадр 3 сервера:
Сделаем ещё один шаг вперёд, чтобы посмотреть, как система справляется с утерянными пакетами. Теперь мы находимся в кадре 3. Клиенты продолжают отправлять команды серверу.
Client2 потерпел урон и здоровье теперь равно H. Но Client1 не подтвердил последнее обновление. Возможно, потерялся UDP сервера, возможно, потерялся ACK клиента, но в результате его невозможно использовать.

Несмотря на это, процесс остаётся тем же:

1. Копируем общее состояние игры в следующий слот истории клиента: (индекс 2): это Snapshot3
2. Сравниваем последний правильный подтверждённый снапшот (snapshot1).

В результате, сообщение отправляет его частично и содержит сочетание старых и новых изменений: (pos[1]=E и health=H). Заметьте, что snapshot1 может быть слишком устаревшим для использования. В этом случае движок снова использует «пустой снапшот», что приводит к полному обновлению.

Красота и элегантность системы — в её простоте. Один алгоритм автоматически:

• Генерирует частичное или полное обновление.
• Повторно отправляет в одном сообщении СТАРУЮ информацию, которая не была получена, и НОВУЮ информацию.

Самоанализ памяти на C

Вы можете задаться вопросом — как Quake3 сравнивает снапшоты самоанализом… ведь в C нет самоанализа.

Ответ заключается в следующем: каждое местоположение поля для netField_t создаётся предварительно с помощью массива и умных директив предварительной обработки:

    typedef struct {
        char    *name;
        int     offset;
        int     bits;
    } netField_t; 

    // используем оператор преобразования в строку для сохранения типизации...
    #define	NETF(x) #x,(int)&((entityState_t*)0)->x

    netField_t	entityStateFields[] = 
    {
    { NETF(pos.trTime), 32 },
    { NETF(pos.trBase[0]), 0 },
    { NETF(pos.trBase[1]), 0 },
    ...
    }

Полный код этой части находится в MSG_WriteDeltaEntity из snapshot.c ^[11]. Quake3 даже не знает, что сравнивает: он слепо использует индекс, смещение и размер entityStateFields и отправляет по сети различия.

Предварительная фрагментация

Углубившись в код, можно увидеть, что модуль NetChannel разрезает сообщения на блоки по 1400 байт (Netchan_Transmit ^[12]), даже несмотря на то, что максимальный размер датаграммы UDP составляет 65507 байт. Так движок избегает разбивания пакетов роутерами при передаче через Интернет, потому что у большинства сетей максимальный размер пакета (MTU) равен 1500 байтам. Избавление от фрагментации в роутерах очень важно, потому что:

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

Сообщения с надёжной и ненадёжной передачей

Хоть система снапшотов и компенсирует утерянные в сети датаграммы UDP, некоторые сообщения и команды должны быть доставлены обязательно (например, когда игрок выходит из игры или когда серверу нужно, чтобы клиент загрузил новый уровень).

Такая обязательность абстрагирована модулем NetChannel: я писал об этом в одном из предыдущих постов ^[9].

Рекомендуемое чтение

Один из разработчиков, Брайан Хук, написал небольшую статью о сетевой модели ^[13].

Автор Unlagged Нил «haste» Торонто (Neil «haste» Toronto) тоже её описывал ^[14].

Виртуальная машина

Если предыдущие движки отдавали виртуальной машине на откуп только геймплей, то idtech3 поручает ей существенно более важные задачи. Среди прочего:

• Визуализация запускается в клиентской виртуальной машине.
• Механизм компенсации задержки целиком реализован в клиентской ВМ.

Более того, её дизайн гораздо более сложен: в нём сочетается защита/портируемость виртуальной машины Quake1 с высокой производительностью нативных DLL Quake2. Это достигается компиляцией на лету байт-кода в команды x86.

Интересный факт: виртуальная машина изначально должна была стать простым интерпретатором байт-кода, но производительность оказалась очень низкой. Поэтому команда разработчиков написала компилятор x86 времени выполнения. Согласно файлу .plan от 16 августа 1999 года ^[15], с этой задачей справились за один день.

Архитектура

Виртуальная машина Quake III называется QVM. Постоянно загружены три её части:

• Сторона клиента: загружены две виртуальные машины. В зависимости от состояния игры сообщения отправляются одной из них:
  • cgame: получает сообщения в фазе боя. Выполняет только отсечение невидимой графики, предсказания и управляет renderer.lib.
  • q3_ui: получает сообщения в режиме меню. Использует системные вызовы для отрисовки меню.

• Сторона сервера:
  • game: всегда получает сообщения, выполняет игровую логику и использует bot.lib для работы ИИ.

Внутренности QVM

Прежде чем приступить к описанию использования QVM, давайте проверим, как генерируется байт-код. Как обычно, я предпочитаю объяснять с помощью иллюстраций и краткого сопроводительного текста:

quake3.exe и его интерпретатор байт-кода сгенерированы с помощью Visual Studio, но в байт-коде ВМ применяется совершенно другой подход:

1. Каждый файл .c (модуль трансляции) компилируется отдельно при помощи LCC.
2. LCC используется со специальным параметром, благодаря которому выполняется вывод не в PE (Windows Portable Executable), а в промежуточное представление, которое является текстовой сборкой стековой машины. Каждый созданный файл состоит из частей text, data и bss с экспортом и импортом символов.
3. Специальный инструмент id Software под названием q3asm.exe получает все текстовые файлы сборок и собирают их вместе в файл .qvm. Кроме того, он преобразует всю информацию из текстового в двоичный вид (ради скорости, на случай, если невозможно применить нативные преобразованные файлы). Также q3asm.exe распознаёт вызываемые системой методы.
4. После загрузки двоичного байт-кода quake3.exe преобразует его в команды x86 (не обязательно требуется).

Внутренности LCC

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

    extern int variableA;
    
    int variableB;
    
    int variableC=0;
    
    int fooFunction(char* string){
	    
        return variableA + strlen(string);
        
    }

Сохранённый в модуле трансляции module.c lcc.exe вызывается со специальным флагом, чтобы избежать генерации объекта Windows PE и выполнить вывод в промежуточное представление. Это файл вывода .obj LCC, соответствующий представленной выше функции C:

    data
    export variableC
    align 4
    LABELV variableC
    byte 4 0
    export fooFunction
    code
    proc fooFunction 4 4
    ADDRFP4 0
    INDIRP4
    ARGP4
    ADDRLP4 0
    ADDRGP4 strlen
    CALLI4
    ASGNI4
    ARGP4 variableA
    INDIRI4
    ADDRLP4 0
    INDIRI4
    ADDI4
    RETI4
    LABELV $1
    endproc fooFunction 4 4
    import strlen
    bss
    export variableB
    align 4
    LABELV variableB
    skip 4
    import variableA

Несколько замечаний:

• Байт-код разделён на части (text, data и bss): мы чётко видим bss (неинициализированные переменные), data (инициализированные переменные) и code (обычно называемую text)
• Функции определяются с помощью сендвича из proc, endproc.
• Промежуточное представление LCC — это стековая машина: все операции выполняются в стеке и никаких допущений о регистрах ЦП не делается.
• В конце фразы LCC у нас есть группа файлов, импортирующих/экспортирующих переменные/функции.
• Каждое объявление начинается с типа операции (например, ARGP4, ADDRGP4, CALLI4...). Каждый параметр и результат передаётся в стек.
• Импорт и экспорт находятся здесь, поэтому ассемблер может «связать» модули трансляции вместе. Заметьте, что используется import strlen, потому что ни q3asm.exe, ни интерпретатор ВМ не обращаются к стандартной библиотеке C, strlen считается системным вызовом и выполняется виртуальной машиной.

Такой текстовый файл генерируется для каждого файла .c в модуле ВМ.

Внутренности q3asm.exe

q3asm.exe получает текстовые файлы промежуточного представления LCC и собирает их вместе в файл .qvm:

Здесь можно заметить следующее:

• q3asm разбирается в каждом из символов импорта/экспорта в текстовых файлах.
• Некоторые методы заданы предварительно в текстовом файле системных вызовов. Можно увидеть syscall для клиентской ВМ ^[16] и для серверных ВМ ^[17]. У символов системных вызовов есть атрибуты в виде отрицательных целочисленных значений, чтобы их мог распознать интерпретатор.
• q3asm меняет представление с текстового на двоичное с целью получения пространства и скорости, но ничего более, никаких оптимизаций здесь не выполняется.
• Первым собираемым методом должен быть vmMain, потому что это диспетчер вводимых сообщений. Кроме того, он должен находиться в 0x2D текстового сегмента байт-кода.

QVM: как она работает

Снова рисунок, демонстрирующий уникальную точку входа и уникальную точку выхода, выполняющие диспетчеризацию:

Некоторые подробности:

Сообщения (Quake3 -> ВМ) отправляются виртуальной машине следующим образом:

• Любая часть Quake3 может вызвать VM_Call( vm_t *vm, int callnum, ... ).
• VMCall может получать до 11 параметров и записывает каждое 4-битное значение в байт-код ВМ (vm_t *vm) с 0x00 по 0x26.
• VMCall записывает идентификатор сообщения в 0x2A.
• Интерпретатор начинает интерпретировать опкоды в 0x2D (куда q3asm.exe записал vmMain).
• vmMain используется для диспетчеризации и маршрутизации сообщения к соответствующему методу байт-кода.

Список сообщений, отправляемых клиентской ВМ ^[18] и серверной ВМ ^[19], представлены в конце каждого файла.

Системные вызовы (ВМ -> Quake3) выполняются так:

• Интерпретатор один за другим выполняет опкоды ВМ (VM_CallInterpreted).
• Когда он встречает опкод CALLI4, то проверяет индекс метода в int.
• Если значение отрицательное, то вызов системный.
• Вызывается с параметрами указатель функции системного вызова (int (*systemCall)( int *parms )).
• Функция, на которую указывает systemCall, используется для диспетчеризации и маршрутизации системного вызова к нужной части quake3.exe

Список системных вызовов, предоставляемых клиентской ВМ ^[18] и серверной ВМ ^[19], находится в начале каждого файла.

Интересный факт: параметры всегда имеют очень простые типы, они или примитивные (char,int,float), или являются указателями на примитивные типы (char*,int[]). Подозреваю, что так сделано для минимизации проблем связи struct между Visual Studio и LCC.

Интересный факт: ВМ Quake3 не выполняет динамическое подключение, поэтому разработчик мода QVM не имел доступа ни к каким библиотекам, даже к стандартной библиотеке C (strlen, memset здесь есть, но на самом деле являются системными вызовами). Некоторым удавалось эмулировать их с помощью предварительно заданного буфера: Malloc in QVM ^[20].

Беспрецедентная свобода

Благодаря переносу функций в виртуальную машину сообщество моддеров получило гораздо более широкие возможности. В Unlagged Нила Торонто ^[21] система предсказаний была переписана с использованием «обратного согласнования».

Проблема производительности и её решение

Из-за такого длинного тулчейна разработка кода ВМ была сложной:

• Тулчейн был медленным.
• Тулчейн не был интегрирован в Visual Studio.
• Для сборки QVM требовалось использование инструментов командной строки. Это мешало процессу разработки.
• Из-за большого количества элементов тулчейна сложно было найти части, ответственные за ошибки.

Поэтому idTech3 также имелась возможность загрузки нативных DLL для частей ВМ, и это решило все проблемы:

В целом система ВМ была очень гибкой, потому что виртуальная машина имеет возможность выполнения:

• Интерпретируемого байт-кода
• Байт-кода, скомпилированного в команды x86
• Кода, скомпилированного в Windows DLL

Рекомендуемое чтение

^[22]

^[23]

^[24]

Искусственный интеллект

Сообщество моддеров написало системы ботов для всех предыдущих движков idTech. В своё время довольно известными были две системы:

• Для Quake1 был Omicron ^[25].
• Для Quake2 написали Gladiator.

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

Источник: страница 275 книги «Masters of Doom»:

К тому же не был готов фундаментальный ингредиент игры — боты. Боты — это персонажи, управляемые компьютером. Правильный бот должен хорошо вписываться в игру, дополнять уровни и взаимодействовать с игроком. Для Quake III, которая была исключительно многопользовательской игрой, боты оказались неотъемлемой частью игры в одиночку. Они должны были стать безусловно сложными и действовать подобно человеку.

Кармак впервые решил передать задачу создания ботов другому программисту компании, но потерпел неудачу. Он снова посчитал, что все, как и он, целеустремлённы и преданы работе. Но Кармак ошибался.

Когда Грэм попытался остановить работу, обнаружилось, что боты совершенно неэффективны. Они не вели себя, как люди, и были просто ботами. Команда начала паниковать. Это был март 1999 года, и причины для страха конечно же были.

Архитектура

В результате над ботами работал Жан-Поль ван Ваверен (Mr.Elusive), и это забавно, ведь он написал «Omicron» и «Gladiator». Это объясняет, почему часть серверного кода ботов выделена в отдельный проект bot.lib:

Я мог бы написать об этом, но Жан-Поль ван Ваверен (Jean-Paul van Waveren) сам написал
103-страничный труд ^[26] с подробным объяснением. Более того, Алекс Шампана (Alex J. Champandard) создал обзор кода системы ботов ^[27], в котором описывается местоположение каждого модуля, упомянутого в труде ван Ваверена. Этих двух документов достаточно для понимания ИИ Quake3.

Автор: PatientZero

Источник ^[28]