Eckhard Stolberg wrote:
> But you might also have to give some hints about how to fit
> all those levels into a 4KB VCS binary. ;-)
Well it's quite complicated, but I'll try now:
First you have to look at the 6x6 grid as six strips for rows and columns each.
Each empty! strip can have (22) different pattern of small and long cars. The patterns are sorted by their frequency. The empty pattern is the most frequent, patterns with two cars are least frequent.
The first strip, that's defined is the one with the yellow car. This can only have four different patterns.
The following strips are defined in a special order, a vertical stripe allways follows a horizontal one. You'll soon see why.
Before I define a new strip (execept the first one), i count the number of patterns that still fit into the empty spaces of the strip. These numbers can be 22 (empty strip), 13, 8, 7, 4, 2 and 1 (only the empty pattern fits) and there's a special compression table for each number. Then i'm calculating the index of the new pattern in the compression table.
That means: I'm going through the sorted list of all patterns and try if a pattern fits into the current strip or not. If it fits, I increase the index. I stop when I reach the pattern which has to be defined. Now i've got the index into my compression table.
The compression tables define the bit pattern for each index, more frequent indices get shorter bit patterns of course. (If the number is 1, i don't need any bits at all!) The first strip (with the yellow car) has his own compression table too.
A compression table for number 4 might look like this: %110, %10, %0, %111. So i'll get an average of (hopefully) much less than the normal needed 2 bits (2^2 = 4).
Now you can see the reason why I'm mixing columns and rows when defining the strips. The sooner i can reduce the number of free patterns, the more efficent is the compression.
Then I tried all computed defined pattersn, and choose those which I could compress best, optimized the compression tables and iterated the process. Then I had to remove all nearly duplicate patterns and I tried to reduce the average number of used spaces, because that makes the puzzles a bit more difficult.
That way I now need less than 2.3 bits/strip or about 2k for 600 puzzles.
Due to this, the decompression is a bit slow (~7000 cycles/puzzle), you'll see when you select random levels.
I hope that was a bit understandable.
Have fun!
_______________________________________________________
Thomas Jentzsch | *** Every bit is sacred ! ***
tjentzsch at web dot de |
______________________________________________________________________________
Die Fachpresse ist sich einig: WEB.DE 18mal Testsieger! Kostenlos E-Mail,
Fax, SMS, Verschlüsselung, POP3, WAP....testen Sie uns! http://freemail.web.de
-
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
