В настоящее время интерес к софтверным движкам, как из игр Quake, DOOM или Duke Nukem 3D практически нулевой. Однако, эти движки имели своё очарование и мне, например, очень нравится графика именно таких вот движков с нереалистичными текстурами на стенах. Конечно, такие текстуры можно накладывать без фильтрации и в OpenGL, получая такой же уровень графики, но всё же, написать собственный софтверный движок было весьма интересно. Движок уровня Quake я написать в своё время не смог, так как не удалось создать редактор 3D карты – я просто не представлял, как вообще рисовать в 3D карту. Да и с большой вероятность текстурирование в произвольном случае в моём исполнении (без ассемблера) было бы очень медленно. Но движок уровня DOOM мне покорился. Основу такого движка я написал в 2002 году, пользуясь книжкой Шикина и Борескова “Компьютерная графика. Полигональные модели”. На базе того движка используя графику из Doom я написал некое подобие игры под MS-DOS на Watcom C. Несколько лет назад я решил вынуть из той игры код движка и переработать его под мои текущие знания языка Си++ и представления о том, как стоило бы устроить этот движок. Ну и заодно перенести этот движок под Windows и дополнить наклонами головы, как в Blood или Duke Nukem. О том, что в результате получилось, я и написал в этой статье.
Итак, в этой статье я расскажу, как написать движок уровня Duke Nukem 3D, однако, без наклонных поверхностей, которые есть в этой игре. То есть, до движка Build моё творение не дотянуло. Кроме того, представленный движок будет использовать не BSP (как DOOM), а метод порталов. Изначальный мой движок использовал как раз BSP, но, как оказалось, метод порталов работает быстрее. Про BSP же я тоже расскажу и приведу сам движок его использующий.
В движках описываемого типа плоская карта. Это значит, что лабиринт состоит из зон (секторов), которые не могут находиться одна над другой. Сектора для удобства работы с ними мы будем считать выпуклыми многоугольниками.
Вид лабиринта из редактора карты
Для каждого сектора задаётся высота пола и потолка, а также стены (сегменты), которые находятся в секторе. Такие сегменты являются сплошной стеной и выводятся при отрисовке от пола до потолка. Между секторами располагаются специальные сегменты – линии раздела. Линии раздела закрывают перепады высот между секторами и, кроме того, являются порталами в другой сектор из выбранного. Следует иметь в виду, что для портального движка внутри сектора сегменты и линии раздела не могут располагаться не выпуклым многоугольником, иначе потребуется упорядочивание сегментов внутри сектора (если этого не сделать, будет неясно, какой сегмент выводить на переднем плане, а какой на заднем). Для BSP-движка это не важно – он сам упорядочивает сегменты на этапе разбиения карты.
Как же работает BSP-движок? Да очень просто. Достаточно взять какой-либо сегмент или линию раздела карты и разрезать ей всё пространство карты (корень дерева) на две половинки, как показано на рисунке — это будет левое и правое поддерево.
Разбиение карты
Каждую из этих половинок тоже можно разрезать другой выбранной линией. И так далее, до того момента, когда разбивать будет уже нечего и вы пришли в лист дерева (или вы достигли требуемого качества разбиения – DOOM, например, разбивает, насколько я помню, до выпуклых многоугольников, а я разбиваю до отдельных линий). При таком разрезании из-за ошибок округления сегменты и линии раздела будут разрезаться с ошибками округления, поэтому стоит выбрасывать из списка получающихся фрагментов фрагменты с длиной уровня погрешности. В целом, алгоритм рекурсивный. При выводе же графики достаточно рекурсивно сравнивать положение игрока относительно разбивающих линий и выводить лабиринт от листа (где находится игрок) к корню в обратном порядке. Тем самым вы автоматически получите упорядочение сегментов и линий раздела от игрока в бесконечность. В процессе обработки дерева можно определять видимость поддеревьев, если описать вокруг них прямоугольники и проверять, может видеть игрок эти прямоугольники или нет. Такой приём также ускорит вывод лабиринта.
Портальный движок работает несколько иначе. Прежде всего, он не требует разбиения пространства. Мы просто должны узнать, в каком из секторов находится игрок, и имея список порталов сектора, последовательно переходить из сектора в сектор через эти порталы. Чтобы не крутить по кругу, стоит блокировать порталы, через которые мы уже проходили. Алгоритм такого хождения тоже рекурсивный и тоже в результате мы получаем упорядочивание секторов и сегментов от игрока в бесконечность. Порталы могут быть геометрические (с помощью математики мы отрезаем куски карты, видимые через портал (со всеми ошибками округления в подарок)) и экранные (здесь мы корректируем левую и правую границу зоны вывода картинки на экран). Экранный портал для софтверного движка более предпочтителен, так как очень просто реализуем и работает очень быстро. Единственная непонятная ситуация возможна, когда игрок стоит прямо на портале. В этом случае при отрисовке этого портала границы портала не изменяем, иначе одна из половинок окажется неотрисованной.
Экранный портал
Для того, чтобы определить, стоит игрок на портале или нет, воспользуемся уравнением
В этом уравнении портал задаётся прямой с координатами (x1;y1)-(x2;y2), а положение игрока соответствует координатам (x,y). Если в результате расчета значение P окажется в некотором диапазоне (я принял от -10 до +10), то можно считать, что (x,y) находится очень близко к прямой, на которой лежит портал.
Общим в обоих вариантах движков является метод рисования вертикальных и горизонтальных поверхностей. Так как движок у нас типа DOOM, то никаких произвольно ориентированных поверхностей у нас не будет – только вертикальные и горизонтальные. Как их выводить? Допустим, с помощью порталов или BSP-дерева мы получим упорядоченный от игрока в бесконечность набор сегментов и линий раздела. Чтобы находящиеся вдали сегменты не затёрли уже выведенные ближние к игроку, мы будем использовать линии горизонта. Для каждого столбца экрана (размер окна по X зададим макросом WINDOW_WIDTH) мы зададим две координаты – верхнюю и нижнюю. Итого, нам нужен массив TopLine[WINDOW_WIDTH] и массив BottomLine[WINDOW_WIDTH]. Перед выводом сцены нужно инициализировать эти массивы так:
for(n=0;n<WindowWidth;n++)
{
//инициализировали линии горизонта
TopLine[n]=0;
BottomLine[n]=WindowHeight-1;
}
Где WindowHeight – высота окна, а WindowWidth-ширина окна.
Если для какого-либо столбца экрана x при выводе окажется, что TopLine[x]>BottomLine[x], то данный столбец полностью заполнен, и выводить его не требуется.
Сегмент или линия раздела (которая выводится два раза – как верхняя и как нижняя) при выводе всегда отсекаются по линиям горизонта. Текстурируется только та часть, которая находится между линиями горизонта. В промежуток между верхней точкой выводимой линии или сегмента и TopLine[x] выводится текстура потолка, а между BottomLine[x] и нижней точкой текстура пола (разумеется, для верхней линии раздела пол не рисуется, как и для нижней не рисуется потолок).
При выводе сегмента мы должны установить после вывода столбца TopLine[x]>BottomLine[x], так как сегмент закрывает собой всё, что за ним находится.
Вывод сегмента
При выводе верхней линии раздела, TopLine[x] переносится в нижнюю точку линии раздела. При выводе нижней линии раздела, BottomLine[x] переносится в верхнюю точку линии раздела.
При построении сцены используется перспективная проекция в соответствии с формулой:
Здесь Z – координата глубины (от игрока), а X и Y – положение объекта относительно игрока.
Перед проецированием отображаемый объект нужно сначала переместить относительно позиции игрока и развернуть на угол зрения:
После разворота и отсечения относительно линии, задающей полуплоскость, на которую смотрит игрок, (в моём случае это (-1;1)-(1;1)) можно выполнять проецирование.
Текстурирование сегментов и линий раздела осуществляется вертикальными линиями столбец за столбцом. При этом используется тот факт, что внутри столбца точки текстуры изменяются линейно, а между столбцами линейно изменяются 1/Z и t/Z (t-значение точки внутри текстуры). Разумеется, при всяких обрезаниях сегментов и линий раздела необходимо корректировать начальную и конечную точку текстуры как внутри столбцов, так и между столбцами.
Текстурирование полов и потолков выполняется уже горизонтальными линиями. Это текстурирование со всей математикой немного сложнее, и подробно рассмотрено в книжке Шикина и Борескова “Компьютерная графика. Полигональные модели” в главе “Текстурирование горизонтальных поверхностей”, поэтому я поленился написать здесь формулы перехода между индексами текстуры при таком текстурировании. Я лучше расскажу о том, чего в книжке Шикина и Борескова нет.
Чтобы верно залить пол или потолок после вывода сегмента/линии раздела нам потребуется такая штука, как таблица VisualPlanes. Дело в том, что стены мы выводим вертикально, а пол/потолок горизонтально. Следовательно, нам нужно сначала вывести стену, а затем уже пол или потолок. Вот для этого и нужна эта таблица. Что она собой представляет?
//параметры текстурирования полов и потолков
struct SVisualPlanes
{
long MinX;//минимальная координата X области
long MaxX;//максимальная координата X области
long TopY[WINDOW_WIDTH];//верхняя координата
long BottomY[WINDOW_WIDTH];//нижняя координата
};
Такая вот структура описывает всего лишь фрагмент пола (или потолка) от MinX до MaxX с заданной внутри него верхней и нижней координатой столбцов. Выглядит просто и логично, да? Не так просто будет понять, как из этого набора вертикальных столбцов перейти к горизонтальным линиям. Таких таблиц нужно две – для пола и для потолка. В DOOM эти таблицы полов/потолков собираются и объединяются друг с другом (и этим обусловлено ограничение на их количество в одной сцене). Я так не стал делать и использую одни и те же две таблицы пола и потолка, а вывожу пол и потолок сразу после вывода стены. Точки в эти таблицы добавляются вот по каким критериям:
//----------------------------------------------------------------------------------------------------
//заполнение линии буфера текстур пола
//----------------------------------------------------------------------------------------------------
void CEngine_Base::DrawFloorLine(long x,long y1,long y2,SVisualPlanes &sVisualPlanes_Bottom)
{
if (y2<WindowYCenterWithOffset) return;
if (y1>=WindowHeight) return;
if (y1<WindowYCenterWithOffset) y1=WindowYCenterWithOffset;
if (y2>=WindowHeight) y2=WindowHeight-1;
if (x>sVisualPlanes_Bottom.MaxX) sVisualPlanes_Bottom.MaxX=x;
if (x<sVisualPlanes_Bottom.MinX) sVisualPlanes_Bottom.MinX=x;
if (y1<sVisualPlanes_Bottom.TopY[x]) sVisualPlanes_Bottom.TopY[x]=y1;
if (y2>sVisualPlanes_Bottom.BottomY[x]) sVisualPlanes_Bottom.BottomY[x]=y2;
}
//----------------------------------------------------------------------------------------------------
//заполнение линии буфера текстур потолка
//----------------------------------------------------------------------------------------------------
void CEngine_Base::DrawFlowLine(long x,long y1,long y2,SVisualPlanes &sVisualPlanes_Top)
{
if (y2<0) return;
if (y1>WindowYCenterWithOffset) return;
if (y1<0) y1=0;
if (y2>WindowYCenterWithOffset) y2=WindowYCenterWithOffset;
if (x>sVisualPlanes_Top.MaxX) sVisualPlanes_Top.MaxX=x;
if (x<sVisualPlanes_Top.MinX) sVisualPlanes_Top.MinX=x;
if (y1<sVisualPlanes_Top.TopY[x]) sVisualPlanes_Top.TopY[x]=y1;
if (y2>sVisualPlanes_Top.BottomY[x]) sVisualPlanes_Top.BottomY[x]=y2;
}
Здесь x – координата столбца, y1-верхняя точка столбца, y2-нижняя точка столбца, WindowYCenterWithOffset-координата центра экрана (наш движок позволит наклонять голову и тем самым нам вместо истинного центра экрана нужен будет смещённый центр – об этом ниже).
Инициализируются эти таблицы перед каждым выводом стены так:
SVisualPlanes sVisualPlanes_Top;
SVisualPlanes sVisualPlanes_Bottom;
sVisualPlanes_Top.MinX=WINDOW_WIDTH-1;
sVisualPlanes_Top.MaxX=0;
sVisualPlanes_Bottom.MinX=WINDOW_WIDTH-1;
sVisualPlanes_Bottom.MaxX=0;
for(n=0;n<WINDOW_WIDTH;n++)
{
sVisualPlanes_Top.TopY[n]=WINDOW_HEIGHT-1;
sVisualPlanes_Top.BottomY[n]=0;
sVisualPlanes_Bottom.TopY[n]=WINDOW_HEIGHT-1;
sVisualPlanes_Bottom.BottomY[n]=0;
}
А вот рисование по таким таблицам выполняется следующим кодом:
//----------------------------------------------------------------------------------------------------
//рисование потолков
//----------------------------------------------------------------------------------------------------
void CEngine_Base::DrawFlow(long sector_index,const SVisualPlanes &sVisualPlanes_Top)
{
//параметры сектора
long level=vector_CISectorPtr[sector_index]->GetUp();
long texture=vector_CISectorPtr[sector_index]->GetCTextureFollow_Up_Ptr()->GetCurrentTexture().TextureIndex;
long bright=vector_CISectorPtr[sector_index]->GetLighting();
long z=static_cast<long>((level-PlayerZ)*(WindowYCenter));
long x1;
long x2;
long x;
long y;
x1=sVisualPlanes_Top.MinX;
x2=sVisualPlanes_Top.MaxX;
if (x2<x1) return;
long y_top=sVisualPlanes_Top.TopY[x1];
long y_bottom=sVisualPlanes_Top.BottomY[x1];
for(y=y_top;y<=y_bottom;y++) X_Table[y]=x1;
for(x=x1;x<=x2;x++)
{
long zd;
long y1=sVisualPlanes_Top.TopY[x];
long y2=sVisualPlanes_Top.BottomY[x];
if (y2<y1) continue;//при возможных пропусках точек на границах (а они есть), алгоритм развалится
//если верхняя линия поднимается
while(y1<y_top)
{
y_top--;
X_Table[y_top]=x;
}
//если нижняя линия опускается
while(y2>y_bottom)
{
y_bottom++;
X_Table[y_bottom]=x;
}
//если верхняя линия опускается
zd=(WindowYCenterWithOffset-y_top)+1;
while(y_top<y1)
{
long dist=z/zd;
long scale=dist/zd;
DrawTextureLine(dist,scale,bright,texture,y_top,X_Table[y_top],x-1);
y_top++;
zd--;
}
//если нижняя линия поднимается
zd=(WindowYCenterWithOffset-y_bottom)+1;
while(y_bottom>y2)
{
long dist=z/zd;
long scale=dist/zd;
DrawTextureLine(dist,scale,bright,texture,y_bottom,X_Table[y_bottom],x-1);
y_bottom--;
zd++;
}
}
//заливаем промежуток между top и bottom
long zd=(WindowYCenterWithOffset-y_top)+1;
for(y=y_top;y<=y_bottom;y++,zd--)
{
long dist=z/zd;
long scale=dist/zd;
DrawTextureLine(dist,scale,bright,texture,y,X_Table[y],x2);
}
}
//----------------------------------------------------------------------------------------------------
//рисование полов
//----------------------------------------------------------------------------------------------------
void CEngine_Base::DrawFloor(long sector_index,const SVisualPlanes &sVisualPlanes_Bottom)
{
//параметры сектора
long level=vector_CISectorPtr[sector_index]->GetDown();
long texture=vector_CISectorPtr[sector_index]->GetCTextureFollow_Down_Ptr()->GetCurrentTexture().TextureIndex;
long bright=vector_CISectorPtr[sector_index]->GetLighting();
long z=static_cast<long>((PlayerZ-level)*(WindowYCenter));
long x1;
long x2;
long x;
long y;
x1=sVisualPlanes_Bottom.MinX;
x2=sVisualPlanes_Bottom.MaxX;
if (x2<x1) return;
long y_top=sVisualPlanes_Bottom.TopY[x1];
long y_bottom=sVisualPlanes_Bottom.BottomY[x1];
for(y=y_top;y<=y_bottom;y++) X_Table[y]=x1;
for(x=x1;x<=x2;x++)
{
long zd;
long y1=sVisualPlanes_Bottom.TopY[x];
long y2=sVisualPlanes_Bottom.BottomY[x];
if (y2<y1) continue;//при возможных пропусках точек на границах (а они есть), алгоритм развалится
//если верхняя линия поднимается
while(y1<y_top)
{
y_top--;
X_Table[y_top]=x;
}
//если нижняя линия опускается
while(y2>y_bottom)
{
y_bottom++;
X_Table[y_bottom]=x;
}
//если верхняя линия опускается
zd=(y_top-WindowYCenterWithOffset)+1;
while(y_top<y1)
{
long dist=z/zd;
long scale=dist/zd;
DrawTextureLine(dist,scale,bright,texture,y_top,X_Table[y_top],x-1);
y_top++;
zd++;
}
//если нижняя линия поднимается
zd=(y_bottom-WindowYCenterWithOffset)+1;
while(y_bottom>y2)
{
long dist=z/zd;
long scale=dist/zd;
DrawTextureLine(dist,scale,bright,texture,y_bottom,X_Table[y_bottom],x-1);
y_bottom--;
zd--;
}
}
//заливаем промежуток между top и bottom
long zd=(y_top-WindowYCenterWithOffset)+1;
for(y=y_top;y<=y_bottom;y++,zd++)
{
long dist=z/zd;
long scale=dist/zd;
DrawTextureLine(dist,scale,bright,texture,y,X_Table[y],x2);
}
}
Здесь DrawTextureLine рисует одну горизонтальную линию текстуры пола или потолка. При выводе используется буфер начальных координат X для каждой координаты Y: long X_Table[WINDOW_HEIGHT].
Сначала в этот буфер мы записываем MinX для первого столбца. Идея тут в том, что при проходе по столбцам мы отслеживаем, как ведёт себя координата Y. Если для левой границы при выводе пола верхняя координата уменьшается, а нижняя увеличивается, мы отмечаем этот факт в буфере начальных координат по X для данных координат Y (X_Table[y]). Но если изменение Y пойдёт в обратную сторону, значит, мы перешли к “закрыванию” линии и перед закрытие линию нужно текстурировать. Этот фокус работает потому, что мы используем выпуклые сектора. Кстати, при выводе сцены с помощью BSP-дерева, следует помнить, что выводится стена целиком, при этом её части могут быть перекрыты другими стенами (при выводе в этих местах линии горизонта установлены в TopLine[x]>BottomLine[x]), а это значит, что при таких разрывах требуется запускать текстурирование полов и потолков и начинать формировать таблицу VisualPlanes заново. В методе порталов таких проблем нет, там стена всегда отсекается по порталу.
Текстурирование с помощью VisualPlanes
В моём движке можно наклонять голову. Это делается сдвигом координат центра экрана на величину, равную тангенсу угла наклона, умноженного на половину высоты экрана. Разумеется, это даёт эффект искажения картинки, столь известный по играм на движке Build.
Также в движке есть освещение. Ну тут совсем всё просто – чем дальше от игрока (координата Z), тем темнее. И для стен и для полов/потолков реализация такого затемнения сложности не представляет.
Ну вот, вроде как и всё.
В архиве лежит сам движок и редактор карт (пока до конца недоделанный – например, нельзя изменить стартовую позицию игрока). Не пугайтесь, если в исходниках увидите многочисленные сдвиги (>> и <<) – местами я использовал вычисления с фиксированной точкой.
В движке управление – курсор, мышка, F1-F3-смена класса движков (экранный портал, геометрический портал, BSP-дерево), F5-сохранить координаты игрока, F9-восстановить координаты игрока.
Автор: da-nie
