Making of Trisector: Collision Detection

Collision detection is the core of any action game, and this article will describe how Trisector handles the mess of bullets, lasers, enemies, terrain, and the player ship colliding with each other.

The collision detection in Trisector uses a CCRenderTexture and a ccColor4B buffer. When the Collision class is initialized, the CCRenderTexture and ccColor4B buffer are setup.

// size of rt etc
rtHeight = (TILE_HEIGHT * mapDimensions.y) * rtCoarseness;
rtWidth = size.width * rtCoarseness;
rtWidthPixels = (rtWidth * rtSizeMultiplier);   // size of rt in px. double for retina
rtHeightPixels = (rtHeight * rtSizeMultiplier); // size of rt in px. double for retina

// setup the RT
renderTexture = [[CCRenderTexture renderTextureWithWidth:rtWidth height:rtHeight pixelFormat:kCCTexture2DPixelFormat_RGBA4444] retain];

// allocate the buffer
rtBuffer = malloc(sizeof(ccColor4B) * rtWidthPixels * rtHeightPixels);

Since the viewport can scroll up or down within the height of the map, the CCRenderTexture is set to the height of the map in tiles * tile height * coarseness. The coarseness is what allows this collision detection to operate at a decent speed. I’ve found that scaling the CCRenderTexture to about 25% (12.5% on Retina iPad) of the display provides a good mix of speed and accuracy.

For example, on the non-retina iPad, the device screen is 1024px wide and the map height is 960px high (15 tiles high * 64px per tile = height of 960px), which results in a CCRenderTexture that is 256px wide (1024px * 25%) and 240px high (960px * 25%). The 2048×1536 Retina iPad is also scaled to the same size of 256×240 too (since it has double the pixels and is scaled at 12.5%). Generally, I found that performance is decent when the CCRenderTexture is kept under 256×256 in size.

Finally, the Render Texture Buffer (rtBuffer) is setup to the same size as the CCRenderTexture. The raw pixels of the CCRenderTexture will be read to this buffer on each collision pass. Note, for Retina devices, keep in mind that internally cocos2d is scaling everything by 2 so that needs to be taken into account when determining coarseness. For example, here’s how the collision class sets up the coarseness. In this example, COLLISION_SCALE_DOWN is defined as 0.25.

rtCoarseness = 1.0f;

// the sizeMultiplier is used for retina
rtSizeMultiplier = 1;
if( CC_CONTENT_SCALE_FACTOR() == 2){
    rtSizeMultiplier = 2;
}

// for hd ipad, scale RT down even further
if (isiPadRetina()){
    rtCoarseness = COLLISION_SCALE_DOWN * 0.5;
}
else {
    rtCoarseness = COLLISION_SCALE_DOWN;
}

I really like using defines for variables that get tweaked throughout development. Here are some of the defines used in relation to the collision detection below:

#define COLLISION_MASK_ENEMY   1,0,0,0
#define COLLISION_MASK_OBJECTS 0,1,0,0
#define COLLISION_MASK_TERRAIN 0,0,1,0
#define COLLISION_MASK_PLAYER  0,0,0,1
#define COLLISION_COLOR_ENEMY r
#define COLLISION_COLOR_OBJECTS g
#define COLLISION_COLOR_TERRAIN b
#define COLLISION_COLOR_PLAYER a

Now that the buffer is setup and the masks are defined, the various layers (Player, Enemy, Terrain, and Objects) are drawn into the CCRenderTexture every frame. The layers are each a unique CCSpriteBatchNode that holds all the sprites for that layer type. The background, background parallax layer, and the wind are not drawn into the CCRenderTexture since the sprites in those layers don’t collide with anything.

// create new RT. note, if retina width and height are doubled
[renderTexture beginWithClear:0 g:0 b:0 a:0];

// render the collision sprites blue
glColorMask(COLLISION_MASK_TERRAIN);
// translate to RT and draw
CGPoint oldPos = [collisionLayer position];
[collisionLayer setPosition:ccp(oldPos.x*rtCoarseness, oldPos.y*rtCoarseness)];
[collisionLayer setScale:rtCoarseness];
[collisionLayer visit];
[collisionLayer setScale:1.0];
[collisionLayer setPosition:oldPos];

