Sprite encoding/decoding for compact graphics data

[komame]

Hello,

I just bought a HP Prime and after a few days getting to know the device I started writing my first game.
I was a little disgusted by the fact that the graphics occupies a lot of space. I know that flash memory in the HP Prime is large but in spite of this I started to look for a solution that will allow for more compact storage of graphics in the source code.
Normally in source code each character occupies two bytes because of UNICODE coding (16-bit per character).
Thus, using a list of integers for the DIMGROB_P each character takes also two bytes.
Every pixel needs 4 characters (HEX) to code, so one pixel takes 8 bytes in source code.

Reading the forums I have seen ideas to use STRING to store a more compact graphics data and then apply them (decode) to the GROB using PIXON_P.
I have not found a finished solution, so I decided to make my own, but instead of using the PIXON_P (which is slow I think) I wrote a solution that generates a list of integers to use with DIMGROB_P.

Since Unicode uses 16-bit per character I decided to use it.
We can use CHAR(x) to create characters that represent values from 1 to 65535 (2 bytes) and occupy in string only one character, so we can store 8 bytes in 4-character string:

2-byte integers: 4520, 8610, 9992, 12542.
Now we can store these integers in one string variable using CHAR command:

Code:

CHAR(4520)+CHAR(8610)+CHAR(9992)+CHAR(12542)▶z;

The z variable now cantains:
"ᆨ↢✈ヾ"

Now we can read these 16-bit integers from string variable using array index:
z(1) => we get 4520
z(2) => we get 8610
...

The low-byte and hi-byte from the integer we can get using BITAND and BITSR commands.
Following on from this we can encode four 4-bit values or eight 2-bit values in one character.
The only problem is that we can not store the value 0 (number zero) in the string variable because 0 is a special character that marks the end of a string. However, I found the solution to this problem.

I know there is also a command ICON. However, the size of image data is not as small as my method of coding. Besides, my method allows dynamic creation of images, which helps to create the animation.

I created a two pairs of functions. First is for encoding/decoding list of integers for DIMGROB_P (16-bit color), so you can use it in your finished programs where list of integers is used.

These functions names are: ESFC for encoding and DSFC for decoding.
When your program is already finished only the decoding function should remain in it.

At the moment there is no PC version, so (en/de)coding can be performed only on a calculator or emulator.

---
Example of use the first pair of functions:

In this example I used the stone sprite (16x16) from the Sokoban game.

The original code:

Code:

