Duke Nukem 3D: Atomic Edition

Уйдя с работы в Amazon, я провёл много времени за чтением отличного исходного кода.

Разобравшись невероятно замечательным кодом idSoftware, я принялся за одну из лучших игр всех времён: Duke Nukem 3D и за её движок под названием «Build

«.

Это оказался трудный опыт: сам движок имеет большую важность и высоко ценится за свою скорость, стабильность и потребление памяти, но мой энтузиазм столкнулся с исходным кодом, противоречивым в отношении упорядоченности, соблюдения рекомендаций и комментариев/документации. Читая код, я многое узнал о унаследованном коде и о том, что позволяет программному обеспечению жить долго.

Как обычно, я переработал свои заметки в статью. Надеюсь, она вдохновит вас на чтение исходного кода и совершенствование своих навыков. Хочу поблагодарить Кена Силвермана (Ken Silverman)

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

Происхождение

Duke Nukem 3D — не одна, а две
базы кода:

Движок Build
: обеспечивает рендеринг, работу с сетью, файловой системой и службы кэширования.
Игровой модуль: использует службы Build
для создания игры.

Зачем нужно было такое разделение? Потому что в 1993 году, когда началась разработка, только у немногих людей были навыки и рвение, необходимые для создания хорошего 3D-движка. Когда 3D Realms решила написать игру, которая станет конкурентом Doom
, ей нужно было найти мощную технологию. И в этот момент на сцене появляется Кен Силверман.

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

Силверман напишет новый движок для 3D Realms, но сохранит за собой исходный код.

Он предоставит только двоичную статическую библиотеку (Engine.OBJ) с файлом заголовка Engine.h. Со своей стороны, команда 3D Realms возьмёт на себя работу над игровым модулем (Game.OBJ) и выпустит финальный исполняемый DUKE3D.EXE.

К сожалению, исходный код обеих частей игры не был открыт одновременно:

Исходный код движка был выпущен Кеном Силверманом 20 июня 2000 года.
Исходный код игрового модуля был выпущен 3D Realms 1 апреля 2003 года.

В результате полный исходный код стал доступен только через 7 лет после выпуска игры.
Интересный факт:

название движка «
Build
» было выбрано Кеном Силверманом при создании каталога для нового движка. Он воспользовался тезаурусом, чтобы найти синонимы к слову «Construction».

Сюжетная линия

Дюк Нюкем возвращается в Лос-Анджелес после событий игры Duke Nukem II. Неожиданно по радио поступает сигнал бедствия: город штурмует ранее неизвестный враг — агрессивная инопланетная раса, прибывшая с целью похищения женщин и использования их тел в качестве инкубатора. Космический корабль Дюка сбивается ракетой, но ему удаётся катапультироваться на крышу дома. Он берётся за оружие и начинает бойню, сметая горы пришельцев на пути к их лидерам. Каждый эпизод имеет свою особенность в сюжете.

Эпизод 1: L.A. Meltdown

Пролетая над Лос-Анджелесом, корабль Дюка попадает под огонь пришельцев и оказывается сбит. Дюк катапультируется на крышу городского дома. Он пробирается через кинотеатр (Hollywood Holocaust) и «район красных фонарей» (Red Light District). В стриптиз-баре Дюка ожидает неприятный сюрприз — он оказывается в ловушке инопланетян и попадает в плен. Его перевозят в тюрьму (Death Row), чтобы казнить на электрическом стуле, но Дюк сбегает. Он находит подводную лодку и пытается поплыть на ней, но лодка, проплыв некоторое расстояние, терпит крушение, и Дюк всплывает на территории фабрики по переработке токсичных отходов (Toxic Dump). Пройдя эту зону, Дюк оказывается в ущелье горного района (Abyss). Рядом оказывается огромная приземлившаяся летающая тарелка, и внутри неё Дюк находит и убивает финального босса первого эпизода. После победы Дюк видит на мониторах, что инопланетяне помещают земных женщин в коконы для транспортировки на другую планету. «Nobody steals our chicks… and lives» (рус. Никто не может украсть наших цыпочек… и остаться при этом в живых) — говорит Дюк, и на шаттле отправляется в космос.

Секретный уровень

: в туннеле перед завершением Toxic Dump. Площадка с ракетой (Launch Facility), которую должен уничтожить Дюк.

Эпизод 2: Lunar Apocalypse

Успешно состыковавшись с орбитальным космопортом (Space Port), Дюк понял, что Земля была не первой жертвой пришельцев. Начав зачистку местности, на пассажирской шлюпке герой попадает на заброшенную орбитальную станцию EDF, ставшую инопланетным инкубатором (Incubator). Расправившись со всеми, Дюк отправляется на боевой корабль землян, захваченный пришельцами (Warp Factor). (Корабль по форме сильно напоминает USS Enterprise из сериала Star Trek). На корабле он долетает до инопланетной термоядерной станции (Fusion Station). После её уничтожения Дюк Нюкем попадает на огромную земную космическую станцию на земной орбите (в окнах видна Земля и Луна) (Ocuppied Territory). Её пришельцы превратили в своё гнездо, инопланетные споры и растения опутали половину станции. Уничтожив всех, герой отправился на лунную станцию — Tiberius Station, где зона просто кишела инопланетной гадостью. Пробравшись через неё, Дюк попадает к лунному реактору (Lunar Reactor). Уничтожив реактор, Нюкем отправляется на лунную железнодорожную пересадочную станцию (Dark Side), где на железной дороге попадает в место археологических раскопок. В зоне раскопок Дюк обнаруживает странный монолит (отсылка на роман Артура Кларка «2001: Космическая одиссея

»), коснувшись которого, Дюк оказывается на базе пришельцев (Overlord) где-то на земной орбите. Дюк обнаруживает босса Оверлорда. Перед тем как убить его, Дюк произносит «I’ll rip your head off and shit down your neck» (рус. Я оторву твою башку и насру тебе в глотку; отсылка к Full Metal Jacket), после чего исполняет обещанное. После этого Дюк отключает пушку, бомбящую Землю. В этот момент на дисплее высветился Император, и открыто поиздевался над Дюком. В результате чего Дюк вскипел, и произнёс «Guess again, freakshow, Duke’s coming back to town, and the last thing that’s gonna go thru you mind before you die… is my size 13 boot!» (рус. Знаешь что, урод? Дюк снова берётся за дело, и последнее, что пронесётся в твоей голове перед смертью… будет мой ботинок сорок шестого размера!). Дюк возвращается на Землю…

