Duke Nukem II Map Format

From ModdingWiki
Jump to: navigation, search
Duke Nukem II Map Format
Duke Nukem II Map Format.png
Format typeMap/level
Map type2D tile-based
Layer count3
Tile size (pixels)8×8
Viewport (pixels)256×160
Games

Duke Nukem II stores its levels in an evolution of the level format used by Cosmo's Cosmic Adventures. One considerable change is the addition of a second map layer, allowing foreground and background tiles to be placed in the same cell. Surprisingly, given the number of other changes to the file format, the layer data was not restructured to handle this new feature. Instead, some of the new data was shoehorned to fit in the existing space, with the rest of the data tacked on to the end of the file in a somewhat clunky manner. This resulted in some unusual limitations, such as a small number of tiles that can only be placed in the foreground layer if there is no background tile in the same cell.

File format

The file is in this basic layout:

Data type Description
UINT16LE iBackgroundOffset Offset where the background layer starts
char cCZoneName[13] CZone filename (tileset)
char cBackdropName[13] Name of the graphic to use as the level background (one of the BD*.MNI files)
char cMusicName[13] Name of the IMF file to use as background music
BYTE bFlags Level flags (define type of parallax scrolling and more)
BYTE bAltBackdrop Number of alternate backdrop file, zero if no alternate backdrop is used
UINT16LE iUnknown Unknown value, is zero in all original levels
UINT16LE iActorSize Number of UINT16 values in the actor block
ACTORDATA actorData[] Variable-length array of all the actors in the level
GRIDLAYER gridData see #Foreground and Background Layers below for what this contains
UINT16LE iExtraFGLength Length of the additional mask/foreground manipulation data
BYTE iExtraFGData[iExtraFGLength] See #Supplemental foreground data below
char cAttrName[13] Zone attribute filename
char cTileName[13] Zone tile filename
char cMaskName[13] Zone masked tiles filename

The three filenames at the end of the level file never appear to be used. In fact, the level files can end directly after the supplemental foreground data and the game will still load them without reporting any errors. These are probably the names of Cosmo-style tileset files ("zones") that were used before the CZone format (the "c" probably stands for "compound") was introduced.

For all level files of the full version, the iActorSize value is reliable and the gridData begins directly after the last actor, leaving no padding between actor data and grid data.

Level Flags

This is what each bit in the bFlags value indicates:

Bit | Description
----+------------
 7  | switch backdrop when using teleporter (used in L1)
 6  | switch backdrop when destroying force field (used in L5)
 5  | earthquake
 4  | permanent backdrop movement ^^
 3  | permanent backdrop movement <<
 2  | ??? (not set in any level)
 1  | x-scrolling backdrop
 0  | x- and y-scrolling backdrop

Bits 6 and 7 require an alternate backdrop index. The files where these bits are set are also the only files that have a non-zero alternate backdrop number.

Most of the bits can NOT be combinated! For example, combining bits 3 and 4 will not lead to combined movement. The game probably treats parts of the flags byte as a number, not as individual bits.

Foreground and Background Layers

At the offset indicated by iBackgroundOffset in the header, the grid/cell data begins:

Data type Description
UINT16LE iMapWidth Map width (in tiles)
UINT16LE iMapData[32750] Actual map data

Each "element" in iMapData refers to the foreground and/or background tile used in a single grid cell. The grids are arranged left to right, top to bottom, so the index can be calculated by this formula:

int iIndex = (y * iMapWidth) + x;
iMapData[iIndex] = <new value to set at x,y>

The map data is a constant 32750 UINT16LE cells long (65500 bytes), so the map height can be calculated from this:

int iMapHeight = 32750 / iMapWidth;

Mapping cell values to tiles

The method of mapping elements in the iMapData structure into tiles is a little complicated. There are two different methods of storing values:

  1. If the most significant bit is set (iMapData[x] & 0x8000) then the cell contains both a foreground and background tile.
  2. Otherwise the cell value is a raw pixel-based index into the tilemap.