// render enemy and projectiles
glColorMask(COLLISION_MASK_ENEMY);
// translate to RT and draw
oldPos = [enemyLayer position];
[enemyLayer setPosition:ccp(oldPos.x*rtCoarseness, oldPos.y*rtCoarseness)];
[enemyLayer setScale:rtCoarseness];
[enemyLayer visit];
[enemyLayer setScale:1.0];
[enemyLayer setPosition:oldPos];

// render objects
glColorMask(COLLISION_MASK_OBJECTS);
// translate to RT and draw
oldPos = [objectLayer position];
[objectLayer setPosition:ccp(oldPos.x*rtCoarseness, oldPos.y*rtCoarseness)];
[objectLayer setScale:rtCoarseness];
[objectLayer visit];
[objectLayer setScale:1.0];
[objectLayer setPosition:oldPos];

// render player
glColorMask(COLLISION_MASK_PLAYER);
// translate to RT and draw, prescaled to rtCoarseness size
oldPos = [player position];
[player setPosition:ccp(oldPos.x*rtCoarseness, oldPos.y*rtCoarseness)];
[player visitCollisionSprite:rtCoarseness];
[player setPosition:oldPos];

// normalize mask
glColorMask(1, 1, 1, 1);

// rtBuffer is setup in init.  Read pixels (numPx = width/height)
glReadPixels(0, 0, rtWidthPixels, rtHeightPixels, GL_RGBA, GL_UNSIGNED_BYTE, rtBuffer);

// end the RT
[renderTexture end];

Stepping through the above, the CCRenderTexture is first cleared to all zeros. Next, the glColorMask is used to mask the layer that’s about to be drawn to one of the four color channels. In the example of the terrian collision sprites, they are drawn to the blue channel (0,0,1,0). Then, the layer is positioned and scaled utilizing the rtCoarseness value, which ensures they are translated to the proper position on the CCRenderTexture. Next, the layer is drawn via calling the layer’s visit method. Finally, the layer is restored to it’s normal scale and position.

Each layer is drawn in succession into the CCRenderTexture, which follows Z order for clarity. After all of the layers are drawn, the glColorMask is normalized. Next, the pixels are read from the CCRenderTexture and stored into the rtBuffer, after which the CCRenderTexture ends.

Now the rtBuffer is full of the pixel data corresponding to the layers and their sprites. A collision exists if a single pixel has a value in more than one color or alpha channel. For example, if a pixel has a value in the RED and ALPHA channel, that indicates an enemy or enemy bullet colliding with the player ship or player laser. If a pixel has a value in the GREEN and ALPHA channel, that indicates the player colliding with a power-up object.

Here’s a picture of the collision detection from the Analyze tool in Xcode. The Green square is the player ship being drawn into the alpha channel of the CCRenderTexture. And if you look close, you can see the terrain layer in dark blue. The CCRenderTexture is the full height of the map since collisions can occur above and below the player off-screen, but the live view is only what the player can see.

Trisector Collision Detection Debug

Here the live view that roughly corresponds to the collision detection picture. Note, it was captured at a different time/attempt so it’s not exactly the same, but it loosely matches up.

Trisector Collision Detection Display

Here’s a picture with the viewport (e.g. the 1024×768 screen) overlaid on the collision detection buffer that corresponds to the full width of the screen (e.g. 1024px) and the full height of the map (e.g. 15 tiles = 960px). Using the map height for the collision detection buffer allows enemies to be struck by the player laser off-screen. In the example below, the Spread Laser would be able to destroy the storage tank at the top of the very top of the screen.

Trisector Collision and Live Overlay

Now that the rtBuffer is full of pixel data, it’s time to check it against the objects. First, the pixels for the sprites in the player CCSpriteBatchNode are checked, and then the bullets in the enemy CCSpriteBatchNode are checked.

Here is a check for the player ship vs enemies, objects, and terrain. The COLLISION_STEP is set to 1 here, meaning that it checks every pixel of the player ship. This computation is sped up if set to 2 or more, which results in more of a rough point sampling. For the enemy projectiles, I use a COLLISION_ENEMY_STEP set to 2 since there are way more enemy bullets and it’s not game breaker if occasionally one bullet’s collision doesn’t register against a wall or the player ship.

