Optimize data overlapping
Programming data overlapping Greedy optimizing
All data is compressed by overlapping the data blocks. For the explosion this was done by Chris before I took over from him. When Nathan asked me, if there is enough space for frames to improve the explosion, I was facing the problem that I would have to optimize the overlapping of the 80 (or more!) blocks by hand again. And that this would always result into less than optimal solutions.
So I decided to write my own program for doing that.
The basic idea was to calculate the overlappings of each block with each other block and then let the code do some recursive depthfirstsearch (DFS) to try all possible combinations. While this worked within reasonable time for 10 blocks, I soon realized, that for 80 blocks this would take forever (complexity is O(n^{n})). So I needed to find a faster way, which should deliver solutions close to the optimum in short time.
I searched the web and found... nothing (well, nothing I could understand ).
Then I experimented with the Greedy algorithm. My first code just started with the 1st block and reordered the other blocks by always selecting the next block with the maximum overlapping. This delivered very fast results, but far from the optimum I had found with my DFS for lower block numbers. So decided to iterate over all blocks as starting blocks for Greedy and then chose the best solution. This returned somewhat better results, but was still not satisfying.
While doing the last improvement, I made a coding error which resulted into mixing the blocks. The calculation result was still OK, but the data generated for DASM was wrong, because I had forgotten to reset the block ordering before each iteration. When I got the result from the last optimization, I remembered that my buggy code had delivered even better results. So I reimplemented the bug again and just fixed the output. Then I let the code run for some more iterations and the results where GREAT!
So this is how my algorithm works now:
 calculate the maximum overlapping between each block and each other block (in both directions)
 call Greedy with random starting blocks many times (e.g. n^{3}) and feed the resulting block order into the next Greedy call
Attached you find the program and some test files, which also offers a lot of options, like page sizes to consider, offsets into pages, various output formats etc. This should be pretty useful.
Attached Files

DOOD v0.91.zip (39.74KB)
downloads: 124 
DOOD v0.93.zip (40.76KB)
downloads: 102
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?