Archive for the ‘qfg5re’ Category

QfG5: the end

Saturday, March 16th, 2024

As I hinted in my previous posts, I’ve decided to stop working on it. This post should serve as a conclusion, explaining my reasons behind it and mentioning some things about the engine I have not mentioned earlier.

The main factor is the diminishing returns with the rapidly increasing efforts required to get them. I.e. locating the code for loading and parsing different resource files was not so bad (even if a good deal of resources were not parsed immediately after loading but rather treated as some structure data and accessed during use, e.g. model or animation data at each render call). Figuring out the overall engine workflow was not so bad either even if took more time. But things related to 3D are hard because of their non-standard nature (more about it below) and Ghidra not decompiling x87 code correctly in all cases. And the in-world objects interactions are even worse as it is done in the conventional C++ object-oriented fashion (and some bits in less conventional Smalltalk object-oriented fashion) so figuring out what objects are implemented as which classes is not fun, let alone all those variable-length messages that may be sent by them (and handled by a different class).

So I looked at the amount of work before me (implementing GUI, which is easy; implementing 3D rendering stuff, which is too complicated; implementing hardcoded logic, which is too tedious—and that’s before you remember that rooms may also implement their own custom logic in DLL files) and decided that I can stop here as I’m not going to re-implement the engine in any usable form anyway.

Of course I could’ve advanced farther but my inability to make 3D rendering work. I mentioned in the post about room backgrounds how I did not get it exactly right because Ghidra sometimes fails to decompile x87 code introducing variables like extraout_ST1 and you have to guess its value yourself and sometimes outright lying by e.g. using multiplication instead of division—and the x87 code is annoying enough for me to translate it by hoof. Additionally I upgraded Ghidra to 11.0 in a foolish hope that it will improve things, but that was a mistake—not only it did not make any better decompilations for the concerned code but it also made things worse by forcing alignment on function arguments which was not done before (and considering how many functions mixed integers, pointers and doubles as their arguments, I had to correct annoyingly many function prototypes to put them in order again); additionally it changed some interfaces so LX loaders do not work with it yet (it is unrelated but still complicates thing for me; and that is why I’m not so eager to move to the latest version of the software I actively use). In theory spending a bit more time on maths I could get it right but model rendering proved out to be even worse.

I have next to no experience with 3D renderers, especially triangle-based (the books tend to describe ray-tracing approaches instead) yet it is not that hard even for me to understand: surface is split into triangles, each one is defined by its vertices, rotation is performed by multiplying those coordinates by rotation matrix (which is also easy to derive), then you do projection to plane and fill. I’ve managed to make a wireframe model of the object render and after messing with barycentric coordinates I could even make textures appear on some of them.

The problem is that QfG5 engine uses a different approach: normally projected coordinates would be calculated as x/(z/k+1) where k is the distance from the viewer to the projection plane. Inside the engine this +1 bit is missing (yes, I’ve checked the assembly to be sure) which gives unexpected results. What’s worse, even when I export model data into the standard Wavefront .obj format and use a third-party 3D viewer, it fails to apply the textures properly (and sometimes the polygons themselves look very wrong). So it looks like you have to use the engine code—and it hits the same decompilation problems as above (not as bad in this case but it’s still a mix of floating- and fixed-point code with many opportunities for the decompiler to lie).

As for the in-world logic, it does not help that almost everything is hardcoded in the engine. For instance, item IDs are hardcoded and there’s a special table with item properties which contains e.g. sound IDs for viewing or equipping/using the item and message ID3 which tells you which message you should load from 101.QGM e.g. message ID3=18 means that if you load message 1,18,1,1 you’ll get short item description “Basket” while loading message 1,18,5,1 will return “This simple reed basket looks old, but well-cared for.”. Messages with just one different ID are used in many places, e.g. to tell you that your action will fail because of enemy presence instead of e.g. hunger. But the worst of them is a per-character (hero, NPCs or enemies alike) collection of tables, both integer and floating-point ones, that are used for affecting some actions. I did not even bother to find out what they affect exactly.

Well, that’s it. I don’t know what I’ll do next, maybe some small things for NihAV, maybe I’ll look at other Sierra engines to see if they’re more accessible, maybe I’ll do nothing for a while (there are some strategy games that make me waste a lot of time like Battle for Wesnoth, OpenTTD or Settlers II). In either case I had some fun REing the game and learned some things too, I can only hope the next thing I do will be similarly entertaining (and somewhat useful).

QfG5: RGD revisited

Thursday, March 14th, 2024

