HoMM3 DEF animations

DEF files contain animations, terrain images, map objects and some parts of the game interface, mostly multi-state buttons (that is, the buttons that change their appearance when pressed). The DEF file format is relatively simple, but a bit counter-intuitive in some aspects, due to a specific way of cropping the individual images to the minimal size possible and an even more specific way of encoding the scanlines using a range of weird http://en.wikipedia.org/wiki/Run-length_encoding RLE-derived formats. When reading the file, the images should be overlaid onto a common, solid-color background and repositioned by a given offset to form a consistent animation. The animations themselves are divided into several separate sequences, representing different unit movements etc.

The detailed description is incomplete - there seems to be a way to encode a few more things into a DEF file - but sufficient to read nearly all the standard, in-game DEFs made by NWC for HoMM3 SoD. There are also some weird exceptions that need a more throughout investigation, but it's possible that they're just unused leftovers from an early development stage or otherwise broken files.

The DEF file structure can be divided into three parts - the header, the sequences list and, finally, the frames. The header is 784 bytes long and contains the basic metadata, including the palette:

struct h3def_color_indexed {
	uint8_t r;
	uint8_t g;
	uint8_t b;
};
 
struct h3def_header {
	uint32_t type;
	uint32_t width;
	uint32_t height;
	uint32_t sequences_count;
	h3def_color_indexed palette[256];
};

It is important to remember that the width and height given in the header apply to the final, decoded images. The encoded frames are cropped to the minimal size possible, so their size varies. The DEF type can be one of the following:

It is usually the same as the file type field in the LOD archive, with some exceptions, as noted at the end of this description.

After the header comes the list of sequences. Each of them, in turn, contains a list of frames - first names, then offsets. When a frame is used more than once (which is quite common in the unit animations), it is given the same name and offset each time it appears (in other words, there's just a single stored copy of the frame that is being referenced many times), though it seems to be possible to call several different images the same name or point several names to the same image, with unforeseen and probably highly unpleasant consequences (that is, the game will probably crash and the tools like DefView will probably crash too, or, at best, mangle the extracted images completely).

    struct h3def_sequence {
        uint32_t type;
        uint32_t length;
        uint32_t unknown1;
        uint32_t unknown2;
        char *names[length];
        uint32_t offsets[length];
    };

Interestingly, the names are probably null-terminated, but as all the original HoMM file names follow the 8.3 scheme very strictly, it needs to be checked for to be sure. Any information on the subject will be appreciated. The unknown values probably are actually a set of eight separate 8-bit numbers (only then they are of a sensible magnitude and mostly multiplies of 10), maybe they're color indexes, maybe time delays, maybe something entirely different. They're not critical for reading the frames, but, again, feel free to contact me if you know what they mean.

Finally, the frames start. It is, however, quite pointless, even if perfectly possible, to read them sequentially from this point on - it would be needlessly complicated to match the actual images with their names this way. Instead, it makes the most sense to iterate over a list of frames prepared while reading the sequences and extract the data using offsets given therein. Either way, one ends up with a frame description that consists of a header and an encoded image.

    struct h3def_frame_header {
        uint32_t data_size;
        uint32_t type;
        uint32_t width;
        uint32_t height;
        uint32_t img_width;
        uint32_t img_height;
        uint32_t x;
        uint32_t y;
    };

The data size field does not include the header size, that is obviously 32 bytes, which means that the whole frame takes data_size+32 bytes. The type can be 1, 2 or 3. Type 1 frames are the creature animations used at the combat screen, encoded using an adaptive http://en.wikipedia.org/wiki/Run-length_encoding RLE algorithm similar to the http://developer.apple.com/technotes/tn/tn1023.html Apple PackBits. Type 2 and 3 are both encoded using an even more contorted algorithm and differ only in semantics - type 2 frames are used for road and rivers only, while everything else is type 3. The width and height fields are redundant, that is, they contain the same information as the global DEF header (with an exception of the OVSLOT.def file, as noted below). The actual size of the cropped image comes afterwards, followed by its position relative to the top-left corner of a full, decoded frame. The next data_size bytes is the encoded image. Refer to the following sections for the encoding formats used.

I'll demonstrate the DEF file format, using the CGOBLI.def file as an example - that is, the combat animation of a Goblin. The file used comes from HoMM3 SoD Complete (Polish version), is 155062 bytes long and has an MD5 signature of 00c04ce355db1ffd16e78b845b6d2ab4.

The header:

This encoding method has a lot in common with an old data compression algorithm called http://developer.apple.com/technotes/tn/tn1023.html Apple PackBits, albeit it's not as elegant. Actually, it's a pretty ugly take on image compression, but hopefully it's pretty smiple.

Given an encoded image of x by y pixels and data size n, there are y 32-bit offsets, one for each encoded scanline (that is, a row of pixels), indicating its starting point, respective to the beginning of the image data. There's no scanline length given, but it can be calculated as a difference between the adjacent offsets (and n, in the case of the last scanline). Starting from those offsets, the actual pixels begin. There are two kinds of data blocks there. One is a classic RLE-style repeat - a single length byte between 0 and 0xFE followed by a single color index byte. The indicated color spans a row of pixels of a given length. The other data block is a literal string of different pixels, used when there's a lot of different colors and it would be wasteful to use single-pixel RLE blocks. It starts with an 0xFF byte, then a single length byte and finally a string of color indexes of the given length. While that might seem complicated, it becomes clear when explained using an example, which follows below.

There are several exceptions to the DEF file format, of varying magnitude and importance. Some are probably just broken or deprecated files, left over from the development process and never used by the game, some might be the effects of an oversight and some are an outright mystery.

This file, while it's being used by the game just fine (it contains background graphics for the kingdom overview window), is the only one with frames of a size different from the one given in the DEF header. No one knows why, or how exactly the game deals with that.