Обзор исходного кода Quake 3: Архитектура (Часть 1)

Так как у меня была одна неделя до моего следующего контракта, я решил закончить мой цикл статей id. После Doom,Doom Iphone, Quake1, Quake2, Wolfenstein iPhone и Doom3, я решил изучить код, который я еще не рассматривал: idTech3 — 3D движок Quake III и Quake Live.

Движок по сути усовершенствованный idTech2, но есть несколько интересных усовершенствований. Ключевые пункты могут выглядеть в результате следующим образом:

• Часть 2: двухъядерное средство визуализации с материалами на основе шейдеров (создано через OpenGL Fixed Pipeline)
• Часть 3: новая сетевая модель, основанная на snapshots
• Часть 4: виртуальные машины играют главную роль в движке, комбинирующие мобильность/безопасность Quake1 и скорость Quake2
• Часть 5: новый искусственный интеллект для ботов.
Я был особенно впечатлен:

• Системой виртуальных машин и соответствующим инструментарием, которые в целом составляют 30% кода. С этой точки зрения idTech3 представляет собой мини-операционную систему, обеспечивающую системные вызовы трех процессов.
• Изящная сетевая система на основе снимков и самоанализе памяти.

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

Первый контакт

Так как многоуважаемый ftp.idsoftware.com был недавно закрыт, код вы можете найти на GitHub аккаунте id Software's.

git clone https://github.com/id-Software/Quake-III-Arena.git 

Когда приходит время изучать большой проект, я предпочитаю использовать XCode: быстрая подсветка, сочетания клавиш для нахождения определения и строковое выделение делает инструмент более мощным, чем VisualStudio. Но открытие проекта с Quake3 показало, что XCode 4.0 не может открыть проект XCode 2.0.
В конце концов я решил использовать Visual Studio 2010 Professional на Windows 8. После установки Productivity Power Tools к Visual Studio, работать стало приятнее.
Первое, что поразило меня в Visual Studio это то, что вместо одного проекта она открыла 8. Не все они используются, зависит от вида сборки: DEBUG или RELEASE (в частности game,cgame и q3_ui: проекты виртуальной машины). Некоторые из проектов вообще не используются (splines и ui).
Таблица лучше показывает, какой проект на какие модули влияет:

Небольшое отступление: рабочее название idTech3 было “Trinity”. Так как idTech4 назвали “Neo”, я подумал, что это связано с фильмом “Матрица”… но id Software утверждало в своем интервью с firingsquad.com, что назвали движок в честь «реки Trinity в Далласе».

Архитектура

Удобный способ понять архитектуру: надо сначала рассматривать ПО как черный ящик получающий входные сигналы (стрелки вверху слева) и генерирующий выходные (стрелки внизу):

Теперь посмотрим внутреннюю структуру в виде белого ящика с 6 модулями(quake3.exe, renderer.lib, bot.lib, game, cgame и q3_ui) взаимодействующими следующим образом:

Нужно понять 2 важные вещи в проекте:

• Каждый входной сигнал (клавиатура, сообщения win32, мышь, UDP сокет) преобразовывается в event_t и помещается в централизованную очередь событий (sysEvent_t eventQue[256]). Также это позволяет записывать(вести журнал) каждое воздействие, чтобы потом воссоздать ошибки. Это проектное решение было подробно обсуждено в .plan Джона Кармака 14 октября 1998.

• Явное разделение клиента и сервера (это было изложено в общих чертах в Q&A, который я сделал с Джоном Кармаком.

— Серверная часть ответственна за поддержание состояния игры, определение, что нужно клиентам и соединения их по сети. Она статически линкуется с bot.lib, который является отдельным проектом из-за его хаотической истории разработки.

— клиентская часть ответственна за предсказание, где находятся объекты (для компенсации задержки) и рендеринга изображения. Она статически линкуется с проектом рендеринга: отдельный проект, который позволил бы Direct3D или даже ПО для рендеринга включить очень просто.

Код

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

int WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)
    {
       
        Com_Init
        
        NET_Init
        
        while( 1 )
        {
            // Общий код
            IN_Frame()  // Добавление Win32 событий джойстика и мыши как event_t в общую очередь событий
            {
	             IN_JoyMove                                    
	             IN_ActivateMouse
	             IN_MouseMove
            }
	        
            Com_Frame
            {
                 // Общий код
                 Com_EventLoop    // Pump win32 message, UDP socket and console commands to the queue 
                                                                      // (sysEvent_t eventQue[256]) 
                 Cbuf_Execute
                 
                 // Код сервера
                 SV_Frame
                 {
                     SV_BotFrame                                 // переход к bot.lib
                     VM_Call( gvm, GAME_RUN_FRAME, svs.time )    // Переход к VM игры, где выполняется
                                                                      // игровая логика
                     
                     SV_CheckTimeouts
                     SV_SendClientMessages          // послать снимок или изменение снимка 
                                                                   // подключившемуся клиенту
                 } 
                 
                 // Common code
                 Com_EventLoop
                 Cbuf_Execute
                  
                 // Client code
                 CL_Frame
                 {
                     CL_SendCmd                                 // кладем событие в очередь и
                                                                    // отправляем команды на сервер
                     
                     SCR_UpdateScreen
                        VM_Call( cgvm, CG_DRAW_ACTIVE_FRAME);   // отправляем сообщение
                                            // на клиентскую VM (do Predictions).
                             or
                        VM_Call( uivm, UI_DRAW_CONNECT_SCREEN); // если меню видимо, сообщение отправлено
                     
                     S_Update                                   // обновить буфер звука
                 }
            }
            
        }
    }

Вот полностью развернутый цикл, который я использовал как карту, пока изучал код.
Интересную вещь можно заметить здесь, которая прекрасно иллюстрирует как важны виртуальные машины: нигде мы не видим вызова RE_RenderScene(функция, которая отбирает и дает команды OpenGL). Что вместо этого происходит:

1. Quake3.exe отправляет сообщение VM клиента: CG_DRAW_ACTIVE_FRAME, которое сигнализирует, что необходимо обновление.
2. Виртуальная машина выбирает некоторый объект и делает предсказание, затем вызывается OpenGL через системный вызов Quake3(CG_R_RENDERSCENE).
3. Quake3.exe получает системный вызов и фактически вызывает RE_RenderScene.

Статистика

Вот некоторые статистические данные от cloc:

На круговой диаграмме прекрасно видно, насколько необычны пропорции, так как 30% кода занимают инструменты.

Это объясняется отчасти потому, что в idtech3 реализованы функции ANSI C компилятора: Little C Compiler (LCC) с открытым исходным кодом используется, чтобы генерировать байт-код для виртуальных машин.

Выделение памяти

Здесь использовались два обычных аллокатора:
Zone Allocator: работает во время выполнения, выделение маленькой и кратковременной памяти
Hunk Allocator: работает во время загрузки уровня, большое и долговременное выделение памяти, в которую загружается содержимое pak файлов(геометрия, карты, текстуры, анимация).

Рекомендую почитать

Masters of Doom for history.
The two best compiler books to understand fully the Quake Virtual Machines.
A paper to understand LCC Intermediate Representation