Исходный код Quake III

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

Рендерер 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.
  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 уже недоступно! [Зато оно есть на youtube.]

Шейдеры

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

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

Многим неизвестно, что Quake III Arena была выпущена с поддержкой SMP с помощью 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 в winglimp.c (часть с ускорением SMP внизу).

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

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

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

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

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

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

Архитектура

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

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



Примечание: поскольку каждому полю предшествует битовый маркер (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. Quake3 даже не знает, что сравнивает: он слепо использует индекс, смещение и размер entityStateFields и отправляет по сети различия.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Архитектура

Виртуальная машина 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 для клиентской ВМ и для серверных ВМ. У символов системных вызовов есть атрибуты в виде отрицательных целочисленных значений, чтобы их мог распознать интерпретатор.
• 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 используется для диспетчеризации и маршрутизации сообщения к соответствующему методу байт-кода.

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

Архитектура

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



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