// Read buffer. The playerRect origin/size are already scaled to 25% or 12.5% as needed
// COLLISION_STEP is 1 for the player.
for (NSUInteger y=playerRect.origin.y; y<playerRect.size.height; y+=COLLISION_STEP){
    for (NSUInteger x=playerRect.origin.x; x<playerRect.size.width; x+=COLLISION_STEP){
        ccColor4B color = rtBuffer[(y*rtWidthPixels) + x];

        // check for enemy and player collision
        if (color.COLLISION_COLOR_ENEMY > 0 && color.COLLISION_COLOR_PLAYER > 0){
            // set collision to true to set type
            collisionFlag = TRUE;
            collisionType = COLLISION_TYPE_PLAYER_ENEMY;
            collisionPoint = ccp(x/rtSizeScaler,y/rtSizeScaler);
            
            // max out
            y = playerRect.size.height;
            x = playerRect.size.width;
        }
        // check for terrain and player collision
        else if (color.COLLISION_COLOR_TERRAIN > 0 && color.COLLISION_COLOR_PLAYER > 0){
            // set collision to true to set type
            collisionFlag = TRUE;
            collisionType = COLLISION_TYPE_PLAYER_TERRAIN;
            collisionPoint = ccp(x/rtSizeScaler,y/rtSizeScaler);
            
            // max out
            y = playerRect.size.height;
            x = playerRect.size.width;
        }
        // check for object and player collision
        else if (color.COLLISION_COLOR_OBJECTS > 0 && color.COLLISION_COLOR_PLAYER > 0){
            // set collision to true to set type
            collisionFlag = TRUE;
            collisionType = COLLISION_TYPE_PLAYER_OBJECT;
            collisionPoint = ccp(x/rtSizeScaler,y/rtSizeScaler);
            
            // max out
            y = playerRect.size.height;
            x = playerRect.size.width;
        }

    } // end x loop
} // end y loop

// return true if there was a collision detected
return collisionFlag;

For player lasers, the above is performed with the exception of player laser vs object check since those do not interact. For enemy and enemy bullets, they are only checked vs terrain since the collision of enemy and enemy bullets against the player will be found when checking the player as above.

If there is a detected collision, the collision point and type are used to perform an action in response to the collision. For example, if the player laser collides with an enemy bullet, that enemy bullet will be removed from the enemy layer. If the player laser collides with an enemy ship, the ship will take damage and if it’s enough damage to destroy the enemy ship, then the enemy ship will be removed.

Originally, I had the collision check method inline after all of the core game play logic. However, after much testing, I found that the performance was noticeably better when the collision check is placed in it’s own scheduler apart from the main update: schedule. COLLISION_DETECTION_INTERVAL is set to 0.016666, which is 60fps.

// set scheduler for collision detection
[self schedule:@selector(collisionUpdate:) interval:COLLISION_DETECTION_INTERVAL];

And the collisionUpdate method looks like this:

-(void) collisionUpdate: (ccTime) dt;
{
    [self checkPlayerCollision];            // player
    [self checkPlayerProjectilesCollision]; // player projectiles
    [self checkEnemyProjectilesCollision];  // enemy projectiles
}

The three check..Collision methods check for collision of the appropriate type, and then perform an action in response to detecting a collision, as described above.

The performance of the collision detection is pretty fast, taking a few ms per frame. A benefit of this collision detection is that Trisector has a lot of irregular terrain and object shapes, and this method provides pixel perfect (well, scaled pixel perfect) collisions between objects and terrain. Also, I didn’t have to define any collision shapes, which was a plus as the shapes of almost everything changed a few times over the course of development.

One consideration in creating the sprites is that the sprites could not use pure black in large areas of the sprites since as the sprites needed to have some color value > 0 in the proper channel for their object type. Overall, I’m pretty happy with the performance and accuracy of the collision detection, and the overall clarity and cleanness of the collision detection code.

Hope you found this article on Trisector’s Collision Detection interesting,

Jesse from Smash/Riot