1 Utility for Games
01-25-2014, 06:46 PM (This post was last modified: 01-26-2014 02:13 AM by patrice.)
Post: #1
 patrice Member Posts: 180 Joined: Dec 2013
1 Utility for Games
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); "$$9b4w7b3wsb2w7bwb2c2bw7bw2bc2bw7bw5bw7b3w2b2w9bw3bw9bw3dw9b5w$$$!" // 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. Patrice “Everything should be made as simple as possible, but no simpler.” Albert Einstein 01-27-2014, 06:41 AM Post: #2  cyrille de brébisson Senior Member Posts: 877 Joined: Dec 2013 RE: 1 Utility for Games 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 01-27-2014, 07:50 AM (This post was last modified: 01-27-2014 07:52 AM by patrice.) Post: #3  patrice Member Posts: 180 Joined: Dec 2013 RE: 1 Utility for Games 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. Patrice “Everything should be made as simple as possible, but no simpler.” Albert Einstein 01-27-2014, 11:25 PM (This post was last modified: 01-27-2014 11:32 PM by ArielPalazzesi.) Post: #4  ArielPalazzesi Member Posts: 90 Joined: Dec 2013 RE: 1 Utility for Games Very, very, very nice!!!!!! In a few days i return with a long reply Thanks! PS: remember me "UUENCODE/UUDECODE", from FidoNET / Unix, etc..... 03-11-2014, 01:04 PM Post: #5  patrice Member Posts: 180 Joined: Dec 2013 RE: 1 Utility for Games It is now in the Sokoban program. The 40 levels compression saves 40K in source code Patrice “Everything should be made as simple as possible, but no simpler.” Albert Einstein 03-11-2014, 03:18 PM (This post was last modified: 03-11-2014 03:18 PM by Han.) Post: #6  Han Senior Member Posts: 1,811 Joined: Dec 2013 RE: 1 Utility for Games (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.

Graph 3D | QPI | SolveSys
03-11-2014, 06:42 PM
Post: #7
 patrice Member Posts: 180 Joined: Dec 2013
RE: 1 Utility for Games
(03-11-2014 03:18 PM)Han Wrote:
(01-27-2014 07:50 AM)patrice Wrote:  and an RLE coding gives
Code:
"$$9b4w7b3wsb2w7bwb2c2bw7bw2bc2bw7bw5bw7b3w2b2w9bw3bw9bw3dw9b5w$$$!" 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. Patrice “Everything should be made as simple as possible, but no simpler.” Albert Einstein 03-11-2014, 07:43 PM Post: #8  Han Senior Member Posts: 1,811 Joined: Dec 2013 RE: 1 Utility for Games (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).

Graph 3D | QPI | SolveSys
03-11-2014, 08:42 PM
Post: #9
 patrice Member Posts: 180 Joined: Dec 2013
RE: 1 Utility for Games
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.

Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)