News:

Printed Amstrad Addict magazine announced, check it out here!

Main Menu
avatar_EgoTrip

[cpctelera]Bit Arrays

Started by EgoTrip, 23:51, 24 February 16

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

EgoTrip

How do I use bit arrays? The example isn't very useful and I can't figure it out.

What I want to do is convert my level data so each byte stores two tiles instead of one. This way I can halve the memory I am currently using (10240 bytes) and then I will hopefully have enough space left over to finish the game.

Munchausen

Is it just C?

I guess you want to work with nibbles (units of 4 bits in length)? Why don't you just use an unsigned char and masks? This would give you more control over the generated code. Otherwise, you can do something like

struct A {
  unsigned int nibble1 : 4;
  unsigned int nibble2 : 4;
}


or

union A {
  struct B {
    unsigned int nibble1 : 4;
    unsigned int nibble2 : 4;
  };
  unsigned char byte;
}

arnoldemu

Quote from: EgoTrip on 23:51, 24 February 16
How do I use bit arrays? The example isn't very useful and I can't figure it out.

What I want to do is convert my level data so each byte stores two tiles instead of one. This way I can halve the memory I am currently using (10240 bytes) and then I will hopefully have enough space left over to finish the game.
This may sound stupid, but how many tiles do you have?
If you have less than or exactly 16 then you can store more than 1 in a byte, more than 16 and you can only store 1.
My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

EgoTrip

#3
@Munchausen I am using CPCtelera and there are Bit Array functions which I assume are what I need to use.

@arnoldemu  Theres more than 16. Cant remember off the top of my head but theres at least 40 different tiles and tile types.

Surely its possible to store two, if there are less than 128, one in the first 4 bits and the other in the second. I assume the CPCtelera bit array functions cater for this, for 1 2 and 4 bits storing values. I think I understand it in principle. I just don't understand how to use it. My maths brain isn't very good remember.

Heres's an example level:


    0x10, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x12,
    0x17, 0x00, 0x00, 0x00, 0x00, 0x00, 0x24, 0x24, 0x24, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13,
    0x17, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x24, 0x0E, 0x00, 0x00, 0x0E, 0x00, 0x00, 0x13,
    0x17, 0x24, 0x00, 0x24, 0x24, 0x24, 0x00, 0x00, 0x24, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13,
    0x17, 0x24, 0x00, 0x24, 0x00, 0x00, 0x00, 0x00, 0x24, 0x00, 0x18, 0x19, 0x00, 0x00, 0x00, 0x00,
    0x17, 0x24, 0x00, 0x24, 0x00, 0x24, 0x00, 0x00, 0x24, 0x00, 0x1B, 0x1A, 0x00, 0x00, 0x00, 0x13,
    0x17, 0x24, 0x00, 0x24, 0x00, 0x24, 0x00, 0x00, 0x24, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13,
    0x17, 0x24, 0x24, 0x24, 0x00, 0x24, 0x00, 0x00, 0x00, 0x0E, 0x00, 0x00, 0x0E, 0x00, 0x00, 0x13,
    0x17, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x24, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13,
    0x16, 0x15, 0x00, 0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x14


So am I right in understanding that you could combine two tiles into one, so the first two are 0x10 and 0x11. If the first tile 0 uses the first 4 bits (0-0x7f) then the second tile would use the second 4 bits (0x80-0xFF)which would increase its value to 0x91 by adding 0x80? Then add the two together to give the encoded byte 0xA1?

I need to figure out how to automate it too, because encoding by hand is going to be a labourious task. I could probably do that in BASIC and output to the printer or and ASCII file in WinAPE. Decoding it in C is a whole other matter and thats where I'm completely lost.

In fact none of the tiles go above 0x3F so could I even encode four in each byte?

arnoldemu

Quote from: EgoTrip on 10:33, 25 February 16
@arnoldemu  Theres more than 16. Cant remember off the top of my head but theres at least 40 different tiles and tile types.
4 bits gives a max of 16. So you can't use less than a byte. Sorry. So this means some bits are unused but not much you can do about that.

1 bit gives max of 2,
2 bits gives a max of 4,
3 bits gives a max of 8,
4 bits a max of 16,
5 bits a max of 32.
6 bits a max of 64.
7 bits a max of 128.
8 bits a max of 256.

Say you have a max of 32, there is 3 bits unused in one byte UNLESS two/three bytes are put together. Now you can reduce the waste but how you access the data is more complex.

My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

EgoTrip

OK so is there any other way of compressing that data? RLE is too confusing and won't really reclaim much memory anyway. Otherwise the game will be impossible to finish.

gerald

Quote from: EgoTrip on 10:58, 25 February 16
OK so is there any other way of compressing that data? RLE is too confusing and won't really reclaim much memory anyway. Otherwise the game will be impossible to finish.
RLE is one method, you can also use procedural generation.
On the level you posted, you have a border. If this border is there on all level, just add a function to generate it. For the opening in it, just store their location and 'open' them once the border is generated.
You can also have functions for drawing lines of the same tiles (0x24 in your level). One function for vertical,  one for horizontal. may be one for rectangle.

Since you level is 16*10, you can store coordinate in one byte, so where you have 5 consecutive tiles, you can compress them as 2/3 bytes ( xxxxyyyy lllttttt)
2 bytes if you use a table of line
3 bytes if you use a byte to specify the line type

Munchausen

You could store 4 tiles in 3 bytes as long as you have less than 64 tiles, but it is going to slow you down doing a lot of bit manipulating. Gerald's idea sounds better.

ronaldo

#8
Hi @EgoTrip ,
   as @arnoldemu and others have already pointer out, there is no way to store 40 values on 4 bits. 4 bits give you at most 2^4 = 16 values. The only thing you could do for this is ensuring that you have only 16 different tiles per screen. You could have 40 tiles for your complete game, but never use more than 16 per screen (or on most of your screens, and have a special treatment for screens having more than 16 tiles). Other more complex possibilities will include using 16 tiles for the upper part of the screen and 16 for the lower... You could think of different combinations, but with 4 bits you can only address 16 different values at the same time.
   
   Now, let's explain how bitarrays work.


   To store 2 values into each single byte, you have cpct_set4Bits and cpct_get4Bits. This 2 functions let you read and store values into the bitarray. So, let's imagine we wanted to store a 10x10 tiles screen into a bitarray, having 2 tiles per byte. We will need 50 bytes for that (10x10 = 100 tiles, 100/2 = 50 bytes, as we store 2 tiles per byte). We define a normal array to store our values:

   const u8 map[50];  // 10 * 10 / 2

   Let's imagine tile 0 as a void space and tile 1 as a wall. We can some loops to create a frame with walls (fill the 4 borders of the map with walls):

   // Fill in the upper and lower borders.
   // First line of the map= 10 first tiles, last line = 10 last tiles
   //----------------------------------------------------------------------------------
   for(i=0; i < 10; i++) {
      cpct_set4Bits(map, 1, i);      // This is equivalent to map[i] = 1;
      cpct_set4Bits(map, 1, i + 90); // This is equivalent to map[90 + i] = 1; Remember that our 4-bits map is 10x10 = 100 tiles.
   }

   // Fill in the left and right borders.
   // Left border = first tile of every line = {0, 10, 20...}
   // Right border = last tile of every line = {9, 19, 29...} (+9)
   // Take into account that 0, 9, 90 and 99 are already set
   //----------------------------------------------------------------------------------
   for(i=10; i < 90; i+=10) {
      cpct_set4Bits(map, 1, i);     // Left tile
      cpct_set4Bits(map, 1, i + 9); // Right tile
   }

   Now, let's create a function to draw the map in the screen.

   void drawTheMap() {
      u8 x, y, i;


      // 'i' will be the index of the next tile in the map
      i=0; 
      for(y=0;y<10;y++) {
         for(x=0;x<10;x++) {
            u8 tile = cpct_get4Bits(map, i); // equivalent to tile=map[i];
            drawNextTile(tile);              // This imaginarily draws a tile and stays ready for next one to the right
            i++;                             // Next tile from the map
         }
         jumpToNextTileLine(); // This imaginary function sets everything ready for drawing next tile line
      }
   }

   Another way to populate a bitarray is doing it at the same time it is defined. For doing this you have to take into account the way it works. In this example, we want to use 4-bits for each tile. 4-bits is a nibble, and corresponds to 1 hexadecimal digit. So, we can initialize our map using hexadecimal numbers, taking into account that each digit will be the value of a tile. It will be like this:

   // 0x is the prefix for hexadecimal numbers. We use a define for getting rid of it visually
   // For this example, 0=space, 15=wall_type1, 10_wall_type2, 1=door, 2=enemy respawn, 3=weapon respawn
   //------------------------------------------------------------------------
   #define _ 0x
   const u8 map[50] = {
      _FF,_FF,_FF,_FF,_FF,
      _F0,_00,_00,_00,_3F,
      _F0,_AA,_20,_AA,_0F,
      _F0,_AA,_A1,_AA,_0F,
      _F0,_00,_00,_00,_0F,
      _F0,_AA,_1A,_AA,_0F,
      _F0,_AA,_00,_AA,_0F,
      _F0,_00,_00,_A2,_0F,
      _F0,_3A,_00,_00,_0F,
      _FF,_FF,_FF,_FF,_FF
   };
   #undef _

   To better view this map, I have created a PNG with some random tiles. The right part of the image is the same map, both with non-zero values overlayed to note their meaning.
   [attachimg=1]
   I hope this works as an example on how bitarrays work.

