Doom engine

Doom engine («движок Doom»), также известный как id Tech 1 — псевдотрёхмерный игровой движок, разработанный американской компанией id Software и применяемый в компьютерных играх Doom, Heretic, HeXen, Strife, HacX и других играх, созданных по лицензии. Создан Джоном Кармаком, вспомогательные функции были написаны Майклом Абрашем (), Джоном Ромеро (), Дэйвом Тэйлором () и Полом Райдеком (). Первоначально написан на компьютерах NeXT, затем, для первого релиза Doom был портирован под DOS, а позднее ещё на несколько игровых консолей и операционных систем.

Отличия от Wolfenstein 3D engine 
 Пол и потолок могут иметь любую высоту.
 Стены не обязательно ориентированы в направлении «север-юг» или «запад-восток».
 Изменяющаяся освещённость, повышавшая реалистичность графики.
 Лифты, дистанционно открывающиеся двери, опускающиеся и придавливающие потолки, поднимающиеся ступеньки и другие движущиеся элементы.
 Персонажи могут прыгать, падать с крыш и летать по воздуху (впрочем, пройти под летящим врагом или пролететь сверху в прыжке всё равно невозможно).
 Звуковая подсистема поддерживала стереозвук и микширование до 8 эффектов одновременно.
 Персонаж при движении покачивался вверх-вниз, что создало бо́льшую иллюзию ходьбы (в Wolfenstein точка обзора находилась на постоянной высоте примерно на уровне живота, игрок словно ехал в инвалидной коляске).
 Разрешалось (хоть и не поощрялось) подключение дополнительных модулей (WAD-файлов) с уровнями, графикой и звуками. Идея расширяемости пошла от Джона Кармака, который сам модифицировал игры и хотел, чтобы другие это делали.

Ограничения 
 Лабиринт имеет горизонтальный пол с потолком и вертикальные стены.
 Две комнаты не могут находиться одна над другой. Таким образом, карта уровня является совершенно двумерной.
 Во всей игре масштаб спрайтов и текстур постоянный. Поэтому, например, невозможно установить высокодетализированный плакат на менее детальной стене.
 Авторы так и не проработали вертикальные столкновения объектов. Поэтому нельзя, например, пробежать под летящим какодемоном или, разогнавшись на какой-нибудь крыше, перепрыгнуть через факел. (Исправлено в Heretic и Hexen, так как в них это было необходимо из-за подбираемой магической возможности полёта игрока.)
 Игра не делала и других проверок по оси Z — например, рыскающий в подвале имп вполне мог нанести повреждения игроку, находящемуся в паре сотен метров выше, на чердаке, а взорвавшаяся у основания здания ракета наносила урон монстру на крыше. Игрок мог использовать переключатели вне зависимости от высоты (например, всё ещё можно активировать ушедший под землю выключатель на уровне MAP01 Entryway в Doom 2).
 Особая структура уровня (так называемое двоичное разбиение пространства) требовала сборки перед испытанием уровня. Сборка происходит автоматически, на компьютерах того времени менее чем за минуту — тем не менее, это мешало просматривать уровень в реальном времени прямо по ходу редактирования (в отличие от Build Engine). К тому же двоичное разбиение делило стены на «отрезки» () — это усложняло геометрию уровня.
 Из-за этого крайне ограничено горизонтальное движение геометрии уровня (polyobjs из Hexen). Build Engine позволял горизонтальные лифты и вагончики.
 Высота текстуры, если та повторяется по вертикали, должна всегда равняться 128 текселям. Для неповторяющихся текстур (подступёнков, решёток и т. д.) это не требуется. Исправлено в многочисленных портах Doom.
 Просмотр вверх-вниз, реализованный в Heretic, был псевдотрёхмерным, вертикальные линии всегда оставались вертикальными.

Технические особенности 
Движок был написан на Си на рабочих станциях NeXT в операционной системе NEXTSTEP. Изначально использовался компилятор Intel C, но в дальнейшем был использован Watcom C. Утилиты были написаны под NeXT на Objective-C. Движок Doom был прогрессивным для своего времени. Несмотря на то, что Си — язык процедурного программирования, движок Doom написан в явно выраженном объектном стиле.