Most significant bit set

If the most significant bit is set (iMapData[x] & 0x8000) then the cell value contains two indices - one for the solid/background tile, and one for the masked/foreground tile. Unlike the other type of cell value, these are actual tile indices as opposed to pixel indexes (i.e. a value of 2 refers to the third tile.)

The lower ten bits are the index of the background tile (this can provide a value between 0 and 1023, however since there are only 1000 tiles this value should always be less than 1000.) The lower ten bits can be isolated like this:

iSolid = iMapData[x] & 0x03FF;

The ignoring the most significant bit (which is used to indicate this type of tile value) the remaining five most significant bits are used as the index of the foreground/mask tile. These bits can be isolated as follows:

iMask = (iMapData[x] >> 10) & 0x1F;

This only provides a value between 0 and 31 - but since there are 160 masked tiles, this value needs to be further manipulated to produce an index into the masked tileset. An additional two bits per tile are stored in the #Supplemental foreground data which are used for this purpose, but this will still only allow the first 127 tiles to be used.

Most significant bit NOT set

If the most significant bit is not set, then the cell value is a pixel index into the tilemap. Imagine the tileset laid out left to right all on the one row. Since each tile is 8x8 pixels, at 16 pixels into the image, the third tile will begin (x = 0 for first tile, x = 8 for second tile, x = 16 for third tile.) The cell value is essentially x-coordinate in the previous value (if it's 16, then the third tile should be displayed in that cell.)

Note that in the CZone tileset file, the solid tiles are made up of 1000 4-plane (16-colour) images, and these are followed by 160 5-plane images (16-colour + transparency.) Although seperate images, they appear to be concatenated when the game loads them, as the cell value will be zero for the first solid tile, it will be eight for the second solid tile, it will be 7992 for the last solid tile, and it will be 8000 for the first masked tile.

This means that if the solid and masked tiles have been treated as separate images, a check will need to be performed so that any cell value below 8000 is loaded from the solid tileset, and any value larger than this is loaded from the masked tileset (after subtracting 8000 from the cell value, to put it at zero for the first masked tile.) Having said that, for some reason the values for the masked tiles are at multiples of five tiles (tile #0 (x=0) is the first tile, tile #5 (x=40) is the second tile.)

Note that while the cell value cannot be out of range for the solid tiles/background layer (since any values larger than 8000 will be loaded from the masked tileset into the foreground layer) the cell values for the masked tileset have no such restriction.

Supplemental foreground data

Since the tiles containing combined foreground+background data only provide five bits for the foreground tile, this block of data is used to store an additional two bits for each tile, allowing a seven-bit tile number to be specified.

The data is stored in a form of run length encoding (RLE) to reduce the size, given that a relatively small number of tiles need the extra two bits. Because there are eight bits in a byte, four lots of two-bit-chunks can be stored in every data byte. This means each data byte contains the data for four tiles. The rest of this section uses the term "tile cluster" to refer to this grouping of four tiles.

Data layout

The data is read one byte at a time, and the initial byte ("length-byte") indicates how many subsequent bytes need to be read. The length-bytes are signed byte values with the absolute value giving the length to be used for the following data. If the length-byte is positive (high bit is NOT set), then it is a count of the number of affected tile clusters. The following byte is the data byte containing the extra tile data. For example: (brackets inserted for clarity)

[7F 00]  [7F 00]  [05 FF]  [7F 00]

This means apply value 00 to the first 254 (0x7F * 2) tile clusters, followed by value FF to the next five tile clusters, followed by 00 to the next 127 tile clusters. The format of these "values" is described below.

If the length-byte is negative (high bit IS set), then a number of data values follow, depending on the absolute value of the length-byte. If the bytes are arranged like this:

[FF 12]  [FE 34 56]  [FF 78]  [FD 9A BC DE]  [00 00]

Then it would be interpreted as follows:

  1. FF == one - apply value 12 to one tile cluster
  2. FE == two - apply 34 to one tile cluster, then 56 to the following tile cluster
  3. FF == one - apply 78 to one tile cluster
  4. FD == three - apply 9A to one tile cluster, BC to the next, and DE to the third tile cluster
  5. 00 == end of data

An easy way to work out how many bytes are affected is this formula:

iCount = 0x100 - iInitialByte

This will return one for 0xFF, two for 0xFE, three for 0xFD, etc. If your variables are signed bytes, you can just use iCount = -iInitialByte instead. A loop can then be used to apply the change to the correct number of tile clusters.

The last two bytes of the compressed data are always zero, which would always be read when the RLE algorithm expects to read a length-byte. So it should be safe to stop decompressing when you read 0 as length value.

Note that since the length is the absolute value of a signed byte, the maximum length for both kinds of RLE flag is 127. A length-byte of 0x80 indicates an error. This is because 0x80 (-128) can't have a positive absolute value as the largest positive value in a signed byte is 127. If the game encounters a length-byte of 0x80 upon loading a level file, it will freeze after fading to black from the loading screen.

Data values

Each of the data values used above affects a tile cluster made up of four tiles. If the tiles are arranged from left to right, the least-significant bits affect the first (left-most) tile, and the most-significant bits affect the last (right-most) tile. For example:

tile1 =  (iChange       & 0x03);
tile2 = ((iChange >> 2) & 0x03);
tile3 = ((iChange >> 4) & 0x03);
tile4 =  (iChange >> 6);

This will give tileX a value between 0 and 3, which when multiplied by 32 can be directly added to the value of the foreground tile. For the computer scientists out there, a more efficient alternative is this:

tile1 = (iChange << 5) & 0x60;
tile2 = (iChange << 3) & 0x60;
tile3 = (iChange << 1) & 0x60;
tile4 = (iChange >> 1) & 0x60;

The values here are already multiplied out, and can be OR'd with the foreground tile numbers.

One major thing to remember is that these extra values ONLY apply to those tiles where a foreground and a background tile is specified in the map data. If the tile only has a background tile, or it only has a foreground tile, then it's possible to specify the full range of tile numbers and the values stored here (if any) should be ignored for those tiles. It's only when a tile has a foreground *and* a background tile that these extra bits must be used.

Example

This is some example code to read in all the tile values into an array, which the map code can later reference as necessary:

int *iExtraValues = new int[65500 / 2]; // one element per tile, maps are fixed length
int *pNextByte = iExtraValues; // running counter

// Read through all the extra data
for (int i = 0; i < iExtraFGLength; i++) {
  unsigned char iVal = readNextByte(); // must be 8-bit for logic below to work

  if (iVal & 0x80) {
    // Multiple bytes concatenated together
    // iVal == 0xFF for one byte, 0xFE for two bytes, etc.
    while (iVal++ > 0) { // should eventually wrap from 0xFF to 0x00 when we're done - only works with an 8-bit variable though
      applyChange(&pNextByte, readNextByte());
      i++;
      assert(iVal < 0x100); // prevent headaches if someone uses an int instead
    }
  } else {
    // iVal <= 0x7F
    UINT8 iChange = readNextByte(); i++;

    if (iChange > 0) {
      // Apply this change iVal times
      while (iVal-- > 0) applyChange(&pNextByte, iChange);
    } else {
      // No changes to the tiles, just skip over them (faster than applying a
      // change of 0x00 to all these tiles!)
      pNextByte += iVal * 4;
      // NOTE: This will only work if you zero the array first - if you don't,
      // use a loop here to zero out the tiles instead.
    }
  }
}

inline void applyChange(int **ppNextByte, int iChange)
  throw ()
{
  // Grab each lot of 2-bits and shift into bits 5&6
  **ppNextByte = (iChange << 5) & 0x60; (*ppNextByte)++; //       10 ->  65
  **ppNextByte = (iChange << 3) & 0x60; (*ppNextByte)++; //     32   ->  65
  **ppNextByte = (iChange << 1) & 0x60; (*ppNextByte)++; //   54     ->  65
  **ppNextByte = (iChange >> 1) & 0x60; (*ppNextByte)++; // 76       ->  65
  return;
}

Example

The following code converts a cell value into two tile indices for that cell - an index into the solid/background tilemap, and another index into the mask/foreground tileset.

#define DN2_NUM_SOLID_TILES  1000
#define DN2_NUM_MASKED_TILES  160
#define DN2_TILEWIDTH           8  // Tiles are 8x8

int iSolid, iMasked;        // Index into respective tilesets
int iValue = iMapData[x];   // This is the cell to convert
int iExtra = iExtraData[x]; // Extra data for this cell

if (iValue & 0x8000) {
  // Most significant bit is set (see #Most significant bit set above),
  // so this cell has a foreground *and* a background tile.

  // First 10 bits are the index of the solid tile
  iSolid = iValue & 0x3FF;

  // Remaining five bits (not counting the sixth bit which was used as
  // the 0x8000 flag above) are the index of the mask tile.
  iMasked = ((iValue >> 10) & 0x1F);

  // Add the extra two bits (see #Supplemental foreground data above)
  iMasked |= iExtra; // assumes iExtra has already been multiplied out
  //iMasked = iMasked + (iExtra * 32); // if it hasn't been multiplied out

} else if (iValue < DN2_NUM_SOLID_TILES * DN2_TILEWIDTH) {
  // Background only tile (see #Most significant bit NOT set above)

  // Convert the number from a pixel coordinate into a tile unit.
  iSolid = iValue / 8;

  iMasked = -1;  // No mask tile in this cell

} else {
  // Foreground only tile (see #Most significant bit NOT set above)

  // Convert the number from a pixel coordinate into a tile unit.
  int iRawIndex = iValue / 8;

  // Make the first masked tile start at zero, instead of following on
  // from the solid tiles.
  int iMaskIndex = iRawIndex - DN2_NUM_SOLID_TILES;

  // For some reason the mask index has five images per tile...or something.
  iMasked = iMaskIndex / 5;

  // No solid tile in this cell, so using zero will make the solid cell
  // transparent, allowing the map backdrop to show through.
  iSolid = 0;
}

Gotchas

  • The masked tileset has no "blank" tile, so if the foreground layer is being loaded into an array a value will need to be used to indicate that no foreground tile occupies that cell. Zero can't be used without tweaking, as masked tile zero is an actual graphic tile.
  • The first tile in the solid tileset is used as a transparent tile. It will appear as a red square if drawn (e.g. in a map editor) however the game does not draw this tile, so any cells with this as the background cell will be where the map backdrop shows through.
  • Even with the supplemental foreground data, there are only seven bits available for the foreground tile. This means that only 127 of the 160 available tiles can be used!

Actor data

The actorData block is in the following format:

Data type Description
UINT16LE iType Type of actor
UINT16LE iX X-coordinate of actor (in tile units)
UINT16LE iY Y-coordinate of actor (in tile units)

Because the iActorSize value in the header is in UINT16s and there are three UINT16s per actor, the number of actors can be obtained quite simply:

iNumActors = iActorSize / 3

The iType field can conveniently be used as an index into the ACTRINFO.MNI sprite file. If iType is zero, the first actor image is used.

Not all actors have images however, some point to actor sprites with zero frames. It appears to be that some of these "actors" are actually flags, indicating that the next actor (in the level, not in the ACTRINFO.MNI) will only appear when the level is played at a certain difficulty level.

Tools

The following tools are able to work with files in this format.

Name PlatformView? Create new? Modify? Access hidden data? Edit metadata? Notes
Nukem2Print QtYesNoNoN/AN/A

Credits

This file format was reverse engineered by Dave Bollinger. Most of this info came from the specs on his website. Szevvy figured out how to map the cell values back to the tilesets. Malvineous figured out the format of the supplemental foreground data. If you find this information helpful in a project you're working on, please give credit where credit is due. (A link back to this wiki would be nice too!)