What is the best routine for graphics compression?

The place for codemasters or beginners to talk about programming any language for the Spectrum.
Joefish
Manic Miner
Posts: 622
Joined: Tue Nov 14, 2017 10:26 am

Re: What is the best routine for graphics compression?

Post by Joefish » Wed Sep 25, 2019 11:56 am

Another problem with compression - it's fine if you've got a ROM cartridge or disk to store your compressed data, but if you have to hold it in RAM and hold the expanded version in RAM then you have to decide if it's worth it.

For screens, you can uncompress them straight to the screen memory, so it's not a huge issue. But for game sprites, data, etc. you really need to be achieving 50% compression or it's just not worth it.

For example, if you have two levels in a game and each is 2K of data, that's 4K in total. If you compress it, you're still going to need 2K of unpacked live level data for your game. Now if you can pack your level data by 50% such that each level is now only 1K, then your 2K of live upacked data plus 2 x 1K of compressed data takes up the same space as before, 4K, so you've just broken even.

Now four levels would have taken up 8K, but now take up only 2K + 4 x 1K = 6K, so now you're saving memory. But if your compressed level data isn't shrinking by much, then it's not worth it.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

I've been doing some experiments with Einar's code as I've now got it into my head to compress the title screen of Go-Go BunnyGun and use it as an attract mode even in the 48K game, and even though I'm already running short of memory!

Using the linear screen re-arrangement helps the compression, but an algorithm I wrote myself also helps. That works from the bottom of the screen up, XOR-ing each line with the one above. So where the line is the same as above, you just get empty pixels. It doesn't help on highly detailed screens, or ones with lots of stippling, but for a manga-style image like mine with vertical lines and big blocks of colour, it leaves large blank areas and shaves a few hundred bytes off the compressed screen. Which is now down to under 4K.

What I want to do is try some experiments to see if I can optimise the image itself for compression; maybe reducing the detail a bit as well, and see how significant that is in the compressed file size.

I'm also trying to work out if it's worth compressing the sprites individually or as a block. An 8-frame sprite animation is 720 bytes, and some have only minor changes between frames, so 50% compression is readily achievable. That improves a little if I concatenate several sprites in one block, but makes it more awkward to unpack and extract the ones I want for a level.

Of course, sprites common to all levels (explosions, weapon pod) shouldn't be compressed at all as that would just be a waste of memory.
0 x

Joefish
Manic Miner
Posts: 622
Joined: Tue Nov 14, 2017 10:26 am

Re: What is the best routine for graphics compression?

Post by Joefish » Fri Sep 27, 2019 10:58 am

Hmm - I seem to have written a compression routine that actually runs on the Speccy itself and compresses my title screen even further, down to 3742 bytes. (The re-rodered ZX7 encoding gave 4247 bytes). Not sure how well it'll fare with other screens, but for the sort of thing people had drawn for the recent Hobbit update - lots of lines and large patches of colour - I suspect it could be pretty good. Though I need to verify it is doing everything reliably and I haven't made a big mistake somewhere. And that's still a big chunk of memory that wouldn't be available to the game!

I need to optimise the cack out of the post-processor stage and probably the decoder too. It's not massive, but I'm no expert and writing super-efficient code.

I want to see if I can do something more efficient for my sprite data too, though it (like my screen code) would take advantage of a bit of knowledge of the sprite format. I've got an idea for improving the encoding of back-referencing small sections of repeated runs in small blocks of data. The question then is whether using two or more custom encoding systems saves enough memory to have more than one decoder programmed in...
0 x

User avatar
Ast A. Moore
Dynamite Dan
Posts: 1194
Joined: Mon Nov 13, 2017 3:16 pm

Re: What is the best routine for graphics compression?

Post by Ast A. Moore » Fri Sep 27, 2019 1:19 pm

I use RLE for the title and the award ribbon in Yankee. I simply count empty (zero) bytes in vertical rows and write down the number of consecutive empty bytes. The decompressor is very fast and it saves quite a few bytes in images that contain a lot of blank bytes. I do decompress them directly onto the screen, so it’s worth it.

You could, I suppose, apply compression to some level data. If you then always decompress it to the same pre-allocated portion of RAM, it seems like a viable option. Maybe you could also pre-populate that area with some graphics, if you’re going to regularly copy them onto the screen. Then again, sprite graphics usually don’t compress well.
0 x
Every man should plant a tree, build a house, and write a ZX Spectrum game.

Author of A Yankee in Iraq, a 50 fps shoot-’em-up—the first game to utilize the floating bus on the +2A/+3,
and zasm Z80 Assembler syntax highlighter.

Joefish
Manic Miner
Posts: 622
Joined: Tue Nov 14, 2017 10:26 am

Re: What is the best routine for graphics compression?

Post by Joefish » Fri Sep 27, 2019 1:49 pm

