Kostya's Boring Codec World

While I’m still looking at various bits of the engine, here’s yet another post about the part I more or less understand.

Overall, the engine was designed to be portable as it was supposed to work both on little-endian PC and big-endian Mac. That is why PC version essentially uses just minimum OS and DirectX interfaces to perform the necessary stuff (event tracking, drawing and audio playback; multi-player game would require an additional library for the network stuff but since it was cut we’re not talking about it).

The engine essentially draws the 3D world by default and maintains a stack of windows (e.g. a death screen, a main menu or various dialogues) to be shown over it. Windows are organised as a rectangle on the screen with optional background (loaded from GRA file) and a collection of widgets on it. Each widget is essentially a rectangle inside window with a custom code to draw it and maybe handle some custom events (for example, report when it was clicked). Essentially the main screen class tracks keyboard and mouse events and passes them to the current window. It also handles redraw events (by calling a corresponding function from the window interface) and when a widget is clicked, it also invokes a function to tell the window which widget was clicked and to act on it. Also if a widget specifies tooltip/hint text it will be drawn too when a mouse stays in certain point long enough and there’s a widget interface function provided. It sounds rather simple but seems to work good enough for the game, even drag-and-drop combining items in inventory.

Widgets may be of different type: buttons (background from GRA plus button caption loaded from QGM and rendered with one of QGF fonts), mere image or text label, radio buttons, input boxes (black rectangle plus rendered text) and even model rendering (for a character window).

Windows are mostly hard-coded in the engine with all their creation and handling logic, including room-specific ones like the Adventurers Guild bulletin board, the crane controls on the Scientific Island, Wheel of Fortune minigame in Dead Parrot Inn and such. Nevertheless the engine provides an interface to create a dialogue window with up to four buttons so some rooms should be able to construct their own (maybe, a quiz for Scientific Island?).

Slowly (very slowly!) more and more details about the engine become known to me but the core of the game (3D world rendering and interaction) is terra incognita to me. Let’s see if I ever get there…

Here I’d like to review two formats related to the messages in the game: font files and message files. There’s still a question of how lipsync files work (so far it looks like a series of 16-bit variables probably telling which sprite from corresponding GRA file to show; I may get to that eventually). Update: as one should expect, lipsync format is a lot like it was in SCI—a series of 16-bit time positions (in tertias aka 1/60th of a second) and sprite IDs. Additionally there’s another table of equal size right after the end of that data, its meaning still unknown.

QGF

This is a rather simple bitmap font format. It starts with a header that has the following 32-bit values: maximum character width, character height, space between characters, unknown value, flag telling whether it is a complex pseudo-3D font or a simple line font, another flag (probably for a shadow).

Then there is an array of 512 bytes containing the character widths (only 16-256 range is populated though) followed by an array of 512 32-bit words telling the offset to the character data.

Character data consists of pair of bytes. If the first byte has negative value, it tells you how many pixels to skip, otherwise it is the current pixel opacity (for the fonts with the corresponding flag set where 31 = fully opaque pixel, for simple fonts any non-negative value is an opaque pixel). The second byte value seems to be completely ignored.

QGM

These files contain text messages of various kinds: text spoken by characters, narrator’s text, dialogue options and even all the text in user interface.

Message files start with " MGQ" magic, 32-bit file version (only version 3 and 4 are supported), 32-bit number of message blocks in the file, some unknown 16-bit value and 16-bit file ID (e.g. 160 for 160.QGM).

Then message blocks with 32-bit header and variable-size payload follow. Message block header starts with four 16-bit variables that are used as message identifier (and also used to generate the name for speech/lipsync files, more on that below). They are followed by four unknown 16-bit fields (first of them is probably ID of the character saying the lines), 16-bit number of dialogue options, 16-bit flags (flag 4 means the message contents are obfuscated), another unknown 16-bit field, 16-bit internal message number (unordered), 16-bit message length and 16-bit flag for string message label presence.

The header is followed by optional 13-byte message label (which looks like a filename), dialogue options in the same format (if present) and optional message text. There’s an additional 32-bit number at the end of each message block with unclear meaning which may be related to the message ID).

Before going on message obfuscation scheme and name generation I’d like to talk about the structure. There are essentially two kinds of message types: normal text and dialogue trees that mostly contain links to the other message text.

For example, in the same Arcane Island location message block 2 looks like this:

• option 1 = A0BJ020S.021
• option 2 = A0BJ0208.0E1
• option 3 = A0BJ0208.0F1
• option 4 = A0BJ0208.0G1
• option 5 = A0BJ0208.0H1
• message = “He that wishes to pass through me,
  First must answer questions three.”

