- PVSM.RU - https://www.pvsm.ru -
Уйдя с работы в Amazon, я провёл много времени за чтением отличного исходного кода.
Разобравшись [1] с [2] невероятно [3] замечательным [4] кодом [5] idSoftware [6], я принялся за одну из лучших игр всех времён [7]: Duke Nukem 3D и за её движок под названием "Build".
Это оказался трудный опыт: сам движок имеет большую важность и высоко ценится за свою скорость, стабильность и потребление памяти, но мой энтузиазм столкнулся с исходным кодом, противоречивым в отношении упорядоченности, соблюдения рекомендаций и комментариев/документации. Читая код, я многое узнал о унаследованном коде и о том, что позволяет программному обеспечению жить долго.
Как обычно, я переработал свои заметки [8] в статью. Надеюсь, она вдохновит вас на чтение исходного кода и совершенствование своих навыков.
Хочу поблагодарить Кена Силвермана (Ken Silverman) за вычитку этой статьи: его терпеливость и добросовестные ответы на мои письма были важны для меня.
Duke Nukem 3D — не одна, а две базы кода:
Зачем нужно было такое разделение? Потому что в 1993 году, когда началась разработка, только у немногих людей были навыки и рвение, необходимые для создания хорошего 3D-движка. Когда 3D Realms решила написать игру, которая станет конкурентом Doom, ей нужно было найти мощную технологию. И в этот момент на сцене появляется Кен Силверман.
Согласно его хорошо документированному веб-сайту [9] и интервью [10], Кен (в то время ему было 18 лет) написал дома 3D-движок и отправил демо в 3D Realms для оценки. Они посчитали его навыки многообещающими, и заключили соглашение:
Силверман напишет новый движок для 3D Realms, но сохранит за собой исходный код.
Он предоставит только двоичную статическую библиотеку (Engine.OBJ
) с файлом заголовка Engine.h
. Со своей стороны, команда 3D Realms возьмёт на себя работу над игровым модулем (Game.OBJ
) и выпустит финальный исполняемый DUKE3D.EXE
.
К сожалению, исходный код обеих частей игры не был открыт одновременно:
В результате полный исходный код стал доступен только через 7 лет после выпуска игры.
Интересный факт: название движка "Build" было выбрано Кеном Силверманом при создании каталога для нового движка. Он воспользовался тезаурусом, чтобы найти синонимы к слову «Construction» [9].
Поскольку исходный код выпущен давным-давно (он был предназначен для компилятора Watcom C/C++ и систем DOS), я попытался найти что-то похожее на Chocolate doom [11]: порт, точно воспроизводящий игровой процесс Duke Nukem 3D, таким, каким он был в 90-х, и беспроблемно компилирующийся на современных системах.
Выяснилось, что сообщество исходного кода Duke Nukem уже не слишком активно: многие порты снова устарели, некоторые созданы для MacOS 9 PowerPC. До сих пор поддерживается только один (EDuke32 [12]), но он слишком сильно эволюционировал по сравнению с оригинальным кодом.
В результате я начал работать с xDuke [13], хотя он и не компилировался на Linux и Mac OS X (что исключило использование XCode: отличного IDE для чтения кода и профайлинга).
xDuke, сделанный на Visual Studio, точно воспроизводит оригинальный код. Он содержит два проекта: Engine и Game. Проект «Engine» компилируется в статическую библиотеку (Engine.lib
), а проект «Game» (содержащий метод main
) связывается с ним для генерирования duke3D.exe
.
При открытии VS исходники движка выглядят довольно неприветливо из-за сложных имён файлов (a.c
, cache1d.c
). Файлы эти содержат нечто враждебное глазу и
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 [16]!
Примечание: порт xDuke использует SDL, но преимущество кроссплатформенного API утеряно из-за таймеров WIN32 (QueryPerformanceFrequency
). Похоже, что использованный SDL Timer слишком неточен для эмуляции частоты 120 Гц в DOS.
Разобравшись с SDL и расположением заголовком/библиотек DirectX, можно собрать код за один щелчок. Это очень приятно. Последнее, что осталось — достать файл ресурсов DUKE3D.GRP
, и игра запустится… ну, или типа того. Похоже, у SDL есть какие-то проблемы с палитрой в Vista/Windows 7:
Запуск в оконном режиме (или лучше в Windows 8) кажется решает проблему:
Теперь игра работает. За несколько секунд Build предстаёт во всё своём блеске, демонстрируя:
Последний пункт, наверно, больше всего повлиял на игроков в 1996 году. Уровень погружения был непревзойдённым. Даже когда технология достигла своего предела из-за двухмерных карт, Тодд Реплогл (Todd Replogle) и Аллен Блум (Allen Blum) реализовали «эффекторы секторов» позволявшие телепортировать игрока и усиливавшие ощущение погружения в трёхмерный мир. Эта функция используется в легендарной карте «L.A Meltdown»:
Когда игрок запрыгивает в вентиляционную шахту:
Срабатывают эффекторы секторов и перед «приземлением» телепортируют игрока совершенно в другое место карты:
Хорошие игры медленно стареют, и Duke Nukem не стала исключением: двадцать лет спустя в неё всё ещё невероятно интересно играть. А теперь мы ещё и можем изучить её исходники!
Код движка находится в одном файле из 8503 строк и with 10 master functions (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».#define
[18].В целом эту часть кода легко читать и понимать.
Глядя на бесконечное количество портов, порождённых Doom/Quake, я всегда удивлялся, почему так мало портов Duke Nukem 3D. Тот же вопрос возник, когда движок был портирован под OpenGL только после того, как Кен Силверман решил заняться этим самостоятельно.
Теперь, когда я посмотрел на код, рискну объяснить это во второй части этой статьи
Я обожаю этот движок и люблю игру, поэтому не мог оставить всё как есть: я создал Chocolate Duke Nukem 3D [19], порт «ванильного» исходного кода, пытаясь достичь таким образом двух целей:
Надеюсь, эта инициатива поможет унаследовать код. Самые важные модификации будут описаны во второй части статьи.
Build [20] использовался в Duke Nukem 3D и многих других успешных играх, таких как Shadow Warrior [21] и Blood [22]. В момент выпуска 29 января 1996 года он уничтожил движок Doom инновационными возможностями:
Корону у него отнял в июне 1996 года Quake, запущенный на мощных «Пентиумах»… но в течение нескольких лет Build обеспечивал высокое качество, свободу дизайнеров и, что важнее всего, хорошую скорость на большинстве компьютеров того времени.
Большинство 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()
Интересный факт: если вы изучаете код, то есть полностью развёрнутый цикл [24], который я использовал в качестве карты.
Интересный факт: почему метод переключения буферов называется nextpage()
? В 90-х радость программирования для VGA/VESA включала в себя реализацию двойной буферизации: две части видеопамяти выделялись и использовались по очереди. Каждая часть называлась «страницей» («page»). Одна часть использовалась модулем VGA CRT, а вторая обновлялась движком. Переключение буферов заключалось в использовании CRT следующей страницы («next page») заменой базового адреса. Гораздо подробнее можно почитать об этом в Главе 23 книги Майкла Абраша «Black Book of Graphic Programming: Bones and sinew» [25].
Сегодня SDL упрощает эту работу простым флагом видеорежима SDL_DOUBLEBUF
, но имя метода осталось как артефакт прошлого.
Отсутствие BSP означает, что невозможно взять точку p(x,y)
и пройти по узлам дерева, пока не достигнем сектора листа. В Build текущий сектор игрока нужно отслеживать после каждого обновления положения с помощью updatesector(int newX, int newY, int* lastKnownSectorID)
. Игровой модуль вызывает этот метод модуля движка очень часто.
Наивная реализация updatesector
сканировала бы линейно каждый сектор и каждый раз проверяла, находится ли p(x,y)
внутри сектора S. Но updatesector
оптимизирована поведенческим шаблоном:
lastKnownSectorID
, алгоритм полагает, что игрок переместился не очень далеко и начинает проверку с сектора lastKnownSectorID
.lastKnownSectorID
секторы.
На карте слева последним известным сектором положения игрока был сектор с идентификатором 1
: в зависимости от расстояния, на которое переместился игрок, updatesector
выполняет проверку в следующем порядке:
inside(x,y,1)
(игрок переместился не так далеко, чтобы покинуть сектор).inside(x,y,0)
(игрок слегка переместился в соседний сектор).
inside(x,y,0)
(игрок сильно переместился: потенциально необходима проверка всех секторов игры).
inside(x,y,1)
inside(x,y,2)
inside(x,y,3)
inside(x,y,4)
Наихудший сценарий может быть довольно затратным. Но бóльшую часть времени игрок/снаряды перемещаются не очень далеко, и скорость игры остаётся высокой.
Inside — это примечательный по двум причинам метод:
Я подробно рассматриваю этот метод, потому что он отлично демонстрирует, как работает Build: с помощью старых добрых векторных произведений и XOR.
Поскольку в большинстве компьютеров 90-х не было сопроцессора для чисел с плавающей точкой (FPU) (386SX, 386DX и 486SX), в Build использовались только целые числа.
В примере показана стена с конечными точками A и B: задача заключается в том, чтобы определить, находится точка слева или справа.
В Главе 61 книги Майкла Абраша «Black Book of Programming: Frame of Reference» [26] эта задача решается простым скалярным произведением и сравнением.
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
[27].
Пример с вогнутым полигоном и двумя точками: Point 1 и Point 2.
«Современный» алгоритм для определения точки в полигоне (point-in-polygon, PIP) заключается в испускании луча слева и определении количества пересечённых вершин. При нечётном количестве точка находится внутри, при чётном — снаружи.
В Build используется вариация этого алгоритма: он считает количество рёбер на каждой стороне и комбинирует результаты с помощью XOR:
Интересный факт: движку Doom приходилось выполнять примерно такие же трюки в R_PointOnSide [28]. В Quake использовались плоскости и операции с числами с плавающей запятой в Mod_PointInLeaf [29].
Интересный факт: если inside
вам кажется трудным в чтении, советую изучить версию Chocolate Duke Nukem [30], в ней есть комментарии.
Начальный сектор передаётся движку Build игровым модулем. Рендеринг начинается с непрозрачных стен в drawrooms
: два этапа, соединённые стеком.
startingSectorID
) и сохраняет стены в стеке: scansector()
.drawwalls()
.
Что же такое «группа» (bunch)?
Группа — это множество стен, которые считаются «потенциально видимыми». Эти стены относятся к одному сектору и постоянно (соединенные точкой) направлены в сторону игрока.
Большинство стен в стеке будет отброшено, в результате только некоторые рендерятся на экране.
Примечание: «wall proxy» — это целое число, ссылающееся на стену в списке «потенциально видимых» стен. Массив pvWalls содержит ссылку на стену в базе данных мира, а также её координаты, повёрнутые/перемещённые в пространство игрока и экранное пространство.
Примечание: структура данных на самом деле более сложна: в стеке сохраняется только первая стена из группы. Остальные находятся в массиве, используемом как список со ссылками на идентификаторы: это выполняется таким образом, что группы можно быстро перемещать вверх и вниз по стеку.
Интересный факт: для пометки посещённых «секторов» процесс заливки использует массив. Этот массив должен очищаться перед каждым кадром. Для определения того, посещался ли сектор в текущем кадре, он не использует трюк с framenumber [31].
Интересный факт: в движке Doom для преобразования углов в столбцы экрана использовалась квантификация. В Build для преобразования вершин пространства мира в пространство игрока использовалась матрица cos/sin [32].
При заливке порталов используется следующая эвристика: все порталы, направленные в сторону игрока и находящиеся в пределах области видимости 90 градусов, будут залиты. Это часть сложно понять [33], но она интересная, потому что показывает, как разработчики стремились повсюду к экономии циклов:
//Векторное произведение -> компонента 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»). Вот рисунок для объяснения идеи:
На рисунке выше показаны что три сектора сгенерировали четыре группы:
Зачем вообще группировать стены в группы? Потому что в Build нет никакой структуры данных, позволяющей выполнять быструю сортировку. Он извлекает ближайшую группу с помощью процесса (O²), который был бы очень затратным, если бы выполнялся для каждой стены. Затраты ресурсов гораздо ниже, чем при выполнении для множества всех стен.
После заполнения стека групп движок начинает отрисовывать их, начиная от близких к далёким. Движок выбирает первую группу, которая не перекрыта другой группой (всегда есть хотя бы одна группа, удовлетворяющая этому условию):
/* Почти работает, но не совсем :( */
closest = 0;
tempbuf[closest] = 1;
for(i=1; i < numbunches; i++){
if ((j = bunchfront(i,closest)) < 0)
continue;
tempbuf[i] = 1;
if (j == 0){
tempbuf[closest] = 1;
closest = i;
}
}
Примечание: несмотря на название переменной, выбираемая группа не обязательно бывает ближайшей.
Объяснение принципа выбора, данное Кеном Силверманом:
Пусть есть 2 группы. Сначала мы проверяем, не перекрываются ли они в экранных x-координатах. Если не перекрываются, но условие перекрытия не нарушается и мы переходим к следующей паре групп. Для сравнения групп находим первую стену в каждой из групп, которая перекрывается в экранных x-координатах. Потом проводится проверка между стенами. Алгоритм сортировки стен следующий: находим стену, которую можно продолжить в бесконечность без пересечения с другой стеной. (ПРИМЕЧАНИЕ: если они обе пересекаются, то сектор неисправен, и следует ожидать «глюков» отрисовки!) Обе точки на другой (не продолженной) стене должны находиться по одну сторону продолженной стены. Если это происходит на той же стороне, что и точка обзора игрока, то другая стена находится перед ним, в противном же случае — наоборот
bunchfront
— быстрый, сложный и несовершенный, поэтому Build дважды выполняет проверку [34] перед отправкой результата рендереру. Это уродует код, но в результате мы получаем O(n) вместо O(n²).
Каждая выбранная группа отправляется drawalls(closest)
рендерера: эта часть кода отрисовывает как можно больше стен/полов/потолков.
Для понимания этой части важно уяснить, что всё рендерится вертикально: стены, пол и потолки.
В ядре рендерера есть два массива отсечения. Вместе они отслеживают верхнюю и нижнюю границы отсечения каждого столбца пикселей на экране:
//Максимальное разрешение программного рендерера - 1600x1200
#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 [35], span_v2h.kc [36], показывающий, как ceilscan() и florscan() преобразуют список вертикальных диапазонов в список горизонтальных диапазонов:
Метод displayrest:
displayrest
взят из игрового модуля. Основные затраты здесь снова приходятся на отрисовку (оружия). Панель состояния не отрисовывается каждый кадр, она вставляется только при изменении счётчика боеприпасов.
Благодаря X-Mode VGA большинство игроков запускало Build в разрешении 320x240. Но благодаря стандарту VESA движок также поддерживает разрешение Super-VGA. «Ванильные» исходники оснащены кодом VESA, обеспечивавшим портируемое определение разрешения и рендеринг.
Ностальгирующие могут почитать о программировании для VESA в этом хорошем руководстве [37]. Сегодня в коде остались только названия методов, например, getvalidvesamodes()
.
В своё время Duke3D имел впечатляющий движок звуковой системы. Он мог даже микшировать звуковые эффекты для симуляции реверберации. Подробнее об этом можно почитать в reverb.c [38].
Код Build очень трудно читать. Я перечислил все причины этих сложностей на странице Duke Nukem 3D and Build engine: Source code issues and legacy [39].
Никакого. Займитесь лучше скалолазанием — это потрясающе!
Но если настаиваете, то можно почитать id as Super-Ego: The Creation of Duke Nukem 3D [40]
Автор: PatientZero
Источник [47]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/248699
Ссылки в тексте:
[1] Разобравшись: http://fabiensanglard.net/doomIphone/doomClassicRenderer.php
[2] с: http://fabiensanglard.net/quakeSource/index.php
[3] невероятно: http://fabiensanglard.net/wolf3d/index.php
[4] замечательным: http://fabiensanglard.net/quake3/index.php
[5] кодом: http://fabiensanglard.net/quake2/index.php
[6] idSoftware: http://fabiensanglard.net/doom3/index.php
[7] лучших игр всех времён: http://en.wikipedia.org/wiki/List_of_best-selling_PC_video_games
[8] свои заметки: http://fabiensanglard.net/duke3d/notes.txt
[9] хорошо документированному веб-сайту: http://advsys.net/ken/build.htm
[10] интервью: http://www.3drealms.com/news/2006/02/the_apogee_legacy_8.html
[11] Chocolate doom: http://www.chocolate-doom.org/wiki/index.php/Chocolate_Doom
[12] EDuke32: http://eduke32.com/
[13] xDuke: http://vision.gel.ulaval.ca/~klein/duke3d/
[14] мозгу: http://www.braintools.ru
[15] Engine.c (строка 693): https://github.com/fabiensanglard/vanilla_duke3D/blob/master/SRC/ENGINE.C#L1280
[16] черновик сценария Duke V: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Game/src/game.c#L10795
[17] передаются через десятичные: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Game/src/gamedef.c#L459
[18] #define
: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Game/src/gamedef.c#L52
[19] Chocolate Duke Nukem 3D: https://github.com/fabiensanglard/chocolate_duke3D
[20] Build: http://en.wikipedia.org/wiki/Build_engine
[21] Shadow Warrior: http://en.wikipedia.org/wiki/Shadow_Warrior
[22] Blood: http://en.wikipedia.org/wiki/Blood_(video_game)
[23] Воксельными объектами: http://fd.fabiensanglard.net/duke3d/blood_voxels.png
[24] полностью развёрнутый цикл: http://duke3d_code_review_unrolled.txt
[25] Главе 23 книги Майкла Абраша «Black Book of Graphic Programming: Bones and sinew»: http://downloads.gamedev.net/pdf/gpbb/gpbb23.pdf
[26] Главе 61 книги Майкла Абраша «Black Book of Programming: Frame of Reference»: http://twimgs.com/ddj/abrashblackbook/gpbb61.pdf
[27] inside
: https://github.com/fabiensanglard/vanilla_duke3D/blob/master/SRC/ENGINE.C#L2733
[28] R_PointOnSide: https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/r_main.c#L162
[29] Mod_PointInLeaf: https://github.com/id-Software/Quake/blob/master/WinQuake/gl_model.c#L96
[30] версию Chocolate Duke Nukem: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Engine/src/engine.c#L4544
[31] трюк с framenumber: http://fabiensanglard.net/quakeSource/quakeSourceRendition.php#elegant_leaf_marking
[32] использовалась матрица cos/sin: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Engine/src/engine.c#L425
[33] сложно понять: https://github.com/fabiensanglard/vanilla_duke3D/blob/master/SRC/ENGINE.C#L640
[34] дважды выполняет проверку: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Engine/src/engine.c#L2999
[35] evaldraw: http://advsys.net/ken/evaltut/evaldraw_tut.htm
[36] span_v2h.kc: http://fabiensanglard.net/duke3d/span_v2h.kc
[37] в этом хорошем руководстве: http://www.monstersoft.com/tutorial1/
[38] reverb.c: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Game/src/audiolib/mvreverb.c
[39] Duke Nukem 3D and Build engine: Source code issues and legacy: http://code_legacy.php
[40] id as Super-Ego: The Creation of Duke Nukem 3D: http://fabiensanglard.net/duke3d/id%20as%20Super-Ego-%20The%20Creation%20of%20Duke%20Nukem%203D.pdf
[41] отличный постмортем: https://habrahabr.ru/post/321986/
[42] зеркало: http://fd.fabiensanglard.net/duke3d/interviews/ks_interview_3drealms.zip
[43] 25 марта 2010 года: http://misterdai.yougeezer.co.uk/2010/03/25/retro-game-interview-ken-silverman-duke-nukem-3d/
[44] зеркало: http://fd.fabiensanglard.net/duke3d/interviews/ks_interview_misterdai.zip
[45] 1 мая 2012 года: http://videogamepotpourri.blogspot.ca/2012/05/interview-with-ken-silverman.html
[46] зеркало: http://fd.fabiensanglard.net/duke3d/interviews/ks_interview_popourri.zip
[47] Источник: https://habrahabr.ru/post/323426/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.