DIMGROB_P(G1,16,16, {#1084108451C74186:64,#1084108410841084:64,#1084108410841084:64,#312651C710​841084:64,#1084108410844186:64,#2D6B2D6B2D6B1CE7:64,#39CE2D6B2D6B2D6B:64,#312610​842D6B2D6B:64,#1CE71CE71CE71084:64,#1CE7108410841084:64,#2D6B2D6B1CE71CE7:64,#10​8439CE5EF739CE:64,#10841CE71CE71084:64,#10841CE72D6B2D6B:64,#5EF75EF739CE1CE7:64​,#10845EF75EF72D6B:64,#10842D6B1CE71084:64,#2D6B10841CE72D6B:64,#5EF739CE1CE739C​E:64,#10845EF75EF72D6B:64,#10842D6B1CE71084:64,#5EF739CE10841CE7:64,#39CE1CE739C​E5EF7:64,#10845EF75EF72D6B:64,#10842D6B1CE71084:64,#39CE39CE2D6B1084:64,#2D6B39C​E5EF75EF7:64,#10845EF75EF72D6B:64,#1CE72D6B1CE71084:64,#39CE39CE2D6B1084:64,#2D6​B5EF75EF739CE:64,#10845EF75EF739CE:64,#10842D6B1CE71084:64,#39CE2D6B10841CE7:64,​#39CE2D6B39CE39CE:64,#10845EF75EF72D6B:64,#10841CE71CE71084:64,#108410842D6B2D6B​:64,#5EF75EF72D6B2D6B:64,#10845EF739CE2D6B:64,#10841CE71CE71084:64,#2D6B39CE39CE​2D6B:64,#39CE39CE39CE2D6B:64,#10845EF739CE2D6B:64,#1CE710841CE71084:64,#39CE39CE​2D6B1CE7:64,#2D6B39CE39CE39CE:64,#10845EF72D6B39CE:64,#1CE710841CE71084:64,#2D6B​2D6B1CE72D6B:64,#39CE2D6B2D6B2D6B:64,#108439CE2D6B39CE:64,#1CE710841CE71084:64,#​2D6B2D6B2D6B1CE7:64,#39CE39CE2D6B2D6B:64,#108439CE2D6B39CE:64,#1CE71CE710844186:​64,#2D6B2D6B1CE71CE7:64,#39CE39CE39CE39CE:64,#4186108439CE39CE:64,#1084108441863​126:64,#1084108410841084:64,#1084108410841084:64,#3126312610841084:64});

Now you can encode the list of integers - just copy the list as a ESFC parameter:
ESFC({#1084108451C74186:64,#1084108410841084:64, ... ,#1084108410841084:64,#3126312610841084:64})
and you get strange string (lot of symbols and other characters).

Then copy the string and paste in the code as DSFC parameter instead of a list of integers.
It should look like this:

Code:

DIMGROB_P(G1,16,16,DSFC("還還퇇솆還還還還還還還還넦퇇還還還還還솆굫굫굫鳧많굫굫굫넦還굫굫鳧鳧鳧還鳧還還還굫굫鳧鳧還많?還鳧鳧還還鳧굫굫?많鳧還?굫還굫鳧還굫還鳧굫?鳧많還?굫還굫鳧還?​還鳧많鳧많??굫還굫鳧還많많굫還굫많?還?굫鳧굫鳧還많많굫還굫?많還?많還굫鳧還많굫還鳧많굫많많還?굫還鳧鳧還還還굫굫?굫굫還?굫還鳧鳧還굫많많굫많많많굫還?굫​鳧還鳧還많많굫鳧굫많많많還?많鳧還鳧還굫굫鳧굫많굫굫굫還많굫많鳧還鳧還굫굫굫鳧많많굫굫還많굫많鳧鳧還솆굫굫鳧鳧많많많많솆還많많還還솆넦還還還還還還還還넦넦還還"));

Of course the decoding function must be added to the program.

The list of integers before conversion takes 1345 characters (2690 bytes!!!).
After encoding to string it takes 241 characters (482 bytes), so we saved 2208 bytes.
Now one pixel is coded in only one character. Before conversion it was 4 characters.

Decoding function takes less than 240 characters, so even for one sprite it is worth using it.

Decoding time of 16x16 sprite average takes 77ms so it is quite fast.
Decoding should not be done on the fly, so it is best to perform the decoding at the initial stage of your program and the results put in the GROBs for later use.


OK, it's time for the second pair of functions.

The second pair is for encoding/decoding 15-color images (every pixel takes 4 bits), so the data graphics are even more compact, because you can store 4 pixels in one character.
We can not store 0 value, so 15 (not 16) colors are available.
I'm still working on this version, but I can show you the first effects.

The attached programs shows the full-color encoding/decoding (EncDecSpriteFC.hpprgm) and the 15-color sprites decoding (EncDecSprite15c.hpprgm).
In the second method there are five 14x14 sprites. After the encoding one sprite takes only 49 characters in the source code.
The encoding function I will write in the near future where as a parameter I will use list of colors or just matrix and color palette.
I have now a initial version of this function with string as input but it is to hard to use for now, so I want to refine it before I give you.

Best regards,
Piotr Kowalewski

P.S. What you see in the EncDecSprite15c.hpprgm is an early outline of what you will see in my game where I had planned to use animations... and sorry for my bad English

[Han]

Interesting program. However, I wonder if your encoding is truly smaller than an actual PNG file. I have been out of the loop for several months due to a new addition to the family, so there is a bit of catching up for me to do. That said, it appears that the direction for programming is such that one can have binary files available for direct access. Thus, one would have to compare the benefits of encoding a pixel into a character, versus a binary PNG file that requires no decoding by the user.

[komame]

Thank you for your comments.

The solution is rather for game developers.
Binary PNG files can be used only in application libraries in HP Prime and not in the 1-file programs in the program catalog, so not everyone uses them.

And yes, this encoding is smaller than PNG especially with small color palette, but in some cases may happen exceptions.
In general, for more complicated sprite (less compressible) is more worth to use my method.

However, smaller sprites provide also greater profit. If someone uses a lot of small sprites the solution is for him.
Note that PNG also optimizes the color palette. Simple sprites as those of example EncDecSprite15c consist of four-six colors, but was encoded by me using 15 colors. Using a palette 4 color the final result can be reduced even by half (25 characters per sprite 14x14).
The smallest PNG file which I was able to generate the size of 2x2 (4 pixels) of the two colors was the size more than 80 bytes after optimization (take a look at the attachment).
At this size of a sprite using my method you can store the sprite size 12x12 of 15 colors or size 6x6 of 16-bit color.

In addition, most developers just encodes the graphics data in the source code using integers lists (for using with DIMGROB_P) so there is a lot of completed programs which now can be reduced without major modifications to the source code.

A similar method can be used also to encode levels in games like Sokoban
Combined with RLE which is used there we can get really interesting results.

I hope that it will be useful for someone.

BR
Piotr

[komame]

Hi,

I present you the final version of 4-bit encryption / 15 color images.

The source code for the encoding and decoding functions is here:

Code:

// 15-color sprite encoding/decoding
// by Piotr Kowalewski - August 2015

DS15(a,p) //decode 15-color sprite
BEGIN
local b,c=#0:64,d={},e,z;
FOR b FROM 1 TO SIZE(a) DO
R→B(a(b))▶z;
FOR e FROM 0 TO 3 DO
BITSL(c,(e>0)*16)+p(BITAND(z,15))▶c;
BITSR(z,4)▶z;
END;
CONCAT(d,c)▶d;
#0:64▶c
END;
RETURN d;
END;

EXPORT ES15(d) //encode 15-color sprite
BEGIN
local a="",b,c,e=0;
FOR b FROM 1 TO SIZE(d) DO
EXPR("#"+CHAR(d(b)))▶c;
BITSL(e,4)+c▶e;
IF b MOD 4=0 THEN
a+CHAR(e)▶a;
0▶e;
END;
END;
IF SIZE(a)<(SIZE(d)/4) THEN
a+CHAR(e)▶a;
END;
RETURN a;
END;

Now I'll show how to do the sprite encoding.

1. First, you need to have / create the image that you want to encode.
The image can have up to 15 colors including transparency color.

I drew a small tank 16x12 pixels of 6 colors that will be used in this example (PNG file in the attachment).

2. Then transcribe the color palette to a list of integers.
16-bit color is encoded as follows: ARRRRRGGGGGBBBBB (standard for the DIMGROB_P).
A - alpha (transparency bit) - if set, the next bits (RGB) are not important.
R - red 5-bits
G - green 5-bits
B - blue 5-bits

There are 6 colors in my picture:
- 1. black (0 00000 00000 00000 = #0)
- 2. dark gray (0 00101 00101 00101 = #14A5)
- 3. middle gray (0 01010 01010 01010 = #294A)
- 4. light gray (0 01110 01110 01110 = #39CE)
- 5. red (0 11111 00000 00000 = #7C00)
- 6. transparent (1 11111 11111 11111 = #FFFF).

Now we create a list of these colors:
{#0, #14A5, #294A, #39CE, #7C00, #FFFF};

3. Then, each pixel of your image you writes using numbers that correspond to the colors on your list of colors.

In my case, it must look like this:

6663434343434342
6664333333333332
6662232323232322
6666663344444336
6666633433333135
3333333433333135
1111111433333135
6666661433333135
6666663311111336
6663434343434342
6664333333333332
6662232323232322

Now you combine these lines in one long row and a string is an input parameter to the encoding function:
"66634343434343426664333333333332666223232323232266666633444443366666633433333135​33333334333331351111111433333135666666143333313566666633111113366663434343434342​66643333333333326662232323232322"

4. So, let's do the encoding!

Code:

ES15("66634343434343426664333333333332666223232323232266666633444443366666633433333135​33333334333331351111111433333135666666143333313566666633111113366663434343434342​66643333333333326662232323232322");

..and this is the result (much shorter string):
"晣䍃䍃䍂晤㌳㌳㌲晢⌣⌣⌢晦昳䑄䌶晦挴㌳ㄵ㌳㌴㌳ㄵᄑᄔ㌳ㄵ晦昔㌳ㄵ晦昳ᄑጶ晣䍃䍃䍂晤㌳㌳㌲晢⌣⌣⌢"

5. Now we should copy the function of decoding DS15 into our program and as its parameter specify the encoded string and color palette, which had previously been written.

Code:

DS15("晣䍃䍃䍂晤㌳㌳㌲晢⌣⌣⌢晦昳䑄䌶晦挴㌳ㄵ㌳㌴㌳ㄵᄑᄔ㌳ㄵ晦昔㌳ㄵ晦昳ᄑጶ晣䍃䍃䍂晤㌳㌳㌲晢⌣⌣⌢",p);

Our encoded string can be decoded to a variable or directly to DIMGROB_P, for example:

Code:

DIMGROB_P(G1,16,12,DS15("晣䍃䍃䍂晤㌳㌳㌲晢⌣⌣⌢晦昳䑄䌶晦挴㌳ㄵ㌳㌴㌳ㄵᄑᄔ㌳ㄵ晦昔㌳ㄵ晦昳ᄑጶ晣䍃䍃䍂晤㌳㌳㌲晢⌣⌣⌢",p));

6. That's all. Now you can use BLIT_P to display the decoded image.

Code:

BLIT_P(G0,32,32,G1);

You can use several color palettes and decode the same images with different brightness (for example).

I did have a small comparison as between ICON, a list of integers and my encoding method.
Now, the image of the tank size is 50 characters plus size of color palette, which can be only one to multiple images.
If we use the command ICON the same image will take 387 characters.
If we use a list of integers this image will take 1090 characters.

So if you have several or even dozens of sprits in yours program the aggregated differences could be very significant.


In the attachment is placed a finished solution for those who do not want to prescribe

[webmasterpdx]

Couldn't you just store a bunch of sprites in a png and load the ping into a grob and then just have several sprites on the grob that you can blit from. Wouldn't that work?
....or am I missing something?