Устройство уровней 

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

Уровень состоит из десяти блоков .WAD-файла; из них пять (VERTEXES, LINEDEFS, SIDEDEFS, SECTORS и THINGS) непосредственно редактируются пользователем, ещё пять (SEGS, SSECTORS, NODES, REJECT и BLOCKMAP) — вычисляются BSP-построителем.

Уровни строятся по субтрактивному принципу: всё пространство заполнено непроходимой материей, и автор уровня «прорубает» в этой материи туннели. Основой уровня являются вершины () — точки в двухмерном пространстве. Между вершинами проводятся отрезки (). Отрезок может иметь одну или две стороны (). Текстуры задаются не для отрезков, а для сторон, так что отрезок может быть покрыт с разных сторон разными текстурами.

Вершины и отрезки образуют плоский граф; каждая его грань может быть или непроходимым пространством (например, колонной), или сектором (). Иногда структуру секторов намеренно нарушают — на этом основаны спецэффекты наподобие невидимых мостов. Каждый сектор имеет в плане произвольную форму (не обязательно выпуклую или односвязную). У сектора всегда горизонтальные пол с потолком и постоянная освещённость. Односторонние отрезки являются глухими стенами, двусторонние — образуют переходы между секторами.

Чтобы обеспечить высочайшую на то время интерактивность, применены так называемые теги. Отрезок и сектор имеют особое целое поле — «тэг». Чтобы сделать выключатель, опускающий лифт, отрезку-выключателю задаются код действия «выключатель, опускающий лифт» и какой-нибудь тег (например, 5). Этот же тег присваивается сектору-лифту. При активации отрезок будет выполнять указанное действие на всех секторах с этим тегом.

Наконец, на уровне расставляются объекты (). При этом набор характеристик объекта в Doom оказался довольно беден: например, не было Z-координаты, наземный объект в начале игры всегда стоял на полу, а воздушный — висел под потолком. Нельзя сделать, чтобы объект был только в одиночной игре, или только в deathmatch, или только в кооперативной (был лишь флаг «только в сетевых играх»).

Игра 
Все вычисления проводятся с частотой 35 тактов в секунду, в фиксированной запятой 16,16, с машинной единицей, равной одному текселю (рост игрока 56 текселей — значит, 1 тексель примерно равен 4 см). Для угловых величин применяется фиксированная запятая, в которой 232 = 360°. Впрочем, большинство угловых расчётов были грубее — например, повороты игрока рассчитываются с точностью в 360° = 216 = 65536, а тригонометрическая таблица состояла всего из 8192 (213) величин.

Запись демо-роликов и сетевая игра основаны на том, что на цифровой ЭВМ один и тот же код с одними и теми же данными приводит к одному и тому же результату, а поведение целочисленной арифметики жёстко заспецифицировано и не зависит от модели процессора. Игра записывает в демо-ролик (и передаёт по сети) команды управления; если в игре нет грубых ошибок, различные машины, интерпретируя одни и те же команды управления, получают один и тот же результат. Впрочем, ошибки, приводящие к рассинхронизации, в игре всё-таки есть: в частности, если в одиночной игре зайти в меню, игра останавливается, но ролик продолжает писаться. Недостаток такого подхода — невозможность перемотать ролик; его можно только проиграть с начала.

В режиме записи демо-роликов точность поворотов снижалась до 256 на 360 градусов; внимательный игрок может заметить, что в режиме демозаписи наводка становится грубее. Это служит исключительно для экономии памяти в демо-роликах и исправлено в многочисленных портах ценой потери совместимости с исходной игрой.

