next »

[handCraftedRadio]

I was wondering what the most efficient way of storing data for my game is. I have a  variable for each pixel in the screen, 1 or 0, solid or not solid. The game reads the information for each level in a saved file to cut down loading time. The saved file is created by a different program that reads a black and white image and assigns each  pixel its number accordingly. The problem is, a 1024x768 map is over 2MB, and that is going to start adding up. Is there a better way of doing this?

[moi]

If you use one bit per pixel a 1024x768 pic should fit in less than 100 kbytes. You could just save a stream of integers in a file.

[handCraftedRadio]

Ok, but how do I read a file into a 2d array? I've been trying different things but nothing seems to be working.

[moi]

You need to use binary.
Your file should be a serie of bytes. Each byte should indicate the state of 8 consecutive pixels (on or off).
you need to create two functions, one to extract information from the serie and another to put information from the "screen" into the serie.
It should be relatively easy (basic maths + binary calulation).
Then you'd have to write the serie of bytes to disk.

[ஒழுக்கின்மை (Paul Eres)]

Why do you have a variable for each pixel on a screen, out of curiosity? I can't think of any game that has done that.

[ஒழுக்கின்மை (Paul Eres)]

But one thing you could try (if you really must store that data) is just storing it zipped, and then upzip it when you load it. Unzipped it'd be as big a BMP file.

[inmatarian]

Depending on your skill level as a programmer, I suggest going with standard solutions that are easy to implement. For instance, PNGs would be fairly easy to load (with the right libraries) and they compress well for sprite art.

[DrDerekDoctors]

If you have large chunks of solid and non-solid in a row then writing a simple run-length encoder would probably save you SCADS of space.

[Robotacon]

Moi is right, a bitmap with a depth of 1bit would result in a file no bigger than 100K. Don't store Integers on file, that would give you a much bigger file.

If you don't like bitmaps I would create some kind of tile or structure system.

Can you give us a screenshot so we know what you're working with?

[handCraftedRadio]

I don't really know how much a screen shot would help with this, but here it goes.


This is the black and white map that a program takes and converts into 1's and 0's.

Here is the C++ code.

Code:

  ofstream LFile("LevelFile.lvl", ios::out | ios::binary);
  for (int SCheckX = 0; SCheckX < 1024; SCheckX++)
  {
   for (int SCheckY = 0; SCheckY < 768; SCheckY++)
   {
    LFile << MapCo[SCheckX][SCheckY];
    LFile << "\n";
   }
   
  }

This creates a 1.5MB file. Which is way higher than I need it to be. If I convert a png file in game, the loading would take way too long for each screen.

How would I go about writing and reading in binary? So far everything I have tried from online tutorials has made the file twice as big. Some code examples would be a big help. Thanks.

[DrDerekDoctors]

Um, you know you have like 64 bytes of real information there? You're mad if you store that as anything other than rectangles.

If you can blow chunks out of it in the game (or deform it in some other way) you'd be crazy not to opt for run length encoding of some form given how chunky it is.

[PoV]

