Duke Nukem 1’s tile rendering

There are a few areas in Duke Nukem 1 which feature a pitch black background instead of the usual graphical one. Why is that – was it an aesthetic choice? Turns out, it’s actually an interesting trick used to work around limitations in the game’s tile rendering.

Compared to its sequel, the first game’s rendering engine is very simple. There’s only a single layer of tiles, which includes the background (more on that later). Tiles cannot overlap the background, nor can multiple tiles be stacked on top of each other (these features would be added in Cosmo’s Cosmic Adventure and Duke Nukem II, respectively). Sprites are then drawn on top, and that’s pretty much it. Aside from reflective floors used in some levels, there are no special effects – all the rendering is done by straightforward copying of 16×16 pixel blocks of graphics to the framebuffer.

Since there’s only one layer of tiles, tile drawing does not support any kind of partial transparency (aka masking) – tiles are always drawn as fully solid rectangles. Interestingly, the graphics files storing the tile images actually do contain transparency information (masks), but it’s not used by the game. This brings us back to the black backgrounds.

If you look closely at the screenshot above, you may notice that the girders in the background appear angled/sloped. But we’ve just established that the tile drawing code can’t handle partial transparency, which would be needed to create angled shapes out of rectangular graphics. So how does this work? Simple – the “empty” parts of the sloped tiles are actually black pixels. By making the background itself also pure black, it appears as if parts of the tile are transparent when in fact they aren’t.

To illustrate this, let’s modify the level shown in the screenshot above to use a regular background:

Now the illusion breaks down, and we can see that the sloped tiles are actually quite rectangular. I’m pretty sure that if the game had been able to draw tiles with partial transparency, the designers would’ve used regular backgrounds instead of the plain black ones for these types of scenes.

“But wait!”, you say. “I clearly remember some partially transparent tiles in the game! Here, like these windows or the broken buildings:”

And indeed, this very much looks like masked tiles. But these types of visuals are actually not handled by the tile drawing code. They are essentially actors/sprites that are rendered after the tiles along with other game objects – and those do allow partial transparency. This is another way for the game to work around the limitations of its tile drawing. I’m not sure why the same approach wasn’t used for the angled girders – perhaps it would’ve required too many “decoration” actors and caused performance issues?

Now let’s have a closer look at tile rendering, and how the background drawing works.

Tile drawing

As mentioned above, each tile is 16×16 pixels. The visible viewport shows a section of 13×10 tiles, with the rest of the screen covered by the HUD. The viewport is redrawn every frame, whereas the HUD is only updated when something changes. This reduces the amount of data transferred over the slow ISA bus, and was likely an important performance optimization to get the game to run well on slower machines. The engine also utilizes double buffering, by using two separate “pages” of EGA video memory at addresses 0xA0000 and 0xA2000.

The game uses a single tileset of only 384 tiles throughout all 30 levels (for reference, Cosmo has 3000 tiles, and Duke 2 has multiple tilesets with 1160 tiles each). The entire tileset is copied into EGA video memory when the game starts, at address 0xA4000.

This makes it possible to very efficiently draw individual tiles by using the latch copy technique (more about this in my article on Duke Nukem II’s parallax scrolling), at the cost of not being able to draw with partial transparency as discussed. This is implemented by a low-level function written in Assembly (most of the game is written in C), BlitSolidTile (name chosen by me). This function takes two arguments: A source offset, which is an EGA memory offset relative to the base address of 0xA4000, and a destination offset, which is relative to the start of the current screen back buffer (aka “draw page”). The function performs a latch copy of a block of 16×16 pixels from the given source offset to the destination.

Due to the EGA’s planar memory layout, a single byte of EGA video memory address space represents 8 pixels (again, see the article linked above for more details). A 16×16 pixel tile therefore occupies 32 bytes of EGA address space. The very first tile of the tileset is at source offset 0, the second tile at offset 32, etc. Consequently, to address a specific tile index, we need to multiply that index by 32. The level files store tile values with this multiplication already applied – the files essentially contain video memory source offsets, not tile indices. This makes drawing the levels quite straightforward: In the simplest case, all we have to do is go through the currently visible subsection of the level data, and call BlitSolidTile for each tile’s value, along with the correct destination offset to make the tile appear where it’s meant to go on screen.

