Reflection Keen (ports of Keen Dreams and all 3D Catacombs)

Here is where to post about the latest Commander Keen fangame or modification you've finished, a new website you've made, or another Keen-related creation.
User avatar
Levellass
S-Triazine
Posts: 5261
Joined: Tue Sep 23, 2008 6:40

Post by Levellass » Mon Dec 01, 2014 7:47

So we have the format for those hanging around somewhere?
What you really need, not what you think you ought to want.

NY00123
Vorticon Elite
Posts: 442
Joined: Sun Sep 06, 2009 19:36

Post by NY00123 » Mon Dec 01, 2014 21:54

Levellass wrote:So we have the format for those hanging around somewhere?
Clearly reading some code, or even (say) porting it from one platform to a (possibly vastly) different platform is one thing, but understanding more about the code itself is different...

Afraid I won't write full details about the compression itself.

To compare with the compressed Keen Dreams title screen, the only real difference in the file format that I can see at the moment is that the KDreams title screen file has a named compressed "subfile" (LoadLIBShape -> LoadLIBFile), while in the CatAbyss case the file is standalone, at least in terms of having compressed "subfiles" (LoadShape -> BLoad, instead of anything like LoadLIBFile).

So it may be simpler to tell a few facts about the shape archives for CatAbyss. The following is handled by BLoad. The file begins with the 4-bytes string of "CMP1", which appears to imply LZH compression ("COMP" looks like LZW). Since only LZH decompression is involved, this is what is assumed from now on. Next, a 10-bytes long CMP1Header struct is read from the file, and memory is allocated for the decompressed data (its size resides in the struct). Assuming there's enough memory (if not then I think there are *very* big problems, though), the whole file is loaded to memory (looks like there are two open file handles in use for the same file while it's done, hmm...). Finally lzhDecompress is called with the compressed data (all file minus first 14 bytes just read beforehand).

Again ignoring the LZH details for now, and back to LoadShape, we have the decompressed data. It begins with 4 bytes of the "FORM" string, followed by a 4-bytes length value in big-endian order, followed by 4 bytes of "ILBM". For probably-technical reasons this length value is then increased by 4. Assuming we're talking about the file SHP05.ABS from The Catacomb Abyss v1.13, we get to a mention of "BMHD", followed by a 4-bytes chunkLen value in big-endian order. A BitMapHeader struct is then read, with the 16-bit x,y,w,h fields being stored in big-endian order within the file. At this point, let's call (ChunkLen+1) & 0xFFFFFFFE the "corrected" ChunkLen. Then, for any arbitrary reason, "corrected" ChunkLen + 8 bytes are skipped from the beginning of the aforementioned "BMHD" string, and the scanning of decompressed data continues.

It then looks like 56 bytes of an unused chunk follow (4 bytes of length in 32BIT BE format, followed by 48 bytes beginning with "CMAP"). This is repeated with "GRAB" and some "CRNG" chunks, then a "TINY" chunk. Finally the "BODY" chunk appears. Following the "BODY" string is again a 32BE (big endian 32-bits long) 'size' field, representing data to read from the file. Here SHP->BPR is calculated from SHP->bmHdr.w for some reason, and then 'size' bytes are read into a newly allocated buffer to be pointed by SHP->Data. The loop ends once a "BODY" chunk is found.

To finish, about LZH decompression, again I don't have a lot of ideas. While trying to look for something about that, the first result in a Google search was actually CatacombApocalypse/LZHUFF.H.
For a similar query (guess which) the first result is... keen/lzhuf.c.

But maybe this document can be useful: http://oku.edu.mie-u.ac.jp/~okumura/com ... compr2.txt

User avatar
Levellass
S-Triazine
Posts: 5261
Joined: Tue Sep 23, 2008 6:40

Post by Levellass » Tue Dec 02, 2014 5:30

