Format80 decompression

[MrFlibble]

Introversion (www.introversion.co.uk) has release a few games that keep the old 2D form for the most part - great games because they keep focus in the right place: game play before stunning graphics.

Interesting - I'll sure take a look.

Still, I feel that Dune II needs a nice engine recreation (since we're not likely to persuade EA to release the source code anyway - I mean, if they indeed still possess it), something like C&C Gold was to regular C&C. I think Dune Legacy was heading in that direction, but I haven't been checking the project for quite some time. (Stefan's Dune 2 The Maker is different because it's more of a tribute to Dune 2, a project inspired by the classic rather than a straight "clone").

[ArrakisResearchCo]

I've tried to keep the details of my project to myself to avoid disappointing people. Revealing too much too early usually breaks a project so I'll try to keep info limited. The documentation of the Dune 2 files is just a starting point - should be easy enough guessing the outcome from this :)

[MrFlibble]

Fair enough. I haven't been trying to trick some info about your project out of you anyway :) - it was just a general comment. To me, the largest limitation in Dune II is not the absence of the unit group selection as some people often claim, but the strict limit of units and structures available on the map at any given time, and the map size. And, of course, the AI should be improved at any rate (this has been naturally done in all Dune 2 remakes known to me - except Dune 2: The Sleeper Has Awakened which doesn't have single player mode).

[ArrakisResearchCo]

I know that your comment was more of a general nature my friend. I try to keep notes on wishes and suggestions for improvements to the game - kind of a "super wishlist" (even tho most of the notes are scattered across a large number of files, forum threads, site messages and what not).

Most of the limits set in the original Dune 2 were due to hardware and OS limitations back then however I beleive that if Westwood had adopted Lord British' (the Ultima series) way of handling maps Dune 2 could have had a lot more scenarios and way bigger maps.

I do like the limitation on the number of units for any given scenario. Most of the unit limitations keep you on your toes when planning strategies for taking down the computer player. Sometimes it would be nice to have access to a few more structures tho but the limit is still something that forces the player to do more with less - adds to the game play :)

Maps could be a lot larger - even under the DOS 640Kb limit. Those who do plan for remakes or tribute versions should (in my humble oppinion at least) plan for bigger maps. I do. I've looked into the map coding of the Ultima series and I've experimented with map handling like they did back when Ultima 6 was released. Ultima uses map chunks that are then referenced to each other to make memory and disk usage minimal. On todays systems that doesnt seem like a good idea anymore given the size of harddisks and the speeds of modern CPU's however when we start talking about internet transfer times we have a different scenario. Yes - internet uplinks keep getting faster but I'd still prefer only having to wait a few seconds compared to say 5 minutes of map downloading.

I don't have exact numbers at this time (most is just experiments still) but I'm guessing that it would be possible to have maps as large as 16384 x 16384 tiles and still just keep a limit of 4-5 seconds transfer time for maps of these sizes. I'm still working on this.

[MrFlibble]

I do like the limitation on the number of units for any given scenario. Most of the unit limitations keep you on your toes when planning strategies for taking down the computer player. Sometimes it would be nice to have access to a few more structures tho but the limit is still something that forces the player to do more with less - adds to the game play :)

Eh, I was expressing map maker's point of view on that rather than the player's :) E.g. if you really want a nice mission where you have 5 enemy bases (what I want to do in my SD2SE project, and was partially done in the original Super Dune 2), the 80-structure limit is very pressing - you have to cut those AI bases to the utmost, or the player will have huge problems constructing a functional base of his own. You may know that in the last missions for all three Houses in the original Dune 2, all AI players have power shortage, and some don't even have a single windtrap in their base (which leads to AI buildings slowly decaying and production efficiency decreasing). Unit limit is not that problematic, 80 units per map are fine, but nevertheless, a slight increase would be neat.

I don't have exact numbers at this time (most is just experiments still) but I'm guessing that it would be possible to have maps as large as 16384 x 16384 tiles and still just keep a limit of 4-5 seconds transfer time for maps of these sizes.

Sounds impressive :)

[ArrakisResearchCo]

Hmm - keyboard forgot to write my thoughts about the structure limit somehow :P

[MrFlibble]

Seems that some of the shadow pixels and bright pixels are missing or miscalculated in v1.0.

BTW, could you please expand on that, ArrakisResearchCo?