This was the last format I haven’t looked too deep at. But as I’m tying loose ends, I decided to revisit it and see what I can get out of it.

As expected, RGD defines the 3D data for the room. I have not figured out all the additional values stored there (and I’m not sure that I got proper regions marked either) but at least the basic understanding proved out to be correct.

So, here’s what I got:

Arcane Island background

Arcane Island RGD

As you can see (especially if you click on the picture to see it in full glory), it is a flat map for the room (or rather like in Doom and Doom 2, a 3D surface consisting of differently raised polygons, pity I haven’t figured out which property is responsible for the heights). Essentially each region consists of a set of edges of different types (I marked them with different colours, you should be able to spot the blue edges around the area and some green polygons around the walkway and columns outlines). There is also a special list of marked regions (yellow ones on the picture but I’m not so sure about that) that are supposed to be walkable and there are even two connectivity matrices for them (for the record, on this particular map there are about nine hundred regions in total and only fifteen are marked as walkable).

From what I saw in the code, this map is used in the game to translate mouse coordinates into destination region, plot path to it, check the enemy line of sight (and projectiles) and so on.

Fun thing is that the format is not compact as the others (as I described it before, it’s a mess of various lists and references to other lists and so on) and so some data is unread. In some cases it is merely 4-8 bytes of padding between different blocks, in other cases it’s way more. For example, in 251.RGD you can see a piece of text “ctile Only. Region 448 contains entry point(s)” plus some other words here and there.

And as I hinted in my previous posts, that’s about it. I intend to write the final post explaining my problems with 3D rendering and why I’m giving up on it. At least I learned a lot more about my favourite game and had some fun while doing it, so it is not time completely wasted.

QfG: formulae

Tuesday, March 12th, 2024

Since there is not much progress with REing the engine, here I’d like to at least document some formulae from the gameplay mechanics. I realize that most of them are probably well-known already but maybe I’ll cover at least a couple of new ones.

QfG5: some notes about the design

Wednesday, February 21st, 2024

Since I have not progressed far in the recent weeks (the current events put me out of mood) I can at least document some bits before I forget them completely. In this post I’d like to outline the overall game engine design.

QfG5: panorama projection

Saturday, February 3rd, 2024

While I’m slowly, very slowly, approach model rendering, here’s something that is between 2D and 3D.

As I mentioned in my previous post, room backgrounds are supposed to be used as a texture on a virtual cylinder. After some investigations I figured out more details and have somewhat working code.

If you forgot geometry as much as I did, here’s a reminder: cylinder is an extruded circle and an image painted on it will be seen in a distorted way with more of the picture seen in the middle (because the distance varies) and sides of the picture being squished (because cylinder curve is at larger angle to the projection plane).

Computing how the pixels should map to the projection is a costly operation so the engine pre-computes tables for the columns to take, actual amount of that column to scale and the scaling step. As the result, during rendering stage all that is needed is to look up the column offsets for each output column, offset inside the column and scaling coefficient (both stored as 16-bit fixed-point for faster calculations). This also explains why background images are stored in the transposed format, it’s definitely easier to manipulate them this way.

Also while fiddling with all this I understood at last what the floating-point numbers in the header mean—they denote start and end angle for the panorama. Those angles are also used in limiting the distance from which the panorama may be seen.

In case of underwater panorama (with its wavy distortion) there’s yet another table in play but I’ve not touched it yet.

The main problem figuring out the code is that Ghidra has problems dealing with x87 code (and it’s hard to blame it, x87 is even worse in some aspects than x86) and I’m not eager to do it by hoof. In the code calculating those projection coefficients step -= delta * 2.0 / width was decompiled as step -= width / (delta * 2.0), I could understand that the called function is arccosine only from the context as Ghidra refused to decompile it and it also failed to recognize the case when common sub-expression was used in two subsequent calculations i.e. instead of y_offset[i] = (int)(offset * 65536.0); scale[i] = (int)((height * 0.5 - offset) * 2.0 / disp_h) - 1; it had scale[i] = (int)((height * 0.5 - extraout_ST0) * 2.0 / disp_h) - 1; where offset=(1.0 - angle * scale) * height * 0.5 but it’s not stored anywhere except in x87 register. As I said, I understand why decompiling it hard but such mistakes require either to try and reconstruct x87 code by hoof or resort to the geometry to derive the proper formulae and I don’t know which one is worse.

In either case here is an example to conclude the post:

QfG5: now with some code

Tuesday, January 16th, 2024

So while I’m still trying to figure out various details of the engine, I decided to finally start writing some engine code myself instead of having a bundle of tools to do just one task.

