1 Utility for Games

[patrice]

This utility is aimed to games with levels, but can have other usages.
The goal is to save space in source code.
Usually in games with levels, there is a map per level. It is common to describe the levels as a matrix which is not space efficient in source code. Encoding the map in a string and using the RLE simple minded compression can do dramatic savings.

String codes
! can be used for end of code (last char in string)
$ is for a new line
. is the default value (background), usually it is 0 in the matrix
letters are used to describe the diff parts of the map

Exemple with ArielPalazzesi's Sokoban
$ encode a new line in matrix
. encode 0 the background
w encode 1 the Walls
c encode 2 a Cube
d encode 3 a Destination
s encode 4 Sokoban (the pusher)

First is a matrix to string conversion and reverse

Code:

EXPORT m2s(Mt)
BEGIN
LOCAL Row, Col, Sz, Tmp;
Tmp:= ""; Sz:= SIZE(Mt);
FOR Row FROM 1 TO Sz(1) DO
  FOR Col FROM 1 TO Sz(2) DO
    Tmp:= Tmp+ MID(".wcds",Mt(Row,Col)+1,1);
  END;
  Tmp:= Tmp+ "$";
END;
RETURN Tmp;
END;

EXPORT s2m(Rows, Cols, St)
BEGIN
LOCAL Row, Col, Ptr; Tmp;
Row:= 1; Col:= 1;
Tmp:= MAKEMAT(0,Rows,Cols);
FOR Ptr FROM 1 TO DIM(St) DO
  IF MID(St, Ptr, 1) == "$" THEN
    Row:= Row+1; Col:= 1;
  ELSE
    Tmp(Row,Col):= INSTRING(".wcds", MID(St, Ptr, 1))-1;
    Col:= Col+ 1;
  END;
END;
END;

Code:

matriz := [ [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,4,0,1,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,0,2,2,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,0,0,2,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,3,3,3,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] ];

Convert to

Code:

St:=m2s(matriz);
"...................$...................$...................$........wwww.......$​......wwws.ww......$......w.cc..w......$......w..c..w......$......w.....w......$​......www..ww......$........w...w......$........wdddw......$........wwwww......$​...................$...................$...................$"

and since the matrix is already initialized to the background value, they are not needed at the end of line.

Code:

"$$$........wwww$......wwws.ww$......w.cc..w$......w..c..w$......w.....w$......ww​w..ww$........w...w$........wdddw$........wwwww$$$$"

and decoding is done by

Code:

St:="$$$........wwww$......wwws.ww$......w.cc..w$......w..c..w$......w.....w$......ww​w..ww$........w...w$........wdddw$........wwwww$$$$";
matriz:= s2m(15,20,St);

And with the RLE compression on fly

Code:

NTOS(Cnt)
BEGIN
  LOCAL Tmp;
  Tmp:= MID("0123456789", 1+ Cnt MOD 10, 1);
  IF Cnt > 9 THEN
    Tmp:= NTOS(IP(Cnt/10))+Tmp;
  END;
  RETURN Tmp;
END;

EXPORT RLEEnc (Mt) // RLE encodeur
BEGIN
  LOCAL Row, Col, Cod, Cnt, Tmp, Sz;
  Tmp:= ""; Sz:=SIZE(Mt);
  FOR Row FROM 1 TO Sz(1) DO
    Cnt:= 1; Cod:= Mt(Row,1);
    FOR Col FROM 2 TO Sz(2) DO
      IF Cod == Mt(Row,Col) THEN
        Cnt:= Cnt+1;
      ELSE
        IF Cnt <> 1 THEN Tmp:= Tmp+ NTOS(Cnt); END;
        Tmp:= Tmp+ MID(".wcds",Cod+1,1);
        Cnt:= 1; Cod:= Mt(Row,Col);
      END;
    END;
    IF Cod <> 0 THEN
      IF Cnt <> 1 THEN Tmp:= Tmp+ NTOS(Cnt); END;
      Tmp:= Tmp+ MID(".wcds",Cod+1,1);
    END;
    Tmp:= Tmp+ "$";
  END;
  Tmp(SIZE(Tmp)):= "!";
  RETURN Tmp;
