I'm kind of stuck encoding screens. I have ran out of memory and need to compress the level data. But I don't know how. Can someone help me with something in C please? Here's an example screen data:
0x1F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1D, 0x1F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1D,
0x23, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x1E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x1F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1C, 0x1E, 0x1C, 0x1E, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1C, 0x1E, 0x1D, 0x1F, 0x1D, 0x20, 0x1E, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x1C, 0x21, 0x1F, 0x00, 0x00, 0x00, 0x1D, 0x20, 0x1E, 0x00, 0x00,
0x00, 0x00, 0x00, 0x1C, 0x1E, 0x1D, 0x1F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1D, 0x1F, 0x00, 0x00,
0x1E, 0x00, 0x00, 0x1D, 0x20, 0x1E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1C, 0x1E, 0x00, 0x00,
0x1F, 0x00, 0x00, 0x00, 0x1D, 0x1F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1D, 0x1F, 0x00, 0x00,
0x25, 0x25, 0x25, 0x25, 0x25, 0x25, 0x25, 0x00, 0x00, 0x25, 0x25, 0x25, 0x25, 0x25, 0x25, 0x25
From what I understand I could encode it like this: 1,0x1F,6,0x00,1,0x1D,1,0x1F,6,0x00,1,0x1D etc but I have brain freeze and can't figure out how to expand the levels into an array. Please help.
How many different tiles you have for each screen?
Before going for compression, you can start by using bitarrays. If you have 16 different tiles per screen, you can use cpct_get4bits (http://lronaldo.github.io/cpctelera/files/bitarray/cpct_get4Bits-asm.html) / cpct_set4bits (http://lronaldo.github.io/cpctelera/files/bitarray/cpct_set4Bits-asm.html) and you will require arrays of half their original size (you'll be using 4 bits per item instead of 8 . You have a use example of bitArrays included (https://github.com/lronaldo/cpctelera/tree/master/examples/medium/bitArrays).
If you go for compression, is better if you use software like ZX7 or Exomizer. Doing it by hand will take time and effort and will probably yield poorer results.
I don't understand how those bit arrays work. Either I'm just a full on retard or the example makes absolutely no sense/
What you trying to do seems to be RLE, the most basic compression algorithm. It may work fine in your example, but probably not for more complex areas.
Why don't you do like I posted in another of your thread? Have your own format, declaring positions of elements (such as trees), declaring horizontal/vertical lines of uniform tiles (start point, direction, length)?
It's really simple to do and will probably beat Exomizer, because on such tiny areas, there is no much it can do.
QuoteWhy don't you do like I posted in another of your thread? Have your own format, declaring positions of elements (such as trees), declaring horizontal/vertical lines of uniform tiles (start point, direction, length)?
If I can't get to grips with the most basic algorithm then I really am wasting my time.
The map currently uses 12k. If I can get a few K's out of that size that would really help as I am down to my last 400 bytes for the engine now and really need the space to code essential features.
With a nicely built custom format, you could encode all your stuff in 2-3kb, I'm pretty sure. How do you think a game like Saboteur 2 encoded these hundreds of screen within 64kb? Not by compressing. Simply by organizing its data cleverly.
I'm going to make an example for your game. I'll create a data of one (imaginary) room, with comments. This format is just created "off the top of my head", as I would do it if I were to code your game:
ROOM_X2_Y5: ;This is the definition of the Room 2,5.
db tileGrass ;The first byte of our room is the tile which will be spread on the whole background. Here, grass.
;Then, our format indicates "sparse" elements. It is composed of X,Y,TileNumber. The list is zero-terminated.
db 2, 4, tileRock ;At coordinates 2, 4, we have a rock.
db 8, 2, tileRock ;At coordinates 8, 2, we have a rock.
db 14, 10, tileDoor ;At coordinates 14, 10, we have a door.
db 0 ;End of our "sparse element" list.
;Then, our format indicates "horizontal lines". It is composed of Xstart,Ystart,length,TileNumber. The list is zero-terminated.
db 9,5,6, tileRock ; From coordinates 9, 5, we have 6 rocks, towards right.
db 20,2,4, tileRock ; From coordinates 20, 2, we have 4 rocks, towards right.
db 0 ;End of our "horizontal lines" list.
;Then, our format indicates "vertical lines". It is composed of Xstart,Ystart,length,TileNumber. The list is zero-terminated.
db 5,5,10, tileRock ; From coordinates 5, 5, we have 10 rocks, downwards.
db 14,5,3, tileRock ; From coordinates 14, 5, we have 3 rocks, downwards.
db 0 ;End of our "vertical lines" list.
Now you see, with a few bytes, I have encoded a whole room with rocks, a door, and grass everywhere!
That's just an example, but it can be enough. If you need more elaborated structure, it's up to you to create them (for example, a tree is always composed of the same group of tiles, so you should find a way to encode that, instead of encoding each tile of the tree every time).
Reading this format is also very simple. Just be aware that this is YOUR format, and so you should carefully document it to create rooms correctly, and of course, for your engine to read it!
It won't work. There are 7 different tree tiles, four for a lone tree, two for overlapping trees and a 7th for tree huts. I'll figure something out, I need to if I want to finish this game.
Quote from: EgoTrip on 12:20, 29 November 15
I don't understand how those bit arrays work. Either I'm just a full on retard or the example makes absolutely no sense/
Well, the example is not absolutely non-sense, and you are not a retard either. It's sure that more progressive examples are required: this one assumes a lot of previous knowledge about memory. I'll try to explain better how bitarrays work.
Imagine we want to create a pacman-like game. Look at this screenshot:
[attachimg=1]
Let's create an array to store the white-highlighted line (0=space, 1=wall, 2=pellet, 3=magic pellet):
u8 line[22] = { 1, 3, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 2, 2, 3, 1 };
This line takes up 22-bytes, 1-byte per item. Each byte takes up 8-bits of memory. Let's see how this looks like in memory, represented in bits:
Memory space taken by line array (first 6 bytes, 48 bits)
---------------------------------------------------------
binary |00000001|00000011|00000010|00000010|00000001|00000000| ...
---------------------------------------------------------
decimal 1 3 2 2 1 0
If you look at this closely, we are only using the last (right-most) 2 bits of each byte. The rest are always 0. As we only have 4 different items to represent, we only need 2 bits to represent them (00, 01, 10, 11).
So, why not to store them in groups of 2-bits instead of making it in bytes (groups of 8-bits)? We actually can do it, like this (commas are added to separate groups of 2-bits inside bytes, for better understanding):
Memory space taken by 2-bits line array (first 6 bytes, 48 bits)
-------------------------------------------------------------------------
binary |01,11,10,10|01,00,00,00|00,00,00,00|00,00,10,10|10,01,10,10|11,01,00,00|
-------------------------------------------------------------------------
decimal 1, 3, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 2, 2, 3, 1, 0, 0
With this codification, we can enconde the whole 22-bytes line into only 6-bytes, and we still leave the 4 latest bits free. But, how do we do this in C?
First, let's declare the array and initialize it with this binary information (we use prefix '0b' to tell C that we are using binary numbers):
u8 line2bits[6] = { 0b01111011, 0b01000000, 0b00000000, 0b00001010, 0b10011010, 0b11010000 };
Now the problem is how to read/modify each one of our original 22 items individually. When we had our original array, reading/modifiying items was as easy as this:
// Take into account that first item of the array is always 0, so item 1 is the second, item 2 is third and so on
//
line[12] = 3; // Change item 13 of the array to be a wall
// Read item 6 of the array and check if it is a magic pellet (2)
if (line[5] == 2) {
....
However, there is no way to directly use C-arrays to access elements smaller than a byte. For that task we can use cpct_get2Bits (http://lronaldo.github.io/cpctelera/files/bitarray/cpct_get2Bits-asm.html)/cpct_set2Bits (http://lronaldo.github.io/cpctelera/files/bitarray/cpct_set2Bits-asm.html) functions. So, if we have a 2-bits encoded array, the previous code will be the same as this code:
cpct_set2Bits(line2bits, 3, 12); // Change item 13 of the array to be a wall
// Read item 6 of the array and check if it is a magic pellet (2)
if (cpct_get2Bits(line2bits, 5) == 2) {
....
Once you grasp the concept, this is the same as using a normal C-array. The only difference is that you have to use cpct_get2Bits (http://lronaldo.github.io/cpctelera/files/bitarray/cpct_get2Bits-asm.html)/cpct_set2Bits (http://lronaldo.github.io/cpctelera/files/bitarray/cpct_set2Bits-asm.html) instead of the [] operator, and you have to think of your memory in bits instead of bytes.
This example uses arrays of 2-bits items, but you may want to use of 4-bits, to store up to 16 different values per item. You can do it same way, or use hexadecimal values instead of binary, which will be easier. Say that we want to encode fruits, and values 4, 5 and 6 represent diferent fruits. Let's encode the previous pacman line using a 4-bits array with a fruit (6) in the middle:
// 11-bytes equal 11*8 = 88 bits. 88 bits in groups of 4-bits are 88 / 4 = 22 items (same as original array).
// Each hexadecimal value (0-F) is encoded using exactly 4bits. Therefore, 1 hexadecimal value encodes a 4-bits item, and
// 2 of them form a byte.
u8 line4bits[11] = { 0x13, 0x22, 0x10, 0x00, 0x06, 0x00, 0x00, 0x22, 0x21, 0x22, 0x31, 0x00 };
...
cpct_set4Bits(line4bits, 5, 12); // Change item 13 of the array to be a new fruit (5)
...
// Read item 6 of the array and check if it is a magic pellet (2)
if (cpct_get4Bits(line4bits, 5) == 2) {
....
Please, do read this carefully and pay attention to details. Understanding this will give you better knowledge of memory and a powerful tool to optimize its usage.
If you have doubts, please ask me and I'll try to explain what you need to fully master these concepts.
QuoteIt won't work. There are 7 different tree tiles, four for a lone tree, two for overlapping trees and a 7th for tree huts. I'll figure something out, I need to if I want to finish this game.
Now I'd *really* want to know why "it won't work". It works. Many many software work on the principle I exposed, and they rely on raw array only on the last step (when displaying), which is exactly what you *have* to do. I didn't read what Ronaldo kindly wrote, maybe you'll understand better with his explanations.
Quote from: Targhan on 18:08, 29 November 15
Now I'd *really* want to know why "it won't work". It works. Many many software work on the principle I exposed, and they rely on raw array only on the last step (when displaying), which is exactly what you *have* to do. I didn't read what Ronaldo kindly wrote, maybe you'll understand better with his explanations.
Well, what I've written is related to the last step, to how to store and manage arrays/matrices at sub-byte level. Just a way to make these matrices smaller also (whenever possible). Nothing to do with how to store maps in a much optimal way, which is what you explained.
I think that @EgoTrip (http://www.cpcwiki.eu/forum/index.php?action=profile;u=337) will need a different explanation to link his ideas with those you were explaining. Your explanation is fine for me and for experienced people, but @EgoTrip (http://www.cpcwiki.eu/forum/index.php?action=profile;u=337) is still in the first steps of his learning process (regarding C programming and technical design). He is doing a great progress (much faster than most people I know), but still needs some more experience to grasp these concepts. The only thing is that he sometimes gets a little bit angry when things do not work, but I think this also happens sometimes to most of us (though each one of us expresses it in a different way).
Anyways I think this is a nice opportunity to help @EgoTrip (http://www.cpcwiki.eu/forum/index.php?action=profile;u=337) in his progress and to develop good material to help present and future people that will have the same problems :).
If you look at EgoTrips code, you can see tile numbers 0x25. So, if he's using at least 37 different tiles, the compressing into bits isn't going to yield a lot of benefit. You could perhaps restrict it to 16 tiles per room and keep the 16 tile numbers at the start, or you could go for the original plan and use a simple RLE compression to store each room since they're likely to have large repeating sections of wall/floor etc, and if you have less than 128 tiles you can use the top bit to indicate a count,
eg.
u8 line[22] = { 1, 3, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 2, 2, 3, 1 };
becomes
u8 line[22] = { 1, 3, 2, 2, 1, 0x89, 0, 0x83, 2, 1, 2, 2, 3, 1 };
You could use a variable length code if there's too many different codewords for a useful constant-size bit packing, but at that point you may as well just throw a proper compressor at it.