20 февраля 2013 в 21:29

Обзор исходного кода 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 Library/Bytecode cgamex86.dll -
game Dynamic Library/Bytecode qagamex86.dll -
q3_ui Dynamic Library/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 Library/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 файлов(геометрия, карты, текстуры, анимация).

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


По истории Quake — Masters of Doom.
Две лучшие книги по компиляторам, чтобы лучше понять виртуальные машины Quake.
Статья, чтобы понять что такое LCC Intermediate Representation



Перевод: Fabien Sanglard
Тимур @Mungoost
карма
27,0
рейтинг 0,0
Самое читаемое Разработка

Комментарии (27)

  • +8
    оказывается, там всё очень круто
  • +3
    Будет ли перевод остальных частей?
    • +8
      В свободное время постараюсь сделать
  • +1
    Я правильно понял, что виртуальные машины — это для поддержки скриптового языка, как lua и python в некоторых движках?
    • НЛО прилетело и опубликовало эту надпись здесь
      • НЛО прилетело и опубликовало эту надпись здесь
      • +5
        Напоминает эмулятор приставки.
      • +2
        байт-код, которой при загрузке модуля компилируется в машинный код

        без каких-либо изменений запустить результат на линукс/ARM


        Вот только для начала нужно будет в движке дописать компилятор байт-кода в машинный код ARM. Оригинальные исходники под х86 и PowerPC заточены, вроде как
        • +3
          Да ну, вряд ли сильно заточены. Ну или портирование было не особо сложным, ибо он давно уже бегает под АРМом:

          • +1
            Для сомневающихся — это именно нативный Quake3: github.com/blackberry/Quake3
          • 0
            и под андроид тоже
            прикольно на таблетке играть :)
      • 0
        В своё время хотел сделать Quake 3 сервер мода Excessive Plus на роутере, но тогда не хватило мозгов, опыта и т.п. Сейчас не хватает времени и не понятно зачем это теперь и кому нужно :).
  • +2
    Кто заинтересовался виртуальной машиной, гуглите человека и просите у него слайды с последнего FOSDEM–a.
  • +9
    Офигенная подача материала. Начинать разбор любой вещи с ответа на вопрос «что на входе и что на выходе» — лучший способ.
  • +2
    Вот так считаешь что-то вечным, а оно (ftp-сервер) раз и закрылось…
    • +4
      Они просто перенесли все исходники на гитхаб
  • 0
    Многие игры-шедевры не менее красивы изнутри. Из всего что знаю, больше всего запомнились разработчики World of Warcraft, своими красивыми(и одновременно хитрыми) реализациями идей.
    • +1
      Прошу прощения, а где же это можно посмотреть на исходники wow?
    • +3
      Не поделитесь ссылочкой на разработчиков WoW? Я так понимаю, речь не о коде, а о статьях и заметках?
  • +9
    А быстрый обратный квадратный корень на хабре уже обсуждали? В свое время никак не мог понять, как же до такого додумались, да еще и движок игры таким образом ускорили :)
    • +13
      Для тех, кто не в теме — речь об этом.
      На хабре упоминался лишь мельком.
      • 0
        Ничего себе… Точность там, конечно, не ахти, но алгоритм впечатляет…
  • +3
    Последние три строчки — переводчик принял за названия книг, так что переводить (и даже читать) не стал?
    • +1
      Исправил. Под конец я просто устал, и не обратил на них внимания. Спасибо за замечание.
  • 0
    ftp.idsoftware.com вроде бы заработал
  • –4
    Потрясающе интересная тема и ужасно костноязычный текст. Даже затрудняюсь решить, плюсовать или минусовать его…
  • +1
    Моё уважение к Кармаку выросло многократно. Снимаю шляпу. Хоть и не существующую. :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.