Секретные уровни

: центральная непрерывно вращающаяся часть Ocuppied Territory, где Дюк должен обезвредить сектора Альфа, Бета, Гамма и Дельта, и местечко Lunatic Fringe на уровне Dark Side.

Эпизод 3: Shrapnel City

Дюк Нюкем снова оказывается на Земле на крыше здания. Пройдя через японский суши-ресторан (Raw Meat) и банковский район (Bank Roll), он попал в затопленную часть Лос-Анджелеса (Flood Zone; возможно, пришельцы разрушили дамбу). После этого, попав обратно в незатопленную часть города (L.A. Rumble), Дюк встречается с некоторыми оставшимися в живых людьми, которые согласились добросить вертолётом Дюка до стадиона. Но вертолёт подбивают (как всегда), и герой спрыгивает на киносъёмочную студию (Movie Set). Пройдя метро (Rabid Transit), пожарный участок, радиостанцию (Fahrenheit) и отель (Hotel Hell), герой попадает на стадион, где его поджидает инопланетный император Cycloid. Успешно уничтожив его, Дюк наконец-то получает свой заслуженный отпуск.

Секретные уровни:

на уровне Movie Set на съёмочной площадке, где космические декорации, можно нажать на вертикальную табличку с красными буквами, и справа откроется секретная дверь; в Hotel Hell через небольшой водопад у бассейна, на втором этаже гостиницы, можно пройти в секретный уровень городского района.

Эпизод 4: The Birth

(Этот эпизод есть только в издании Duke Nukem 3D: Atomic Edition

)

Дюка вызывает из отпуска генерал армии США. Он говорит, что пришельцы вернулись и показывает ему видео, где пришельцы проводят биологические эксперименты над женщиной. Дюк отправляется на борьбу с ними. Сначала он попадает на горную базу Improbable Mission Facility. Потом оттуда попадает в город, где проходит через забегаловку Duke-Burger (в честь Дюка), в которой, как оказывается, гамбургеры делаются из собак, потом большой супермаркет. Оттуда по канализации он добирается до Babe Land — аналога Диснейленда, потом разбирается с мутировавшими в свинокопов полицейскими Лос-Анджелеса в полицейском участке, проходит через Центральный Почтамт и попадает на порностудию. Оттуда, по пути пройдя через атомную электростанцию, он попадает на большой пришвартованный морской корабль. От корабля ведёт труба куда-то через морское дно, и через неё Дюк попадает на подводную базу инопланетян. Там он наконец побеждает инопланетную Королеву.

Секретный уровень

: В финале уровня Pigsty за портретом Вашингтона находится кабинет Судьи Дредда. Так из полицейского участка можно попасть в «Зону 51», где помимо прохода по уровню, Дюк должен с помощью кода запустить две ракеты типа «Атлас».

Первый контакт

Поскольку исходный код выпущен давным-давно (он был предназначен для компилятора Watcom C/C++ и систем DOS), я попытался найти что-то похожее на Chocolate doom: порт, точно воспроизводящий игровой процесс Duke Nukem 3D, таким, каким он был в 90-х, и беспроблемно компилирующийся на современных системах.
Выяснилось, что сообщество исходного кода Duke Nukem уже не слишком активно: многие порты снова устарели, некоторые созданы для MacOS 9 PowerPC. До сих пор поддерживается только один (EDuke32), но он слишком сильно эволюционировал по сравнению с оригинальным кодом.

В результате я начал работать с xDuke, хотя он и не компилировался на Linux и Mac OS X (что исключило использование XCode: отличного IDE для чтения кода и профайлинга).

xDuke, сделанный на Visual Studio, точно воспроизводит оригинальный код. Он содержит два проекта: Engine и Game. Проект «Engine» компилируется в статическую библиотеку (Engine.lib), а проект «Game» (содержащий метод main) связывается с ним для генерирования duke3D.exe.

При открытии VS исходники движка выглядят довольно неприветливо из-за сложных имён файлов (a.c, cache1d.c). Файлы эти содержат нечто враждебное глазу и мозгу. Вот один из множества примеров в файле Engine.c (строка 693):

if ((globalorientation&0x10) > 0) globalx1 = -globalx1, globaly1 = -globaly1, globalxpanning = -globalxpanning; if ((globalorientation&0x20) > 0) globalx2 = -globalx2, globaly2 = -globaly2, globalypanning = -globalypanning; globalx1 <<= globalxshift; globaly1 <<= globalxshift; globalx2 <<= globalyshift; globaly2 <<= globalyshift; globalxpanning <<= globalxshift; globalypanning <<= globalyshift; globalxpanning += (((long)sec->ceilingxpanning)<<24); globalypanning += (((long)sec->ceilingypanning)<<24); globaly1 = (-globalx1-globaly1)*halfxdimen; globalx2 = (globalx2-globaly2)*halfxdimen;
Примечание:
если имя файла/переменной содержит цифру, то это, вполне возможно, не очень хорошее имя!
Интересный факт:
последняя часть кода game.c содержит черновик сценария Duke V!
Примечание:
порт xDuke использует SDL, но преимущество кроссплатформенного API утеряно из-за таймеров WIN32 (QueryPerformanceFrequency). Похоже, что использованный SDL Timer слишком неточен для эмуляции частоты 120 Гц в DOS.

Настоящее игры[править | править код]

Содержимое этого раздела нуждается в чистке.

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

При запуске игры на современных компьютерах возникают трудности из-за того, что она создавалась под DOS, поэтому на других системах могут возникнуть проблемы с изображением, звуком и скоростью работы.

