Saving bytes instead of objects to write smaller files

Question

This question is about reducing the size of files saved to disk in an infinite world 2D mining game.

I finally added code to my game to save and load distant chunks instead of keeping all of them in memory. Up to this point, I had only used the default NSCoding Apple library to save and load files from disk. In my initial testing, each Chunk consisted of 900 Blocks, and when saved to disk the file was 160kb. This would mean that worlds with just a few million blocks could be bigger than a gigabyte.

I tried a number of different methods to decrease the size of the files. I found some code on Stack Overflow to implement some gzip compression, and that reduced the size down to about 74kb. This was good, but not nearly good enough. The next thing I tried was to reduce the amount of information stored in each block. I removed all the NSStrings, and derived those from other values instead of saving them. I converted all the CGPoints to ints, and saved those instead. This got the file size down to about 52kb. This was almost small enough to work, but I knew I could do better.

The Blocks themselves only had a very small amount of information stored in them. I decided to manually compose the bytes needed to initialize a block, and then manually parse those bytes when the file was loaded.

I succeeded in writing some code to do this, and it got the file size down to 4kb. Each Block is 28 bytes, so this is much closer to a reasonable number. I should note that when I tried without the gzip compression, the file size rose to 25kb. I decided to use the Apple libraries to do this, so I am reading and writing to NSData. I believe there are better ways to achieve this, and I would love to hear about them.

DWBlock.m

#pragma mark - Custom encode and decode
-(instancetype) initWithData:(NSData *)data {
    self = [super init];
    if (self) {
        int theBytesRecovered[7];
        [data getBytes:theBytesRecovered];

        _type = (int)theBytesRecovered[0];
        _damageLevel = (int)theBytesRecovered[1];
        _chunkSize = (int)theBytesRecovered[2];

        int posX = (int)theBytesRecovered[3];
        int posY = (int)theBytesRecovered[4];
        int chunkPosX = (int)theBytesRecovered[5];
        int chunkPosY = (int)theBytesRecovered[6];
        _position = CGPointMake(posX, posY);
        _chunkPosition = CGPointMake(chunkPosX, chunkPosY);

        _blockName = NSStringFromCGPoint(_position);
        _chunkName = NSStringFromCGPoint(_chunkPosition);
        _calculatedPosition = CGPointMake((_chunkPosition.x * _chunkSize * kBlockSpriteWidth) + (_position.x * kBlockSpriteWidth), (_chunkPosition.y * _chunkSize * kBlockSpriteWidth) + (_position.y * kBlockSpriteWidth));
    }
    return self;
}
-(NSData *) customEncode {
    int type = _type;
    int damageLevel = _damageLevel;
    int chunkSize = _chunkSize;
    int posX = _position.x;
    int posY = _position.y;
    int chunkPosX = _chunkPosition.x;
    int chunkPosY = _chunkPosition.y;

    int theBytes[] = {type, damageLevel, chunkSize, posX, posY, chunkPosX, chunkPosY};

    return [NSData dataWithBytes:&theBytes length:sizeof(theBytes)];
}

DWChunk.m

#pragma mark - Custom encode and decode
-(instancetype) initWithData:(NSData *)data {
    self = [super init];
    if (self) {
        _memConstants = [[DWMemoryConstants alloc]init];

        //Iterate through the chunk data
        //Grab the correct number of bytes for each block
        //Compose a new NSData out of those bytes, and add them to an array
        NSMutableArray *blockDatas = [[NSMutableArray alloc]init];
        uint8_t *bytePtr = (uint8_t *)[data bytes];
        NSInteger totalData = [data length] / sizeof(uint8_t);
        for (int i = 0; i < totalData; i+=kChunkSizeInBytes) {
            NSMutableData *blockData = [[NSMutableData alloc]init];
            for (int j = 0; j < kChunkSizeInBytes; j++) {
                [blockData appendBytes:&bytePtr[i + j] length:1];
            }
            [blockDatas addObject:blockData];
        }

        //Create the Block objects
        _blocks = [[NSMutableDictionary alloc]init];
        BOOL firstRun = YES;
        for (NSData *data in blockDatas) {
            DWBlock *block = [[DWBlock alloc]initWithData:data];
            //Get some data about this Chunk from the first block
            if (firstRun) {
                _position = CGPointFromString(block.chunkName);
                firstRun = NO;
            }
            [_blocks setObject:block forKey:[NSValue valueWithCGPoint:CGPointFromString(block.blockName)]];
        }

        _chunkName = NSStringFromCGPoint(_position);
        _bounds = CGRectMake(_position.x * _memConstants.chunkSize * kBlockSpriteWidth,
                             _position.y * _memConstants.chunkSize * kBlockSpriteWidth,
                             _memConstants.chunkSize * kBlockSpriteWidth,
                             _memConstants.chunkSize * kBlockSpriteWidth);
    }
    return self;
}
-(NSData *) customEncode {
    NSMutableData *data = [[NSMutableData alloc]init];

    for (DWBlock *block in _blocks.allValues) {
        //It is very important to get the bytes of the NSData and not just the pointer
        [data appendBytes:[[block customEncode]bytes] length:[[block customEncode]length]];
    }

    return data;
}

Chunks are saved like this:

for (DWChunk *chunk in chunks) {
    NSString *path = [[self applicationDocumentsPath] stringByAppendingPathComponent:[NSString stringWithFormat:@"worldtest%@", NSStringFromCGPoint(chunk.position)]];
    NSData *data = [chunk customEncode];
    data = [DWDataZipper gzipDeflate:data];
    [data writeToFile:path atomically:YES];
}

And loaded like this:

NSString *path = [[self applicationDocumentsPath] stringByAppendingPathComponent:[NSString stringWithFormat:@"worldtest%@", NSStringFromCGPoint(position.CGPointValue)]];
NSData *chunkData = [NSData dataWithContentsOfFile:path];
if (chunkData) {
    chunkData = [DWDataZipper gzipInflate:chunkData];
    DWChunk *chunk = [[DWChunk alloc]initWithData:chunkData];
}

Answer 1

Do chunkLength = chunkPosY-chunkPosX or length = posY-posX have a max limit?
Does damageLevel, type have a max value say 10.
Did you try using a structure and writing that to the file (as in C). A few benefits include:

• Bit field usage.

• Easy retrieval and storing instead of storing block metadata.

  struct NSData { 
      int type :4; // bitfield usage since the max type is 10(1010)
      int damageLevel:4; // bitfield usage since max damageLevel is 8(1000)
      int posX;
      int posY; // If length = posY-posX has a max level with limited bitfield usage; Use it.
      int chunkSize; //Is this a part of the actual data to be stored.
      int chunkPosX;
      int chunkPosY; // Same as above.
  }
  

I have used structs in C and the size is almost equal to the calculated size, i.e.

sizeof(NSData) * number of NSData

One observation:
Since all your data are numbers, if each item's value does not exceed '999'(3 characters), you can serialize it to a string delimited with any character and save it.

    2|5|22|35|123|24|98; // This will occupy less bytes instead of 28 bytes.
    decimal-value delimiter string-end-delimiter. // uses 19 bytes
    2|5|F6|23|7B|F8|62;
    hex-value  delimiter string-end-delimiter. //20Bytes

Note: kb = KiloBits; kB = KiloBytes.
(Unsure how 900Blocks * 28Bytes < 24KB)