Главная
Анализ исходного кода Duke Nukem 3D: Часть 1

Анализ исходного кода Duke Nukem 3D: Часть 1 +95

09.03.2017 12:34

PatientZero 26 26200 Источник

Уйдя с работы в 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».

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

Поскольку исходный код выпущен давным-давно (он был предназначен для компилятора 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.

Сборка

Разобравшись с SDL и расположением заголовком/библиотек DirectX, можно собрать код за один щелчок. Это очень приятно. Последнее, что осталось — достать файл ресурсов DUKE3D.GRP, и игра запустится… ну, или типа того. Похоже, у SDL есть какие-то проблемы с палитрой в Vista/Windows 7:

Запуск в оконном режиме (или лучше в Windows 8) кажется решает проблему:

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

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

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

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

Когда игрок запрыгивает в вентиляционную шахту:

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

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

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

Код движка находится в одном файле из 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

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

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

Корону у него отнял в июне 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 — он не выполняет испускание лучей: вершины сначала проецируются в пространство игрока, а затем генерируется столбец/расстояние из точки обзора.

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

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

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

Вот каждый из этапов в коде:

   //  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, но имя метода осталось как артефакт прошлого.

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

Отсутствие 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)

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

Подробности об inside

Inside — это примечательный по двум причинам метод:

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

Я подробно рассматриваю этот метод, потому что он отлично демонстрирует, как работает Build: с помощью старых добрых векторных произведений и XOR.

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

Поскольку в большинстве компьютеров 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, в ней есть комментарии.

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

Начальный сектор передаётся движку 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[i] = 1;

     if (j == 0){
        tempbuf[closest] = 1;
        closest = i;
     }
}

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

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

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

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

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

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

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

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

//Максимальное разрешение программного рендерера - 1600x1200
#define MAXXDIM 1600

//FCS: (самый верхний пиксель в столбце x, который может быть отрисован)
short umost[MAXXDIM+1];

//FCS: (самый нижний пиксель в столбце x, который может быть отрисован)
short dmost[MAXXDIM+1];

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

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

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

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

Если это сплошная стена:
- Рендерится потолок, если он видим.
- Рендерится пол, если он видим.
- Рендерится стена, если она видима.
- Целый столбец помечается как в массиве отсечения как перекрытый.
Если это портал:
- Рендерится потолок, если он видим.
- Рендерится пол, если он видим.
- Движок «заглядывает» в следующий сектор:
- Массив отсечения обновляется с учётом того, что было отрисовано.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Улица:

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

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

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

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

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

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

Карта:

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

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

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

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

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

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

3. Пауза

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

#define MAXSPRITESONSCREEN 1024
extern long spritesortcnt;
extern spritetype tsprite[MAXSPRITESONSCREEN];

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

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

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

Профайлинг

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

Метод Main:

Неудивительно: бoльшая часть времени тратится на рендеринг непрозрачных стен и ожидание возможности переключения буфера (включена 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 взят из игрового модуля. Основные затраты здесь снова приходятся на отрисовку (оружия). Панель состояния не отрисовывается каждый кадр, она вставляется только при изменении счётчика боеприпасов.

Интересные факты о VGA и VESA

Благодаря X-Mode VGA большинство игроков запускало Build в разрешении 320x240. Но благодаря стандарту VESA движок также поддерживает разрешение Super-VGA. «Ванильные» исходники оснащены кодом VESA, обеспечивавшим портируемое определение разрешения и рендеринг.

Ностальгирующие могут почитать о программировании для VESA в этом хорошем руководстве. Сегодня в коде остались только названия методов, например, getvalidvesamodes().

Звуковой движок

В своё время Duke3D имел впечатляющий движок звуковой системы. Он мог даже микшировать звуковые эффекты для симуляции реверберации. Подробнее об этом можно почитать в reverb.c.

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

Код Build очень трудно читать. Я перечислил все причины этих сложностей на странице Duke Nukem 3D and Build engine: Source code issues and legacy.