QfG: formulae

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.
Read the rest of this entry »

QfG5: some notes about the design

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.
Read the rest of this entry »

FFhistory: ProRes

February 5th, 2024

Apparently there’s some work been done recently on the ProRes encoders in jbmpeg with the intent not merely to fix the bugs but also to leave just one. So why not talk about the format support, it’s about as entertaining as the recent story in the project demonstrating once again that most of the problems in open-source development can’t be solved by throwing donations, even moderately large ones.

So, ProRes, the format with its history being a rather good demonstration about the project issues (CEmpeg and libav back then, and FFmpeg throughout its history in general). This tale is full of whimsy (depending on your sense of humour of course) and contains moral as well.
Read the rest of this entry »

QfG5: panorama projection

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:
Read the rest of this entry »

Idiots finally matter

January 24th, 2024

I thought I’ve said all what I wanted to say about the current events but apparently life constantly gives new reasons to rant.

Unlike many other people, I don’t believe in some deity but rather in a concept of idiocy. More specifically I believe that (as St Wabuu said) most of the humans are so stupid (thinking is a very energy consuming effort after all), idiocy is a side effect of human imperfection and can be eradicated only with the humanity itself, and that if there’s a way to do some idiotic thing somebody will do it (the Darwin Awards and news from Florida keep proving this version of Murphy’s law). Overall, there’s an abundance of idiocy around us and in the last two years it really demonstrated how our lives can be turned to the worse.

2020 (all ~730 days of it) can be called The Year of Arrogant Idiots. The origin of the virus is not relevant for this case (even if it spawned a lot of bickering and misinformation campaigns), but how it grew into the pandemic and how it was handled afterwards is very relevant. Mostly it is remembered for the things like #hugachinese campaign initiated by some Italian mayor (after all, having a close bodily contact with a stranger not merely removes the stigma but also should decrease the chances of transmission for any disease) and the various things from “trust me, I’m a doctor” people.

By those I mean primarily WHO and various heads of local healthcare systems but others qualify as well. I doubt you can give a better explanation why it was so hard to accept that the virus is primarily transmitted by air (even if it does not fall into “airborne” classification for some purely theoretical reasons), that calling it “mild” did not help things, or that the virus gives a mildsevere damage to the immune system so betting on herd immunity and exposing children to it was a dubious idea at best. And that’s not counting all the people who think they know even better and thus can ignore the known facts for being inconvenient (I feel they resort to a circular reasoning “masks/vaccines do not work because we won’t allow those to be used on us”). Thanks guys, without you this year would not be as crappy or as long!

The following 1939 (all 700 days of it and counting) can be called The Year of Selfish Idiots (not that the other idiotic traits are in short supply, it’s just this particular one has been driving this year down). The year started when a certain group of people (if they deserve to be called people at all) decided to act on their beliefs that occupying and plundering another country would do them more good than developing their own country instead. I can understand the initial period of confusion when good decisions were hard to make, but it was followed mostly by the decisions that can be called short-sighted only if you’re a complete diplomat.

You may not like Ukraine or not care about it at all but you should realize that if the aggressor is not stopped it won’t be satisfied with that and will use the resources and people from captured territories to attack other countries (they’re not even hiding the plans of not merely expanding to former USSR borders but conquer Finland, Poland and maybe other bits of Europe). And if some selfish idiot thinks that USA will be left alone and does not need to help other countries at all—well, russians believe Alaska is rightfully theirs as well as a bit of California, and that’s not talking about the whole “USA is our greatest enemy and should be destroyed” rhetoric. Also that’s not counting empowering other terrorist states like Iran, DPRK and that part of Yemen (who also build their ideology on hating USA).

There’s a miniature version of all of this in Israel—it has a certain person who valued staying as a prime minister more than serving his country, whose efforts to grow terrorist threat finally came to fruition last year. And he’s still friends with russia because it’s friends with other terrorist states (at least that was his excuse).