Чтобы решить подобные проблемы, энтузиастами создаются так называемые 3D- или GL-порты игры, то есть программы, написанные с использованием исходного кода игры, открытого разработчиками в 2003 г., запускающие рендеринг или обработку текстур под аппаратными средствами (Direct3D или OpenGL). В итоге получаются запредельные для старых игр разрешения, вроде 1600 на 1200 точек, добавление красочных эффектов в виде освещения, текстурирования, шейдеров и других возможностей современных графических карт.

Первым известным примером подобной технологии для Duke Nukem 3D был JonoF’s Duke Nukem 3D Port — качественный порт игры, разработанный в 2005 г. на основе усовершенствованного движка Build. Поддерживает запуск под OpenGL в разрешении вплоть до 1280 на 1024 точек, позволяет запускать игру под Windows XP, решает проблемы со звуком. Благодаря поддержке 3D-моделей из Quake III и текстур высоких разрешений игру можно преобразить кардинально. Для этого создан и постоянно обновляется Duke Nukem 3D high resolution pack, при использовании которого игра становится по визуальному исполнению на уровне Quake 3. Порт работает на всех версиях игры. Однако он давно не обновлялся (последняя доступная версия датирована 9 октября 2005 г.). Поэтому на его основе появился порт EDuke32, развившийся из eDuke — версии Duke Nukem с усиленными возможностями по модификации игры. Он совмещает в себе все возможности JonoF порта и добавляет новые, например, поддержку аудиоформата Ogg Vorbis, позволяющему заменить старые музыкальные файлы формата MIDI на полноценные композиции с высоким качеством, благодаря чему игра будет ещё и звучать по-новому. Плюс ко всему этому идёт ещё одна версия редактора Build для Windows — Mapster32. Порт работает только с версией игры 1.4 (Atomic Edition).

Помимо реализации под Windows, существует порт под Mac OS X, позволяющий установить как демоверсию, так и обе коммерческих реализации (для их установки потребуется CD).

