исходный код quake 1

Анализ исходного кода Quake

Я с удовольствием погрузился в изучение исходного кода Quake World и изложил в статье всё, что я понял. Надеюсь, это поможет желающим разобраться. Эта статья разделена на четыре части:

Архитектура

Клиент Quake

Изучение Quake стоит начать с проекта qwcl (клиента). Точка входа WinMain находится в sys_win.c. Вкратце код выглядит так:

Здесь мы можем выделить три основных элемента Quake World:

Установка промежуточной точки кода, если случается что-то плохое, то программа возвращается сюда.

Получение сообщений ОС Windows, сворачивание окна и т.п. Соответствующее обновление переменной движка (например, если окно свёрнуто, то мир не рендерится).

Получение информации о вводе с джойстика.

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

Игра начинается с exec quake.rc в буфере команд.

CL_ReadPackets и CL_SendCmd :

Обработка сетевой части движка.

CL_SendCmd перехватывает ввод мыши и клавиатуры, генерирует команду, которая затем отправляется.

Поскольку в Quake World использовался UDP, надёжность передачи гарантировалась набором sequence/sequenceACK в заголовках пакетов netChannel. Кроме того, последняя команда систематически отправлялась повторно. Со стороны клиента не было никаких ограничений на передачу пакетов, обновления отправлялись как можно чаще. Со стороны сервера сообщение клиенту отправлялось только если пакет был получен и скорость отправки была ниже скорости обработки. Этот предел устанавливался клиентом и отправлялся на сервер.

Весь раздел «Сеть» посвящён этой теме.

Выполняли прогнозирование в движке и расчёт коллизий. В основном они предназначены для борьбы с латентностью передачи по сети.

Этой теме посвящён весь раздел «Прогнозирование».

Этому целиком посвящён раздел «Визуализация».

Открытие архива zip и компилирование

После установки Windows и SDK DirectX компиляция в Visual Studio 2008 выявляет одну ошибку:

Компоновщик жалуется на LIBC.lib в проекте qwcl. Просто добавьте его в список игнорируемых библиотек «Ignored Library» и сборка четырёх проектов выполнится.

Инструменты

В качестве IDE замечательно подошла Visual Studio Express (бесплатная). Рекомендую прочитать несколько книг, если вы хотите глубже разбираться в движке на основе BSP/PVS, Id Software и Quake:

Моя полка с книгами на неделе работы с исходным кодом Quake выглядела так:

Сетевая архитектура QuakeWorld в своё время считалась потрясающей инновацией. Во всех последующих сетевых играх использовался тот же подход.

Сетевой стек

С точки зрения OSI NetChannel удобно расположен поверх UDP:

Заголовок NetChannel

Надёжные сообщения

Ненадёжные команды группируются в пакет UDP, он помечается последним исходящим числом sequence и отправляется: отправителю не важно, будет ли он потерян. Надёжные команды обрабатываются иначе. Главное — понять, что между отправителем и получателем может быть только один неподтверждённый надёжный пакет UDP

В каждом игровом цикле при генерировании новой надёжной команды она добавляется в массив message_buf (управляемый через переменную message ) (1). Набор надёжных команд затем перемещается из message в массив reliable_buf (2). Это происходит только если reliable_buf пуст (если он не пуст, это значит, что ранее был отправлен другой набор команд и его получение пока не подтверждено).

Затем формируется окончательный пакет UDP: добавляется заголовок NetChannel (3), затем содержимое reliable_buf и текущие ненадёжные команды (при наличии достаточного места).

На принимающей стороне сообщение UDP парсится, входящее число sequence передаётся в исходящее sequence ACK (4) (вместе с битовым флагом, указывающим на то, что пакет содержит надёжные данные).

При следующем получаемом сообщении:

Контроль передачи

Насколько я понял, контроль передачи выполняется только на стороне сервера. Клиент отправляет обновления своего состояния как можно чаще.

Важные команды

Подробнее о qport