The main annoyance is loading files in Rust. Since the game was designed for case-insensitive filesystems, the directories and files may have names in lowercase, uppercase or mixed. And since certain operating system chose the radically different approach to the Unicode encoding format for the filenames, Rust has OsString in order to handle those external names properly. As the result in order to find the proper name corresponding to the file (e.g. “data/qgm/160.qgm” may be really names “DATA/Qgm/160.QGM”) I have to split path, convert it to an internal string in order to perform case-insensitive comparison and reconstruct the full path again. It’s not complicated but still annoying.

After dealing with this nuisance, I’ve moved to decoding graphic formats. For instance, I could finally dump all sprites and room backgrounds to inspect them better. And in order to do that I could simply create an archive object for loading data, image buffer object to paint room background and/or sprites to, and some objects to decode and paint the actual data.

Here is room 260, the bedroom in Gnome Ann’s Inn that serves as the starting point for the multiplayer games (except that it was cut and it takes some effort to see it):

If you’re familiar with the game you can see that it is not a simple mirror image of the usual single-player bedroom (the pictures are different as well as the chest placement). A subtler thing to notice is that on my picture the floorboards are curved while they look straight in the game—those would be too if I managed to implement the cylindrical mapping the game uses to project the background (I hope to get to it eventually). But since this is not that much fun by itself, here’s a GIF of the room with some of the sprites in place (beware of the size, it can hardly fit on a floppy). If some of them look wrong it’s because they were taken from the single-player bedroom and mirrored (funny enough, there’s a sprite for the second chest taken from there as well).

Speaking about the sprites, I’ve finally figured out why some of the sprites are rotated and some are not. As it turns out, there’s the following hierarchy: each room may have several views (e.g. slightly different views of the arena, front and back parts in the Hall of Kings or overall docks panorama with a specific Pholus shop close-up) and each of the view may have up to a hundred sprites associated with it. So e.g. multi-player bedroom has number 260, its only view has number 2600, and torches in it have sprites number 260000 and 260001 while chests have sprites number 260095 and 260096 correspondingly (with no other sprite numbers between them). Room 900 is a map that uses the standard BMP file for its background while points of interest on it are individual sprites (as well as the map you can see if you look at the inventory map).

So all of the room-associated sprites (except for map markers) are stored in rotated form while various GUI-related sprites (with the numbers in 1xxxxx range) are not.

And if you care about specific GUI sprite numbers, here’s a short list:

  • 100000-100006: main window GUI elements
  • 100010-100181 (but not 100100): character and monster portraits (with various expressions if they have spoken lines);
  • 100100, 100200-101001, 101003: various GUI elements for dialogue windows
  • 101002: small icons for all inventory items (as well as spells and paladin abilities);
  • 101101-101607: animated items (spells, abilities) views for the inventory window;
  • 120000-130001: custom GUI elements for the specific cases (e.g. bulletin board background and notes, power indicator for throwing, main menu background and so on);
  • 140000-140048: GUI elements for the safe-cracking minigame (background, opening segments, dancing figures);
  • 143000-144005: GUI elements for the cut minigame Wizard’s Whirl;
  • 150000-155000: things that can be seen with the telescope in Erasmus’s castle;
  • 156000-157002: pizza diagrams at the Scientific Isle;
  • 160000: save/load game menu background;
  • 161000: map (which looks the same as 900099 but the latter is stored in rotated form);
  • 199909-199913: Wheel of Fortune minigame sprites (background and parrot, spinning wheels, arm and thrown knives are 3D models).

So the easy part is done, the next thing I’ll probably try is proper cylindrical projection for the room backgrounds and 3D object rendering. That should definitely take some time…

QfG5: some words about rendering

Thursday, January 4th, 2024

It is a well-known fact that Sierra implemented its 3D adventure games in parallel (and that’s not counting Dynamix RPG titles), each using its own engine with not so much things in common.

Mask of Eternity was using Direct3D/Glide (and Indeo 5 cutscenes), Gabriel Knight 3 used its custom engine with possible Direct3D backend (and Bink cutscenes as well as MP3 audio), Quest for Glory V used portable software-only 2.5D engine, combining 3D models with projected background (with custom depth map) and 2D sprites for e.g. animating water (and Cinepak cutscenes and MS ADPCM compressed audio).

So let’s look closer at how 3D rendering was done in QfG5.

