- PVSM.RU - https://www.pvsm.ru -
[Перевод первой части находится здесь [1].]
Build — это выдающийся движок, а множество игр, использовавших его, принесли большую и заслуженную славу и Кену Силверману, и 3D Realms.
Кен Силверман выполнил условия договора: он предоставил двоичный файл потрясающего 3D-движка с хорошо задокументированными методами и форматами ресурсов [2]. В качестве признания его заслуг 3D Realms указала его имя в титрах [3] как «Ken 'I can do that' Silverman» (Кен «Я могу это сделать» Силверман). Но разработка Build была сосредоточена на возможностях и скорости, а не удобстве портирования и чтения. После изучения кода я думаю, что open source-разработчики избегали его по следующим причинам:
В этой статье я перечислил часть сложностей, с которыми столкнулся. Также я выпустил порт Chocolate Duke Nukem 3D, призванный решить эти проблемы. Я хотел, чтобы люди запомнили, какой уровень гениальности нужен был для создания 3D-движка в то время. Кроме того, я хотел, чтобы они осознали, как движимый страстью подросток смог внести вклад в одну величайших игр всех времён.
typedef
и struct
не используются внутри (используются только для публичных данных: sectortype
, walltype
и spritetype
). Применяются только массивы примитивных типов данных (например: файловая система GRP [4]):
static long numgroupfiles = 0;
static long gnumfiles[MAXGROUPFILES];
static long groupfil[MAXGROUPFILES] = {-1,-1,-1,-1};
static long groupfilpos[MAXGROUPFILES];
static char *gfilelist[MAXGROUPFILES];
static long *gfileoffs[MAXGROUPFILES];
static char filegrp[MAXOPENFILES];
static long filepos[MAXOPENFILES];
static long filehan[MAXOPENFILES]
inside (long x, long y, short sectnum){
walltype *wal;
long i, x1, y1, x2, y2;
unsigned long cnt;
if ((sectnum < 0) || (sectnum >= numsectors)) return(-1);
cnt = 0;
wal = &wall[sector[sectnum].wallptr];
i = sector[sectnum].wallnum;
do{
y1 = wal->y-y; y2 = wall[wal->point2].y-y;
if ((y1^y2) < 0){
x1 = wal->x-x; x2 = wall[wal->point2].x-x;
if ((x1^x2) >= 0) cnt ^= x1; else cnt ^= (x1*y2-x2*y1)^y2;
}
wal++; i--;
} while (i);
return(cnt>>31);
}
static long xb1[MAXWALLSB], yb1[MAXWALLSB], xb2[MAXWALLSB], yb2[MAXWALLSB];
static long rx1[MAXWALLSB], ry1[MAXWALLSB], rx2[MAXWALLSB], ry2[MAXWALLSB];
static short p2[MAXWALLSB], thesector[MAXWALLSB], thewall[MAXWALLSB];
long
предполагает, что данные будут всегда иметь длину 32 бита.Кен Силверман когда-то поучаствовал в создании порта JonoF [9] и опубликовал множество объяснений своих алгоритмов. К сожалению, форум уже не работает [10] из-за спама. Похоже, что вся эта ценная информация утеряна!
Я с сожалением закрыл форум на сайте. Из-за спам-ботов стало невозможно управлять им, и хотя в постах есть ценный контент, моё время и время модераторов не стоит того.
Если вы хотите сохранять связь с сообществом, то предлагаю обратиться к форумам на Duke4.net.
Chocolate Duke Nukem 3D [11] — это порт Duke Nukem 3D, предназначенный для обучения. Его основная цель — упорядочить код, чтобы программисты могли удобно получать из него знания и лучше осознавали, каково это было — программировать игровые движки в 90-х.
Подобно археологу, работающему с костями, мне важно было сохранить всё «как есть», и избавиться только от «пыли», сосредоточившись на:
Это порт для разработчиков игр, которые хотят узнать об архитектуре и исходном коде Duke Nukem 3D. Если вы просто хотите поиграть в игру, то рекомендую воспользоваться EDuke32 [12].
Если вы всё-таки хотите поиграть в Chocolate Duke Nukem 3D, то просто скачайте исходный код, представляющий собой проект XCode/Visual Studio, и соберите его: ссылка на исходный код [11].
Нехватка портируемости была проблемой. Теперь Chocolate Duke Nukem 3D компилируется под Windows, Intel MacOS X и Linux. Вот как это было сделано:
long
использовался везде, потому что при разработке считалось, что этот тип будет всегда длиной 32 бита. Это одна из причин, по которой движок нельзя было скомпилировать в 64-битном режиме. Используется int32_t
из стандартного inttypes.h
.char
для арифметических операций: поскольку в зависимости от платформы он может быть signed
или unsigned
, использование char
для математических вычислений приводило к неприятному сдвигу; char
следует использовать только для строк. Для арифметических действий в Build теперь явно используется int8_t
или uint8_t
из inttypes.h
, что гарантирует наличие знака.Код стал гораздо более портируемым, но всё ещё не готов для 64 бит: нужно ещё поработать над интерфейсом между модулем движка и модулем отрисовки, в котором адреса памяти обрабатываются как 32-битные целые числа. На эту часть надо потратить много часов, и я не уверен, что смогу уделить столько времени.
Больше всего усилий ушло на упрощение читаемости кода. Вот как я этого добивался:
«Ванильный» исходный код в сущности состоял из трёх транслируемых модулей:
Engine.c
: примерно 95% кода.a.c
: содержит грубую реализацию на C того, что было когда-то оптимизированным ассемблером.cache1d.c
: содержит систему кэширования и файловую систему GRP.
Код был переразбит на модули, дающие чёткое представление о том, что содержится внутри:
Engine.c
: теперь в нём 50% кода.display.c
: буферы поверхностей SDL, в которых рендерится экран, утилиты палитр.draw.c
: реализация ассемблерных процедур на C.tiles.c
: спрайтовый движок.filesystem.c
: всё для создания абстракции файловой системы GRP.network.c
: режим многопользовательской сети не здесь.cache.c
: распределитель произвольной памяти и служба кэширования.math.c
: большинство вспомогательных арифметических функций с фиксированной запятой находится здесь.
У меня было искушение разбить Engine.c
на фронтэнд и бекэнд в подражание архитектуре Quake3/Doom3, состоящей из двух частей, обменивающихся данными через стек. Но в результате я решил, что слишком отдалюсь от духа оригинального движка, поэтому отбросил эту идею.
Для обмена данными с игровым модулем через build.h [13] движок Build использовал struct
, но внутри всё было организовано через массивы примитивных типов данных, без struct
и typedef
.
Я внёс изменения, особенно в части, относящейся к определению видимых поверхностей (Visual Surface Determination) и к файловой системе:
До [4]:
long numgroupfiles = 0;
long gnumfiles[MAXGROUPFILES];
long groupfil[MAXGROUPFILES] = {-1,-1,-1,-1};
long groupfilpos[MAXGROUPFILES];
char *gfilelist[MAXGROUPFILES];
long *gfileoffs[MAXGROUPFILES];
char filegrp[MAXOPENFILES];
long filepos[MAXOPENFILES];
long filehan[MAXOPENFILES];
После [14]:
// Стандартная запись индекса GRP:
// - 12 байтов на имя файла
// - 4 байта на размер файла
typedef uint8_t grpIndexEntry_t[16];
typedef struct grpArchive_s{
int32_t numFiles ;//Количество файлов в архиве.
grpIndexEntry_t *gfilelist ;//Массив, содержащий имена файлов.
int32_t *fileOffsets ;//Массив, содержащий смещения файлов.
int32_t *filesizes ;//Массив, содержащий размеры файлов.
int fileDescriptor ;//fd используется для операций открытия и чтения.
uint32_t crc32 ;//Хэш для распознавания архивов GRP: Duke Shareware, Duke plutonimum и т.д...
} grpArchive_t;
//Все открытые GRP находятся в этой структуре
typedef struct grpSet_s{
grpArchive_t archives[MAXGROUPFILES];
int32_t num;
} grpSet_t;
Я изменял те имена переменных, которые мало помогали в понимании их назначения:
До [7]:
static long xb1[MAXWALLSB], yb1[MAXWALLSB], xb2[MAXWALLSB], yb2[MAXWALLSB];
static long rx1[MAXWALLSB], ry1[MAXWALLSB], rx2[MAXWALLSB], ry2[MAXWALLSB];
static short p2[MAXWALLSB], thesector[MAXWALLSB], thewall[MAXWALLSB];
После [15]:
enum vector_index_e {VEC_X=0,VEC_Y=1};
enum screenSpaceCoo_index_e {VEC_COL=0,VEC_DIST=1};
typedef int32_t vector_t[2];
typedef int32_t coo2D_t[2];
// Это структура, создаваемая для каждой потенциально видимой стены.
// Стек таких структур заполнялся при сканировании секторов.
typedef struct pvWall_s{
vector_t cameraSpaceCoo[2]; //Координаты конечных точек стен в пространстве камеры. Доступ осуществляется через vector_index_e.
int16_t sectorId; //Индекс сектора, которому принадлежит эта стена, в базе данных карты.
int16_t worldWallId; //Индекс стены в базе данных карты.
coo2D_t screenSpaceCoo[2]; //Координаты конечных точек стен в экранном прострастве. Доступ осуществляется через screenSpaceCoo_index_e.
} pvWall_t;
// В этом стеке хранятся потенциально видимые стены.
pvWall_t pvWalls[MAXWALLSB];
У меня не было времени избавиться от всех «магических» чисел. Замена десятичных литералов на enum
или #define
значительно улучшит читаемость кода.
В Chocolate Duke я пытался избежать глобальных переменных. Особенно если они используются в течение срока существования кадра. В таких случаях используемая память будет находиться в стеке:
До [17]:
long globalzd, globalbufplc, globalyscale, globalorientation;
long globalx1, globaly1, globalx2, globaly2, globalx3, globaly3, globalzx;
long globalx, globaly, globalz;
static short sectorborder[256], sectorbordercnt;
static char tablesloaded = 0;
long pageoffset, ydim16, qsetmode = 0;
После [18]:
/*
FCS:
Сканирует секторы с помощью порталов (портал - это стена с атрибутом nextsector >= 0).
Заливка не выполняется, если портал не направлен в сторону точки обзора.
*/
static void scansector (short sectnum)
{
//Стек, содержащий секторы, которые нужно посетить.
short sectorsToVisit[256], numSectorsToVisit;
.
.
.
}
Примечание: будьте аккуратны при использовании кадра стека для хранения больших переменных. Следующий код нормально выполнялся при компиляции в clang и gcc, но приводил к ошибке в Visual Studio:
int32_t initgroupfile(const char *filename)
{
uint8_t buf[16] ;
int32_t i, j, k ;
grpArchive_t* archive ;
uint8_t crcBuffer[ 1 << 20] ;
printf("Loading %s ...n", filename) ;
.
.
.
}
Происходит ошибка переполнения стека (stack overflow), потому что по умолчанию Visual Studio резервирует для стека только 1 МБ. Попытка использовать 1 МБ приводит к переполнению стека, что плохо переваривает chkstk
. Этот код будет нормально выполняться в Clang на Mac OS X.
Исходный код доступен на Github [11].
Автор: PatientZero
Источник [19]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/249052
Ссылки в тексте:
[1] здесь: https://habrahabr.ru/post/323426/
[2] хорошо задокументированными методами и форматами ресурсов: http://fabiensanglard.net/duke3d/BUILDINF.TXT
[3] указала его имя в титрах: http://fd.fabiensanglard.net/duke3d/Duke_credit.png
[4] файловая система GRP: https://github.com/fabiensanglard/vanilla_duke3D/blob/master/SRC/CACHE1D.C#L232
[5] inside: https://github.com/fabiensanglard/vanilla_duke3D/blob/master/SRC/ENGINE.C#L2733
[6] невероятно трудно читать: https://github.com/fabiensanglard/vanilla_duke3D/blob/master/SRC/drawing_routines/A.C
[7] противоречивы: https://github.com/fabiensanglard/vanilla_duke3D/blob/master/SRC/ENGINE.C#L130
[8] загадочные: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Engine/src/engine.c#L2220
[9] JonoF: http://www.jonof.id.au/
[10] форум уже не работает: http://www.jonof.id.au/forum/
[11] Chocolate Duke Nukem 3D: https://github.com/fabiensanglard/chocolate_duke3D
[12] EDuke32: http://eduke32.com/
[13] build.h: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Engine/src/build.h#L64
[14] После: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Engine/src/filesystem.c#L27
[15] После: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Engine/src/engine.c#L109
[16] Dmap: http://fabiensanglard.net/doom3/dmap.php
[17] До: https://github.com/fabiensanglard/vanilla_duke3D/blob/master/SRC/ENGINE.C#L180
[18] После: https://github.com/fabiensanglard/chocolate_duke3D/blob/master/Engine/src/engine.c#L334
[19] Источник: https://habrahabr.ru/post/323684/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.