Qport был добавлен в заголовок NetChannel для исправления ошибки. До qport сервер Quake идентифицировал клиента по комбинации «удалённый IP-адрес, удалённый порт UDP». Чаще всего это работало хорошо, но некоторые маршрутизаторы NAT могут произвольно менять свою схему трансляции портов (удалённого порта UDP). Порт UDP становится ненадёжным, и Джон Кармак (John Carmack) объяснил, что он решил идентифицировать клиент по «удалённому IP-адресу, Qport в заголовке NetChannel». Это исправило ошибку и позволило серверу на лету изменять целевой порт ответа UDP.

Вычисление латентности

Элегантные решения

Зацикленность индекса массива
Сетевая часть движка хранит 64 последних полученных пакетов UDP. Наивным решением циклического прохода по массиву было бы использование оператора остатка целочисленного деления:

Вместо этого вычисляется новое значение с двоичной операцией И для UPDATE_MASK. UPDATE_MASK равняется 64-1.

Настоящий код выглядит так:

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

Прогнозирование

Мы рассмотрели абстракцию NetChannel для сетевого обмена данными. Теперь мы узнаем, как латентность компенсируется с помощью прогнозирования. Вот материал для изучения:

Прогнозирование

Прогнозирование — это, вероятно, сложнейшая, меньше всего задокументированная и важнейшая часть движка Quake World. Цель прогнозирования — победить латентность, а именно компенсировать задержку, необходимую среде для передачи информации. Прогнозирование выполняется на стороне клиента. Этот процесс называется «Client Side Prediction». На стороне сервера техники компенсации лага не применяются.

Как видно, состояние игры «старее» на половину величины латентности (latency). Если добавить время на отправку команды, нам нужно ждать полный цикл (латентность), чтобы увидеть результаты наших действий:

Чтобы разобраться в системе прогнозирования Quake, нужно понять, как NetChannel заполняет переменную frames (массив frame_t ).

На этом этапе мы знаем мир таким, каким он был latency/2 назад. В NAT латентность вполне низкая ( 200ms), и необходимо выполнять прогнозирование для симуляции текущего состояния мира. Этот процесс выполняется по-разному для локального игрока и других игроков.

Локальный игрок

Для локального игрока латентность снижена почти до 0 благодаря экстраполяции того, что будет состоянием сервера. Это выполняется с помощью последнего полученного от сервера состояния и «проигрывания» всех команд, отправленного с того момента.

Поэтому клиент прогнозирует, каким будет его положение на сервере в момент t+latency/2.

Затем все другие игроки определяются в CL_SetSolidPlayers (cl.playernum); как твёрдые объекты (чтобы можно было протестировать коллизии) и «проигрываются» команды, отправленные с последнего полученного состояния до момента: cl.time senttime (коллизии тестируются на каждой итерации с помощью CL_PredictUsercmd ).

Другие игроки

Для других игроков у движка Quake нет «отправленных, но ещё не подтверждённых команд», поэтому вместо них используется интерполяция. Начиная с последнего известного положения cmd интерполируются для прогнозирования получаемого положения. Прогнозируется только положение, без углового поворота.

Quake World учитывает также латентность других игроков. Латентность каждого игрока отправляется вместе с обновлением мира.

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

Эта часть сложна, потому что Quake World не только выполняет прогнозирование для игроков, но и распознаёт коллизии исходя из прогнозов.

Первый вызов не выполняет прогнозирование, он только расставляет игроков в положения, полученные от сервера (то есть с задержкой в t-latency/2).

Здесь выполняется перемещение локального игрока:

Во втором вызове на стороне сервера прогнозируется положение других игроков в текущий момент (но перемещение пока не выполняется). Положение экстраполируется исходя из последних известных команд и последнего известного положения.

Здесь генерируются указания о видимости. Затем они передаются в рендерер.

Визуализация

Визуализация

Процесс визуализиции сцены неотъемлемо связан с BSP карты. Рекомендую почитать подробнее о Binary Space Partitioning (двоичном разбиении пространства) в Wikipedia. Если вкратце, то карты Quake проходили серьёзную предварительную обработку. Их объём рекурсивно разрезался следующим образом:

Этот процесс создавал BSP с листьями (правила создания таковы: выбрать существующий полигон в качестве секущей плоскости и выбрать разделитель, разрезающий меньшее количество полигонов). После создания BSP для каждого листа вычислялся PVS (Potentially Visible Set, потенциально видимый набор). Пример: лист 4 может потенциально видеть листья 7 и 9:

Окончальный PVS для этог листа сохранялся как битовый вектор:

В результате получался глобальный PVS размером примерно 5МБ. Это было слишком много для ПК в 1996 году. Поэтому PVS сжимался с помощью компрессии разности длин.

Закодированный PVS содержал только количество нулей между единицами. Хотя это и не выглядит очень эффективной техникой сжатия, большое количество листьев (32767) в сочетании с очень ограниченным набором видимых листьев снижали размер всего PVS до 20КБ.

Предварительная обработка в действии

Благодаря наличию предварительно рассчитанных BPS и PVS процедура визуализации карты движком была простой:

Примечание 2: При программном рендеринге обход BSP-дерева выполнялся с дальних точек до ближних.

Анализ кода

Вкратце код визуализации можно представить так:

В ней движок Quake извлекает лист/узел в BSP, на который направлена камера в текущий момент.

Mod_PointInLeaf расположен в model.c, он выполняется через BSP (корень BSP-дерева находится в model->nodes ).

Сохраняет в переменную r_viewleaf местоположение камеры в BSP (извлекаемое в R_SetupFrame ), выполняет поиск ( Mod_LeafPVS ) и распаковывает ( Mod_DecompressVis ) потенциально видимый набор (PVS). Затем итеративно обходит битовый вектор и помечает потенциально видимые узлы BSP: node->visframe = r_visframecount.

В этой части используется печально известный режим openGL «immediate mode», в то время он считался «последним словом техники».

В R_RecursiveWorldNode выполняется бóльшая часть операций отсечения поверхностей. Узел отсекается, если:

Формат MDL

Формат MDL — это набор фиксированных кадров. Движок Quake не интерполирует положение вершин для сглаживания анимации (поэтому высокая частота кадров не приводит улучшению анимации).

Элегантные решения

Элегантная пометка листьев

В R_SetupFrame вместо выполнения «быстрой и грязной» рекурсии для обхода BSP и извлечения текущего положения используется цикл while.

Минимизация количества переключений текстур

В openGL переключение текстур с помощью ( glBindTexture(GL_TEXTURE_2D,id) ) очень затратно. Для минимизации количества переключений текстур каждый полигон, помеченный для рендеринга, хранится в цепочке массивов, индексированных по материалу текстуры полигона.

После завершения отсечения цепочки текстур отрисовываются по порядку. Таким образом, выполняется всего N переключений текстур, где N — общее количество видимых текстур.

Источник

Авторов ремастера Quake обвинили в нарушении лицензии GPL

Возможно, разработчики должны были опубликовать исходники проекта.

Bethesda Softworks и студия MachineGames выпустили обновленную версию первой части Quake: ремастер получил поддержку современных ОС, слегка улучшенную графику и дополнительный контент. Есть проблема: возможно, его разработчики нарушили лицензию GPL.

На потенциальное нарушение обратили внимание члены фанатского и моддерского сообщества Quake. Дело в том, что один из основателей id Software Джон Кармак много лет назад опубликовал исходники Quake под лицензией GPL, разрешив модифицировать их и использовать — в том числе в платных проектах.

У лицензии есть оговорка: с момента публикации исходников все проекты, сделанные на базе кода Quake, также должны выкладывать свои исходники в открытый доступ. Даже если речь идет о платной игре.

Ремастер Quake сделан на базе исходников оригинальной игры, опубликованных Кармаком — а значит, теоретически тоже подпадает под действие лицензии. Ремастер вышел, а его исходники все еще не опубликованы; некоторые фанаты-разработчики считают, что это нарушение.