Каждый игровой такт (1/35 секунды) игра проводит цикл управления каждым монстром. Чтобы сэкономить процессорные такты, существует битовая матрица REJECT: для любых двух секторов, если ни из одной точки сектора А не видна никакая точка сектора Б, на этом месте в матрице ставится единица. Если на пересечении строки, соответствующей сектору игрока, и столбца, соответствующего сектору монстра, стоит 0, проводится проверка, видит ли монстр игрока; если 1 — монстр гарантированно не видит игрока. Матрица REJECT очень сложна для построения, и большинство пользовательских редакторов заполняли её нулями (существовало очень мало утилит, которые строили её; основные — RMB и ZENNODE).

Структура BLOCKMAP применяется физическим движком, чтобы ускорить проверку столкновений объектов с отрезками.

Построение изображения 
Для ускорения отображения используется BSP-дерево (в отличие от порталов в Duke Nukem 3D). Объекты изображаются в виде спрайтов, в отличие от Quake.

Движок рекурсивно проходится по BSP-дереву, отрисовывая стены от ближних к дальним:
 функция ПроходПоДереву(узел)

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

   если узел является развилкой

     то   // узел является развилкой - рекурсивно пройти
       если камера слева от секущей плоскости
         то ПроходПоДереву(узел.левый); ПроходПоДереву(узел.правый)
         иначе ПроходПоДереву(узел.правый); ПроходПоДереву(узел.левый)

     иначе // узел является подсектором
       нарисовать(узел)
Здесь и задействованы оставшиеся три блока. Секторы разбиваются секущими на выпуклые элементы, именуемые подсекторами (SSECTORS), отрезки — на сегменты (SEGS). Сама структура дерева (охватывающие прямоугольники, секущие, указатели на «сыновей») хранится в блоке NODES. В этом цикле рисуются только глухие стены (то есть, средние текстуры для односторонних стен, и верхние и нижние — для двусторонних). Объекты, полы и решётки записываются в отдельные массивы и отрисовываются на более поздних стадиях. Массив, в котором хранятся полы, сделан довольно малым, и у самодеятельных конструкторов довольно часто случалось переполнение и выход с сообщением «No more visplanes!».

После того, как отрисованы стены, по строкам рисуются полы, записанные в visplanes.

В каждом секторе держится связанный список объектов, которые находятся в нём. На этапе прорисовки стен видимые объекты вместе с точками отсечки складываются в массив. После того, как движок нарисует полы и потолки, массив сортируется, и ближайшие 128 объектов рисуются от дальних к ближним с помощью тех же процедур, что используются для рисования стен. На этом же этапе рисуются и решётки («средние» текстуры на двусторонних стенах).

Текстуры стен и спрайты хранятся в .WAD-файле по столбцам, текстуры полов и потолков — простой массив 64×64.

Doom для DOS работал в режиме VGA 320×200 с тройной буферизацией, для Linux — использовал обычный режим VGA 13h. При этом величина разрешения была закодирована в ассемблерных процедурах в двух местах; версии игры, которые использовали переменное разрешение, либо имели несколько функций под разные разрешения, либо динамически модифицировали код, подставляя нужное разрешение. Впрочем, в частях игры, которые к движку не относятся, встречалось крайне много магических чисел, связанных с разрешением экрана и экранными координатами различных объектов, поэтому первые порты Doom страдали «расползающейся» в SVGA-режимах графикой меню.

Длительная загрузка 
Doom известен своей длительной загрузкой (больше минуты на компьютерах своего времени). Основная часть времени тратилась на инициализацию «демона перерисовки Doom» ().

Doom распространялся на дискетах и через BBS, важен был каждый байт. Чтобы уменьшить размер, сделали такой механизм. Каждая из текстур для стен состояла из фрагментов (): например, стена с выключателем может состоять из картинки стены и картинки выключателя, или плиточная стена — из трёх-четырёх плиток, хаотически разбросанных по большой текстуре. Текстуры, как сказано выше, рисуются по столбцам. Doom проходился по всем столбцам всех текстур и проверял, какие фрагменты покрывают тот или иной столбец; строилась соответствующая структура данных. Эту структуру можно было закэшировать, или строить при загрузке уровня, достраивая динамически по мере надобности — в этом случае Doom загружался бы намного быстрее.

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

