8
\$\begingroup\$

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];
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I can't make any suggestions in terms of tuning strategy, however maybe some alternative approaches. Can you apply archiving to the disk or a different storage strategy besides just disk? Archive older disk files that might not be used or using a different storage mechanism such that you could use both disk and alternative saving location for certain check points. Then re-access that data later. Obviously wouldn't be as fast as having it on disk but might free up some space. \$\endgroup\$
    – haju
    Dec 8, 2014 at 16:15

1 Answer 1

3
+50
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.