Есть и другое мнение. Предполагается, что как обладатель оригинальной версии исходников Quake, не выпускавшейся под лицензией GPL, Bethesda имеет право модифицировать их, в результате получив ремастер, на который не распространяется действие лицензии.

Кроме того, ремастер Quake работает через KEX Engine, специальный движок, разработанный Nightdive Studios для создания ремастеров ретро-игр. Движок запускает оригинальный Quake, а улучшения добавлены поверх него — то есть исходники, возможно, не модифицировались.

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

Я вообще ничего об этом не знаю, но выглядит отлично! Будет круто, если они опубликуют обновленные исходники так же, как мы это сделали с BFG-изданием Doom 3.

В Bethesda и MachineGames пока не отреагировали на предложение выложить исходники ремастера Quake в открытый доступ.

Источник

«Мясная фабрика». Краткая история Quake

25 лет назад, 22 июля 1996 года, произошло событие, которое в тот момент осталось почти незамеченным мировой айтишной общественностью, но вместе с тем оказало значительное влияние не только на гейм-девелопмент, но и на мировую культуру вообще. В этот день компания Id Software выпустила Quake — игру, буквально перевернувшую наше представление о шутерах от первого лица, ставшую одной из самых популярных игр в 90-е и послужившую фундаментом для зарождения киберспорта.

Помнится, в 1998 году я проходил преддипломную практику на одном жутко режимном предприятии. Высокоинтеллектуальных развлечений у старшекурсников-практикантов было немного: заклеить начальнику отдела скотчем шарик в мышке, или втихаря подложить кому-нибудь из инженеров в сумку мужское половое достоинство, аккуратно вылепленное из пластилина, которым по вечерам опечатывались помещения конструкторского бюро. Но была у нас одна развлекуха и покруче создания пластилиновых инсталляций. В КБ работала сеть, состоявшая из весьма серьезных на тот момент машин — Pentium 166 MMX. После 18:00, когда сотрудники понемногу снимались с насиженных мест и направлялись в сторону проходной, у нас появлялась возможность немного поиграть. Рубились мы в Quake. Разумеется, в deathmatch.

Лично я порой засиживался за компом до закрытия метро, и «наквакивался» до самых натуральных глюков. Бывало, идешь поздним вечером в уборную по длинному конторскому коридору, скрытому в таинственном полумраке: свет уже погашен, работает только тусклое дежурное освещение. Перед глазами мерещится крестик прицела, а в ушах стоит звон падающих гильз. В дверные проемы предусмотрительно заглядываешь, прежде чем зайти, да по привычке оглядываешься, чтобы кто-нибудь ненароком не шмальнул в спину из рокетгана.

Для меня, человека, последовательно игравшего в Wolfenstein 3D и Doom, Quake показался истинным откровением. Это был уже по-настоящему трехмерный шутер, в котором появилась возможность «посмотреть» себе под ноги (сами ноги при этом, правда, оставались невидимыми), или «в зенит». Еще можно было запрыгнуть куда-нибудь на антресоль или на голову другому игроку. В этой игре было нечего делать без мыши — будучи «клавишником-трактористом», я осознал это очень быстро, увидев, с какой невообразимой скоростью перемещаются и стреляют более опытные товарищи, правильно настроившие mouselook. Да и вообще, перед нами открылся дивный новый мир: криповый саунд-трек, прекрасно прорисованные локации, тени и освещение, меняющееся при пролете ракеты… Боты, моды, возможность нестись по уровню, оставляя за спиной кровавую кашу… Стоило полюбить Quake только за это!

▍ Немного истории

В итоге получился наглядный пример одной из самых успешных «халтур» в истории — ведь всего за полгода из имеющихся наработок слепили Франкенштейна: герой остался один, топор ему все-таки выдали (рубить рубит, вращаться не вращается), открытый мир урезали до 28 уровней, разбитых на 4 эпизода, красиво оформили все это в 3D – и отправили по готовым рельсам шутера от первого лица. Обычно подобные фокусы заканчиваются провалом и банкротством компании (да-да, New World Computing, это я вам!), но благодаря множеству нововведений Quake удалось не только выйти из тени старшего брата, но и опередить его со значительным отрывом в деле завоевания фанатских симпатий.