Each 3D model consists of one or several meshes that form an unchangeable part of a whole model that may be manipulated independently (e.g. feet/head/torso or a hero). Rendering is done in straightforward way: calculate the orientation and position of mesh triangles, prune the back surface triangles, render each triangle into a dedicated buffer minding the depth (a separate Z-buffer is maintained for that purpose) and using the texture data to decide the pixel value.

But of course it’s not that straightforward. For starters, there are essentially two rendering modes (with several flavours of each): one draws an opaque 3D model, another one blends it with the already rendered data. Also while the renderer uses pre-calculated LUT for paletted texture pixels in order to have fast shading, it is possible to assign special LUTs for the specific meshes (which is done in the cases hardcoded in the engine). As the result glowing objects (e.g. enchanted armour or weapon) is rendered in three passes, using the same model with special LUTs applied to some meshes in certain rendering passes and some other meshes may be hidden during a rendering pass.

Room background blitting seems to be done by having pre-calculated coefficients used to define how to warp the image.

Overall, nothing especially hard so maybe I’ll get to re-implementing it eventually.

QfG5: savegame format

Monday, January 1st, 2024

So, while I’m still figuring out 3D object rendering details (it seems that various object may have their own rendering functions—up to six variants usually—so figuring it all out will take some time), here’s another random format documentation instead.

QfG5: leftover formats

Saturday, December 23rd, 2023

Looks like I’ve not said much about the three formats used by the game yet: ANM, RGD and STR. So I guess it’s time to rectify that.


Apparently there is only one animation format despite file magic being either 8XOV or MIRT. It starts with 4-byte magic, 32-bit header size (always 36 bytes), 16-bit animation name, 32-bit number of animations in the file, 32-bit number of animation blocks in each animation and 32-bit animation delay (usually 33 or 66 milliseconds).

Each animation block consists of two 32-bit integers (seem to be always 1 and 0 correspondingly), translation vector (three 32-bit floats) and rotation matrix (nine 32-bit floats).

I suppose animation sequences are supposed to be applied to the corresponding meshes in the model (each mesh has an animation ID in its header) and maybe I’ll see it eventually if I ever get to the rendering stage.


This is probably the most annoying format. It describes region data for the room in 3D format (I suppose) and packs a lot of different data that references other parts of the data.

Here’s a brief header description (all items are 32-bit integers):

  • always 0?
  • always 2?
  • total number of regions;
  • region data offset (each region includes among other things a 3-D vector index and an offset to a list of segment IDs);
  • offset to a list of offsets, data those offsets has a list of vector indices;
  • some ignored offset;
  • offset to an array of some region positioning information
  • total number of regions
  • offset to a full list of region IDs
  • total number of region IDs
  • data start offset (seems to be always 0x5C)?
  • number of segments
  • offset to segment data (which includes two point indices and an offset to region ID list);
  • number of points
  • offset to point data (two doubles per point)
  • number of vectors
  • offset to vector data (three doubles per vector)
  • flag signalling that the following fields are meaningful
  • number of special (walkable?) regions
  • connectivity matrix offset (that number of regions squared, -1 and -2 mean there’s no connection)
  • another connectivity matrix (in the same format) offset
  • offset to the list of special region IDs.

As you can see, indirection can get a bit deep. At least until I get my engine reimplementation to the point where I have to worry about pathfinding and hero interaction with things I don’t have to think about it (which is likely never).


This is a special room format that happens only in 30 room (sub)variants. The format by itself is simple: 32-bit number of entries and pairs of 32-bit integers defining points. And as expected from the name, those are used to describe stars (i.e. shiny points in the sky of some locations).

QfG5: (some) cut content

Tuesday, December 19th, 2023

As I keep studying the engine code, I find hints on some planned things that were cut or not fully implemented (because game development).

I’m aware of many things like censored Nawar lines, disabled multiplayer mode, removed Glide spell and some other things being documented already so I’ll try to mention less known things.

For example, the game recognizes about thirty spells but in reality it had about ten more. One was probably deleted Glide spell, there’s something that looks like Dragon Frost spell (which acts like Dragon Fire spell but with a blue dragon head and probably frost damage). I can’t say much about the spells but considering the hints in the code there was supposed to be a completely different category of spells (normal spells have identifiers starting with 101500, paladin abilities have identifiers starting from 101600, those unknown spell IDs start from 101700 and seem to be attack spells only—maybe it’s for multiplayer mode?). For most of those there is no graphics except for one unknown spell:

Or there’s a model 98 called Sparkles which looks like a stone naked woman, I don’t remember seeing that in a game (as well as roaches). Or a blue version of a dragon (which gives only 20-50 drachmas as a loot). If I ever get to rendering stage one day I should provide pictures.