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
|
|||
|
|||
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) 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] ]; Code: St:=m2s(matriz); Code: "$$$........wwww$......wwws.ww$......w.cc..w$......w..c..w$......w.....w$......www..ww$........w...w$........wdddw$........wwwww$$$$" Code: St:="$$$........wwww$......wwws.ww$......w.cc..w$......w..c..w$......w.....w$......www..ww$........w...w$........wdddw$........wwwww$$$$"; And with the RLE compression on fly Code: NTOS(Cnt) Code: St:=RLEEnc(matriz); 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
|
|||
|
|||
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
|
|||
|
|||
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] ]; Code: "...................$...................$...................$........wwww.......$......wwws.ww......$......w.cc..w......$......w..c..w......$......w.....w......$......www..ww......$........w...w......$........wdddw......$........wwwww......$...................$...................$...................$" Code: "$$$........wwww$......wwws.ww$......w.cc..w$......w..c..w$......w.....w$......www..ww$........w...w$........wdddw$........wwwww$$$$" 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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
RE: 1 Utility for Games
(01-27-2014 07:50 AM)patrice Wrote: and an RLE coding gives 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
|
|||
|
|||
RE: 1 Utility for Games
(03-11-2014 03:18 PM)Han Wrote:You perfectly right, if you look at the decoder, you will see that it handle the case already.(01-27-2014 07:50 AM)patrice Wrote: and an RLE coding gives I didn't handled it in the coder for 3 reason:
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
|
|||
|
|||
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. 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
|
|||
|
|||
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: