Doom engine («движок Doom»), также известный как id Tech 1 — псевдотрёхмерный игровой движок, разработанный американской компанией id Software и применяемый в компьютерных играх Doom, Heretic, HeXen, Strife, HacX и других играх, созданных по лицензии. Создан Джоном Кармаком, вспомогательные функции были написаны Майклом Абрашем (), Джоном Ромеро (), Дэйвом Тэйлором () и Полом Райдеком (). Первоначально написан на компьютерах NeXT, для первого релиза Doom был портирован под DOS, а позднее ещё на несколько игровых консолей и операционных систем.
Отличия от Wolfenstein 3D engine Пол и потолок могут иметь любую высоту. Стены не обязательно должны быть ориентированы строго в направлении «север-юг» или «запад-восток». Изменяющаяся освещённость, повышающая реалистичность графики. Лифты, дистанционно открывающиеся двери, опускающиеся потолки, которые могут раздавить игрока, поднимающиеся ступеньки и другие движущиеся элементы. Персонажи могут прыгать, падать с крыш и летать по воздуху (впрочем, пройти под летящим врагом или пролететь сверху в прыжке всё равно невозможно). Звуковая подсистема поддерживала стереозвук и микширование до 8 эффектов одновременно. Персонаж при движении покачивался вверх-вниз, что создало более релистичную иллюзию ходьбы (в Wolfenstein точка обзора находилась на постоянной высоте примерно на уровне живота, игрок словно ехал в инвалидной коляске). На уровне расставлялись объекты (). При этом набор характеристик объекта в Doom оказался довольно беден: например, не было Z-координаты, наземный объект в начале игры всегда стоял на полу, а воздушный — висел под потолком. Нельзя сделать, чтобы объект был только в одиночной игре, или только в deathmatch, или только в кооперативной (был лишь флаг «только в сетевых играх»). Разрешалось (хоть и не поощрялось) подключение дополнительных модулей (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). Этот же тег присваивается сектору-лифту. При активации отрезок будет выполнять указанное действие на всех секторах с этим тегом.
Игра Все вычисления проводятся с частотой 35 тактов в секунду, в фиксированной запятой 16,16, с машинной единицей, равной одному текселюИсходные тексты Doom или первых его портов (например, Doom Legacy 1.11, 1.12).
Запись демо-роликов и сетевая игра основаны на том, что на цифровой ЭВМ один и тот же код с одними и теми же данными приводит к одному и тому же результату, а поведение целочисленной арифметики жёстко заспецифицировано и не зависит от модели процессора. Игра записывает в демо-ролик (и передаёт по сети) команды управления; если в игре нет грубых ошибок, различные машины, интерпретируя одни и те же команды управления, получают один и тот же результат. Впрочем, ошибки, приводящие к рассинхронизации, в игре всё-таки есть: в частности, если в одиночной игре зайти в меню, игра останавливается, но ролик продолжает писаться.
Каждый игровой такт (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. При этом величина разрешения была закодирована в ассемблерных процедурах в двух местах; версии игры, которые использовали переменное разрешение, либо имели несколько функций под разные разрешенияИсходный текст Smack My Marine Up, либо динамически модифицировали код, подставляя нужное разрешениеИсходный текст любой версии Doom Legacy для DOS, функция ASM_PatchRowBytes.. Впрочем, в частях игры, которые к движку не относятся, встречалось крайне много магических чисел, связанных с разрешением экрана и экранными координатами различных объектов, поэтому первые порты Doom страдали «расползающейся» в SVGA-режимах графикой менюНапример, Doom Legacy 1.11, 1.12.
Длительная загрузка Doom известен своей длительной загрузкой (больше минуты на компьютерах своего времени). Основная часть времени тратилась на инициализацию «демона перерисовки Doom» ().
Doom распространялся на дискетах и через BBS, важен был каждый байт. Чтобы уменьшить размер, сделали такой механизм. Каждая из текстур для стен состояла из фрагментов (): например, стена с выключателем может состоять из картинки стены и картинки выключателя, или плиточная стена — из трёх-четырёх плиток, хаотически разбросанных по большой текстуре. Текстуры, как сказано выше, рисуются по столбцам. Doom проходился по всем столбцам всех текстур и проверял, какие фрагменты покрывают тот или иной столбец; строилась соответствующая структура данных. Эту структуру можно было закэшировать, или строить при загрузке уровня, достраивая динамически по мере надобности — в этом случае Doom загружался бы намного быстрееТак поступают многие порты Doom — в частности, Doom Legacy и Smack My Marine Up; исходные тексты того и другого свободно доступны..
Кроме того, Doom имел специализированный метод кэширования данных под названием «зонная память». Инструкция советовала отключить дисковые кэши наподобие SmartDrive — в Doom есть более эффективный кэш.
Сетевой код