[ArrakisResearchCo]

Well - the turret tile you mentioned - tile 367 - is missing a few pixels at the turret base in the v1.0 ICON.ICN file. It should have a wider bright base at the top of the tile and a wider shadow base at the bottom of the tile on both sides of the turret. (I'll update my "ICON.MAP" page later with better images)

All the tiles are stored in a compressed format that needs to be decompressed or expanded - requires a bit of math to do it. I've tried single step debugging my math that decompresses the tiles in an attempt to find a possible math error that could account for this pixel error on that particular tile. I've tried changing the math a bit but all my attempts to try to correct my math for this tile just ends up making all other tiles come out garbled. My guess is that the original graphics designers simply forgot to draw the base of the turret tile 367 with all the pixels. At some point Westwood was notified about this graphics error and may very well have fixed this in later versions as we see in the v1.07 ICON.ICN file.

I'm currently rewriting my site and preparing to migrate from junkyard.dk to dune2.dk but as soon as I've moved I'll start a deep analysis of both versions of ICON.ICN. I currently have 4 different versions of Dune 2 and I'll try to include a complete file reference aswell as documentation for the version differences.

[MrFlibble]

Well - the turret tile you mentioned - tile 367 - is missing a few pixels at the turret base in the v1.0 ICON.ICN file. It should have a wider bright base at the top of the tile and a wider shadow base at the bottom of the tile on both sides of the turret.

So nothing more than that? Good. Then, I suppose, it would suffice to fix this frame and the IX graphics, and we'll get the perfect Dune 2 tileset :)

My guess is that the original graphics designers simply forgot to draw the base of the turret tile 367 with all the pixels. At some point Westwood was notified about this graphics error and may very well have fixed this in later versions as we see in the v1.07 ICON.ICN file.

That's exactly how it is - no error of your tool, but the error of the designers, since it's visible in the game as well. So they fixed it in v1.07, but, for a reason, did not fix the IX graphics. Maybe they were only using House Harkonnen for testing purposes? :)

[ArrakisResearchCo]

I've just finished rewriting my Tile Viewer and it is now able to handle at least the 4 different versions I currently have to test against.

The raw tile data suggests that all tiles are housed by Fremen. The flag / structure / pad / unit colors all conform to the Fremen colors in the IBM.PAL palette.

All 4 versions all have the same pixel error on the House of IX structure - there might very well be a color replacer within the EXE that replaces these pixels on the fly like I do in my Tile Viewer.

The 4 versions I'm currently working with are :

1: 1.00

2: 1.07-US

3: 1.07-EU

4: 1.07-HS ("HS" = "HitSquad" - the version I supplied to the community. Let me know if you want a copy)

I've tried to compare the 4 different versions I have against each other and it seems that the first "half" of the tile set is nearly identical regardless of version. In versions 1.07-* the first tile is black (I havnt yet checked wether it's transparent or contains transparency or not) but in 1.00 it's a cracked concrete slab. Once we get past the second of the two spice bloom tiles we'r in the structure tiles and here's the biggest difference between versions. The 6 tiles that make up the animation for the Hi-Tech Factory dome (opening) and the 4 tiles for the gate of the Repair Facility (opening) are missing in all v1.07 tile sets. That makes up for the 10 tile count difference.

I have not yet analysed the ICON.MAP file for frame differences but since this file is identical in size in all 4 versions there should be a difference in the tile references for the frames making up for the animation frames lost in v1.07-*. A patch of ICON.MAP should make it possible to reintegrate the animations of these two structures provided the ICON.ICN file is also replaced or patched.

My decompression code is based on a piece of C code (sorry dear original Author - I forgot note your name for future credit). I still need to construct a compressor that can compress the raw tile pixels back into the ICON.ICN format. Note that this file is structured in the FORM format (thanks Olaf for pointing this out).

Since all the 1.07 versions are identical it's just a matter of changing the tile indexes for the pixel replace on House of IX.

While writing this I noticed a difference in the IBM.PAL file aswell. It seems that the Fremen colors are a bit more red / darker in v1.00 while a bit more brownish / brighter in v1.07-*. The 3rd darkest color tone of the Fremen house color is near red in v1.00 while it's corrected in the v1.07-*.

I'll note my findings on my site aswell (when I get the time).

[MrFlibble]