EgoTrip

My original confusion was obviously how binary worked. I was thinking you could chop it in half but it doesn't work that was as its not linear.

Theres no easy way of doing this which doesn't involve a complete re-write and redoing the screens is there? Ideally I'd like to do something with the data that RGAS puts out as I really cant be doing with having to do it all over again in some other program or way.

andycadley

#10
I suspect the trick will be to store your screens compressed, then expand the current one into your current easy to use array as you need it. Pretty sure we can help come up with something if you post an example of a screen layout.

Also 100% certain we can transform whatever your current data is into whatever it needs be in a nice automated way.  ;)

Sykobee (Briggsy)

An awkward situation - do you have an example screen that we can see?


There are some tricks - your map can store tile type rather than tile graphic. For example, if you have several wall blocks for corners, straights, etc, then you can algorithmically calculate these on the fly from a single wall block in the map data depending upon what is around it. Ditto for most things with borders - water, paths, etc. All you'd need to do is get the number of tile types to 16.


But special objects (collectables) may be a problem - they're all different. But they share a type - special object, use that, and have a few bytes after each screen's tile type data to specify the special object's actual specific object type (in the order they appear on the screen).


Yes, these methods stop you being able to use the map designer's tools, sorry.

EgoTrip

Attached are some screen shots. As you can see, there is nothing uniform about any of them so some tricks are going to be unusable.

I already have special objects seperate from the map, it was necessary to do it this way as none of them were persistent, they disappeared forever once collected and if I changed them on the map then it would change them forever even after a game over then restart. This is one problem I have solved and it works great.

andycadley

Quote from: EgoTrip on 10:33, 25 February 16Heres's an example level:


    0x10, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x12,
    0x17, 0x00, 0x00, 0x00, 0x00, 0x00, 0x24, 0x24, 0x24, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13,
    0x17, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x24, 0x0E, 0x00, 0x00, 0x0E, 0x00, 0x00, 0x13,

...

Ok, so let's start with the worlds easiest version of RLE possible. Not particularly efficient, or clever and easily beatable once you get your head around it. What we'll do is store our levels in pairs of bytes. The first byte of each pair tells us how many bytes to write into our level array, the second which value to write. So the first three lines of your screen (as quoted) encoded into pairs would look something like:

(1,0x10), (14,0x11), (1,0x12),     
(1,0x17), (5,0x00), (3,0x24), (6,0x00), (1,0x13),   
(1,0x17), (7,0x00), (1,0x24), (1,0x0e), (2,0x00), (1,0x0e), (2,0x00), (1,0x13),

That's got our size down from 48 bytes to 32, a 30% saving without really trying very hard.

The pseudo code to expand this would look something like:


x =0
y =0

while y < heightofscreen
  read count and tile
  while count > 0
     screen(x,y) = tile
     x = x + 1
     if (x > widthofscreen) then x = 0, y = y + 1
  end while
end while


We can be a lot smarter than that if we start looking closer at the data. For example if all our tiles are numbered less than 128, we can use count values less than 128 to mean "just write one of these tiles out" and values of 128 and above to mean (128 + real count value). That would avoid the overhead of encoding single tiles with the byte pair (1, xxx) as above so will pack data tighter. That's "step 2" though, after getting your head around how the easiest encoding pattern would work.

SRS

#14
QuoteWe can be a lot smarter than that if we start looking closer at the data. For example if all our tiles are numbered less than 128, we can use count values less than 128 to mean "just write one of these tiles out" and values of 128 and above to mean (128 + real count value). That would avoid the overhead of encoding single tiles with the byte pair (1, xxx) as above so will pack data tighter. That's "step 2" though, after getting your head around how the easiest encoding pattern would work.