But things do get a bit more interesting. Even though the game uses 16×16 pixel tiles, horizontal scrolling actually works in 8-pixel steps like it does in Cosmo and Duke 2. Most likely, 16-pixel steps would’ve been too coarse and visually unpleasant, so this seems like a good choice (vertical scrolling does 16-pixel steps, but happens less often). However, it means that we need to show only half of the tiles at the left and right edges of the viewport whenever the camera position is not at a multiple of 16 pixels. This is easy to see when looking at the “nuclear waste barrel” tiles at the left edge of the following scene:

Instead of using a dedicated routine to draw only half a tile, the game simply shifts the drawing of all tiles to the left by 8 pixels whenever the camera position is “odd”. This causes a bit of a problem though: It draws over parts of the HUD. To fix that, the relevant parts of the HUD are redrawn on top of the rendered tiles at the end of each frame. If we hack the game’s executable to remove the code that does this, we get the following:

Notice how there’s additional HUD overdraw at the bottom from a blue box sprite, and how the right edge is actually overdrawn completely, not just the first 8 pixels. The game is always drawing one extra column of tiles. When at an “even” camera position, that column is completely covered up by the HUD frame drawn on top of it – making it seem pointless. The extra column is important for the “odd” case, though: If we would only draw 13 columns of tiles (the width of the viewport), and then shift the starting position to the left by 8 pixels, an 8-pixel wide gap would appear at the right edge of the viewport. So we have to draw one additional column of tiles to fill that gap. If you look closely at the screenshot above, you can see that the right half of the overdrawn HUD is actually partially showing an image from a previous frame. Since we’re currently at an odd camera position, only the first 8 pixels of the right side of the HUD are covered by the current frame’s tiles. But during a previous frame, we were at an even camera position, and so the entire right edge was previously overdrawn with tiles.

I do have to wonder what the performance impact of this overdraw is. The HUD pieces are also drawn using latch copies, so it shouldn’t be too inefficient, but it’s still a chunk of bandwidth that’s essentially wasted since it doesn’t result in any end-user visible output. Perhaps using a dedicated half-tile drawing routine could’ve made the game more efficient. Then again, it would’ve required more complicated clipping logic when drawing sprites. The somewhat brute-force overdraw approach seems to work fine enough, as the game runs well even on a 286.

Now, let’s talk about how the backgrounds fit into this.

Drawing backgrounds

Duke Nukem 1 did something that was very uncommon for DOS games at the time: It had separate layers for the background and foreground. Most games scrolled the entire screen as a whole, including Commander Keen which was famous for introducing console-like smooth scrolling on the PC. But Duke 1 has a static background behind scrolling foreground, creating a simple form of parallax. How was this achieved?

The background graphics are the same size as the visible viewport, i.e. 13×10 tiles or 208×160 pixels. The data is stored as a sequence of tiles. Each level has two backgrounds, a primary and secondary – this is how the game is able to show different backgrounds in different parts of a level. Which images are used for each level is hardcoded into the executable. When the game loads a level, it loads the respective background graphics into video memory just like the tileset, at offsets 0x4000 and 0x8100 (absolute addresses 0xA8000 and 0xAC100). The first two tiles in the tileset, offsets 0 and 32, indicate that part of the respective background should be shown at that location.

In the “even” case, all we have to do then is to check for each tile if it’s one of the “background” tiles, and then draw the corresponding background portion instead of a tile from the tileset. Since the background is arranged like a tileset and resident in EGA memory, we also use BlitSolidTile for drawing the background. But instead of using the current tile value as the source offset, we use a variable which starts out at 0 and then increases by 32 after each tile we draw, regardless if it was a background or foreground tile. This way, the variable goes through the entire background’s memory space, but we only draw background at locations where no foreground tile is visible. To draw the secondary background, we add a fixed offset of 0x4100 to the source offset, which is the distance in bytes between the two background images in memory.

Again, the “odd” case is a bit more involved. If we would draw the background in the same way as before, it would appear to shift back and forth as we alternate between even and odd camera positions, since the starting position is offset to the left for odd positions. But we want the background to always appear in the same place: within the visible viewport. To solve this, the game draws background tiles at 8 pixels to the right of the current position when at odd camera positions, basically cancelling out the 8-pixel left-shift added to the foreground. This causes a problem though: Background tiles now appear half-way inbetween two foreground tiles.