While writing this I noticed a difference in the IBM.PAL file aswell. It seems that the Fremen colors are a bit more red / darker in v1.00 while a bit more brownish / brighter in v1.07-*. The 3rd darkest color tone of the Fremen house color is near red in v1.00 while it's corrected in the v1.07-*.

That's a very interesting find indeed.

I've always thought the ICON.ICN file is identical for all versions 1.07...

[ArrakisResearchCo]

I've run a binary compare of the 3 v1.07 ICON.ICN files. They are in fact identical. I'll be documenting the differences between versions on my site in the future aswell.

[Nyerguds]

you can check that with the command line command 'fc'.

fc /b file1 file2

will compare the 2 and tell you if they're different or not.

('/b' means binary compare. If you don't specify this it'll interpret the files as text, which can give pretty ugly results since it'll try to show any differences as text too)

[ArrakisResearchCo]

That's what I did to compare them :)

[Nyerguds]

Yeah, you replied while I was writing that post :P

[ArrakisResearchCo]

I've been trying to dig deeper into the base nature of the compression of the tiles (50% compression rate is pretty good). Someone may have figured this out a long time ago but I have not been able to find anything describing this so I'll share the info here.

Tile compression is made up of 3 data blocks / reference tables.

(In the following "TileCount" refers to 399 tiles for v1.00 and 389 for v1.07-*)

1: Reference Palette (This is the "RPAL" block in the file)

The compression is based on a 16 color maximum for each tile - i.e. no tile contains more than 16 colors in any given tile.

Since each tile never contains more than 16 colors the stored data block is only 16 bytes pr. tile where each byte is a reference to the palette index of the color needed.

Each of these 16 byte blocks is sorted lowest palette index first highest palette index last. If less than 16 colors are used the rest of the 16 byte block is filled by zeros. Note that if palette index zero (the first black color) is in the tile a leading zero is placed in the block otherwise the first (and lowest palette index) is the first byte.

Since these blocks are all sorted there's a chance that the same color contents of a tile may be repeated and if repeated already stored blocks are re-referenced.

2: Structure Set Block (This is the "SSET" block in the file)

The structure set block contains TileCount * 128 bytes of "compressed" data. These blocks are 128 double-nibbles (a nibble is a 4 bit value - double-nibble is a byte). 128 * 2 = 256 pixel values - 16 * 16 = 256 pixels. Each nibble in a 128 byte block is a simple reference to one of the 16 byte color references. That's why each compressed byte is split up in two.

(Side note: this block in the file contains 8 bytes prefix data that are currently unknown and have to be removed before attempting to decompress the tiles. What these 8 bytes contain and are supposed to do I have no clue. Anyone ?)

3: Reference Table (This is the "RTBL" block in the file)

The Reference Table is exactly TileCount large of bytes. Each byte is a simple and direct reference to the Reference Palette block - the index of the 16 bytes associated with this tile.

To decompress a tile first read the byte from the Reference Table for the corresponding tile and use the value as a reference to the two other block creating two new data blocks: one that's 16 bytes large and one that's 128 bytes large. Split each byte in the 128 byte block into two new byte values (hi-order nibble is drawn first, lo-order nibble is drawn second). Each nibble is a reference to the 16 byte block - get the value from the 16 byte block - then get the color in the palette that the nibble points to and you have which color to draw. Repeat for the second nibble.

Now that I've figured out the exact nature of the compression I should be able to write a compressor that can re-compress the tiles. Since there's a limit of 16 colors maximum for each tile the editor used to edit a tile should also respect this limit. The editor should also respect that palette index 0 (the first black color) is used as transparency in the tiles. My new TileViewer is able to handle the different versions of the ICON.ICN file and it already has a palette view and a zoom view of the tiles. I'll attempt to write a tile compressor, add a pixel editor to the existing UI of the TileViewer and I'll try to include a ICON.MAP editor in it aswell.

[Nyerguds]

So, to make your own tile, you basically need to have a 16 colour palette with colours which can be selected from a loaded Dune II palette, and then a graphical editor to paint a 16x16 image with those 16 selected colours?

It's kinda funny to see that it isn't really compressed at all, but just stored in nibbles, using a 16-colour sub-palette of the original 256-colour one.

I wish I had some time to look into this stuff myself.

Of course, at this point, another issue is if files you create yourself are accepted by the game if they don't have that information you remove. Could you check if that information could just be something like the radar colour? I've seen that with TS SHP graphics files, where unknown information that was discarded turned out to be the radar colour (which is unused for units and buildings, but still important for stuff like tiberium and rocks. All editors made it black).

[ArrakisResearchCo]

Correct.

All tiles are drawn using the IBM.PAL palette - no exceptions.

The "Windtrap" structure uses palette blending to create the animation of the three "towers". Palette entry 223 is used for this palette blending. All other structures use tile swapping to create the structure animations - including all the flags.

I havnt had the time yet to experiment with decompression / compression of ICON.ICN because I've been trying to figure out what the first 8 bytes in the "SSET" block mean but there's a difference between the two versions (v1.00 and v1.07-*). There has to be a meaning for these bytes since they differ but I'll just have to experiment with the two prefix 8 byte blocks for the different versions.

My plan is to re-write my TileViewer to become a TileEditor with a built in pixel editor that respects the 16 color per tile limit aswell as treat color zero as transparent. Once completed I'll distribute a setup package and make the source code available for download aswell. Most people should be able to read VB6 code if I put in some comments about what's going on.

[Nyerguds]

Nice :)