Впервые – ура! – нам завезли настоящее 3D. Сейчас это «тридэ» кажется довольно-таки примитивным, но для тех лет подобная графика стала настоящим прорывом. В Квейке персонаж наконец-то получил возможность по-настоящему передвигаться вверх-вниз в пространстве. А зачем нужны игры, где нельзя прыгать? Это, в свою очередь, дало возможность создавать многоуровневые локации с подводными пространствами и «чердаками», на которые предприимчивые игроки быстро научились взлетать на «рокет-джампе» — выстреливая себе под ноги, и с веселым «уиииии!» улетая в голубые дали (при этом рискуя в прямом смысле убиться об стену). Кроме того, новый движок кардинально изменил мультиплеер, в котором — тоже впервые — появилась возможность командной игры. Война одним кланом против другого вдохнула в геймплей принципиально новое содержание.

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

Еще один бесполезный факт: на одном из турниров и закрепилась классическая ныне раскладка WASD под левой рукой с мышью в правой. Продемонстрировал ее миру Деннис «Thresh» Фонг – победитель турнира «Red Annihilation», состоявшегося 21 июня 1997 года. За что получил памятное место в наших сердечках, а также суперприз: а-а-автомобиль «Феррари», принадлежавший ранее одному из разработчиков, Джону Кармаку. А вот левши получили еще одно напоминание о том, что мир несправедлив.

▍ Под капотом

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

В Quake Engine использовался оригинальный алгоритм обсчета трехмерной графики: часть локаций обсчитывалась заранее, что позволяло снизить нагрузку на аппаратные ресурсы компьютера. Ускорение работы движка достигалось еще и за счет того, что при обработке карт препроцессор убирал из рендеринга те поверхности окружения, которые игрок никогда не увидит (например, потому, что они находятся внутри стен). А в самом процессе игры ради экономии ресурсов из рендеринга исключались части пространства, которые в настоящий момент не видны игроку. Этот подход позволяет значительно ускорить обработку 3D-объектов даже при быстром перемещении игрока по локации.

В отличие от предыдущих движков (в том числе, лежащего в основе Doom), где каждый виртуальный источник света освещал определенный участок локации, в Quake разработчики применили специальную технологию карт освещения, которые накладывались на карту уровня, и трехмерных источников света. Это позволило не только сделать освещенность локаций еще более реалистичной, но также снизить нагрузку на процессор.

Ко всему прочему, игровой движок Quake первым в истории поддерживал аппаратное 3D-ускорение графики. Во времена популярности игры существовало не так уж много 3D-акселераторов: самой популярной железякой на тот момент была плата Voodoo от компании 3DFX, соединявшаяся специальным переходником с обычной видеокартой. Плата стоила, как самолет, но, тем не менее, ее приобретали многие игровые клубы — именно с тем, чтобы завлечь к себе «квакеров».

С ростом популярности 32-разрядной винды к Quake Engine прикрутили поддержку OpenGL. Спустя некоторое время движок стал доступен под открытой лицензией GNU General Public License, что позволило, во-первых, портировать Quake на другие платформы, а во-вторых, подарило жизнь множеству оригинальных игровых проектов и форков — игровых движков, основанных на Quake Engine.

▍ Франшиза

Оригинальный Quake, хоть и замахнулся на полноценный онлайн-режим, до конца не учитывал специфику нового формата – при попытке выйти в большие интернеты часто начинались проблемы. Из-за того, что разные игроки имели разную скорость соединения, у некоторых пользователей игра изрядно лагала, а если на сервере присутствовали одновременно игроки, имеющие высокую и низкую скорость соединения, первые получали ощутимое преимущество. Пришлось спешно выпускать вдогонку к игре версию QuakeWorld с переработанным кодом и поддержкой протокола UDP. Умная машина отныне предсказывала положение игроков на карте и позволяла играть даже обладателям медлительного диал-апа. QuakeWorld, к слову, жив и вполне неплохо чувствует себя и сегодня. Можно скачать клиента, заглянуть на один из серверов, и вспомнить молодость.

