10
\$\begingroup\$

I've spent a couple days on my latest project, and I believe that I have achieved a sufficient level of efficiency to post it here for review.

The idea of the game is to mine out an "infinite" world of blocks by tapping on the screen. Objective-C (and Sprite Kit specifically) do not allow you to process a large number of sprites without extreme slowdown. Even though Sprite Kit is supposedly truncating the nodes to only those that are visible on screen, if thousands of nodes are present in the world, the slow down is completely obvious.

To overcome this problem I have devised a simple chunk loader that will only load the visible nodes into the world before rendering. It is working very well, and it includes dynamically expanding the view when zooming in or out.

Edit: I have made some major changes to the code that improved performance dramatically. I have edited the code in this question to include these changes. Next time I will make sure to wait a day before posting a question like this so that I do not miss such obvious performance increases. Initially, I was re-rendering the entire scene on each update. Now I have created a system that identifies which parts of the scene need to be updated, and only updates those.

I will only include the relevant parts of the scene:

DWScene.h

//this runs each update loop in a fixed time step
#pragma mark - Update
-(void) updateWithWorldBounds:(CGRect)worldBounds {
    [_game.gameWorld loadChunksForBounds:worldBounds];
    [self loadNewChunks];
    [self removeChunks];
    [self updateBlocks];

}
-(void) loadNewChunks {
    for (DWChunk *chunk in _game.gameWorld.loadedChunks) {
        if (![_visibleChunks childNodeWithName:chunk.chunkName]) {

            SKNode *chunkNode = [[SKNode alloc]init];
            chunkNode.name = chunk.chunkName;
            [_visibleChunks addChild:chunkNode];

            for (DWBlock *block in chunk.blocks.allValues) {
                [chunkNode addChild:[self blockSpriteForBlock:block]];
            }
        }
    }
}
-(void) removeChunks {
    for (DWChunk *chunk in _game.gameWorld.chunksToRemove) {
        SKNode *chunkNode = [_visibleChunks childNodeWithName:chunk.chunkName];
        if (chunkNode) {
            [chunkNode removeAllChildren];
            [chunkNode removeFromParent];
        }
    }
    [_game.gameWorld.chunksToRemove removeAllObjects];
}
-(void) updateBlocks {
    for (DWBlock *block in _game.gameWorld.blocksToUpdate) {
        SKNode *chunkNode = [_visibleChunks childNodeWithName:block.chunkName];
        if (chunkNode) {
            SKNode *blockNode = [chunkNode childNodeWithName:block.blockName];
            if (blockNode) {
                [blockNode removeFromParent];
                [chunkNode addChild:[self blockSpriteForBlock:block]];
            }
        }
    }
    [_game.gameWorld.blocksToUpdate removeAllObjects];
}
//this is passed into the above update method by another method (not included)
-(CGRect) worldBounds {
    return CGRectMake(-_world.frame.origin.x/_world.xScale, -_world.frame.origin.y/_world.yScale,
                      _screenBufferX/_world.xScale, _screenBufferY/_world.yScale);
}

And here is the game model:

DWConstants.h

static const int kStartingChunks = 10; //must be even because it will be divided in half
static const int kChunkSize = 10;
static const int kBlockSpriteWidth = 64;
static const float kBufferFactor = 1.2;

DWWorld.h

#import <Foundation/Foundation.h>

@interface DWWorld : NSObject

-(void) loadChunksForBounds:(CGRect)bounds;

@property NSMutableArray *loadedChunks;
@property NSMutableArray *chunksToRemove;
@property NSMutableArray *blocksToUpdate;

-(void) damageBlockAtPosition:(CGPoint)position;

@end

DWWorld.m

#import "DWBlock.h"
#import "DWChunk.h"
#import "DWConstants.h"
#import "DWWorld.h"

@implementation DWWorld {
    NSMutableDictionary *_chunks;
}

