Doom engine

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

id Tech 1
Рушій гри (Список)
Частина серії рушіїв	id Tech
Попередній рушій серії	Wolfenstein 3D engine
Наступний рушій серії	Quake Engine
Ліцензія	до 1997 року — Комерційне ПЗ з 1997 року — Вільне ПЗ: ліцензія GNU GPL
Перша гра на рушію	Doom / 10.12.1993
Остання гра на рушію	Strife / 31.05.1996

Відмінності від 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 не здатний на таке. Через це рух об'єктів можливий, але по горизонтальній площині рух обмежено, на відміну від Build Engine.
• Висота текстури, якщо та повторюється по вертикалі, повинна завжди дорівнювати 128 текселям. Для неповторюваних текстур (щаблів, ґрат і т. д.) це не потрібно. Виправлено в численних портах Doom.
• Перегляд вгору-вниз, реалізований в Heretic, був псевдотривимірним, вертикальні лінії завжди залишалися вертикальними.

Технічні особливості

Рушій був написаний на Сі на робочих станціях NeXT в операційній системі NEXTSTEP. Спочатку використовувався компілятор Intel C, але в подальшому був використаний Watcom C. Утиліти були написані під NeXT на Objective-C. Рушій Doom був прогресивним для свого часу. Незважаючи на те, що Сі — мова процедурного програмування, рушій Doom написаний в явно вираженому об'єктному стилі.

Будова рівнів

Рівень у редакторі

Всі рівні в Doom насправді двовимірні, що вказує на одне з обмежень рушія: неможливо мати кімнату (сектор) над іншою кімнатою. Однак, з іншого боку, це дозволяє без особливих проблем малювати карту рівня з відображенням всіх стін і об'єктів, на відміну від інших ігор цього жанру.

Рівень складається з десяти блоків .WAD-файла; з них п'ять (VERTEXES, LINEDEFS, SIDEDEFS, СЕКТОРІВ і THINGS) безпосередньо редагуються користувачем, ще п'ять (SEGS, SSECTORS, NODES, REJECT і BLOCKMAP) — обчислюються BSP-побудовником.

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

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

Щоб забезпечити найвищу на той час інтерактивність, застосовані так звані теги. Відрізок і сектор мають особливе ціле поле — «тег». Щоб зробити вимикач, який опускає ліфт, відрізку-вимикачу задаються код дії «вимикач, опускає ліфт» і який-небудь тег (наприклад, 5). Цей тег присвоюється сектору-ліфта. При активації відрізок буде виконувати вказану дію на всіх секторах з цим тегом.

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

Гра

Всі обчислення проводяться з нерухомою комою 16,16, з машинною одиницею, що дорівнює одному текселю (зріст гравця 56 текселів — отже, 1 тексель приблизно дорівнює 3 см). Для кутових величин застосовується нерухома кома, в якій 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 — була зроблена за фільмом «Чужий». Згодом з'явилися модифікації й за іншими фільмами: «Мисливці за привидами», «Бетмен» і «Секретні матеріали».

Відкриття сирцевого коду

У 1994 році відкрили тексти сирців мережевих драйверів. Ентузіасти почали розробляти власні драйвери: наприклад, для LPT-кабелю (PARSETUP) і навіть для ланцюжка COM-кабелів (HX8).

У грудні 1997 року повний сирцевий текст Doom для Linux був опублікований під невільною безкоштовною ліцензією (версія для DOS не публікувалася через платну звукову бібліотеку DMX). Вже в січні 1998 року з'явився перший порт цього коду для DOS — DosDoom.

Піонерами розширення 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. Підтримка OpenGL3D-підлог, динамічного освітлення, розширені можливості редагування вже наявних об'єктів і створення нових, підтримка 3D-моделей. Офіційний сайт GZDoom [1] [Архівовано 9 серпня 2019 у Wayback Machine.].
• SkullTag — порт для мережевої гри. Відрізняється більш якісним мережевим кодом і розширеними можливостями. Заснований на портах ZDoom і GZDoom. Підтримує OpenGL.
• jDOOM — переводить Doom на тривимірний рушій: графіка під керуванням OpenGL, тривимірні моделі монстрів, зброї і предметів, присутні ефекти освітлення і огляд миші вгору-вниз, не призводить до «ефекту Єльцина» або «ефекту портрета». Одним словом, jDOOM змінює старий 2,5-вимірний Doom, візуально перетворюючи його в 3D-гру. Проте, jDOOM не можна назвати повноцінною 3D-грою — він не підтримує 3D-підлоги і похилі площини. Можливості мапінгу і моддінгу також слабкі, на рівні звичайного DOOM, тобто значно поступаються іншим портам. Один з головних недоліків jDOOM на поточний момент^[коли?] — низька якість аматорських полігональних моделей.
• Risen3D — порт, заснований на jDOOM. Підтримує всі графічні доповнення jDOOM, за твердженнями розробників (Офіційний сайт [2] [Архівовано 6 серпня 2019 у Wayback Machine.]), застосовані поліпшені алгоритми OpenGL-візуалізації, швидше і якісніше відображаються текстури високої роздільності і тривимірні моделі. Також підтримуються похилі поверхні і 3D-підлоги. Крім цього, розробниками цього порту була порушена ліцензія GNU GPL у зв'язку з закриттям сирцевих текстів. Ця проблема значно пізніше була врегульована з розробниками jDOOM.

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

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

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