And those IDs point at the other message blocks:

• message block 0 with text ‘Say “%s.”‘ (i.e. hero’s name)
• message block 13 with text ‘Say “King Arthur of Pendragon.”‘
• message block 15 with text ‘Say “Putentane.”‘
• message block 16 with text ‘Say “Sir Robin-the-Not-So-Brave.”‘
• message block 17 with text ‘Say “Oh, no, not again.”‘

(Also those message blocks have optional message label set to the ID of the message block 2, probably for the easier return. In other files a character’s reply may have the same label set as well.)

Those familiar with the game may remember it as the first question the cloud gargoyle asks the hero and possible replies to it.

Now about the message IDs. Those are generated from the QGM ID and four integers using the following format: A(3-character QGM ID)(2-character ID1)(2-characted ID2).(2-characted ID3)(1-character ID4). Integers are converted using base 36 i.e. numbers and uppercase letters e.g. 415 gets converted to 0 11 19 and coded as 0BJ. If audio part is present, it has the same name. Lipsync data is the same as well but uses 'S' as the first letter in the file name instead.

And as for the message text obfuscation, if the corresponding field has bit 2 (like in the majority of the message files), then it should be de-obfuscated using the following algorithm:

1. split data into 4-byte chunks and tail 0-3 bytes long;
2. for each 4-byte chunk repeat steps 3-6:
3. read those bytes as 32-bit little-endian number;
4. exclusive-or the value with constant 0xf1acc1d;
5. rotate value cyclically left by 15 bits;
6. store 32-bit number back as four bytes;
7. invert bits in all bytes of the tail.

I’d call this scheme lame but the constant speaks for itself.

And as bonus for those who care here are the extracted font files (under the cut):
Read the rest of this entry »

Each room has several formats associated with it, some of them are binary, describing various objects but here I’ll describe the following formats:

• IMG
• NOD
• ZZZ
• FTR
• ROM
• GRA

GRA format is a more general format used for animated sprites, some window backgrounds and GUI elements as well as talking character portraits.

NOD

This has nothing to do with C&C is a palette format for the room backgrounds. It starts with QFG5 magic and 32-bit file size but in reality the game engine simply reads 1024-byte RGBA palette starting at the offset 0xA8 and that’s it.

IMG

This is actual room background data. It starts with a header consisting of two 32-bit big-endian words and two 64-bit big-endian floating-point numbers and then the same header repeated in little-endian format. The parameters are height, width, two parameters probably related to the room positioning (probably an offset and full intended room perimeter—the rooms can be circular like the Silmaria main square) and two unknown floating-point numbers.

Then RLE-compressed image follows coded in columns starting from the right edge and with its height doubled (so e.g. 4000×400 image will be decoded as 800×4000 image with the image left edge being at the bottom). The lower part of image is not used (maybe a leftover when it was used for a depth buffer). The actual data is 8-bit indices to the NOD palette with the same resource number.

RLE works in the following way: for each decoded line (or rather column) a signed 8-bit value is read; zero signals the end of line, negative values signal raw data (e.g. 0xFE or -2 means copy two following bytes to the output), positive values mean repeating the next byte the specified number of times.

ZZZ

This is a room depth map. This file contains RLE-compressed depth values (0 = closest to the screen, 255 = farthest) without any header. Data is compressed in the same way as single line of IMG format and has the same dimensions but it is stored in line-by-line format right edge first (i.e. mirrored compared to the background image);

FTR

This is a format defining room regions. It consists of signed 16-bit numbers. First number declares the number of regions in the file, then region data follows consisting of 4-word header (region depth maybe, always zero, an exit portal flag, and the number of points) and the region points (two 16-bit words each).

And here is an example of decoded room images.

Arcane Island background

Arcane Island depth map (and an Easter egg)

Arcane Island region map

ROM

This is a room properties file consisting of two integers and two floats: first field (32-bit integer) seems to be a big-endian version of the third field, second field (32-bit float) is unknown, third field (32-bit integer) declares the number of additional resources that should be loaded for the room (e.g. battle arena has three alternative views), fourth field (32-bit float) seems to specify an angle increase (for circular rooms, I suppose). In either case floating-point numbers seems to be non-zero only for the room 200 (Silmaria main square).

GRA

This is a format used for animated sprites and static images in the various parts of the game.

The file starts with 32-bit image coding mode, 32-bit number of sprite collections, 512-byte palette (in RGB555 format) followed by the 32-bit offsets to the sprite collection data,

