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

в 7:30, , рубрики: duke nukem 3d, Алгоритмы, анализ исходных кодов, разработка игр, старые игры

image

[Перевод первой части находится здесь.]

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

Build — это выдающийся движок, а множество игр, использовавших его, принесли большую и заслуженную славу и Кену Силверману, и 3D Realms.

Кен Силверман выполнил условия договора: он предоставил двоичный файл потрясающего 3D-движка с хорошо задокументированными методами и форматами ресурсов. В качестве признания его заслуг 3D Realms указала его имя в титрах как «Ken 'I can do that' Silverman» (Кен «Я могу это сделать» Силверман). Но разработка Build была сосредоточена на возможностях и скорости, а не удобстве портирования и чтения. После изучения кода я думаю, что open source-разработчики избегали его по следующим причинам:

  • Его обескураживающе сложно читать и получать из него знания.
  • Он не был портируемым.

В этой статье я перечислил часть сложностей, с которыми столкнулся. Также я выпустил порт Chocolate Duke Nukem 3D, призванный решить эти проблемы. Я хотел, чтобы люди запомнили, какой уровень гениальности нужен был для создания 3D-движка в то время. Кроме того, я хотел, чтобы они осознали, как движимый страстью подросток смог внести вклад в одну величайших игр всех времён.

Сложность в понимании

  • Вся база кода состоит всего из трёх модулей, поэтому сложно в уме разбить их на подмодули.
  • typedef и struct не используются внутри (используются только для публичных данных: sectortype, walltype и spritetype). Применяются только массивы примитивных типов данных (например: файловая система GRP): 
    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): 
    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);
}

  • Процедуры отрисовки были написаны на оптимизированном вручную ассемблере x86. Позже они были портированы обратно на C, но их всё равно невероятно трудно читать.
  • Символьные названия иногда противоречивы: 
    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];

  • В коде встречаются загадочные «магические» числа (особенно при манипуляциях со стенами, полом и потолком).
  • Основные модули трансляции (game.c и engine.c) настолько большие, что тормозят IDE. Иногда вплоть до сбоя XCode.

Сложность портирования

  • Предполагается использование процессора с прямым порядком байтов (Little-Endian).
  • Использование в движке типа long предполагает, что данные будут всегда иметь длину 32 бита.
  • Предполагаются 32-битные адреса и они обрабатываются как целые числа.
  • Оптимизированный вручную ассемблер x86 без аналога кода на C.
  • Ожидается 120 циклов на кадр: так работал таймер DOS.
  • Нет слоя абстракции. «Сырые» вызовы файловой системы/рендерера.

Утерянные ресурсы

Кен Силверман когда-то поучаствовал в создании порта JonoF и опубликовал множество объяснений своих алгоритмов. К сожалению, форум уже не работает из-за спама. Похоже, что вся эта ценная информация утеряна!

Я с сожалением закрыл форум на сайте. Из-за спам-ботов стало невозможно управлять им, и хотя в постах есть ценный контент, моё время и время модераторов не стоит того.

Если вы хотите сохранять связь с сообществом, то предлагаю обратиться к форумам на Duke4.net.

image

Chocolate Duke Nukem 3D

Chocolate Duke Nukem 3D — это порт Duke Nukem 3D, предназначенный для обучения. Его основная цель — упорядочить код, чтобы программисты могли удобно получать из него знания и лучше осознавали, каково это было — программировать игровые движки в 90-х.

Подобно археологу, работающему с костями, мне важно было сохранить всё «как есть», и избавиться только от «пыли», сосредоточившись на:

  • Читаемости: сделать код удобным для понимания.
  • Портативности: сделать код простым в компилировании, запуске и проведении экспериментов.

Двоичный код

Это порт для разработчиков игр, которые хотят узнать об архитектуре и исходном коде Duke Nukem 3D. Если вы просто хотите поиграть в игру, то рекомендую воспользоваться EDuke32.

Если вы всё-таки хотите поиграть в Chocolate Duke Nukem 3D, то просто скачайте исходный код, представляющий собой проект XCode/Visual Studio, и соберите его: ссылка на исходный код.

Портируемость

Нехватка портируемости была проблемой. Теперь 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, что гарантирует наличие знака.
  • Устранение платформозависимого API. Когда точность таймера SDL была средней, у порта появлялись проблемы с обеспечением обязательных 120 циклов на кадр. Теперь движок либо использует SDL, либо обеспечивает платформенную реализацию для POSIX и Windows.

Код стал гораздо более портируемым, но всё ещё не готов для 64 бит: нужно ещё поработать над интерфейсом между модулем движка и модулем отрисовки, в котором адреса памяти обрабатываются как 32-битные целые числа. На эту часть надо потратить много часов, и я не уверен, что смогу уделить столько времени.

Понимаемость

Больше всего усилий ушло на упрощение читаемости кода. Вот как я этого добивался:

Переназначение модулей

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

«Ванильный» исходный код в сущности состоял из трёх транслируемых модулей:

  • Engine.c: примерно 95% кода.
  • a.c: содержит грубую реализацию на C того, что было когда-то оптимизированным ассемблером.
  • cache1d.c: содержит систему кэширования и файловую систему GRP.

Анализ исходного кода Duke Nukem 3D: Часть 2 - 4

Код был переразбит на модули, дающие чёткое представление о том, что содержится внутри:

  • 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 движок Build использовал struct, но внутри всё было организовано через массивы примитивных типов данных, без struct и typedef.

Я внёс изменения, особенно в части, относящейся к определению видимых поверхностей (Visual Surface Determination) и к файловой системе:

До:

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];

После:

// Стандартная запись индекса 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;

Улучшение символьных имён

Я изменял те имена переменных, которые мало помогали в понимании их назначения:

До:

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];

После:

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];

Комментарии и документация

  • Документация: поскольку посты на форуме JoFo утеряны, я надеюсь, что первая часть статьи о внутренностях Build поможет разработчикам в понимании высокоуровневой архитектуры движка.
  • Комментарии: в этот пункт я старался вложить больше всего усилий. Я абсолютно уверен в преимуществе обилия комментариев в коде (Dmap — отличный пример исходников, где комментариев больше, чем кода).

«Магические» числа

У меня не было времени избавиться от всех «магических» чисел. Замена десятичных литералов на enum или #define значительно улучшит читаемость кода.

Распределение памяти

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

До:

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;

После:

/*
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.

Автор: PatientZero

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js