-(instancetype) init {
    self = [super init];
    if (self) {
        _chunks = buildInitialChunks();
        _loadedChunks = [[NSMutableArray alloc]init];
        _chunksToRemove = [[NSMutableArray alloc]init];
        _blocksToUpdate = [[NSMutableArray alloc]init];
    }
    return self;
}
NSMutableDictionary* buildInitialChunks() {
    NSMutableDictionary *chunks = [[NSMutableDictionary alloc]init];
    for (int i = -kStartingChunks/2; i < kStartingChunks/2; i++) {
        for (int j = -kStartingChunks/2; j < kStartingChunks/2; j++) {
            CGPoint position = CGPointMake(i, j);
            DWChunk *chunk = [[DWChunk alloc]initWithPosition:position];
            [chunks setObject:chunk forKey:[NSValue valueWithCGPoint:position]];
        }
    }
    return chunks;
}

-(void) loadChunksForBounds:(CGRect)bounds {
    for (DWChunk *chunk in _chunks.allValues) {
        if ([chunk intersectsWithBounds:bounds]) {
            if (![_loadedChunks containsObject:chunk]) {
                [_loadedChunks addObject:chunk];
            }
            //perform adding operation here
            //check if it is close to the border and new chunks need to be added
        } else if ([_loadedChunks containsObject:chunk]) {
            [_loadedChunks removeObject:chunk];

            if (![_chunksToRemove containsObject:chunk]) {
                [_chunksToRemove addObject:chunk];
            }
        }
    }
}

-(void) damageBlockAtPosition:(CGPoint)position {
    DWBlock *block = [self blockForPosition:position];
    [block damageBlock];
    [_blocksToUpdate addObject:block];
}

-(DWBlock *) blockForPosition:(CGPoint)position {
    int chunkXPos = floor(position.x / kBlockSpriteWidth / kChunkSize);
    int chunkYPos = floor(position.y / kBlockSpriteWidth / kChunkSize);
    DWChunk *chunk = [_chunks objectForKey:[NSValue valueWithCGPoint:CGPointMake(chunkXPos, chunkYPos)]];

    int topLeftPosX = chunkXPos * kChunkSize * kBlockSpriteWidth;
    int topLeftPosY = chunkYPos * kChunkSize * kBlockSpriteWidth;
    int blockXPos = floor((position.x - topLeftPosX) / kBlockSpriteWidth);
    int blockYPos = floor((position.y - topLeftPosY) / kBlockSpriteWidth);
    DWBlock *block = [chunk.blocks objectForKey:[NSValue valueWithCGPoint:CGPointMake(blockXPos, blockYPos)]];
    return block;
}

@end

DWChunk.h

#import <Foundation/Foundation.h>

@interface DWChunk : NSObject

-(instancetype) initWithPosition:(CGPoint)position;

@property NSDictionary *blocks;
@property NSString *chunkName;

-(BOOL) intersectsWithBounds:(CGRect)bounds;

@end

DWChunk.m

#import "DWBlock.h"
#import "DWChunk.h"
#import "DWConstants.h"

@implementation DWChunk {
    CGRect _bounds;
    CGPoint _position;
}

-(instancetype) initWithPosition:(CGPoint)position {
    self = [super init];
    if (self) {
        _position = position;
        _blocks = buildChunk(position);
        _chunkName = NSStringFromCGPoint(position);

        _bounds = CGRectMake(position.x * kChunkSize * kBlockSpriteWidth, position.y * kChunkSize * kBlockSpriteWidth,
                             kChunkSize * kBlockSpriteWidth, kChunkSize * kBlockSpriteWidth);
    }
    return self;
}
NSDictionary* buildChunk(CGPoint chunkPosition) {
    NSMutableDictionary *blocks = [[NSMutableDictionary alloc]init];
    for (int i = 0; i < kChunkSize; i++) {
        for (int j = 0; j < kChunkSize; j++) {
            CGPoint position = CGPointMake(i, j);
            DWBlock *block = [[DWBlock alloc]initWithPosition:position chunkPosition:chunkPosition];
            [blocks setObject:block forKey:[NSValue valueWithCGPoint:position]];
        }
    }
    return blocks;
}

-(BOOL) intersectsWithBounds:(CGRect)bounds {
    return CGRectIntersectsRect(bounds, _bounds);
}

@end

DWBlock.h

#import <Foundation/Foundation.h>
#import "DWBlockType.h"

@interface DWBlock : NSObject

-(instancetype) initWithPosition:(CGPoint)position chunkPosition:(CGPoint)chunkPosition;

@property BlockType type;
@property NSString *blockName;
@property NSString *chunkName;
@property CGPoint calculatedPosition;

@property int damageLevel;
-(void) damageBlock;

@end

DWBlock.m

#import "DWBlock.h"
#import "DWConstants.h"

@implementation DWBlock {
    CGPoint _position;
}

-(instancetype) initWithPosition:(CGPoint)position chunkPosition:(CGPoint)chunkPosition {
    self = [super init];
    if (self) {
        _position = position;
        _type = arc4random_uniform(BlockTypeNumTypes);
        _calculatedPosition = CGPointMake((chunkPosition.x * kChunkSize * kBlockSpriteWidth) + (position.x * kBlockSpriteWidth), (chunkPosition.y * kChunkSize * kBlockSpriteWidth) + (position.y * kBlockSpriteWidth));

        _damageLevel = 0;
    }
    return self;
}

-(void) damageBlock {
    switch (self.type) {
        case BlockTypeDirt:
            if (_damageLevel < 3) {
                _damageLevel+=3;
            } else {
                [self changeToBlack];
            }
            break;
        case BlockTypeRock:
            if (_damageLevel < 3) {
                _damageLevel++;
            } else {
                [self changeToBlack];
            }
            break;
        default:
            break;
    }
}

-(void) changeToBlack {
    _type = BlockTypeNumTypes;
}

@end

I am open to any kind of feedback, but the most important thing is to increase the performance in any way possible. I've tried to do as much of this as I can, but it is still not perfect. I will note that the reason I have the calculatedPosition property in the DWBlock class is to save time doing those calculations when the sprites are drawn on the screen.

\$\endgroup\$
5
\$\begingroup\$

When I first read this question, my first thought is... how come this is all run on a single thread?

I realize that part of this reason is because at the end, we're drawing UI and that all has to be done on the main thread. But that doesn't mean everything has to be done on the main thread.

However, it should be noted that I really don't like this term "load" or "loading" in your title, methods names, etc. What we're actually doing here is rendering.

To me, "load" says we're moving things into memory. This can either mean we're either reading from a file and instantiate objects to represent the contents of that file, or we're reading from some sort of webserver, to do the same thing, or we're instantiating from scratch based off preset constants, random values, or user inputs. The point here is, to me, "load" is the step from which we go to having no instantiate objects in RAM to represent whatever we're "loading" to the point of having those objects in RAM.

Meanwhile, "render", to me, says we're taking instantiated objects in RAM and representing them graphically on the screen. In practice, a lot of times, this may mean instantiating a new object... but this is different from loading. We're instantiating a UI object only to represent the graphics of the model object we "loaded" in the loading step. In reality, a lot of times, we're actually "re-rendering." Consider how a UITableView works. We only render (instantiate a new UI object) if there isn't already one of that time in the table view. Otherwise, we rerender (recycle) the one that has just scrolled off the screen. We don't instantiate a new cell, we simply grab the old one and change how it looks a bit. If we rendered a new one each time, we'd run into one of two problems. Either a) we'd run out of memory as we stuck a ton of cells into RAM or b) we'd scroll very slowly as we'd be taking the time to deallocate, allocate, and initialize a new cell every time one scrolled off and a new one scrolled on.


I know this seems like a long rant just to point out a seemingly inconsequential difference in word choice... but it's not actually inconsequential.

At the end of the day, you've written this code because keeping all the rendered chunks in memory was too much, so instead, now, this code just keeps the models of the chunks in memory and then renders them just-in-time to appear on the screen. That's fine (though, I still recommend multithreading the rendering).

But how big can the world get? What's the memory footprint of the chunks? Is is possible that the player's world is too large to keep all the models of the chunks in memory at once?

We might have to do something similar to this to actually load chunk models into memory from file (at a farther distance than we render them) and then save them to file from memory (then deallocate) as they move farther away. Even if the current game limits wouldn't be too much to keep the entire world in memory, making this change would allow your worlds to have an unlimited size. (Well, less limited anyway... there's still a limit on how much you can write to file... but you could even save it on the cloud, etc).

\$\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.