END;

EXPORT RLEDec (Rows, Cols, RLE) // RLE décodeur
BEGIN
  LOCAL Row, Col, Ptr, Cnt, Cod, Tmp;
  Row:= 1; Col:= 1; Cnt:= 0;
  Tmp:= MAKEMAT(0,Rows,Cols);
  FOR Ptr FROM 1 TO DIM(RLE) DO
    CASE
      IF INSTRING("0123456789", MID(RLE, Ptr, 1)) <> 0 THEN Cnt:= Cnt*10+EXPR(MID(RLE, Ptr, 1)); END;
      IF MID(RLE, Ptr, 1) == "$" THEN Row:= Row+MAX(1, Cnt); Col:= 1; Cnt:= 0; END;
      DEFAULT
      Cod:= INSTRING(".wcds", MID(RLE, Ptr, 1));
      FOR Col FROM Col TO Col+MAX(1, Cnt)-1 DO Tmp(Row,Col):=Cod- 1; END; Cnt:= 0;
    END;
  END;
  RETURN Tmp;
END;

gives

Code:

St:=RLEEnc(matriz);
"$$$9b4w$7b3wsb2w$7bwb2c2bw$7bw2bc2bw$7bw5bw$7b3w2b2w$9bw3bw$9bw3dw$9b5w$$$!"
// And back to matrix
matriz:= RLEDec(15,20,St);

Replace ".wcds" with your own set of values in the functions
Nota: numbers are reserved for the RLE compression

RLE compression is simple enough that one can encode a map by hand.

[cyrille de brébisson]

Hello,

If you want to save raw data, the best is to use a string with and the ASC and CHAR commands. This allows you to save 16 bits of data per character and would be the fastest/easiest way to do it...

cyrille

[patrice]

Bonjour Cyrille,

I think it do not apply, unless it is permitted to have source code in ASCII which I doubt.

In fact, the idea is to save space in source code and in compiled code.

The problem with games using levels, it is that there is a map per level, Ariel is planning 100 levels for Sokoban
One level in actual source code looks like

Code:

matriz := [ [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,4,0,1,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,0,2,2,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,0,0,2,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,3,3,3,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] ];

a simple conversion to a string looks like

Code:

"...................$...................$...................$........wwww.......$​​......wwws.ww......$......w.cc..w......$......w..c..w......$......w.....w......​$​......www..ww......$........w...w......$........wdddw......$........wwwww.....​.$​...................$...................$...................$"

a clever use of background lead to

Code:

"$$$........wwww$......wwws.ww$......w.cc..w$......w..c..w$......w.....w$......ww​​w..ww$........w...w$........wdddw$........wwwww$$$$"

and an RLE coding gives

Code:

"$$$9b4w$7b3wsb2w$7bwb2c2bw$7bw2bc2bw$7bw5bw$7b3w2b2w$9bw3bw$9bw3dw$9b5w$$$!"

The hard part is to replace the matrices in source code by the strings and decode them on fly as needed.

[ArielPalazzesi]

Very, very, very nice!!!!!!
In a few days i return with a long reply

Thanks!

PS: remember me "UUENCODE/UUDECODE", from FidoNET / Unix, etc.....

[patrice]

It is now in the Sokoban program.

The 40 levels compression saves 40K in source code

[Han]

(01-27-2014 07:50 AM)patrice Wrote:  and an RLE coding gives

Code:

"$$$9b4w$7b3wsb2w$7bwb2c2bw$7bw2bc2bw$7bw5bw$7b3w2b2w$9bw3bw$9bw3dw$9b5w$$$!"