Хотя движок игры открыт для модификации, файлы данных (за исключением shareware-версии L.A. Meltdown

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

Погружение в процесс

Теперь игра работает. За несколько секунд Build
предстаёт во всё своём блеске, демонстрируя:

Наклонные потолки
Реалистичное окружение
Возможность свободного падения
Ощущение истинного 3D.

Последний пункт, наверно, больше всего повлиял на игроков в 1996 году. Уровень погружения был непревзойдённым. Даже когда технология достигла своего предела из-за двухмерных карт, Тодд Реплогл (Todd Replogle) и Аллен Блум (Allen Blum) реализовали «эффекторы секторов» позволявшие телепортировать игрока и усиливавшие ощущение погружения в трёхмерный мир. Эта функция используется в легендарной карте «L.A Meltdown»:
Когда игрок запрыгивает в вентиляционную шахту:

Срабатывают эффекторы секторов и перед «приземлением» телепортируют игрока совершенно в другое место карты:

Хорошие игры медленно стареют, и Duke Nukem не стала исключением: двадцать лет спустя в неё всё ещё невероятно интересно играть. А теперь мы ещё и можем изучить её исходники!

Версии игры

Наиболее распространёнными версиями Duke Nukem 3D являются:

Lameduke — бета-версия игры. Получила популярность среди фанатов оригинала в связи с тем, что в значительной степени отличается от финальной версии игры — внешний вид большинства противников, а также оружия отличается от конечного, в игре присутствуют отличные от оригинальных локации (однако, уровень Derelict из Lameduke вошёл в Atomic Edition).
Shareware — содержит один из трёх эпизодов, доступных в полной версии игры и имеет ограниченный набор вооружений (нет наиболее оригинальных и замысловатых орудий, вроде замораживателя или уменьшителя). Несмотря на ознакомительный статус, стоит отметить, что доступный эпизод «L.A. Meltdown» является одним из самых запоминающихся по архитектуре и построению уровней. Многие игроки начинали знакомство с «Duke Nukem 3D» именно с shareware версии.
1.3d — полная версия игры. Содержит 3 эпизода: «L.A. Meltdown», «Lunar Apocalypse» и «Shrapnel City» и предлагает полный набор вооружений.
Atomic Edition — расширенная версия игры, которая содержит дополнительный четвёртый эпизод «The Birth», дополнительное оружие (увеличитель) и новых врагов: существ, похожих на монстров из фильмов серии Чужой, свинокопов в танках и главного босса. Также в игре имелась возможность подключения ботов через параметры командной строки. Отличительной особенностью эпизода стал дизайн уровней и атмосфера — парки развлечений, большое количество декоративных роботов, которые внешне выглядят как люди.
Total Meltdown — версия для Sony Playstation, включает в себя три оригинальных эпизода и новый, «Plug N’ Pray», состоящий из шести новых уровней. В новый эпизод были включены новые враги: две разновидности свинокопов и новый босс по имени CyberKeef. Дизайн некоторых уровней Plug N’ Pray заметно хуже, чем в оригинале, но сами уровни стали сложнее.
Duke Nukem 64 — версия для Nintendo 64. В игре заново перерисованы большинство текстур, изменены многие спрайты оружия и врагов. Сами уровни теперь не разбиты по эпизодам, а предстают одной сплошной кампанией. Среди любопытных нововведений: наличие ослабленных версий второго босса Overlord (по аналогии с первым боссом), четвёртый босс (Alien Queen) встречается раньше третьего — Cycloid Emperor, который в этой версии предстает в виде 3D-модели. К тому же эту версию можно проходить сразу 2 игроками.

Кроме этого, к игре сторонними компаниями, энтузиастами и просто фанатами создано несколько модификаций:

«Nuclear Winter» — игра вышла в канун Рождественских праздников и обладает соответствующей «спецификой», вроде рождественских нарядов на врагах, злых снеговиков и злых эльфов в качестве противников, и порабощенного пришельцами Санта-Клауса в качестве главного злодея.
«Duke it out in D.C.» — модификация, в которой предстоит побывать в округе Колумбия и спасти президента от злобных инопланетных захватчиков. Действие происходит и в Белом доме, и в подвалах Пентагона, и даже в здании ФБР.
«Caribbean — Life’s a Beach» — Дюк Нюкем в отпуске. Летняя тематика, новые уровни, новые звуки, новое оружие и предметы (водяной пистолет, ананасовые бомбы, бананы вместо аптечек и т. п.).
«Sonic the Hedgehog 3D» — фанатская игра про Соника на движке Build. Над данной игрой работа ещё не закончена, но демоверсия уже имеется.
«Starship Troopers» — фанатская игра по вселенной фильма «Звёздный Десант».

Обзор библиотеки движка

Код движка находится в одном файле из 8503 строк и с 10 основными функциями (Engine.c) и в двух дополнительных файлах:

cache1.c: содержит виртуальную файловую систему (sic!) и процедуры системы кэширования.
a.c: реализация на C воссозданного обратной разработкой кода, который был высокооптимизированным x86-ассемблером. Код работает, но читать его — огромная мука!

Три модуля трансляции и несколько функций составляют высокоуровневую архитектуру, которую сложно понять. К сожалению, это не единственные сложности, с которыми придётся столкнуться читателю.
Внутренностям движка Build

я посвятил целый раздел (см. ниже).

Обзор игрового модуля

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

(отрисовка, загрузка ресурсов, файловая система, система кэширования и т.д.). Единственное исключение — звуки и музыка, они полностью относятся к
Game
.

Поскольку меня больше интересовал движок, особо я здесь не разбирался. Но в этом модуле видно больше опыта и организации: 15 файлов делят исходный код на понятные модули. В нём даже есть types.h (инициатор stdint.h) для улучшения портируемости.

Пара интересных моментов:

game.c — это монстр из 11 026 строк кода.
В menu.c есть 3000 строк со «switch case».
Большинство методов имеют параметры «void» и возвращают «void». Всё выполняется через глобальные переменные.
В наименованиях методов не используется camelCase или префикс NAMESPACE.
В модуле есть хороший парсер/лексический анализатор, хотя и значения токенов
передаются через десятичные значения вместо #define.

В целом эту часть кода легко читать и понимать.

Унаследованный исходный код

Глядя на бесконечное количество портов, порождённых Doom/Quake, я всегда удивлялся, почему так мало портов Duke Nukem 3D. Тот же вопрос возник, когда движок был портирован под OpenGL только после того, как Кен Силверман решил заняться этим самостоятельно.
Теперь, когда я посмотрел на код, рискну объяснить это во второй части этой статьи

Chocolate Duke Nukem 3D

Я обожаю этот движок и люблю игру, поэтому не мог оставить всё как есть: я создал Chocolate Duke Nukem 3D, порт «ванильного» исходного кода, пытаясь достичь таким образом двух целей:

Обучение: простота чтения/понимания и удобство портирования.
Достоверность: игровой процесс должен быть похожим на тот, который мы видели в 1996 году на наших 486-х.

Надеюсь, эта инициатива поможет унаследовать код. Самые важные модификации будут описаны во второй части статьи. Build
использовался в Duke Nukem 3D и многих других успешных играх, таких как Shadow Warrior и Blood. В момент выпуска 29 января 1996 года он уничтожил движок
Doom
инновационными возможностями:

Разрушаемым окружением
Наклонными полами и потолками
Зеркалами
Возможностью смотреть вверх и вниз
Способностью летать, ползать и плавать под водой
(появились позже в «Blood»)
Настоящим погружением в 3D (благодаря телепортам).

Корону у него отнял в июне 1996 года Quake, запущенный на мощных «Пентиумах»… но в течение нескольких лет Build
обеспечивал высокое качество, свободу дизайнеров и, что важнее всего, хорошую скорость на большинстве компьютеров того времени.

Duke Nukem (1991)

«Дюк Нюкем» 1991 года был в пиксельной расцветке. Шёл он на старенькой операционной системе MS-DOS. По сюжету, в далёком будущем зловещий доктор Протон решается на захват всего мира. Для этого он создал приспешников – Технороботов. В этом апокалиптическом безумии Дюку Нюкему приходит контракт от правительства. Ему придётся избавить мир от зла и стать сильнейшим.

Важнейшая концепция: система порталов

Большинство 3D-движков разделяло игровые карты с помощью двоичного разбиения пространства (Binary Space Partition) или октодерева (Octree). Doom, например, предварительно обрабатывал каждую карту затратным по времени методом (до 30 минут), в результате чего получалось BSP-дерево, позволявшее:

Сортировать стены
Определять положение
Обнаруживать столкновения.

Но в угоду скорости приходилось идти на уступки: стены не могли передвигаться
.
Build
снял это ограничение, он не обрабатывал предварительно карты, а вместо этого использовал
систему порталов
:

На этой карте гейм-дизайнер нарисовал 5 секторов (сверху) и соединил их вместе, пометив стены как порталы (снизу).

В результате база данных мира Build

стала до смешного простой: один массив для секторов и один массив для стен.
Секторы (5 записей): Стены (29 записей) : ============================ ========================================== 0| startWall: 0 numWalls: 6 0| Point=[x,y], nextsector = -1 // Стена в секторе 0 1| startWall: 6 numWalls: 8 ..| // Стена в секторе 0 2| startWall: 14 numWalls: 4 ..| // Стена в секторе 0 3| startWall: 18 numWalls: 3 3| Point=[x,y], nextsector = 1 // Портал из сектора 0 в сектор 1 4| startWall: 21 numWalls: 8 ..| // Стена для сектора 0 ============================ ..| // Стена для сектора 0 ..| Первая стена сектора 1 >> 6| Point=[x,y], nextsector = -1 7| Point=[x,y], nextsector = -1 8| Point=[x,y], nextsector = -1 9| Point=[x,y], nextsector = 2 //Портал из сектора 1 в сектор 2 10| Point=[x,y], nextsector = -1 11| Point=[x,y], nextsector = 0 //Портал из сектора 1 в сектор 0 12| Point=[x,y], nextsector = -1 Последняя стена сектора 1 >> 13| Point=[x,y], nextsector = -1 ..| 28| Point=[x,y], nextsector = -1 =========================================== Ещё одно заблуждение относительно Build
— он не выполняет испускание лучей: вершины сначала проецируются в пространство игрока, а затем генерируется столбец/расстояние из точки обзора.

Обзор рабочего цикла

Высокоуровневое описание процесса рендеринга кадра:

Игровой модуль
передаёт
модулю движка
сектор, с которого должен начаться рендеринг (обычно это сектор игрока, но может быть и сектор с зеркалом).
Модуль движка
обходит систему порталов и посещает
интересующие
секторы. В каждом посещённом секторе:
Определяются спрайты, которые видимы в этом секторе, и сохраняются в стек.
Группы обрабатываются в порядке от ближних к далёким: рендерятся сплошные стены и порталы.
Рендеринг останавливается: ожидание, пока игровой модуль
обновляет видимые спрайты.
Рендерятся все спрайты и прозрачные стены в порядке от далёких к ближним.
Переключаются буферы.

Вот каждый из этапов в коде: // 1. При каждом перемещении игрока его текущий сектор должен быть обновлён. updatesector(int x, int y, int* lastKnownSectorID) displayrooms() { // Рендеринг сплошных стен, потолков и полов. Заполнение списка видимых спрайтов (они при этом НЕ рендерятся). drawrooms(int startingSectorID) { // Очистка переменной «gotsector», битового массива «visited sectors». clearbufbyte(&gotsector[0],(long)((numsectors+7)>>3),0L); // Сброс массивов umost и dmost (массивы отслеживания отсечения). // 2. Посещение секторов и порталов: построение списка групп («bunch»). scansector(startingSectorID) { // Посещение всех соединённых секторов и заполнение массива BUNCH. // Определение видимых спрайтов и сохранение ссылок на них в tsprite, spritesortcnt++ } //На этом этапе уже назначен numbunches и сгенерирован bunches. // Итерация стека групп. Это операция (O)n*n, потому что каждый раз алгоритм ищет ближайшую группу. while ((numbunches > 0) && (numhits > 0)) { //Поиск ближайшей группы методом (o) n*n for(i=1;i>numbunches;i++) { //Здесь неудобочитаемый код bunchfront test } //ОТРИСОВКА группы стен, определяемых по bunchID (closest) drawalls(closest); } } // 3. Остановка рендеринга и выполнение игрового модуля, чтобы он мог обновить ТОЛЬКО видимые спрайты. animatesprites() // 4. Рендеринг частично прозрачных стен, таких как решётки и окна, и видимых спрайтов (игроков, предметов). drawmasks() { while ((spritesortcnt > 0) && (maskwallcnt > 0)) { drawsprite or drawmaskwall } } } // Код игрового модуля. Отрисовка 2D-элементов (интерфейс, рука с оружием) displayrest(); // 5. Переключение буферов nextpage() Интересный факт:
если вы изучаете код, то есть полностью развёрнутый цикл, который я использовал в качестве карты.

Интересный факт:

почему метод переключения буферов называется nextpage()? В 90-х радость программирования для VGA/VESA включала в себя реализацию двойной буферизации: две части видеопамяти выделялись и использовались по очереди. Каждая часть называлась «страницей» («page»). Одна часть использовалась модулем VGA CRT, а вторая обновлялась движком. Переключение буферов заключалось в использовании CRT следующей страницы («next page») заменой базового адреса. Гораздо подробнее можно почитать об этом в Главе 23 книги Майкла Абраша «Black Book of Graphic Programming: Bones and sinew».

Сегодня SDL упрощает эту работу простым флагом видеорежима SDL_DOUBLEBUF, но имя метода осталось как артефакт прошлого.

С чего начинать рендеринг?

Отсутствие BSP означает, что невозможно взять точку p(x,y) и пройти по узлам дерева, пока не достигнем сектора листа. В Build
текущий сектор игрока нужно отслеживать после каждого обновления положения с помощью updatesector(int newX, int newY, int* lastKnownSectorID).
Игровой модуль
вызывает этот метод
модуля движка
очень часто.

Наивная реализация updatesector сканировала бы линейно каждый сектор и каждый раз проверяла, находится ли p(x,y) внутри

сектора S. Но updatesector оптимизирована поведенческим шаблоном:

Записывая lastKnownSectorID, алгоритм полагает, что игрок переместился не очень далеко и начинает проверку с сектора lastKnownSectorID.
Если пункт 1 выполнить не удалось, алгоритм проверяет с помощью порталов соседние lastKnownSectorID секторы.
И, наконец, в наихудшем сценарии он проверяет все сектора линейным поиском.

На карте слева последним известным сектором положения игрока был сектор с идентификатором 1: в зависимости от расстояния, на которое переместился игрок, updatesector выполняет проверку в следующем порядке:

inside(x,y,1) (игрок переместился не так далеко, чтобы покинуть сектор).
inside(x,y,0) (игрок слегка переместился в соседний сектор). inside(x,y,2)
inside(x,y,0) (игрок сильно переместился: потенциально необходима проверка всех секторов игры). inside(x,y,1) inside(x,y,2) inside(x,y,3) inside(x,y,4)

Наихудший сценарий может быть довольно затратным. Но бóльшую часть времени игрок/снаряды перемещаются не очень далеко, и скорость игры остаётся высокой.

Технические детали

Графический движок игры называется Build Engine. На его основе было создано ещё несколько известных игр: Shadow Warrior, Blood, Redneck Rampage. Игровой движок давал следующие возможности: достаточно реалистичный и интерактивный трёхмерный мир, в котором стало возможным прыгать и приседать, появилась квази-возможность двигаться в трёх измерениях, появилась возможность частично взаимодействовать с игровыми предметами. Враги, в отличие от полигонального Quake, всё ещё представлялись в виде плоских спрайтов.

Комнаты изображались с помощью технологии порталов (в отличие от BSP-дерева в Doom). Благодаря порталам, общая скорость игры зависела только

от сложности пространства, окружающего игрока. И, в придачу, для отображения уровня не требовалось никаких предварительных вычислений, так что можно было видеть уровень в 3D прямо по ходу редактирования. Однако Build Engine всё ещё оставался 2,5-мерным движком, к тому же, при взгляде игрока вверх объекты сильно искажались: возникал эффект параллакса.

Странный, жуткого вида зелёный слизняк (protozoid slimer), наползающий на лицо, при попытке удаления монстра из игры обнаруживается встроенным в движок Build полной версии игры, то есть кода Протозоида, как такового, в *.CON файлах не обнаружено, в то время как спрайты и звуки монстра находятся в основном (*.GRP) файле игры.

В игре используются некоторые «недокументированные» особенности движка и расширенные возможности порталов. Например, секретный уровень Tier Drops представляет собой большую комнату, содержимое которой меняется в зависимости от того, с какой стороны в неё зайти. С помощью модификации файлов с параметрами игры можно включить несколько неиспользуемых возможностей в игре — например, уничтожаемые камеры наблюдения или невидимые лазерные сенсоры мин. Эти же файлы могут быть использованы для создания простых модификаций на основе игры.

Эпоха вычислений с фиксированной запятой и вездесущие векторные произведения

Поскольку в большинстве компьютеров 90-х не было сопроцессора для чисел с плавающей точкой (FPU) (386SX, 386DX и 486SX), в Build
использовались только целые числа.

В примере показана стена с конечными точками A и B: задача заключается в том, чтобы определить, находится точка слева или справа.

В Главе 61 книги Майкла Абраша «Black Book of Programming: Frame of Reference» эта задача решается простым скалярным произведением и сравнением.

bool inFrontOfWall(float plan[4], float point[3]) { float dot = dotProduct(plan,point); return dot < plan[3]; }

Но в мире без операций с плавающей запятой задача решается векторным произведением.

bool inFrontOfWall(int wall[2][2], int point[2]) { int pointVector[2], wallVector[2] ; pointVector[0] = point[0] — wall[0][0]; //Синий вектор pointVector[1] = point[1] — wall[0][1]; wallVector[0] = wall[1][0] — wall[0][0]; //Красный вектор wallVector[1] = wall[1][1] — wall[0][1]; // Скалярное произведение crossProduct вычисляет только компоненту Z: нам нужен только знак Z. return 0 < crossProduct(wallVector,wallVector); }
Интересный факт:
если задать в исходном коде
Build
строку поиска «float», то не найдётся ни одного совпадения.
Интересный факт:
использование типа float популяризировал Quake, потому что он был предназначен для процессоров Pentium и их сопроцессоров для чисел с плавающей точкой.

Внутри вогнутого полигона

Узнав, как векторное произведение можно использовать для определения положения точки относительно стены, мы можем подробнее рассмотреть inside.
Пример с вогнутым полигоном и двумя точками: Point 1 и Point 2.

Point 1 считается находящейся снаружи.
Point 2 считается находящейся внутри.

«Современный» алгоритм для определения точки в полигоне (point-in-polygon, PIP) заключается в испускании луча слева и определении количества пересечённых сторон. При нечётном количестве точка находится внутри, при чётном — снаружи.
В Build

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

Интересный факт:

движку Doom приходилось выполнять примерно такие же трюки в R_PointOnSide. В Quake использовались плоскости и операции с числами с плавающей запятой в Mod_PointInLeaf.

Интересный факт:

если inside вам кажется трудным в чтении, советую изучить версию Chocolate Duke Nukem, в ней есть комментарии.

Duke Nukem Forever (2011)

Именно данный проект стал проклятием серии про отважного спасателя Земли. Всё дело в разработке, которая затянулась на 11 лет. Игру то отменяли, то происходила нехватка финансирования или оно вообще отсутствовало. Всё это в купе повлияло и на качество игры.

После выхода Duke Nukem Forever была разбита критиками в пух и прах. Сюжет получился глупым, геймплей неинтересным. Игра осталась сырой из-за обилия багов и глюков, но в неё всё-таки можно поиграть. Главное, что Дюк остался смешным и саркастичным.

Портальные и непрозрачные стены

Начальный сектор передаётся движку Buildигровым модулем
. Рендеринг начинается с непрозрачных стен в drawrooms: два этапа, соединённые стеком.

Этап предварительной обработки заливает портальную систему (начиная с startingSectorID) и сохраняет стены в стеке: scansector().
Стек состоит из элементов «bunch».
Элементы стека передаются в метод рендерера: drawwalls().

Что же такое «группа» (bunch)?

Группа — это множество стен, которые считаются «потенциально видимыми». Эти стены относятся к одному сектору и постоянно (соединенные точкой) направлены в сторону игрока.

Большинство стен в стеке будет отброшено, в результате только некоторые рендерятся на экране.

Примечание:

«wall proxy» — это целое число, ссылающееся на стену в списке «потенциально видимых» стен. Массив pvWalls содержит ссылку на стену в базе данных мира, а также её координаты, повёрнутые/перемещённые в пространство игрока и экранное пространство.

Примечание:

структура данных на самом деле более сложна: в стеке сохраняется только первая стена из группы. Остальные находятся в массиве, используемом как список со ссылками на идентификаторы: это выполняется таким образом, что группы можно быстро перемещать вверх и вниз по стеку.

Интересный факт:

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

Интересный факт:

в движке Doom для преобразования углов в столбцы экрана использовалась квантификация. В
Build
для преобразования вершин пространства мира в пространство игрока использовалась матрица cos/sin.

При заливке порталов используется следующая эвристика: все порталы, направленные в сторону игрока и находящиеся в пределах области видимости 90 градусов, будут залиты. Эту часть сложно понять, но она интересная, потому что показывает, как разработчики стремились повсюду к экономии циклов:

//Векторное произведение -> компонента Z tempint = x1*y2-x2*y1; // С помощью векторного произведения определяем, направлен ли портал на игрока, или нет. // Если направлен: добавляем его в стек и увеличивает счётчик стека. if (((uint32_t)tempint+262144) < 524288) { //(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) is the squared length of the wall if (mulscale5(tempint,tempint) <= (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) sectorsToVisit[numSectorsToVisit++] = nextsectnum; }

Генерирование групп

Стены внутри сектора группируются в «группы» («bunches»). Вот рисунок для объяснения идеи:
На рисунке выше показаны что три сектора сгенерировали четыре группы:

Sector 1 сгенерировал одну группу, содержащую одну стену.
Sector 2 сгенерировал одну группу, содержащую три стены.
Sector 3 сгенерировал две группы, каждая из которых содержит по две стены.

Зачем вообще группировать стены в группы? Потому что в Build
нет никакой структуры данных, позволяющей выполнять быструю сортировку. Он извлекает ближайшую группу с помощью процесса (O²), который был бы очень затратным, если бы выполнялся для каждой стены. Затраты ресурсов гораздо ниже, чем при выполнении для множества всех стен.

Использование групп

После заполнения стека групп движок начинает отрисовывать их, начиная от близких к далёким. Движок выбирает первую группу, которая не перекрыта другой группой (всегда есть хотя бы одна группа, удовлетворяющая этому условию): /* Почти работает, но не совсем */ closest = 0; tempbuf[closest] = 1; for(i=1; i < numbunches; i++){ if ((j = bunchfront(i,closest)) < 0) continue; tempbuf = 1; if (j == 0){ tempbuf[closest] = 1; closest = i; } } Примечание:
несмотря на название переменной, выбираемая группа не обязательно бывает ближайшей.

Объяснение принципа выбора, данное Кеном Силверманом:

Пусть есть 2 группы. Сначала мы проверяем, не перекрываются ли они в экранных x-координатах. Если не перекрываются, но условие перекрытия не нарушается и мы переходим к следующей паре групп. Для сравнения групп находим первую стену в каждой из групп, которая перекрывается в экранных x-координатах. Потом проводится проверка между стенами. Алгоритм сортировки стен следующий: находим стену, которую можно продолжить в бесконечность без пересечения с другой стеной. (ПРИМЕЧАНИЕ: если они обе пересекаются, то сектор неисправен, и следует ожидать «глюков» отрисовки!) Обе точки на другой (не продолженной) стене должны находиться по одну сторону продолженной стены. Если это происходит на той же стороне, что и точка обзора игрока, то другая стена находится перед ним, в противном же случае — наоборот

bunchfront — быстрый, сложный и несовершенный, поэтому Build
дважды выполняет проверку перед отправкой результата рендереру. Это уродует код, но в результате мы получаем O(n) вместо O(n²).

Каждая выбранная группа отправляется drawalls(closest) рендерера: эта часть кода отрисовывает как можно больше стен/полов/потолков.

Визуализация стен/полов/потолков

Для понимания этой части важно уяснить, что всё рендерится вертикально: стены, пол и потолки.
В ядре рендерера есть два массива отсечения. Вместе они отслеживают верхнюю и нижнюю границы отсечения каждого столбца пикселей на экране:

//Максимальное разрешение программного рендерера — 1600×1200 #define MAXXDIM 1600 //FCS: (самый верхний пиксель в столбце x, который может быть отрисован) short umost[MAXXDIM+1]; //FCS: (самый нижний пиксель в столбце x, который может быть отрисован) short dmost[MAXXDIM+1];
Примечания:
движок обычно использует массивы примитивных типов вместо массива struct.

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

Примечание:

бóльшую часть времени массив отсечения обновляется только частично: порталы оставляют в нём «дыры».

Каждая стена в группе проецируется в экранное пространство, а затем:

Если это сплошная стена:
Рендерится потолок, если он видим.

Рендерится пол, если он видим.

Рендерится стена, если она видима.
Целый столбец помечается как в массиве отсечения как перекрытый.

Если это портал:

Рендерится потолок, если он видим.

Рендерится пол, если он видим.

Движок «заглядывает» в следующий сектор:

Массив отсечения обновляется с учётом того, что было отрисовано.

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

Это гораздо проще понять на примере, разбивающем сцену, например, знакомый всем зал:

На карте порталы показаны красным, а сплошные стены — белым:

Три стены первой группы проецируются в экранное пространство: на экран попадают только нижние части.

Поэтому движок может рендерить пол вертикально:

Затем движок «заглядывает» в соседние с каждой из трёх стен секторы: поскольку их знчение не -1, эти стены являются порталами. Видя разницу между высотами полов, движок понимает, что надо отрисовывать для каждого из них уступ вверх («UP»):

И это всё, что рендерится с первой группой. Теперь в экранное пространство проецируется вторая группа.

И снова попадает только нижняя часть. Это значит, что движок может рендерить пол:

Заглянув в следующий сектор и увидев самый длинный портал, движок может отрисовывать уступ вверх («STEP UP»). Однако второй портал в группе ведёт к более низкому сектору: уступ НЕ отрисовывается.

Процесс повторяется. Вот видео, показывающее полную сцену:

Внутри театра:

В результате отрисовки портала двери
Build
отрисовал уступ вверх и уступ вниз двумя разными текстурами. Как это возможно с помощью только одного picnum?:

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

Я скомпилировал в видео две другие сцены:

Улица:

С 0:00 до 0:08 : портал нижней линии тротуара использован для отрисовки вертикальной части пола.

На 0:08 движок ищет уровень пола сектора после тротуара. Поскольку он поднимается вверх, отрисовывается портальная стена: рендеринг тротуара завершён.

С 0:18 до 0:30: группа, состоящая из двух тротуаров слева используется для рендеринга огромного куска пола.

Снаружи театра:

Это интересная сцена, в которой появляется окно.

В последнем видео показано окно. Вот подробности о том, как оно создаётся:

Карта:

Первая группа содержит четыре стены, которые при проецировании в экранное пространство позволяют отрисовать потолок и пол:

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

Третья стена — это портал. Посмотрев на высоту следующего сектора, видно что он ниже, поэтому необходимо отрендерить стену уступа вниз:

Тот же процесс «заглядывания» выполняется и для пола. Поскольку он выше, то отрисовывается стена уступа вверх:

И, наконец, обрабатывается последняя стена. Она не является порталом, поэтому отрисовываются полные столбцы пикселей.

Интересный факт:

поскольку стены отрисовываются вертикально, Build хранит текстуры в ОЗУ повёрнутыми на 90 градусов. Это значительно оптимизирует использование кэша.

Пауза

В этот момент все видимые сплошные стены записаны в закадровый буфер. Движок останавливает свою работу и ждёт выполнения игрового модуля
, чтобы он мог анимировать все видимые спрайты. Эти спрайты записываются в следующий массив: #define MAXSPRITESONSCREEN 1024 extern long spritesortcnt; extern spritetype tsprite[MAXSPRITESONSCREEN];

Рендеринг спрайтов

После того, как игровой модуль
завершит анимацию всех видимых спрайтов,
Build
начинает отрисовку: с дальнего к ближнему в drawmasks().

Вычисляется расстояние от точки обзора до каждого спрайта.
Массив спрайтов сортируется алгоритмом Шелла
Движок поочерёдно берёт данные из двух списков (один для спрайтов и один для прозрачных стен).
После исчерпания одного списка движок пытается минимизировать ветвление и переключается на цикл, рендерящий только один тип: спрайты или стены.

Профайлинг

Запуск Duke Nukem 3D
через отладчик «Instruments» натолкнул на мысль о том, на что тратятся циклы процессора:

Метод Main:

Неудивительно: бóльшая часть времени тратится на рендеринг непрозрачных стен и ожидание возможности переключения буфера (включена vsync).

Метод displayrooms:

93% времени тратится на отрисовку сплошных стен. 6% отведено визуализации спрайтов/прозрачных стен.

Метод drawrooms:

Несмотря на свою сложность, определение видимых поверхностей (Visible Surface Determination) занимает всего 0,1% этапа визуализации сплошных стен.

Метод drawalls:

Функции *scan — это интерфейс между движком и процедурами ассемблера:

wallscan(): стены
ceilscan(): потолки без наклона
florscan(): полы без наклона
parascan(): параллакс неба (использует внутри wallscan())
grouscan(): наклонные потолки и полы — работает медленнее

Комментарии Кена Силвермана:

ceilscan() и florscan() сложны, потому что они преобразуют список вертикальных диапапзонов в список горизонтальных диапазонов. Именно для этого нужны все эти циклы while. Я сделал это, потому что накладывать текстуры на потолки и полы без наклона гораздо быстрее в горизонтальном направлении. Это критически важная оптимизация движка, которую вы, наверно, не заметили. Я видел похожие циклы while и в исходном коде Doom.

Кен прислал мне скрипт evaldraw, span_v2h.kc, показывающий, как ceilscan() и florscan() преобразуют список вертикальных диапазонов в список горизонтальных диапазонов:
Метод displayrest:

displayrest взят из игрового модуля

. Основные затраты здесь снова приходятся на отрисовку (оружия). Панель состояния не отрисовывается каждый кадр, она вставляется только при изменении счётчика боеприпасов.

Duke Nukem 3D: Megaton Edition

20 марта 2013 г. Devolver Digital и General Arcade выпустили игру в популярной системе цифровой дистрибьюции Steam в переиздании Duke Nukem 3D: Megaton Edition. Пакет включает в себя 3 официальных дополнения к игре, новый официальный порт, к которому обещается поддержка мультиплеера через SteamWorks, а также классическая версия игры, запускаемая через эмулятор DosBox. Также в игре появится поддержка Steam WorkShop, в котором игроки смогут делиться между собой уровнями и модификациями.

Новый порт Megaton Edition, кроме интеграции со Steam, имеет полную совместимость с современными операционными системами Windows и Mac, а также улучшенный рендеринг OpenGL, благодаря чему игра лучше выглядит на высоких, широкоэкранных разрешениях.

В конце июля 2013 г. объявлено о выходе бета-версии для Linux[3].

В январе 2014 г. был добавлен мультиплеер.[4]

По состоянию на 31 мая 2020 Megaton Edition, как и все игры серии, недоступна для покупки ни в одном из сервисов цифровой дистрибуции по причине окончания действия соглашения между Devolver Digital и Gearbox Software.[5] Несмотря на это, игра по прежнему доступна всем, кто успел приобрести её до середины января 2016 года.

Настоящее игры

Содержимое этого раздела нуждается в чистке.

При запуске игры на современных компьютерах возникают трудности, из-за того, что она создавалась под DOS, поэтому на других системах могут возникнуть проблемы с изображением, звуком и скоростью работы.

Хотя движок игры открыт для модификации, файлы данных (за исключением shareware-версии L.A. Meltdown

На PC и консолях вышло переиздание Duke Nukem 3D с новыми уровнями

Происхождение

Сюжетная линия

Эпизод 1: L.A. Meltdown

Эпизод 2: Lunar Apocalypse

Эпизод 3: Shrapnel City

Эпизод 4: The Birth

Первый контакт

Настоящее игры[править | править код]

Погружение в процесс

Версии игры

Обзор библиотеки движка

Обзор игрового модуля

Унаследованный исходный код

Chocolate Duke Nukem 3D

Duke Nukem (1991)

Важнейшая концепция: система порталов

Обзор рабочего цикла

С чего начинать рендеринг?

Технические детали

Эпоха вычислений с фиксированной запятой и вездесущие векторные произведения

Внутри вогнутого полигона

Duke Nukem Forever (2011)

Портальные и непрозрачные стены

Генерирование групп

Использование групп

Визуализация стен/полов/потолков

Пауза

Рендеринг спрайтов

Профайлинг

Duke Nukem 3D: Megaton Edition

Рекомендуемое чтение

Настоящее игры