Yeah, we have the format of the decompressed data down pat; a lot is based on the old paint files used to construct the graphics. (Keen Dream's title screen even has a preview image stored in the data I believe.) The RLE compression is also understood, it's the LZH that's a problem.
What you really need, not what you think you ought to want.

Calvero
Vortininja
Posts: 86
Joined: Tue Jan 29, 2008 15:31

Post by Calvero » Tue Dec 02, 2014 21:32

NY00123 wrote:It begins with 4 bytes of the "FORM" string, followed by a 4-bytes length value in big-endian order, followed by 4 bytes of "ILBM". For probably-technical reasons this length value is then increased by 4. Assuming we're talking about the file SHP05.ABS from The Catacomb Abyss v1.13, we get to a mention of "BMHD", followed by a 4-bytes chunkLen value in big-endian order. A BitMapHeader struct is then read, with the 16-bit x,y,w,h fields being stored in big-endian order within the file. At this point, let's call (ChunkLen+1) & 0xFFFFFFFE the "corrected" ChunkLen. Then, for any arbitrary reason, "corrected" ChunkLen + 8 bytes are skipped from the beginning of the aforementioned "BMHD" string, and the scanning of decompressed data continues.

It then looks like 56 bytes of an unused chunk follow (4 bytes of length in 32BIT BE format, followed by 48 bytes beginning with "CMAP"). This is repeated with "GRAB" and some "CRNG" chunks, then a "TINY" chunk. Finally the "BODY" chunk appears. Following the "BODY" string is again a 32BE (big endian 32-bits long) 'size' field, representing data to read from the file. Here SHP->BPR is calculated from SHP->bmHdr.w for some reason, and then 'size' bytes are read into a newly allocated buffer to be pointed by SHP->Data. The loop ends once a "BODY" chunk is found.
That's just the LBM Format, isn't it?

User avatar
Levellass
S-Triazine
Posts: 5261
Joined: Tue Sep 23, 2008 6:40

Post by Levellass » Wed Dec 03, 2014 6:32

It is indeed good sir, it is indeed.
What you really need, not what you think you ought to want.

NY00123
Vorticon Elite
Posts: 442
Joined: Sun Sep 06, 2009 19:36

Post by NY00123 » Wed Dec 03, 2014 23:03

Yeah, looks like it is the case.

I guess that for now, reading some parts of the document "compr2.txt" linked above, and possibly some accompanying source codes (although not all of them are necessarily available), can be a good path to a better understanding of the LZHUF decompression routines.

User avatar
Multimania
Grunt
Posts: 20
Joined: Sat Nov 10, 2007 8:10
Location: Hiding in a small, cramped corner of the BwB megarocket.
Contact:

Post by Multimania » Thu Dec 04, 2014 11:41

Okay, a (very) rough guide to LZHUF:

It's adaptive Huffman + LZSS.

Basically, there's a Huffman dictionary that encodes both output bytes (0-255) and lengths of repeated data (from 2–30 bytes). This dictionary
starts off with all leaves having equal probability.

Every time you decode (or encode) a value, you increase its probability by 1. If the probabilities exceed 0x7fff, they are halved (rounding up). When the probability of any node is changed, the tree is reconstructed to be optimal for those probabilities.

If the value you decode is < 256, then you output that character. If it's >= 256, then you have a reference to N = (value - 256 + 2) bytes of repeated data. The position of that data is encoded in two parts. The top 6 bits are encoded with a fixed Huffman table (stored in the decompression code), the bottom 6 bits are stored directly. You then go back that number of bytes, and copy N bytes into the output.

It's a moderately complicated algorithm, and the LZHUF code from Keen Dreams is really difficult to understand. :bloody


Hope this helps.
– David

User avatar
Levellass
S-Triazine
Posts: 5261
Joined: Tue Sep 23, 2008 6:40

Post by Levellass » Fri Dec 05, 2014 6:19

It helps a great deal; it's amazing they went to such lengths before settling on equally effective plain Huffman.
What you really need, not what you think you ought to want.

NY00123
Vorticon Elite
Posts: 442
Joined: Sun Sep 06, 2009 19:36

Post by NY00123 » Sat Dec 20, 2014 22:51

Alright, this is going to be a three-parts post:

1. I should've really said (or typed) it earlier, but thanks to Multimania for the information about the LZHUF decompression! These can surely be useful for at least one individual, or so I guess.

2. It may also be a good chance for a little correction of mine. There's a bit earlier Shareware release of The Catacomb Abyss, that is version 1.12, for which there's no separate INTRO.EXE program. Basically, the closest thing to an intro is "embedded" in the game executable, which doesn't really differ from a few of the first titles produced by the original id Software members, even if for Softdisk (say Keen Dreams, Commander Keen 4-6 and Catacomb 3-D). So an earlier comment of mine about having a separate intro for the purpose of conserving memory may not apply, but then maybe it does. The various object states are defined in The Catacomb Armageddon and Apocalypse to be in so-called "far memory", meaning they don't have to reside in a specific 64K-sized data segment (this is not the case with the other games supported by these source ports as of typing this post).

Furthermore, it looks like the choice of difficulty (Novice vs Warrior) doesn't exist in v1.12.

3. Finally, there's another update to the source port(s). Quoting again from the recently edited first post, support for the whole Catacomb Adventure Series is now in. This release should be compatible with the 3D Catacomb titles currently available from GOG.com, or to be more specific: Catacomb 3-D: The Descent v1.22, The Catacomb Abyss v1.24, The Catacomb Armageddon v1.02 and The Catacomb Apocalypse v1.01.

Please note that Armageddon/Apocalypse saved games are generally incompatible with the DOS executables. For more details you can check out the README file, although admittedly a few details are a bit technical, but there's a workaround that may partially work.

Changelog

Dec 20, 2014 (v0.9.12):
- Complete support for the Catacomb Adventure Series has been integrated.
In addition to version 1.13 of The Catacomb Abyss (Shareware release),
there is support for Abyss v1.24, Armageddon v1.02 and Apocalypse v1.01.
- It shall be noted that while it's possible to save and load games for The
Catacomb Armageddon/Apocalypse, most chances are they won't be compatible with
any of the original DOS executables. A new, hidden farptrsegoffset setting can
be added to the cfg file in order to make this somewhat more feasible, although
there's no guarantee it'll always work with the same value, given the structure
of the saved games (doesn't apply to Abyss).
- For another note, if the cheat code letting one cycle through ceiling/sky
colors is used while there is flashing (a lightning), this can lead to
so-called "undefined behaviors". It may look like there's no harm,
but a crash and/or other unexpected side-effects may occur.
- It turns out VSync was still enabled in the preceding release (v0.9.6) by
default for The Catacomb Abyss (and Catacomb 3-D), as well as Keen Dreams with
CGA graphics. Now, though, some adjustments were made in regards to timing, so
Skull 'n' Bones from Catacomb 3-D can be played back at a rate closer to the
original while VSync is toggled on, and not just while it's off. Furthermore,
VSync is again toggled on by default for all supported games, with the
exception of the CGA release of Keen Dreams (where it's off by default).

User avatar
Levellass
S-Triazine
Posts: 5261
Joined: Tue Sep 23, 2008 6:40

Post by Levellass » Sun Dec 21, 2014 1:57

*Salutes*
What you really need, not what you think you ought to want.

NY00123
Vorticon Elite
Posts: 442
Joined: Sun Sep 06, 2009 19:36

Post by NY00123 » Fri Mar 13, 2015 7:48

Alright, it's true some time has passed since the last release of December, but this can happen. Anyway, we have a new release now. If you want, you may call this a "pre-Keen day" release.

Quoting from the recently edited first post as usual, it's a little bit overdue, but finally there is a title for the whole codebase now, not just specific source ports. It shouldn't be a surprise, but this name is Reflection Keen. Some other titles may still be mentioned, here and there, though.

Along with other updates, this release has experimental "modern" support for game controllers (with the layout of the Xbox 360 controller or similar). It is currently disabled by default, and there may be some limits (e.g., you still need a keyboard in order to activate debug keys' functionalities, aka cheat codes).

More details can be found on the README. However, as a little side-note I've forgotten to mention in the README that you may currently use the left face button (X button on the Xbox 360 controller) for toggling "Shift" in text input...

Image

Changelog

Mar 13, 2015 (v0.10.0):
- After some time of not having one title covering the whole codebase,
"Reflection Keen" is finally in use.
- Experimental support for alternative controller schemes is implemented. This
should theoretically make it more comfortable to use game controllers with the
Xbox 360 Controller layout. Taking advantage of the SDL_GameController API,
a mapping table is used so this is theoretically not limited just to XInput
controllers. This is currently disabled by default, though, and at
least one edit to the generated cfg file is expected. Furthermore,
as a side-effect SDL 2.0.2+ is known to be required now.
- Alright, it's probably better to consider this unofficial, but there is now
partially-tested support for big-endian architectures (or bi-endian archs in
big-endian modes). It's a bit difficult to test this with the lack of
appropriate hardware, though (in particular audio support is totally untested).
In addition, commonly used architectures of these days (x86, x86-64, ARM)
generally operate in little-endian modes. So, again, better assume that
big-endian modes aren't officially supported.
- It should be possible to disable the sound subsystem by enabling
the "disablesndsubsystem" setting in the generated cfg file. The code
changes also include a fix for an infinite loop in SD_WaitSoundDone
in case the sound subsystem is disabled. Furthermore, in such a case
a silent PC Speaker is emulated, but the OPL emulator isn't running.
- Code can optionally be built as C++ now, using g++ version 4:4.8.2-1ubuntu6
(should be based on v4.8.2). It is still built as C by default, but the ability
to build the code as C++ assisted with catching at least a few bugs.
- Added a fix (or possibly more than one) for Catacomb 3-D crashes. Note
that the way this was done, a vanilla Catacomb 3-D rendering glitch is *not*
reproduced now. It may be possible with more efforts, although this obviously
depends on the original EXE's layout.
- As in the original DOS executables, there shouldn't be a noticeable fizzle
fade after loading a saved game in any of the Catacomb Adventure Series titles
(except for maybe the first time after starting the application).

NY00123
Vorticon Elite
Posts: 442
Joined: Sun Sep 06, 2009 19:36

Post by NY00123 » Sat Oct 17, 2015 11:55

Hey there,

As you can see, a (relatively?) long time has passed since the last release. While I don't expect any addition as exciting as support for an additional game, there are clearly changes to the codebase. For some more details you can check out the source code repository: https://github.com/NY00123/refkeen/

As of this post, I would like to have at least a bit of feedback on the following.

One thing that Reflection Keen currently lacks is its own application icon. Having a brief idea of what can be used (a pair of mirrors on the sides, filled with a light cyan color), pckf.com member DoomJedi has been kind to work on a few samples:

Image

I think that my current preference is towards having humans in the mirrors, as well as a full symmetry (with respect to a central vertical line). You can ignore these, though.

Thanks for any opinion/suggestion that one may bring out!

GoldenRishi
Vortininja
Posts: 223
Joined: Mon Nov 05, 2007 3:20

Re: Reflection Keen (ports of Keen Dreams and all 3D Catacom

Post by GoldenRishi » Sat Oct 17, 2015 23:50

NY00123 wrote:UPDATE (Mar 13 2015): It's a little bit overdue, but finally there is a title for the whole codebase now, not just specific source ports. It shouldn't be a surprise, but this name is Reflection Keen. This comes from a release which, along with some other modifications, has experimental "modern" support for game controllers (with the layout of the Xbox 360 controller or similar).

UPDATE (Dec 20 2014): Support for the whole Catacomb Adventure Series is now in. This release should be compatible with the 3D Catacomb titles currently available from GOG.com, or to be more specific: Catacomb 3-D: The Descent v1.22, The Catacomb Abyss v1.24, The Catacomb Armageddon v1.02 and The Catacomb Apocalypse v1.01.

Please note that Armageddon/Apocalypse saved games are generally incompatible with the DOS executables. For more details you can check out the README file, although admittedly a few details are a bit technical, but there's a workaround that may partially work.

ImageImage

UPDATE (Nov 30 2014): Support for Catacomb 3-D (The Descent) has been added. It has taken much less time to add this than Abyss, given that Abyss is close to a direct derivative of 3-D with some added "Gamer's Edge" specific code. As expected, this port is called "Ref Catacomb 3-D".

Image

UPDATE (Oct 25 2014): Support for Catacomb Abyss has been added. One main reason is that both Keen Dreams and Catacomb Abyss share a lot of common code.
I remember playing these games 10 years ago and really liking them. It's cool to see community support for these. When I think of 2.5D FPS games, this is actually the one that comes to mind. I never actually played a lot of Wolfenstein 3D or Doom.
(Used to be LordofGlobox)

User avatar
Nospike
Keen Minecrafter
Posts: 1308
Joined: Tue Mar 30, 2010 13:56
Location: Carlsbad, Czech Republic

Post by Nospike » Sun Oct 18, 2015 11:21

Wouldn't Duke 3D also count as a 2.5D shooter? The map is pretty detailed 3D but all the actors, items and things to interact with are 2D sprites...
It just might be done someday. The chance is always there.

GoldenRishi
Vortininja
Posts: 223
Joined: Mon Nov 05, 2007 3:20

Post by GoldenRishi » Sun Oct 18, 2015 16:03

Nospike wrote:Wouldn't Duke 3D also count as a 2.5D shooter? The map is pretty detailed 3D but all the actors, items and things to interact with are 2D sprites...
Yes, absolutely. It was made from the in-house Apogee 3-D engine, which was a ray-casting 2.5-D engine. I read about this a few weeks ago, it's pretty interesting.

I've got to be honest, I have NO idea how they made those 2.5-D engines so computationally efficient and capable of being run on 1992 computers. Honestly, John Carmak is kind of a programming genius, it's really incredible. I mean, Apogee had the leg up when it wrote the engine for Duke 3D, but Carmak created the technology for games for the first time (Yeah, there's some debate over that, but he created it for the first time rendering sprites and having sound and music, etc, all of which at the time was a serious feat). It's really amazing. I mean, hopping from side-scrolling engines to functional 2.5-D engines to literal 3-D vector games in the space of 5 years is just ridiculously amazing. Everyone at Id Software (The real Id Software, imo, which was just 5 people: Hall/Carmak/Carmak/Romero/Prince) were extremely talented and had a great synergy.
(Used to be LordofGlobox)

Post Reply