The hard part is to replace the matrices in source code by the strings and decode them on fly as needed.

Even shorter is to code multiple $'s in the form n$. For example, $$$ should be coded as 3$. It shouldn't be all that hard to create a small program to convert from matrix over to a string -- it's easier to edit a matrix than it is to create a string and keep all the codes correct.

[patrice]

(03-11-2014 03:18 PM)Han Wrote:  

(01-27-2014 07:50 AM)patrice Wrote:  and an RLE coding gives

Code:

"$$$9b4w$7b3wsb2w$7bwb2c2bw$7bw2bc2bw$7bw5bw$7b3w2b2w$9bw3bw$9bw3dw$9b5w$$$!"

The hard part is to replace the matrices in source code by the strings and decode them on fly as needed.

Even shorter is to code multiple $'s in the form n$. For example, $$$ should be coded as 3$. It shouldn't be all that hard to create a small program to convert from matrix over to a string -- it's easier to edit a matrix than it is to create a string and keep all the codes correct.

You perfectly right, if you look at the decoder, you will see that it handle the case already.
I didn't handled it in the coder for 3 reason:

• 3 or more empty lines in a row is not very common over the 40 levels.
• it complicate the encoder for only a very little gain.
• I like to see all the $ , it help me do manual checking of the coding.
  

If you like it, feel free to tweak the various levels, it saves a bout 30 chars across the 40 levels.
When I first put it in Sokoban, I didn't removed the drawscreen() comand which have a side effect, it removes the pusher from the level matrix. So I have done some manual testing before I understood where was the problem.

[Han]

(03-11-2014 06:42 PM)patrice Wrote:  

(03-11-2014 03:18 PM)Han Wrote:  Even shorter is to code multiple $'s in the form n$. For example, $$$ should be coded as 3$. It shouldn't be all that hard to create a small program to convert from matrix over to a string -- it's easier to edit a matrix than it is to create a string and keep all the codes correct.

You perfectly right, if you look at the decoder, you will see that it handle the case already.
I didn't handled it in the coder for 3 reason:

• 3 or more empty lines in a row is not very common over the 40 levels.
• it complicate the encoder for only a very little gain.
• I like to see all the $ , it help me do manual checking of the coding.
  

If you like it, feel free to tweak the various levels, it saves a bout 30 chars across the 40 levels.
When I first put it in Sokoban, I didn't removed the drawscreen() comand which have a side effect, it removes the pusher from the level matrix. So I have done some manual testing before I understood where was the problem.

Yeah, I guess that would be a much smaller gain if there are not many blank rows. I was basing this idea off of how I encode bitmaps as sub-bitmaps for this game. There are certain bitmaps that are used very frequently (i.e. a "default" bitmap). In your particular example, the b and w's appear most frequently. One of those (say b) can be considered the default. So rather than encoding as: "3b4w" you save a few more characters by using "34w" -- with the understanding that a digit without an alpha code refers to repeated blanks. If the digits need to be larger than 0-9, then you can just use A through Z in upper case (gives you up to 26 repeats). Or use any consecutive block of characters for the count, and a separate block of characters for the type. Thus you would have either: <ascii char for count> [<ascii char for type>] (the second value being optional). The count char should come from A through Z (for example) and the type perhaps from a through z (all lower case).

Without doing any hard analysis, a quick glance suggests that most of the code is a digit followed by b or a digit followed by w. So roughly speaking ~20% might be saved? Since it is done during initialization, you would hardly notice the extra bit of code/time needed to handle the differentiation between <count><code> vs. just <count> by itself (for the default "blank" code).

[patrice]

Yes, I know, there is always a specialized encoding that will perform better than a general purpose one.
My goal here was to show how a rather general purpose compression scheme could be used to save space. It is quite efficient while still rather easy to encode by hand.
The RLE encoding is well documented and in use in a lot of programs.
I first played with RLE because it is common encoding for the "Game of Life" data sets.