[The translation of the first part is here .]

Legacy code

Build is an outstanding engine, and the many games that used it brought great and well-deserved fame to both Ken Silverman and 3D Realms.

Ken Silverman complied with the terms of the contract: he provided a binary file of an amazing 3D engine with well-documented methods and formats of resources . In recognition of his merits, 3D Realms indicated his name in the credits as “Ken 'I can do that' Silverman” (Ken “I can do this” Silverman). But Build's development focused on features and speed, rather than portability and readability. After studying the code, I think that open source developers avoided it for the following reasons:

• It is discouragingly difficult to read and receive knowledge from.
• It was not portable.

In this article, I have listed some of the difficulties that I have encountered. I also released the Chocolate Duke Nukem 3D port, designed to solve these problems. I wanted people to remember what level of genius was needed to create a 3D engine at that time. In addition, I wanted them to realize how a passionate teenager could contribute to one of the greatest games of all time.

Difficulty in understanding

• The entire code base consists of only three modules, so it is difficult to break them down into submodules in the mind.
• typedefand structnot used inside (used only for public data: sectortype, walltype, and spritetype). Only arrays of primitive data types are used (for example: GRP file system ):
  
  

  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]

  
  
• Comments are few. Therefore, mathematical methods are difficult to understand (for example: 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);
  }

  
  
• The rendering procedures were written in manually optimized x86 assembler. They were later ported back to C, but they are still incredibly difficult to read .
• Character names are sometimes contradictory :
  
  

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

  
  
• The code contains mysterious "magic" numbers (especially when manipulating walls, floors and ceilings).
• The main translation modules (game.c and engine.c) are so large that they slow down the IDE. Sometimes up to Xcode crashes.

Porting Difficulty

• It is supposed to use a processor with direct byte order (Little-Endian).
• Using a type in the engine longassumes that the data will always be 32 bits long.
• 32-bit addresses are assumed and they are treated as integers.
• Manually optimized x86 assembler without C code equivalent.
• 120 cycles per frame are expected: this is how the DOS timer worked.
• There is no abstraction layer. Raw file system / renderer calls.

Lost resources

Ken Silverman once participated in the creation of the JonoF port and published many explanations of his algorithms. Unfortunately, the forum is no longer working due to spam. It seems that all this valuable information has been lost!

I regretfully closed the forum on the site. Spam bots made it impossible to manage it, and although the posts have valuable content, my time and the time of the moderators are not worth it.

If you want to keep in touch with the community, I suggest referring to the forums on Duke4.net.

Chocolate Duke Nukem 3D

Chocolate Duke Nukem 3D is a Duke Nukem 3D port for learning . Its main goal is to streamline the code so that programmers can conveniently get knowledge from it and better realize what it was like to program game engines in the 90s.

Like an archaeologist working with bones, it was important for me to keep everything “as is” and get rid of only “dust”, focusing on:

• Readability: Make code easy to understand.
• Portability: make code easy to compile, run, and experiment.

Binary code

This is a port for game developers who want to learn about the architecture and source code of Duke Nukem 3D. If you just want to play the game, then I recommend using EDuke32 .

If you still want to play Chocolate Duke Nukem 3D, then just download the source code, which is an XCode / Visual Studio project, and compile it: a link to the source code .

Portability

Lack of portability was a problem. Now Chocolate Duke Nukem 3D compiles for Windows, Intel MacOS X and Linux. Here's how it was done:

• Using internal type aliases now provides the correct size for integers. The type was longused everywhere, because during development it was believed that this type would always be 32 bits long. This is one of the reasons why the engine could not be compiled in 64-bit mode. Used int32_tfrom standard inttypes.h.
• Getting rid ofchar for arithmetic operations: since depending on the platform it can be signedor unsigned, use charfor mathematical calculations led to an unpleasant shift; charshould be used only for strings. For arithmetic operations, Build is now explicitly used in int8_tor uint8_tout inttypes.h, which guarantees the presence of a sign.
• Elimination of a platform-specific API . When the accuracy of the SDL timer was average, the port had problems providing the required 120 cycles per frame. Now the engine either uses SDL or provides a platform implementation for POSIX and Windows.

The code has become much more portable, but still not ready for 64 bits: we still need to work on the interface between the engine module and the rendering module , in which the memory addresses are processed as 32-bit integers. Many hours must be spent on this part, and I'm not sure that I can devote so much time.

Comprehensibility

Most of the effort went into simplifying code readability. Here's how I got it:

Reassignment of modules

The “vanilla” source code essentially consisted of three translated modules:

• Engine.c: approximately 95% of the code.
• a.c: contains a crude C implementation of what was once an optimized assembler.
• cache1d.c: contains the caching system and the GRP file system.

The code has been repartitioned into modules giving a clear idea of ​​what is contained inside:

• Engine.c: now it contains 50% of the code.
• display.c: buffers of SDL surfaces in which the screen is rendered, palette utilities.
• draw.c: Implementation of assembly procedures in C.
• tiles.c: sprite engine.
• filesystem.c: all for creating an abstraction of the GRP file system.
• network.c: Multiuser network mode is not here.
• cache.c: random memory allocator and caching service.
• math.c: Most auxiliary fixed-point arithmetic functions are here.

I was tempted to split Engine.cinto a front-end and a back-end to emulate the Quake3 / Doom3 two-part architecture that exchanges data through the stack. But as a result, I decided that I was too far from the spirit of the original engine, so I rejected this idea.

Data structure

To build data with the game module via build.h, the Build engine used it struct, but inside everything was organized through arrays of primitive data types, without structand typedef.

I made changes, especially in the part related to the definition of visible surfaces (Visual Surface Determination) and the file system:

Before :

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

After :

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

Symbol Name Enhancement

I changed those variable names that helped little in understanding their purpose:

Before :

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

After :

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

Comments and documentation

• Documentation: Since the posts on the JoFo forum have been lost, I hope that the first part of the article on Build internals will help developers understand the high-level architecture of the engine.
• Comments: I tried to put the most effort into this item. I am absolutely sure of the advantage of having lots of comments in the code ( Dmap is a great example of source code, where there are more comments than code).

Magic numbers

I did not have time to get rid of all the "magic" numbers. Replacing decimal literals with enumor #definewill significantly improve code readability.

Memory allocation

In Chocolate Duke, I tried to avoid global variables. Especially if they are used during the life of the frame. In such cases, the used memory will be on the stack:

Until :

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;

After :

/*
FCS:
Сканирует секторы с помощью порталов (портал - это стена с атрибутом nextsector >= 0).
Заливка не выполняется, если портал не направлен в сторону точки обзора.
*/
static void scansector (short sectnum)
{
    //Стек, содержащий секторы, которые нужно посетить.
    short sectorsToVisit[256], numSectorsToVisit;
    .
    .
    .
}

Note: Be careful when using the stack frame to store large variables. The following code executed normally when compiling in clang and gcc, but resulted in an error in 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)   ;
    .
    .
    .
}

A stack overflow error occurs because, by default, Visual Studio reserves only 1 MB for the stack. Attempting to use 1 MB results in a stack overflow, which is a poor digest chkstk. This code will execute normally in Clang on Mac OS X.

Source

Source code is available on Github .