Обзор исходного кода 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).
Таблица лучше показывает, какой проект на какие модули влияет:

Projects	Type	DEBUG Builds	RELEASE Builds	Comments
botlib	Static Library	botlib.lib	botlib.lib	A.I
cgame	Dynamic Libary/Bytecode	cgamex86.dll	—
game	Dynamic Libary/Bytecode	qagamex86.dll	—
q3_ui	Dynamic Libary/Bytecode	uix86.dll	—
quake3	Executable	quake3.exe	quake3.exe
renderer	Static Library	renderer.lib	renderer.lib	OpenGL based
Splines	Static Library	Splines.lib	Splines.lib	Used NOWHERE !
ui	Dynamic Libary/Bytecode	uix86_new.dll	—	Used for Quake III Arena.

Небольшое отступление: рабочее название 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 файлов(геометрия, карты, текстуры, анимация).