Yeah I could quite easily do .net and perhaps even java ports of that.

[ArrakisResearchCo]

I didnt notice your edit before now Nyerguds but I'll try to describe my findings up till now.

As mentioned there's an 8 byte prefix block in the "SSET" part of the file. Here are the decimal values of these 8 bytes for the two versions of ICON.ICN :

v1.00

-----

0, 0, 128, 199, 0, 0, 0, 0

v1.07-*

-------

0, 0, 128, 194, 0, 0, 0, 0

If I compare these numbers to tiles then the third byte, 128, points to the plan sand tile regardless of version. The fourth byte, 199 / 194, could be a half-value of the tile count. Remember that v1.00 contains 399 tiles: 199 * 2 = 398 .. v1.07 contains 389 tiles: 194 * 2 = 388. The first tile in the file is never used and in v1.07 is a checkerboard of two dark shaded colors while it's a cracked concrete slab in v1.00. If we remove this tile from the tile count we get the same numbers as the fourth byte indicates.

My guess is still that the third byte, 128, is a reference pointer to the first environment tile which means that the environment tiles must be within a byte range. Wether I'm correct or not remains to be seen.

I've already tried comparing these values to the palette but there doesnt seem to be anything solid there. Colors don't match anything that makes sense at this point. The only thing that makes sense is a sand pointer and a total tile count divided by two.

I'll post more on this 8 byte prefix block when I've finished writing the "compression" class I'm working on. Once it's completed I can start experimenting with changing tiles and the 8 byte prefix block and start the game to see what happens if I change things. May get confirmation of my theories about this block.

[Nyerguds]

so, try changing it and see how the game reacts? It's standard procedure in research like this :P

[ArrakisResearchCo]

Yup - that's the plan. "Trial and error" - only way to get anything confirmed when researching stuff :)

I'm working on my new Tile class that will handle (de)compression of the tile data. I'll post my findings later.

[Nyerguds]

Hmm... a bit of messing around reveals that changing the first byte (80) doesn't seem to do much at all. The second byte does indeed seem related to the size. If I put it on 00, all tiles are messed up. On 80, the terrain is OK but the buildings are still messed up. Increasing it to the original value shows increasingly less messes up buildings, showing that it progresses through the tiles list. Going over the limit didn't seem to do much at first, but when I went too far over it, the ingame screen suddenly stuffed up (completely, as opposed to just messed up tiles) and the game crashed with a "memory corrupted" error message.

(I just edit dune.pak directly with my hex editor. The SSET string is easy to find)

[ArrakisResearchCo]

Interesting. Confirms my theory about size for the fourth byte. We just need to keep the number of total tiles in the file of equal number. Other than that we should be able to change the number of tiles as we wish - allowing for more animated tiles for structures.

[Nyerguds]

We just need to keep the number of total tiles in the file of equal number.

How so? I'd think that identifying this 4th bytes allows us to add as many tiles as we want... well, up to 255

[edit]

Hmm... adding a 01 behind byte 4 also stuffed up everything. This might mean it's read as either a 2-byte or even 4-byte value, which might mean we're not limited to 512 tiles... well unless some other tile indexing systems ARE limited to that, of course. Not sure about that, don't remember exactly how it worked in icon.map