Сетевой код 
Doom основан на модели «равный с равным». Как было сказано выше, синхронность игры на всех машинах обеспечивается тем фактом, что один и тот же код с одними и теми же данными возвращает один и тот же результат. С каждым пакетом передаётся «свёртка синхронизации» — обычно координата одного из игроков; если полученная с пакетом свёртка не совпадает с локально вычисленной, игра прекращает работу с сообщением о рассинхронизации. Никаких средств противостояния задержкам передачи нет; если средний пинг превышает 1/35 секунды, замедляется реакция игры на управление. Игра может запрашивать потерянные пакеты и дублировать их, чтобы запросы повторной передачи шли как можно реже. Входа в начатую игру нет.

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

Каждый из игроков имеет свой цвет: первый — зелёный, второй — серый, третий — коричневый, четвёртый — красный. Номера игроков (и, соответственно, цвета) раздаются сетевым драйвером, а не игрой. В игре по IPX через программу IPXSETUP отдаваемые игрокам цвета зависят от MAC-адресов сетевых плат, в игре по модему или кабелю через SERSETUP — от случайных факторов.

Интересной недокументированной функцией версий 1.0 и 1.1 была одиночная игра на трёхмониторной системе: один показывает то, что спереди от игрока, второй — то, что слева, третий — то, что справа. Поскольку видеоплат с таким количеством мониторов на то время не существовало, для такой игры нужны были три компьютера, соединённых сетью. Впрочем, эта функция существовала лишь в зачатке: чтобы загрузиться с сохранения, требовалось на всех трёх компьютерах перезапустить игру.

Список игр, использующих Doom engine 
Движок Doom продавался другим компаниям. На нём был сделан ряд игр. Среди них:

Также фанатами игры создавались пользовательские модификации, которые полностью преображали игру. Первая из них — Alien Doom — была сделана по фильму «Чужой». Впоследствии появились модификации и по другим фильмам: «Охотники за привидениями», «Бэтмен» и «Секретные материалы». См. Моддинг Doom’a.

Открытие исходного кода 
В 1994 году открыли исходные тексты сетевых драйверов. Энтузиасты начали разрабатывать собственные драйверы: например, для LPT-кабеля (PARSETUP) и даже для цепочки COM-кабелей (HX8).

В декабре 1997 года полный исходный текст Doom для Linux был опубликован под несвободной бесплатной лицензией (версия для DOS не публиковалась из-за платной звуковой библиотеки DMX). Уже в январе 1998 года появился первый порт этого кода для DOS — DosDoom. Вместо DMX использовали открытый Allegro.

Пионерами расширения Doom были Ли Киллоу (Boom — расширенная версия Doom, в которой были исправлены многие ошибки оригинальной игры), Денис Фабрис и Борис Перейра (Doom Legacy с поддержкой высоких разрешений), а также Брюс Льюис (glDoom, первый порт Doom под OpenGL).

После полугода разработки поломка жёсткого диска компьютера Льюиса поставила крест на glDoom: резервной копии не было. Из-за этого Кармак перелицензировал исходные тексты под GNU General Public License: если бы лицензия не была такой ограничивающей, исходный текст обязательно нашёлся бы у кого-то. Остальные ресурсы так и остаются платными. Спустя 12 лет исходный код нашёлся — у друга, к которому Льюис ходил с диском.

В Doom было найдено огромное количество ошибок. Физический движок и рендерер по-разному определяли, является плоскость «небесной» или нет: ракета могла ударить в небо и взорваться, и наоборот, могла «улететь», не взрываясь, через глухую стену. Монстры застревали в дверях, а Arch-Vile, воскрешая раздавленный труп, одновременно делал его неуязвимым и способным проходить через стены. Обычно порты проверяли версию демо-ролика: ошибки включались, если ролик записан исходной версией игры, и выключались, если портом. Подобные ошибки на некоторых пользовательских уровнях были критичны для прохождения — поэтому в Boom и производных портах их можно было включить через меню.