Which would be:

x10,x8E,x11,x12,
x17,x85,x00,x83,x24,x86,x00,x13
x17,x87,x00,x24,x0e,x82,x00,x13

Thats 20 Bytes instead of 48. 

And may I suggest another First Byte that statest "I am  compressed" (lets say x80) and "I am uncompressed" (x00).

I think your first Level would be better of beeing uncompressed.

// handling compressed screen

x =0
y =0

while y < heightofscreen
  read data;
  if data < x81  then screen(x,y) = data
  else
   {
    count = data - 0x80;
    read tile;
    while count > 0
     screen(x,y) = tile
     x++
     if (x > widthofscreen) then x = 0, y++
    count--
  end while // count
  }
end while  // y


ronaldo

#15
   I was writting a post with 2 encoding ideas, being one of them a simple RLE encoding, just like @andycadley has suggested. In fact, I was going to suggest the approach of using tile identifiers greater than a value (be it 128, 64 or whatever) as "commands" for repeating. In fact, you could think of them as "commands" in the broader sense to do things, and write a parser for them. Let's take your 3-houses map, for instance, and encode one similar to it. Imagine your first line of the map to be this one:
   
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,2,

   Let's define that a value greater than 128 in your array means exactly this "repeat this-128 times the next tile". That let's us encode previous line as this:

   128+38, 0, 1, 2

   We could do the same with a line encoding the upper side of your 3 houses (without vegetation):

   0,0,0,0,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0,0,0,0,0,1,2,

   It will be like this,

   128+4, 0,   128+6, 4,   128+5, 0,   128+6, 4,   128+5, 0,   128+6, 4,   128+6, 0,   1, 2,

   To improve readability, we could create a macro

   // Macro for inserting repetitions encoded in our "manual RLE"
   #define R(Num,Value)  (128+Num), (Value)
   ....
   const u8 map[] = { .....
   ....
   R(4, 0), R(6, 4), R(5, 0), R(6, 4), R(5, 0), R(6, 4), R(6, 0), 1, 2,
   ....

   Now it is easy to read "Repeat 4 times 0", "Repeat 6 times 4".


   The only thing left is creating a function that transforms this encoding into a byte-by-byte one, to use it for the screen that is to be drawn. We could do it as follows:

   // Maximum value for a tile. Anything greater than that will be
   // considered a command in the encoded map
   #define MAX_TILE  128
   
   const u8 vis_map[20*20];   // Visible map. The one that will be drawn to screen


   // Decompresses an encoded map into a byte-by-byte one
   void decompress_map(u8* encoded_map) {
      u16 i = 0, e = 0;       // Indexes for the map arrays (they will be greater than 256)


       // Repeat until vis_map is complete
      while(i < 20*20) {
         u8 c = encoded_map[e];  // Get next value from encoded_map
         e++;                    // Point to the next value in the encoded map


         // Check if value got is a command or a tile-id
         if (c <= MAX_TILE) {
            // c is a tile-id, we only have to copy it to the visible map and
            // Point to the next value to be inserted in the visible map
            vis_map[i] = c;
            i++;
         } else {
            // c is a command. Get next value as tile-id and point to the next value in encoded_map
            u8 r, tile = encoded_map[e];
            e++;


            // Insert tile in visible_map (c - MAX_TILE) times
            for(r=0; r < (c - MAX_TILE); r++) {
               vis_map[i] = tile;     // Insert tile in the next visible_map location
               i++;                       // Point to the next visible_map location
            }
         }
      }
   }

   
   With this, and the examples that @andycadley and @SRS have given, you have an introduccion on how to encode your maps to save space with a manual RLE.


   As I mentioned earlier, you can develop this technique much more thinking of your values greater than MAX_TILE as commands. For instance, you could create commands like "Repeat next complete line N times" for maps where you have 5 or 6 lines that are identical, like your second one. However, I suggest starting first with a basic encoding, grasp it fully and then advance one step at a time.

SRS

#16
@ronaldo - thats a good explanation and suggestion.

@EgoTrip - if you want automatic encoding instead of doing it all manual for your levels rosetta may help: "Run-length encoding - Rosetta Code; - it uses the <128 >128 method

And, btw: nice, "nintendo-style" gfx !

EgoTrip

I give up.  Consider this project abandoned.

SRS

Quote from: EgoTrip on 15:21, 26 February 16
I give up.  Consider this project abandoned.

;) - nice try. As others said  - if you need help, even coding that, we are here ! Maybe you can put it on GitHub for shared work.

