For whom it may concern

All data is compressed by overlapping the data blocks.

 

Does this mean that, in order to get the 6th frame of animation for a sprite you must iterate through frames 1, 2, 3, 4 and 5?

No, we use pointers to the beginning of each block of the frames.

 

ExplodePtrLo
DC.B <Explode0_0, <Explode0_1, <Explode0_2, <Explode0_3, <Explode0_4
DC.B <Explode1_0, <Explode1_1, <Explode1_2, <Explode1_3, <Explode1_4
DC.B <Explode2_0, <Explode2_1, <Explode2_2, <Explode2_3, <Explode2_4
...
DC.B <Explode15_0, <Explode15_1, <Explode15_2, <Explode15_3, <Explode15_4

And a 2nd table (ExplodePtrHi) for the high byte.

greedy works great if the dataset is structured to match it. there will always be exceptions, but usually when the data is random, that is, you cant' organize it.

That's why my algorithm permanently randomizes the data set. So Greedy will met bad and good conditions.

I promised to release my program when it is done. This is now and I have added the executable to the first post.

Sounds awesome! Doesn't run so well under wine. Any chance we'll see the sources?

I don't think the code is ready for that. Sorry.

Updated to version 0.93

Improvements:

• much better scanner (handles tabs and comments, skips empty lines)
• output can be identical to input now (new default)
• fixed a bug when data is completely included in other data
• overlapping matrix file is sorted identical to data in generated output file
• can handle special zz and zr formats (constants used for easier graphics data definition)
• some new statistic information added

Maybe a stupid question, but: how do I run this?

(limited to linux, and if wine wont do, Im screwed but still I'd like to know

You just start the executable with the file containing the graphics you want to optimize as an argument. There are a few more arguments for fine tuning, but none of them is really required.

 

The output are two files:

• a matrix showing how each graphic block overlaps with each other
• and the optimized graphics file.

The code is a mess, so I won't post it here. It uses FreePascal which is available for Linux too. I can PM you the code then.

 

Or you send me the graphics file and I optimize it for you.

The code is a mess, so I won't post it here. It uses FreePascal which is available for Linux too. I can PM you the code then.

 

 

I'm set up for Pascal now and should be able to create a Mac executable.

Sorry for the very late bump, but I just came across this post. Could you provide some background as to how the "overlapping blocks" method of packing data works, in principle?

 

I would like to better understand how to efficiently pack large amounts of repeating data.

 

dZ.

This is very simple.

 

If the last n bytes of one data block are identical with the first n bytes of another data block, we can remove the last n bytes of the first data block and overlap the end of this data block with the beginning of the other one.

 

Also it may be possible, that the content of a whole data block is completely included in another data block, but that's very rare.

Thank you, Thomas, for that explanation, it makes sense.

 

I do have more questions. It seems that this algorithm will force you to mix the frames of multiple sequences, which will require some indexing strategy, consuming space in the process. This also incurs additional processing during reads.

 

I guess since you are using this technique, the savings overwhelm the costs in additional complexity and processing overhead, but I would like hear your thoughts on the typical overall savings this produced, and what strategies there are to reduce the overhead.

 

-dZ.

Also, would you mind stating the problem in terms of the Greedy algorithm? I'm having a hard time understanding how you applied it your optimization. (I'm new at this.)

Not sure why you think it increases complexity. Unless you can calculate the address (e.g. for same size date like digits), you need an address label anyway. Maybe I misunderstand you here. Can you give an example?

 

The savings greatly depend on the amount and type of data you have. The more random the data is, the lower the chances for overlapping are. But usually the data has some structure and then you can save 20% or more.

 

As for Greedy: Greedy only finds local minimums (see Wikipedia). A single loop will usually be far from the optimum. By randomizing the data before applying Greedy, you create different situations, which result into different local minimums. All you have to do, is to remember the lowest minimum. Usually it takes only a few hundred or thousand iterations until the best solution (or a very, very close one) is found.

Edited Friday at 05:23 PM by Thomas Jentzsch

Update: There seems to be a severe bug in v0.93. Until this is fixed (which may take quite some time) please use v0.91 instead!