Doom engine

id Tech 1
Тип	Игровой движок (Список)
Разработчик	id Software
Ключевой программист	Джон Кармак
Часть серии движков	id Tech
Предыдущий движок серии	Wolfenstein 3D engine
Следующий движок серии	Quake engine
Аппаратные платформы	ПК, Macintosh, Amiga, SNES, Sega 32X, Sega Saturn, 3DO, PlayStation, Game Boy Advance, Atari Jaguar и другие
Поддерживаемые ОС	DOS, Linux, FreeBSD, другие UNIX-подобные
Написан на языке	Си, язык ассемблера
Лицензия	до 1997 года — Коммерческое ПО после 1997 года — Свободное ПО: лицензия GNU GPL
Первая игра на движке	Doom / 10 декабря 1993 года
Последняя игра на движке	Strife / 31 мая 1996 года

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

Отличия от Wolfenstein 3D engine

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

Ограничения

• Лабиринт имеет горизонтальный пол с потолком и вертикальные стены.
• Две комнаты не могут находиться одна над другой. Таким образом, карта уровня является совершенно двумерной.
• Во всей игре масштаб спрайтов и текстур постоянный. Поэтому, например, невозможно установить высокодетализированный плакат на менее детальной стене.
• Авторы так и не проработали вертикальные столкновения объектов. Поэтому нельзя, например, пробежать под летящим какодемоном или, разогнавшись на какой-нибудь крыше, перепрыгнуть через факел. (Исправлено в Heretic и Hexen, так как в них это было необходимо из-за подбираемой магической возможности полёта игрока.)
• Игра не делала и других проверок по оси Z — например, рыскающий в подвале имп вполне мог нанести повреждения игроку, находящемуся в паре сотен метров выше, на чердаке, а взорвавшаяся у основания здания ракета наносила урон монстру на крыше. Игрок мог использовать переключатели вне зависимости от высоты (например, всё ещё можно активировать ушедший под землю выключатель на уровне MAP01 Entryway в Doom 2).
• Особая структура уровня (так называемое двоичное разбиение пространства) требовала сборки перед испытанием уровня. Сборка происходит автоматически, на компьютерах того времени менее чем за минуту — тем не менее, это мешало просматривать уровень в реальном времени прямо по ходу редактирования (в отличие от Build Engine). К тому же двоичное разбиение делило стены на «отрезки» (англ. segs) — это усложняло геометрию уровня. Duke Nukem 3D версии 1.3 успешно работал на компьютерах класса Pentium-100 на разрешении 640×480 — ни один порт Doom не способен на такое.
• Из-за этого крайне ограничено горизонтальное движение геометрии уровня (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-построителем.

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

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

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

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

Игра

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

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

В режиме записи демо-роликов точность поворотов снижалась до 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» (англ. Init Doom refresh daemon).

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

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

Сетевой код

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

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

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

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

Список игр, использующих Doom engine

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

Название игры	Дата выхода	Разработчик/и	Платформы
Doom	1993	id Software	MS-DOS, Windows, Mac OS, Linux, Acorn Archimedes, SNES, Sega 32X, Sega Saturn, 3DO, PlayStation, Game Boy Advance, Atari Jaguar, Xbox, Xbox 360, PlayStation 3, iOS, Android
Doom II: Hell on Earth	1994	id Software	MS-DOS, Windows, Mac OS, Game Boy Advance, Sega Saturn, Tapwave Zodiac, PlayStation, Xbox 360, PlayStation 3, Android
Heretic	1994	Raven Software	PC, PSX,Mac OS, Amiga, GNU/Linux
Hexen	1995	Raven Software	MS-DOS, Mac OS, Linux, PlayStation, Nintendo 64, Sega Saturn
Final Doom	1996	id Software, Team TNT, братья Касали	MS-DOS, PlayStation, PlayStation 3, Mac OS
Strife	1996	Rogue Entertainment	MS-DOS, Microsoft Windows, Linux, macOS
Chex Quest	1996	Digital Café	MS-DOS, Microsoft Windows
Chex Quest 2: Flemoids Take Chextropolis	1997	Digital Café	MS-DOS, Microsoft Windows
Doom 64	1997	Midway Games	Nintendo 64
Hacx: Twitch 'n Kill	1997	Banjo Software	MS-DOS, Microsoft Windows
Cruis'n Velocity	2001	Graphic State	Game Boy Advance
Dark Arena	2002	Graphic State	Game Boy Advance

Также фанатами игры создавались пользовательские модификации, которые полностью преображали игру. Первая из них — 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.