Run length encoding would be too wonky for a deformable map.  RLE implies some sort of pattern and repeat count (though 1-bit RLE could work with byte sized counts that alternate on/off's), which isn't too nice for inserting new elements.  You'd have to move everything forward to insert new runs, or back to remove runs.

- -

The problem with the code is you're writing as text.  If you open the file in a text editor, you should see a bunch of numbers, one on each line.  Technically readable yes, but not practically usable.  The easy first thing to do is change that to binary.

Technically, binary files and text files are exactly the same thing.  "ios::binary" is a flag that tells ofstream/ifstream how to encode/read something called a newline.  Newline's are a little symbolic character that actually means go to the next line, like pushing "enter" in a text editor.  You're probably familiar with one of these syntaxes when using cout.

cout << "Hello World" << std::endl;
cout << "Hello World/n";

Both do the exact same thing, but depending on weather ios::binary is enabled or not, and what platform your on (Windows, Mac, Linux), it changes how the newline is read/written.  Without going in to more detail, the easy answer is, use ios::binary whenever your reading/writing binary files, and omit it when reading/writing text files.

There's two way to write and read binary via C++ streams.  As bytes, or as streams (arrays) of bytes.  Writing individual bytes has some sign related problems that I'd rather not explain unless I'm asked, so I'll skip over that and go right to the general purpose method.

To write binary, you use "write".

Code:

ofstream MapFile("MyMap.map", ios::out | ios::binary);
int MyVariable = 25;
MapFile.write( (char*)&MyVariable, sizeof(int) );

"write" takes 2 arguments.  A char pointer to data, and the size of data in bytes.  So in the above, we're taking the pointer of MyVariable using the & operator.  That gives us an int* type variable, but "write" requires a char* type variable.  So we prefix "&MyVariable" with a cast to char* type (i.e. the "(char*)" part).  Any pointer can be cast in to another pointer type, but you should know what you're doing before you try casting in to something crazier.

"sizeof(...)" is a built in C function that return the size of a variable in bytes.  Since "write" wants a value in bytes, these 2 functions work great together.  Write can take a type directly, or a variable name, and it will automatically determine the type for you.  Be warned though, the automatic part treats pointers as the size of a pointer (4 bytes), so it's only useful for internal variables, C style arrays, class's/struct's, and any of the previous if dereferenced from a pointer (*MyPointer).

Your modified writer would look something like this:

Code:

  ofstream LFile("LevelFile.lvl", ios::out | ios::binary);
  for (int SCheckX = 0; SCheckX < 1024; SCheckX++)
  {
   for (int SCheckY = 0; SCheckY < 768; SCheckY++)
   {
    LFile.write( (char*)&MapCo[SCheckX][SCheckY], sizeof(MapCo[SCheckX][SCheckY]) );
   }
  }

Reading in binary is done with "read".

Code:

ifstream MapFile("MyMap.map", ios::in | ios::binary);
int MyVariable;
MapFile.read( (char*)&MyVariable, sizeof(int) );

Read expects a pointer to something than can hold the data.  So in the above example, we give it a pointer to an integer variable.  Integer's are 4 bytes in size, so 4 bytes are read from the file and written to it.

The updated read would look something like this.  Be sure your "MapCo" structure is sized correctly first, else we'll be doing some un-friendly things to ram. 

Code:

  ifstream LFile("LevelFile.lvl", ios::in | ios::binary);
  for (int SCheckX = 0; SCheckX < 1024; SCheckX++)
  {
   for (int SCheckY = 0; SCheckY < 768; SCheckY++)
   {
    LFile.read( (char*)&MapCo[SCheckX][SCheckY], sizeof(MapCo[SCheckX][SCheckY]) );
   }
  }

Hopefully that helps.  The next step would be to encode the map as binary data, which is different than binary files.

[DrDerekDoctors]

Run length encoding would be too wonky for a deformable map.  RLE implies some sort of pattern and repeat count (though 1-bit RLE could work with byte sized counts that alternate on/off's), which isn't too nice for inserting new elements.  You'd have to move everything forward to insert new runs, or back to remove runs.

1 bit RLE is precisely what I'm referring to, and given that this isn't for real-time storage in memory, but for when it's written to the hard drive I really don't see why RLE isn't a great solution?

[PoV]

If you can blow chunks out of it in the game (or deform it in some other way) you'd be crazy not to opt for run length encoding of some form given how chunky it is.

I think you meant "you'd be crazy to opt for...", because of the run adding/removal problem.   That's why I tried to clarify.

[moi]

Um, you know you have like 64 bytes of real information there? You're mad if you store that as anything other than rectangles.

Yeah, for some reason I assumed he wanted perpixel accuracy with possibility of real time modification like for example some sort of dig-dug game.
But this screen looks like what a zx-81 would typically do with a few bytes.
Sometimes it's good to be an old fart who had to work with old systems.

[handCraftedRadio]

PoV: The method that you used increases the file size to 3.0MB, double what it was before. I think I'm going to have to take it to the next level and encode it as binary data like you said, but I have no idea how to do it.

[DrDerekDoctors]

If you can blow chunks out of it in the game (or deform it in some other way) you'd be crazy not to opt for run length encoding of some form given how chunky it is.

I think you meant "you'd be crazy to opt for...", because of the run adding/removal problem.   That's why I tried to clarify.

Nope, because he's talking about saving it to disc, not how it's stored in memory. Obviously you wouldn't store it in memory in RLE form because you've plenty of memory. But when you save it to disc, given that the data is comprised of large runs of values, RLE seems the natural choice.

[Chris Whitman]

Hell, if you've got two values, 'on' and 'off,' you could do an RLE scheme where the high bit determines which value you're writing and the rest of the entry encodes the length information. It's simple and homogeneous enough to be interpreted by an extremely reduced set of states.

Additionally, if you have only two values and you're worried about memory space, storing every 1 or 0 in a separate byte is massively wasteful. You could just pack it all in there, bit by bit, and you'd save memory by a factor of eight.

Furthermore, I would avoid using magic numbers in your reading or writing routines (by 'magic numbers,' I mean explicit numbers like 768 or 1024). You could substitute variables there, or predefined constants at the very least, so you're not restricting yourself to a particular size, in case you want to change it later on. As a general rule, don't let low level routines make important choices that should be made by their callers.

Even furthermore, I'd like to point out that the next step, as it is in all algorithm development, is the first step, which is designing the entire thing and doing it correctly the first time. If you'd like to do a run length encoding scheme, sit down and figure out how it will work on paper, then implement that.

[PoV]

If you can blow chunks out of it in the game ...

Well then, don't hint at "blowing chunks" out of anything, whilst supporting the idea of RLE. 

PoV: The method that you used increases the file size to 3.0MB, double what it was before. I think I'm going to have to take it to the next level and encode it as binary data like you said, but I have no idea how to do it.

It might sound strange, but that's actually good.  Understanding why is important to the "next step", the idea of binary encoding. 

So, in your original example, you were writing text to the file.  An ASCII '0' or '1', followed by an ASCII newline character (0x13 and/or 0x10, for simplicity, lets assume it's only 1 byte for the newline).  That's two bytes per pixel.  To contrast, what we've written with the binary file example is the entire 4 bytes of of an integer, which is as you noted, twice the size of the text representation.

So, the solution to this problem is to somehow write less data per pixel to the file.  Given that you're only need 1 bit of information per pixel, that's our ideal size.  However, a first step could be to go from writing 2-4 bytes, and reduce that to writing 1 byte per pixel.

Bytes can hold values between 0-255 (or -128 and 127), and a byte is 8 bit's long.  Bytes are our basic measurement in computers, and are out minimum unit of space we can use.  What that means, is even though we only want 1 bit of information, we're required to use up at least 1 whole byte to do it.  Bytes represent basic text characters (A, B, C, 1, 2, 3, ...).  "C style strings" are arrays of bytes, followed by a terminator character ('H', 'e', 'l', 'l', 'o', 0).  Integers, pointers, and float's are built up of 4 bytes.

In C/C++, our unit of bytes is represented by the types 'char' and 'unsigned char'.  So the easy/lame solution is to move your data to a 'char', then write it.

Code:

ofstream MapFile("MyMap.map", ios::out | ios::binary);
int MyVariable = 25;
char MyByte = (char)MyVariable;
MapFile.write( &MyByte, sizeof(char) );

Code:

ifstream MapFile("MyMap.map", ios::in | ios::binary);
char MyByte;
int MyVariable;
MapFile.read( &MyByte, sizeof(char) );
MyVariable = (int)MyByte;

However, all this does for us is reduce the data to 1 byte in size, half of your smallest file so far.

Now, how to encode in to binary.

As it's been mentioned, binary is that whole 0 and 1 thing.  As far as whole numbers are concerned, binary is also known as the "base 2" number system.  Decimal is "base 10".  That means for every digit (i.e. character), there are that many options.  Every digit in a decimal number is between 0-9, and every digit in binary is between 0-1.

http://en.wikipedia.org/wiki/Binary_numeral_system

I'm going to assume you know what binary is for the rest of this, as well as it's basic operations (addition, subtraction, shifting, "OR", "AND", "XOR").  Review the above link to learn more/brush up on it.

Now, as it was said earlier, our smallest unit we can deal with on computers is the byte, not the bit.  To use bits, we need to cram/fit them in to a byte.  Since a byte is 8 bits in size, we can fit 8 of them in one.

So, what we want to do is change our reading and writing code to work with 8 pixels at one time.

Code:

  ofstream LFile("LevelFile.lvl", ios::out | ios::binary);
  for (int SCheckX = 0; SCheckX < 1024; SCheckX+=8)
  {
   for (int SCheckY = 0; SCheckY < 768; SCheckY++)
   {
     // ??
   }
  }

Inside that, we'll be doing something with 8 of our pixels.  Note that I changed the X to increment by 8, instead of 1.

To work with the idea of binary, we need to be sure our numbers are 0 and 1.  The number 1 in an integer or a byte is actually the equivalent of setting the first bit on.  2 in an integer or byte is the 2nd bit on.  4 in an integer or byte is the 3rd bit on, and so on.

We can move bit's around an integer or byte using shifts.  Down shift ">>" and up shift "<<".  An easy way to remember which is which is to think of the symbol as an arrow, and to look at a number.  "500".  If I wan to add another zero (5000), that'd be bigger.  If I was to remove a zero (50), that'd be smaller.  Up and down.  Up shifting makes that number bigger (doubles it to be exact).  So moving the number that way (<-), and it gets bigger (hence, "up").  "500 << 1" becomes "1000" after up shifting.  Down shifting half's the number, rounding down.  "500 >> 1" becomes "250".  Multiple shifts is like applying a shift multiple times.  "500 >> 2" would be 125, a quarter the size of the original, or 4x the size if shifting up.  Doing it again would be an 8th the size shifting down, or 8x the size if shifting up.

This is actually a binary operation behind the scenes.  Your number 50 in binary is "110010".  Shifting up, the binary number becomes "1100100", aka 100 in decimal.  Shifting down, the binary number becomes "11001", aka 25.  Shift that down again, and that right side 1 gets clipped off ("1100"), resulting in 12.  That's also an easy way to know if a number is odd or even (checking that first bit).

So, to encode our 8 pixels in to a byte, we need to fit each one in to a binary slot of a byte.  The first one is fine where it is (MyNumbers[X]).  The 2nd one needs to be shifted up by 1 (MyNumbers[X+1] << 1).  The 3rd one needs to be shifted up 2 slots (MyNumbers[X+2] << 2).  And so on, up to the last one (MyNumbers[X+7] << 7).  That'll give us individual binary bits.  Now to merge them in to one byte.

There's actually 3 ways to do this.  Adding the numbers together (+), XOR'ing the numbers together (^), or OR'ing the numbers together (|).  Technically in this case, they'll all do the same thing, but if there was bit overlap, the results of each operation would be different.  Our ideal operation for merging bit's is OR'ing.

Code:

int Bits = (Num[X+0] << 0);
Bits |= (Num[X+1] << 1);
Bits |= (Num[X+2] << 2);
Bits |= (Num[X+3] << 3);
Bits |= (Num[X+4] << 4);
Bits |= (Num[X+5] << 5);
Bits |= (Num[X+6] << 6);
Bits |= (Num[X+7] << 7);

I used the "OR Equals" operator because this wouldn't have fit cleanly on 1 line.

The above is what we'd do to combine all the bits for each pixel together in to a single number.  Convert that to a "char", and write it as binary to a file.

This post is long, so I'll do reading in a new one.

[PoV]

Reading. 

If we were to write that data all packed in to a single byte to the file, we'd now need to decode that to use it.

So like the modified writer, each single byte you read would contain information for every 8 pixels.

To extract bits from a bit-mask (another name for what we just created), we need to use shifts and AND's (&).

Code:

unsigned char Number = 50; // technically, binary number "110010"
int Bit[8];
Bit[0] = (Number >> 0) & 1;
Bit[1] = (Number >> 1) & 1;
Bit[2] = (Number >> 2) & 1;
Bit[3] = (Number >> 3) & 1;
Bit[4] = (Number >> 4) & 1;
Bit[5] = (Number >> 5) & 1;
Bit[6] = (Number >> 6) & 1;
Bit[7] = (Number >> 7) & 1;

Bit[1], Bit[4] and Bit[5] would be 1, and the rest would be 0.

What AND'ing does is only allows bits through that match the bit mask.  Our bit mask is "1", which is only the first bit.  And since we shifted up to place each bit, we now shift down to place them in the 1's spot.

A lot to take in, but that's binary encoding.  Writing a physical single byte, for 8 bits of information, instead of more.