Сейчас существует несколько десятков расширенных версий Doom — от простейших до чрезвычайно мощных. Они позволяют играть с более высоким разрешением, чем оригинальный Doom, имеют дополнительные возможности (обзор вверх-вниз, перекрестие прицела), а также расширенную сетевую игру. Наиболее известные из этих версий:

 Производные Boom, например, Smack My Marine Up, prBoom. Имеют мощные средства разработчика: скриптовый язык FraggleScript, дополнительные типы объектов, язык редактирования свойств объектов (BEX) и т. д. Как правило, у производных Boom совместимость с исходной игрой предельная — вплоть до того, что демо-ролики, записанные в Doom, под Boom никогда не рассинхронизируются.
 Doom Legacy — имеет качественный пользовательский интерфейс, портирован на DOS, Windows и Linux. Последние версии ограниченно поддерживают многоэтажные лабиринты. Есть игра вдвоём на одной машине двумя мышами (для второй, подключаемой по COM-порту, в игре есть встроенный драйвер). Многое что взято из ныне замороженного Smack My Marine Up. Согласно описанию проекта, в нём ставится задача максимально глубокой обратной совместимости всех нововведений, то есть возможности возвращения к оригиналу путём выбора соответствующих настроек.
 ZDoom — в отличие от большинства расширений Doom, которые написаны на чистом Си, игра полностью переписана на C++. Фокусируется на мультиплеерных возможностях, реализован даже захват флага. В проекте не ставится цель глубокой обратной совместимости, опытный игрок ощущает значительную разницу с оригиналом в геймплее буквально сразу же, но зато многие баги, использовавшиеся авторами модификаций как источники недокументированных эффектов, можно включить при необходимости из меню. Более не разрабатывается, был поглощён GZDoom.
 ZDaemon — порт для сетевой игры. В настоящее время теряет популярность, уступая более продвинутому порту Skulltag. Основан, в свою очередь, на порте ZDoom.
 GZDoom — порт, основанный на ZDoom. Поддержка OpenGL, 3D-полов, динамического освещения, расширенных возможностей по редактированию уже имеющихся объектов и созданию новых, поддержка 3D-моделей.
 SkullTag — порт для сетевой игры. Отличается более качественным сетевым кодом и расширенными возможностями. Основан на портах ZDoom и GZDoom. Поддерживает OpenGL.
 jDOOM — переводит Doom на трёхмерный движок: графика под управлением OpenGL, трёхмерные модели монстров, оружия и предметов, присутствуют эффекты освещения и обзор мышью вверх-вниз, не приводящий к «эффекту Ельцина» или «эффекту портрета». Одним словом, jDOOM преображает старый 2,5-мерный Doom, визуально превращая его в 3D-игру. Тем не менее, jDOOM нельзя назвать полноценной 3D-игрой — он не поддерживает 3D-полы и наклонные плоскости. Возможности маппинга и моддинга также слабы, на уровне обычного DOOM, то есть значительно уступают остальным портам. Один из главных недостатков jDOOM на настоящий момент — низкое качество любительских полигональных моделей.
 Risen3D — порт, основанный на jDOOM. Поддерживает все графические навороты jDOOM, по утверждениям разработчиков, применены улучшенные алгоритмы OpenGL-рендеринга, быстрее и качественнее отображаются текстуры высокого разрешения и трёхмерные модели. Также поддерживаются наклонные поверхности и 3D-полы. Кроме этого разработчиками этого порта была нарушена лицензия GNU GPL в связи с закрытием исходных текстов. Эта проблема в далёком последствии была урегулирована с разработчиками jDOOM.

В Doom Legacy, ZDoom и SkullTag присутствует возможность игры с ботами.

Менее значимые модификации кратко перечислены в списке портированных версий игр серии Doom.

Файлы данных Doom по сей день остаются платными. Для создания полностью свободного IWAD-файла был начат проект FreeDoom.

Примечания 

Свободные игровые движки
Игровые движки разработки id Software