To address this, we need to check both the current and the next tile value, and draw a background tile if either of the two matches. This is easiest to explain by looking at the (decompiled) code:

if (cameraPosX & 1) /* equivalent to cameraPosX % 2 */
{
  if (*mapCell == 0 || *(mapCell + 1) == 0) /* Background A */
  {
    BlitSolidTile(backdropTile, dest + 1);
  }
  else if (*mapCell == 0x20 || *(mapCell + 1) == 0x20) /* Background B */
  {
    BlitSolidTile(backdropTile + 0x4100, dest + 1);
  }
}
else
{
  if (*mapCell == 0) /* Background A */
  {
    BlitSolidTile(backdropTile, dest);
  }
  else if (*mapCell == 0x20) /* Background B */
  {
    BlitSolidTile(backdropTile + 0x4100, dest);
  }
}

backdropTile is the variable mentioned above, which goes through the background tile addresses in sequence. The variable dest holds the current on-screen target location as a memory offset. By passing dest + 1 to BlitSolidTile, we draw at that location + 8 pixels to the right (since 1 byte represents 8 pixels).

Now the final piece of the puzzle is tile animation.

Tile animation

In Duke 2, animated tiles are controlled via attributes in each tileset. Duke 1 keeps it simple: All tile indices between 2 and 47 (inclusive) are considered animated. If we look at the image of the tileset again (see above), that’s the entire top row of tiles (excluding the first two, which are for backgrounds).

All animations consist of exactly 4 frames, which are cycled through in sequence repeatedly. A single global variable is used to keep track of the current animation step. This variable holds a source offset, so to advance to the next step, we add 32. Once we reach 128 (4 * 32), we reset it back to 0. So the variable goes through a repeating sequence of 0, 32, 64, 96. Stepping the variable happens each time the map is rendered – so the animation speed is tied to the game’s frame rate, not to elapsed time. The game does limit its frame rate to a maximum of about 16 FPS, so it will keep running at a reasonable speed on faster systems. But it will also run slightly slower on less powerful machines.

While drawing, we then check if the tile we’re currently drawing is within the animated range, and if it is, we add the current value of the animation step variable to the source offset passed to BlitSolidTile. The actual tile value in the level’s map data does not change, it is just displayed differently depending on the current animation step.

This means that whatever tile value is placed into the level actually acts as an animation starting index. It’s up to the level designer to ensure this starting index falls onto a meaningful sequence of 4 tiles within the tileset.

There’s another neat trick we can see here. Since a single variable governs all tile animations, all animated tiles will normally animate in lockstep. But the flashing lights in the image below seem to have individual animation sequences, creating variety in the flashing. How is that possible?

It works due to the way the animation is laid out in the tileset. The flashing light sequence only has 4 frames of animation, but there are 8 frames in the tileset: The first 4 frames are duplicated. This makes it possible to pick any starting location within the first 4 tiles, and end up with a distinct animation sequence of 4 frames.

The same approach is also used in Duke 2, and it’s used extensively in Major Stryker, another Apogee game which has a lot of technical details in common with Todd Replogle’s games (Duke 1 &2 and Cosmo) although it was made by Allen H. Blum III.

One special case worth mentioning is conveyor belts. These also appear as animated tiles, but the animation is handled by modifying the actual level data in-place by the actor code.

Conclusion and source code links

This wraps up our look at how the first Duke Nukem game renders tiles. It’s very simple, but quite effective thanks to some clever tricks. And we can already see the foundations for subsequent games: Cosmo’s Cosmic Adventure and Duke Nukem II. Both use a very similar approach at the core. They add additional features like scrolling backgrounds and masked tiles, and their tile drawing logic is more complex as a result, but the basic principle is still the same: Redraw the game each frame, draw background and foreground in one go using latch copies for efficient tile drawing. The main difference is that both games use 8×8 pixel tiles instead of 16×16, and thus can do away with the slightly convoluted shifting and overdrawing logic of the first game.

If you’re interested, check out the full source code for the tile drawing function and for BlitSolidTile. For Cosmo, the equivalent functions are DrawMapRegion and DrawSolidTile. For Duke 2, it’s UpdateAndDrawGame and BlitSolidTile.

I hope you enjoyed this look at a classic DOS game’s internals. My intention is to continue writing about various other aspects of the game’s engine, so stay tuned!