Well, I refined my earlier idea of XORing rows and added a function to calculate the row addresses in pixel order. So each pixel row is XORed with the one above. And similarly, the attributes sweep backwards one byte at a time, XORing with the previous byte in memory. The result of this is that repeated data gets turned into lots and lots of zeroes. Large blocks of pixels become just a line across the top and a few dots down the sides. Stipples become alternate solid and clear lines. I then use a 0 bit in the compressed data stream to encode a zero byte, so the more of those can be generated the better. Everything else is encoded with a 1 followed by further data, that is either literal bytes, or a limited dictionary of the most common values. I tried a full dictionary but it wasn't worth it - it took too many bits to identify an entry compared to just supplying a literal byte value. That might be a useful approach for text compression too, rather than encoding a full dictionary. And has the advantage that you could decode any part of the data at any time, since there are no back-references.

My earlier one for title graphics - you might like this - takes advantage of the fact that no-one ever uses the FLASH bit. For each character, the attribute comes first. If there's no FLASH bit then the next byte is an 8-bit mask. This tells you for which bytes in the 8 rows of the character there is data to come. Set bits in the mask use the next byte in the data stream for the pixel byte. Any blank bits in the mask result in a 0 byte being written. So a full character takes 10 bytes. But a half-character only 6. The trick is that if the FLASH bit is set, it's first stripped from the attribute, but then the pixel mask byte is re-used from the previous character. So it might encode the same pattern of bytes present in the character, or if the mask is 0, then another empty character is drawn. It simply eliminates all the blank bytes in an image. And it does it using whole bytes, rather than faffing around with an arbitrary stream of bits. I think I also had a set of bytes for each line where each bit meant 'copy the previous attribute and process accordingly'.
0 x

User avatar
Morkin
Manic Miner
Posts: 611
Joined: Mon Nov 13, 2017 8:50 am
Location: Bristol, UK

Re: What is the best routine for graphics compression?

Post by Morkin » Sat Sep 28, 2019 1:24 pm

Joefish wrote:
Fri Sep 27, 2019 1:49 pm
My earlier one for title graphics - you might like this - takes advantage of the fact that no-one ever uses the FLASH bit. For each character, the attribute comes first. If there's no FLASH bit then the next byte is an 8-bit mask. This tells you for which bytes in the 8 rows of the character there is data to come. Set bits in the mask use the next byte in the data stream for the pixel byte. Any blank bits in the mask result in a 0 byte being written. So a full character takes 10 bytes. But a half-character only 6. The trick is that if the FLASH bit is set, it's first stripped from the attribute, but then the pixel mask byte is re-used from the previous character. So it might encode the same pattern of bytes present in the character, or if the mask is 0, then another empty character is drawn. It simply eliminates all the blank bytes in an image. And it does it using whole bytes, rather than faffing around with an arbitrary stream of bits. I think I also had a set of bytes for each line where each bit meant 'copy the previous attribute and process accordingly'.
That's quite good.

I guess depending on what you're printing, e.g. if it's static graphics, you could also use the BRIGHT bit for something as well? Not sure what.
0 x

User avatar
TomD
Berk
Posts: 31
Joined: Tue Nov 13, 2018 9:47 am
Location: Leeds UK
Contact:

Re: What is the best routine for graphics compression?

Post by TomD » Sat Sep 28, 2019 9:38 pm

I created a compression routine for exactly this purpose, being able to compress "cutouts" of the screen for titles or small blocks of graphics for intros but can be used for anything. You can read more about it here http://www.tomdalby.com/other/lzf.html

It has two modes for the "cutouts", static and moveable. If you need to move the "cutout" each time you paste to screen then moveable should be used and the only real difference is the decompressor is larger at 151bytes vs. the static version at 92bytes. Full screen is also in the utility.

Any questions let me know.

TomD
2 x
Retro enthusiast and author of Flynn's Adventure in Bombland, The Order of Mazes & Maze Death Rally-X. Check them out at http://tomdalby.com

User avatar
TomD
Berk
Posts: 31
Joined: Tue Nov 13, 2018 9:47 am
Location: Leeds UK
Contact:

Re: What is the best routine for graphics compression?

Post by TomD » Sat Sep 28, 2019 9:41 pm

If you want to see an example of it working try this https://tomdalby.com/speccy/cobra_w.tap
0 x
Retro enthusiast and author of Flynn's Adventure in Bombland, The Order of Mazes & Maze Death Rally-X. Check them out at http://tomdalby.com

catmeows
Berk
Posts: 36
Joined: Tue May 28, 2019 11:02 am

Meanwhile on my computer :)

Post by catmeows » Sun Sep 29, 2019 3:57 pm

Image
0 x

Bedazzle
Berk
Posts: 11
Joined: Sun Mar 24, 2019 9:03 am

Re: What is the best routine for graphics compression?

Post by Bedazzle » Wed Oct 02, 2019 3:58 am

What about megalz packer?
0 x

catmeows
Berk
Posts: 36
Joined: Tue May 28, 2019 11:02 am

Re: What is the best routine for graphics compression?

Post by catmeows » Wed Oct 02, 2019 6:15 am

Bedazzle wrote:
Wed Oct 02, 2019 3:58 am
What about megalz packer?
https://github.com/emmanuel-marty/lzsa/ ... /README.md

Here is quite handy chart showing compression/speed ratio.
0 x

Post Reply