Sprites

Decoding and extracting sprites from Doom, by
2019-03-21

Sprites in Doom are stored in a custom format, tailor made for the rendering engine and in a sense even for the final output medium. It has taken me a while to implement support for this format in wad-gfx (formerly doom-gfx), not because of any complexity in the format, but because I had a hard time figuring out how to most faithfully represent the source data in a normal contemporary image file format.

Anamorphic pixels

If you were into computers back when Doom was released, it is not unlikely that you have good feelings associated with the resolution 320x200 on a 4:3 monitor. This is what anything good was using back then. You can consider a 4:3 monitor to be 4 length units wide and 3 length units tall, for some length unit. Dividing the screen into 320x200 then makes each pixel 4/320 by 3/200 length units square. Calculating it all out, the aspect ratio for each pixel is (4/320):(3/200) = 5:6. Horrors! The pixels aren't square!

And it is not something you can simply look past, the pixels are a full 20% taller than they are wide! So if we extract a sprite and display it pixel-for-pixel directly on a modern screen with normal square pixels, it looks squashed compared to the original game:

Imp rendered with anamorphic pixels Imp rendered with square pixels
Pixel-for-pixel extraction Stretched 120% vertically

So, on the one hand there's the exact pixel-for-pixel extraction, and on the other there's the visually faithful extraction. I opted for supporting both, with the visually faithful mode as default and the pixel-for-pixel exact mode behind the command line option --anamorphic.

More as a side-note, the PNG format (which wad-gfx uses) supports different pixel aspect ratios via the pHYs chunk. wad-gfx uses this to correctly declare the pixel aspect for the anamorphic extractions, but I have yet to encounter a single image editor or viewer that makes use of this for display…

Transparency

With indexed coloring, the typical way to have transparency in sprites is to dedicate one color index to be transparent. Then you get to have a regular 2D array of pixels, each of which may or may not be transparent. This is the established way, and PNG supports this technique. But it is of course not what Doom does.

First, I should mention that the sprites are stored column by column instead of the more common row major ordering. This is because everything vertical in Doom – that is, everything except the flats – is rendered column by column. The restrictions on Doom's 3D projections makes sure that all lines that are vertical in world-space end up vertical in screen-space, which in turn means that rendering a column is a relatively simple matter of scaling instead of a more advanced projection. It also ties in with the anamorphic pixels: The pixels end up the same way on screen as stored, so the pixel aspect ratio remains unchanged. The upshot of these details is that it is simpler for the rendering engine to work in columns, so it does.

Painting sprites with a transparent color index requires you to have a check for each pixel to decide whether or not to paint that pixel. So, in order to paint fewer pixels on screen, you have to do more work. That doesn't seem right, and Doom manages to do away with this inefficiency: Each column is encoded as a series of spans and each span consists of a top position, a length and then length bytes of pixel data. So, in a way, this implements compression via run-length encoding. Another way to look at it is like a more imperative description of how to paint the sprite, rather than a "dead" dataformat.

In the end, this scheme allows sprites to use all the 256 colors of the palette, and they do. So how should this be represented in a PNG when there is no universally unused color index? I wound up supporting three different output formats:

Imp with transparency Imp with opaque background Transparency mask for imp
Full color Indexed Mask

Moving forward

So how does this help me towards my goal of rendering a Doom map? Why am I even bothering with the sprites? Well, wall textures are vertical, like sprites, and they can be transparent, like sprites. "Transparent?", I hear you ask. Yes, there are a few wall textures with transparency for things like fences. So they are stored like sprites!

But that is not quite true either. Wall textures are composed of patches, which are stored like sprites. But the textures themselves are stored in another format which composes patches at different positions. So we will have to get back to textures another time.

But as a teaser, let's have a look at some patches:

SW11_1 EXIT1 EXIT2 WALL00_2
, 2019