Good scene compression

[+DZ-Jay]

For P-Machinery 2.0, I'm trying to devise a general compression/compacting scheme for graphical background scenes. These are the kind of scenes that are drawn when initializing a level (or a title screen), so processing time is not really a significant concern. Storage size (including size of decompression function) is the main concern.

 

I also don't want to get bogged down in complexity. I don't have much interest in implementing gzip for the Intellivision if RLE would be "good enough" in most cases. (Unless, of course, the benefits are deemed worth the trouble.)

 

What would be a good compression scheme to use? So far I was thinking of using Run Length Encoding, which is simple to use and generally better than nothing in most common cases. Any other ideas? What's typically used on these ancient machines?

 

-dZ.

[+DZ-Jay]

By the way, I found this site with a very nice tutorial on how compression works, for those interested.

[Arnauld]

For what it's worth, below is the scheme I'm using in a few projects. Each command is 8-bit wide, so each word contains 2 commands. Note that this version assumes FG/BG mode and doesn't support GROM cards apart from the blank one. It also relies on the assumption that the order of appearance of new GRAM cards is sorted. It would definitely require some tuning to support any background scene.

 

nnnnn001 -> draw N+1 blank cards, using the background color
nnnnn101 -> draw N+1 blank cards, using the foreground color
nnnnnn00 -> draw GRAM card #N
nnnnn010 -> draw the next N+1 GRAM cards (e.g. if the GRAM index is currently set to 7 and N = 2, this will draw cards #7, #8 and #9 and update the GRAM index to 10)
nnnnn110 -> repeat the last GRAM card N+1 times (NB: blank cards may have been inserted in-between)
-nnnn011 -> set the background color to N
1----111 -> end of image
0-nnn111 -> set the foreground color to N

Edited December 7, 2017 by Arnauld

[carlsson]

^{See also newcoleco's threads in the ColecoVision programming section. While it is a different platform, many of the concepts should be similar, in particular the low amount of RAM for temporary storage.}

[+DZ-Jay]

For what it's worth, below is the scheme I'm using in a few projects. Each command is 8-bit wide, so each word contains 2 commands. Note that this version assumes FG/BG mode and doesn't support GROM cards apart from the blank one. It also relies on the assumption that the order of appearance of new GRAM cards is sorted. It would definitely require some tuning to support any background scene.

 

nnnnn001 -> draw N+1 blank cards, using the background color
nnnnn101 -> draw N+1 blank cards, using the foreground color
nnnnnn00 -> draw GRAM card #N
nnnnn010 -> draw the next N+1 GRAM cards (e.g. if the GRAM index is currently set to 7 and N = 2, this will draw cards #7, #8 and #9 and update the GRAM index to 10)
nnnnn110 -> repeat the last GRAM card N+1 times (NB: blank cards may have been inserted in-between)
-nnnn011 -> set the background color to N
1----111 -> end of image
0-nnn111 -> set the foreground color to N

 

Thanks, Arnauld. Similarly, I was thinking of something bespoke for Color Stack (my preferred mode at the moment). Certainly, specialized algorithms could be used for FG/BG and Color Stack. In Color Stack, for instance, if the card is GROM, we don't need to store any data except the Advance Bit. This can be treated as a special case, and since the BACKTAB word is only 13 bits wide, we could encode the special case in the next word. Moreover, I thought I could encode the color/advance and card information separately and build it on the fly during decompression.

 

Carlsson, I'll check out the link. Thanks!

 

-dZ.