So what other countries do? Follow their selfish interests that hurt them in the long run: here in Germany we had at least two chancellors who willingly traded German interests for cheap russian gas (some argue it’s been a tradition since 1980s when they decided that cheap gas from USSR is more important than supporting Polish struggle for independence), or, in more recent events, the previous minister of defence is remembered for not doing anything with the significantly increased defence budget except giving her son a ride on a helicopter. Or there’s a situation where Europe decided to help Ukraine with munition but because of some selfish idiots who wanted to sponsor domestic industry more than to fulfil the pledge the promised amount has not been delivered (resulting in a current stalemate on the front-line). Speaking of Europe, those countries that try to help russia for cheap resources forget that being a russian ally makes you their backstabbing target (so far I think only Germany in WWII period evaded that fate—by backstabbing first). And there’s USA where politicians decided that their local political ambitions are a good reason to hold foreign aid hostage.

As I mentioned earlier, such decisions may have bad consequences for the whole world and for their country as well (but if the politicians made sane reasonable decisions I’d not have a reason to name them selfish idiots). And if you say “it’s the will of the people” then those people are no different (at least they may have an excuse for not having an idea about things outside their backwater town). America got great not all by itself but rather by setting the rules by which other countries agreed to play, and thus not eliminating the threat to the system (and russia openly declares ruining this system as one of its goals) will only lead to the downfall of USA. The same can be said about Temporarily Occupied West Taiwan which started to prosper only after its involvement in the world trade—a position which a certain selfish idiot will likely sacrifice for small territorial gains.


I don’t know why it’s just last two years. There are no facts (known to me at least) that show any factors causing the recent sharp increase in idiocy in human population. So it looks more plausible to me that the overall idiocy kept accumulating until the already stressed supports of society finally gave way under overload and external crises.

Do I think the situation can be improved? Hardly. The majority of population will be against any kind of reforms (especially where people are expected to think and/or to learn) for the obvious reason that I don’t need to repeat. So even if the current issues will be resolved, what prevents it from repeating again? After all we still have not learned a lesson from the pandemic (IMO people just got tired and decided to pretend that the virus does not matter and those frequent disruptions due to many people still falling ill from it also do not matter) and a frank and unambiguous statement from Temporarily Occupied West Taiwan that it intends to occupy the rest of Taiwanese territory and why should we hope that this upcoming conflict will be handled in a better way?

Some words about LZ77

January 23rd, 2024

It somewhat amuses me how people discover they can use deflate to estimate text complexity or similarity. The reason for that is that this compression algorithm was essentially a by-product of efforts to estimate the string complexity. The original paper states it outright that the compression algorithm is “an adaptation of a simple copying procedure discussed recently” (referring to A. Lempel and J. Ziv, “On the complexity of finite sequences,” IEEE Trans. Inform. Theory, vol. IT-22, pp. 75-81, Jan. 1976). Apparently it went the full circle, proving that their original approach to complexity was right and that the authors (who did more work in that field than if field of compression) should be celebrated for this subject as well.

Deceivingly simple

January 18th, 2024

There are several approaches to designing the architecture that may reasonable at a quick glance but prove to be rather bad in the long run. One of those is monolith design (where the software is an interconnected mess where you cannot isolate any part without breaking half of it) and its variation panelák, a monolith that looks like it has modular structure but in reality those modules are often connected by undocumented interfaces and removing one of those may break the rest—just look at systemd, a modern init system that for some reason has to reimplement various previously stand-alone services as its components in order to function properly (like network management).

But recently I’ve noticed another, rather opposite, design pattern that nevertheless leads to equally bad outcome: having a simple but rather useless core that anybody can implement but won’t be satisfied with, which leads to creating a lot of (often competing) extensions that rarely get supported by the majority, ending up with a mess that you can’t rely upon. I think the appropriate metaphor here would be amoebas: something with a small core, amorphous body, cloning itself and the resulting clones may end up very different from each other over time (and detrimental to your health).
Read the rest of this entry »

QfG5: now with some code

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

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

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.
Read the rest of this entry »