February 14th, 2013

Duke Nukem 3D: Chocolate Duke Nukem 3D (PART 4 OF 4) >>

Chocolate Duke Nukem 3D is a port of Duke Nukem 3D aimed at education. The main goal is to clarify the code so programmers can extract knowledge easily and get a better idea of what it was to program game engines in the 90s.

Like an archeologist working on bones it was important to keep things the way they were and only the "dust" has been removed with focus on:

Binaries

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

If you want to play Chocolate Duke Nuken 3D anyway, just download the source code which features an XCode/Visual Studio project and built it : Link to the source code.

Portability

The lack of portability was an issue now Chocolate Duke Nukem 3D compiles on Windows, Intel MacOS X and Linux is one makefile away. Here is what has been done:

The code is much more portable but still not 64 bits ready: More work is still necessary in the interface between the Engine Module and the Drawing Module where memory address are manipulated as 32 bits integers. This part will require many hours and I am unsure I will be able to dedicate that much time.

Understandability

Most of the workload went into making the code easy to read. Here is a list of what was done:

Modules definition


The vanilla source code was essentially contained in three translation units:





The code has been redistributed in units that give a clear idea of what the code inside does :

I was tempted to break down Engine.c into a frontend and backend: Mimicking the Quake3/Doom3 architecture with two parts communicating via the bunch stack. In the end I judged it too far from the original spirit of the engine and dropped the idea.

Data structure

Build used struct to communicate with the Game Module via build.h but internally everything was done with arrays of primitive data types: No struct and no typedef.
This has been modified and especially with regards to the Visual Surface Determination and Filesystem:

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:



    // A typical GRP index entry:
    //     - 12 bytes for filename
    //     -  4 for filesize
    typedef uint8_t  grpIndexEntry_t[16]; 

    typedef struct grpArchive_s{
        int32_t  numFiles             ;//Number of files in the archive.
        grpIndexEntry_t  *gfilelist   ;//Array containing the filenames.
        int32_t  *fileOffsets         ;//Array containing the file offsets.
        int32_t  *filesizes           ;//Array containing the file offsets.
        int fileDescriptor            ;//The fd used for open,read operations.
        uint32_t crc32                ;//Hash to recognize GRP archives: Duke Shareware, Duke plutonimum etc...
    } grpArchive_t;

    //All GRP opened are in this structure
    typedef struct grpSet_s{

       grpArchive_t archives[MAXGROUPFILES];
       int32_t num;

    } grpSet_t;

	 

Symbols name sanitization

Variable names have been modified when they provided little clue about their usage:

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

    // This is the structure emitted for each wall that is potentially visible.
    // A stack of those is populated when the sectors are scanned.
    typedef struct pvWall_s{
        vector_t cameraSpaceCoo[2]; //Camera space coordinates of the wall endpoints. Access with vector_index_e.
        int16_t sectorId;           //The index of the sector this wall belongs to in the map database.
        int16_t worldWallId;        //The index of the wall in the map database.
        coo2D_t screenSpaceCoo[2];  //Screen space coordinate of the wall endpoints. Access with screenSpaceCoo_index_e.
    } pvWall_t;

    // Potentially Visible walls are stored in this stack.
    pvWall_t pvWalls[MAXWALLSB];


Comments and documentation

Magic numbers

I haven't had the time to remove all the magic numbers. Change decimal literal in favor of enum or #define would improve readability a lot.

Memory allocation

Chocolate Duke attemps to avoid global variables. Especially if they are used only for the lifetime of a frame. In those cases the memory used will be on the stack:

Before:


    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:
    Scan through sectors using portals (a portal is wall with a nextsector attribute >= 0).
    Flood is prevented if a portal does not face the POV.
    */
    static void scansector (short sectnum)
    {
    
        //The stack storing sectors to visit.
        short sectorsToVisit[256], numSectorsToVisit;
        .
        .
        .
    }
   
	


Note : Be careful when using a stack frame to store big variables. The following code ran well when compiled on clang and gcc but failed with 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 occurred because Visual Studio reserves only 1MB for the Stack by default. Trying to use 1MB overflowed the stack and that made chkstk very unhappy. This code ran fine with Clang on Mac OS X.

Source code

The source code is available on github.

Comments

 

Fabien Sanglard @2013