Позднее разработчики говорили в интервью, что хотели разделить франшизу так, чтобы третья часть продолжала первую, а вторая и четвертая выступили отдельными произведениями – но что-то пошло не так. Помимо новой графики в Quake II неожиданно появился сюжет: игрок должен защищать Землю от инопланентного нашествия цивилизации строггов. В игру добавили миссии, которые игроку надо выполнять в свободное от «кровь-кишки» время. Следуя славной традиции, компания выпустила исходный код игры на потеху мододелам на правах свободной общедоступной лицензии – и не прогадала. Сами разработчики признаются, что были в восторге от находок сообщества, а постоянные дополнения и ответвления позволили игрушке дымиться еще десяток лет на чистом энтузиазме.

Для третьей части культовой саги в Id Software не стали изобретать велосипед, а выпустили концентрированное мочилово с прицелом на дуэльные и командные сражения. Одиночный режим в игре тоже присутствовал, но напоминал скорее «тренировку с ботами» в рамках подготовки к матчам с игроками. Возможно, именно поэтому третий «квейк» характеризуют, как отличный дуэльный шутер, но жалуются на слабый мультиплеер.

Коммерческий успех был несколько подпорчен уже имеющимися в открытом доступе модами ко второй части – зачем платить за то, во что уже давно бесплатно поиграл? Плюс не все фанаты охотно пересаживались на новый движок, считая его неудобным и излишне прожорливым. Но несмотря на недочеты, Quake III активно ворвался в мир киберспорта. Чемпионаты по нему проводились несколько раз в год, в том числе, игра засветилась на World Cyber Games и Cyberathlete Professional League. В 2010 году Quake III мутировал в Quake Live со множеством сетевых режимов, и сейчас эта игра доступна в Steam за вполне вменяемые деньги.

Заключительная (на сегодняшний день) часть франшизы носит порядковый номер IV, и разработана она компанией Raven Software. Сюжет продолжает вторую часть франшизы – после того, как атака инопланетного разума на Землю была успешно отбита, мы высаживаемся в стиле «Звездного десанта» на планету строггов и выполняем заданные миссии, которые сводятся в целом к уничтожению живой силы противника. Движок игры позаимствовали у сводного брата – Doom 3, но разработчики хорошо поработали над дизайном и оптимизацией производительности. Мультиплеер в четвертой части – это та же третья, только динамичнее. В итоге получилась коммерчески выверенная поделка без намека на оригинальность. Красивая, глянцевая, яркая и красочная. Но без души.

Для желающих не просто «пострелять», а «прикоснуться к легенде», доступна еще одна версия игры под названием Quake Champions. К разработке вернулись уже знакомые нам id Software, а пригрела их под крылышком в качестве издателя большая важная Bethesda. Игра распространяется условно-бесплатно: на старте игроку доступен только один персонаж, остальных можно докупить за игровую валюту (но не сразу), либо за реальные деньги (зато быстро). Примечательно, что в разработке Quake Champions принимали участие профессиональные игроки в предыдущие части Quake, что как бы намекает на серьезный подход к достижению высокой «играбельности». Помимо классического deathmatch в Quake Champions доступны дуэльный и командный режимы, а также увлекательный бой на рельсотронах, убивающих с первого попадания. В общем, интересный проект — особенно для любителей классического Quake, которым по какой-то причине не зашел QuakeWorld.

▍ И все же…

Quake стал революционным продуктом, который фактически создал не только киберспорт, но еще и целое семейство других игр, породив целый жанр шутеров нового поколения. А лаконичная эстетика Quake, демонстрирующая игроку минимум деталей, дабы не отвлекать его от самого главного — игрового процесса — сделалась законодателем этого жанра. Quake появился к месту и ко времени, разделив историю гейм-девелопмента на «до» и «после». Те, кто играл в классическую «Квяку», невольно будут сравнивать новые шутеры именно с ним. И не всегда это сравнение будет в пользу новинок.

Источник