Each sprite collection starts with the header containing the following 32-bit values: horizontal sprite position, vertical sprite position, width, height, number of sprites in the collection, delay between frames and flags. It is followed by the offsets (from the sprite collection data start) to the individual frames. Depending on image coding mode frames can be stored in the following way:

1. mode 0—unpacked image data;
2. mode 1—unpacked image data interleaved with depth values (i.e. in the following order: palette index byte, depth byte, palette index byte, depth byte and so on);
3. mode 2—the same RLE compression as in IMG format;
4. mode 3—the same as the previous mode but index 0xFF is used for the transparent pixel;
5. mode 4—similar to the previous mode but value 0xFF signals that the original background pixel should be restored instead.

And here’s an example of a sprite from the same scene (in the same orientation as actual scene background):

I’ll probably try to cover the messages and speech next (font formats, message files and lipsync) but it may take more time. And then only 3D data will be left for figuring out. It’s a pity I don’t know much about 3D though…

There are sixteen formats known:

• 0 – MDL (model format);
• 1 – ANM (model animation);
• 2 – ROM (room parameters, always two integers and floats);
• 3 – NOD (room background palette);
• 4 – IMG (room background image);
• 5 – ZZZ (depth buffer for room background);
• 6 – GRA (sprites);
• 7 – QGM (message format);
• 8 – FTR (some room data);
• 9 – WAV (effects and music);
• 10 – RGD (region data);
• 11 – MOV (intro and cutscenes);
• 12 – QGF (font files);
• 13 – STR (some room data);
• 14 – AUD (speech audio, still in WAV format);
• 15 – SNC (lipsync data to accompany speech).

I’ll try to document all these formats (except for AUD, MOV and WAV).

SPK is the archive format used for storing most of the game resources. There are four known archives: CDA.SPK which seems to contain speech (and lip synchronisation data), CDN.SPK probably with scene-specific data, HDN.SPK contains game music plus world map and some other files, HDNW.SPK contains mostly 3D models and animations (plus some QGF files).

Read the rest of this entry »

So while I have no real breakthroughs, here is some information about the engine in general.

Quest for Glory V seems to be a 2.5D engine (some 3D objects interacting essentially in circular rooms using static background images) rendering output in 15-bit RGB (while using floats internally and paletted assets). The engine logic is hardcoded, partly inside the executable, partly inside dynamically loaded room modules (in Windows or Mac native format). From what I’ve already seen, there are several global objects responsible for various parts of game engine, including the main engine class with around 160 callable methods; room class takes a pointer to it and provides around ten methods that can be invoked by the engine (and which in their turn may invoke engine methods for various actions). So it’s about a megabyte of engine code and over four megabytes of code in room modules. At least I don’t need to decompile them all at once.

The game data is organised in stand-alone files and SPK archives. Cutscenes are Cinepak in MOV (though IIRC my official pirate copy re-compressed them to use SVQ1 instead), audio is MS ADPCM in WAV. Overall there are fifteen resource types known (audio, lipsync data, text messages, panorama background and its palette, 3D models and its textures, GUI decals and so on). Most of the files are contained in SPK archives which are essentially slightly hacked ZIP archives with initial header replaces with custom index per resource type and each PK entry has numbers changed so it won’t be detected as a ZIP archive without header (at least there’s no compression employed as far as I can tell).

So overall I just need to discover how the main engine loop works, what are all those file formats and reconstruct the room logic. That should take a long time (supposing I don’t give up earlier). Either way I’m doing it mostly to pass time and to find out how far I can get REing something more complex than a codec.

As I mentioned previously, NihAV is feature complete so while I may still return to improve it, it is not likely that there will be much work to to be done there. That is why I decided to try my hoof at something different—trying to reverse engineer (and maybe re-create) a game engine. I’ve chosen Quest for Glory V for this task as I still have interest in that game and fine folks from ScummVM are not likely to work on it (as it’s a hardcoded engine, more about it later). I fully understand that I may fail as my knowledge about game engines is about zero and having about five megabytes of code to decompile may be too much so I may give up out of boredom as well. In either case it’s not a big loss.

I’m not sure if I’ll ever release the final code (if there is any final code) but at least I will try to document the formats and inner engine working for the posterity. Otherwise it will be about as bad as with the modding community: I’ve seen people making better 3D models for the game and even patching the game logic to do but there is almost no public information about the formats (except for the trivial ones) let alone about something more serious. I know Mike suggested Xentax Wiki once as a better place for such work but I can’t find it so I’ll just keep blogging here.