Arnaud

#19
I tried an easy solution :

       
  • creation of a file with your data level.
  • use exomizer to compress in command line the data level : 160 -> 76 Bytes
  • convert with cpctelera the binary file into data.h
  • decompress the data level with the function cpc_UnExo from the cpcrslib
cpc_UnExo(dataLevelCompress, currentLevel);

That all !


EgoTrip

This isnt the only reason I have given up. I keep encountering bugs that I can't fix and appear for no apparent reason, its stressing me out and im not having any fun doing this so whats the point.

SRS

Okay, that is an issue no more fun - this all is a hobby, and hobby without fun, no way.

     You could release your work into public so someone could have a look, get it in shape and so on. Just maybe, so all your work does not get lost.

reidrac

@ronaldo Very nice examples, it is similar to what I've done in some projects.

I recommended @EgoTrip to use an existing RLE compressor (like ZX7 by Einair Saukas) and compress all maps data, and use a "working" version of each screen so he can uncompress to that memory address before rendering the map. ZX7 has a compressor that can be run in a regular PC and Z80 ASM code to be used in the CPC.

Map data usually contains repeating patterns that compress OK with a good RLE compressor.

For example, I use UCL (from UPX fame) in Space Pest Control and this is what I get for the 25 screens:


ucl: 100 bytes compressed into 57 bytes
ucl: 100 bytes compressed into 58 bytes
ucl: 100 bytes compressed into 53 bytes
ucl: 100 bytes compressed into 54 bytes
ucl: 100 bytes compressed into 46 bytes
ucl: 100 bytes compressed into 62 bytes
ucl: 100 bytes compressed into 57 bytes
ucl: 100 bytes compressed into 64 bytes
ucl: 100 bytes compressed into 59 bytes
ucl: 100 bytes compressed into 64 bytes
ucl: 100 bytes compressed into 72 bytes
ucl: 100 bytes compressed into 48 bytes
ucl: 100 bytes compressed into 50 bytes
ucl: 100 bytes compressed into 80 bytes
ucl: 100 bytes compressed into 66 bytes
ucl: 100 bytes compressed into 75 bytes
ucl: 100 bytes compressed into 67 bytes
ucl: 100 bytes compressed into 44 bytes
ucl: 100 bytes compressed into 65 bytes
ucl: 100 bytes compressed into 52 bytes
ucl: 100 bytes compressed into 77 bytes
ucl: 100 bytes compressed into 64 bytes
ucl: 100 bytes compressed into 53 bytes
ucl: 100 bytes compressed into 21 bytes
ucl: 100 bytes compressed into 64 bytes


Being 100 bytes a 20 x 10 tiles screen (using 4-bit per tile, that's 100 bytes).

That's 1472 bytes for the 25 screens, that's a 41.12% of savings (over 1K). And of course I use the uncompress code in other places, so it really pays off!

So exactly what @Arnaud said!

Your 4-bit example is similar to what I used in Space Pest Control (and most recently in Castaway, a ZX Spectrum title). The CPCTelera functions must be really handy as they're highly optimised in ASM and I had to write mine for the same effect ;)

@EgoTrip don't give up. Just give it time. What you're trying to achieve isn't simple, but you'll get it right eventually.
Released The Return of Traxtor, Golden Tail, Magica, The Dawn of Kernel, Kitsune`s Curse, Brick Rick and Hyperdrive for the CPC.

If you like my games and want to show some appreciation, you can always buy me a coffee.

FloppySoftware

Quote from: EgoTrip on 18:32, 26 February 16
This isnt the only reason I have given up. I keep encountering bugs that I can't fix and appear for no apparent reason, its stressing me out and im not having any fun doing this so whats the point.

To improve your programming skills can be a good reason to finish the project.  ;)

I have lots of unfinished projects, but they are not abandoned, just waiting for the right time.  ;)

BTW, nice bitmaps.  :)
floppysoftware.es < NEW URL!!!
cpm-connections.blogspot.com.es

FloppySoftware

Quote from: SRS on 18:18, 26 February 16
;) - nice try. As others said  - if you need help, even coding that, we are here ! Maybe you can put it on GitHub for shared work.

It sounds nice! It seems a good opportunity for a team project.
floppysoftware.es < NEW URL!!!
cpm-connections.blogspot.com.es

Powered by SMFPacks Menu Editor Mod