Learn & Master Cocos2D Game Development

Detecting collisions on pixel-perfect boundaries is the holy grail of collision detection in 2D games. As such, it seems like the ideal, if not to say perfect, solution to collision detection in general. Yet, it’s also quite complicated and the straightforward solutions don’t perform very well until you start optimizing the code.

This first post focuses on creating a pixel mask by analyzing the raw image data, as proposed over 3 years ago by Ernesto Corvi. It’s the fastest solution if you want to test if a point collides with a pixel on an image, which also works for rotated and scaled sprites. However it does take some optimizing to speed up detecting collisions between a bounding box of a node and the pixel mask, or two pixel masks.

The alternative solution is to render the two colliding objects onto a CCRenderTexture, as developed by Dani and others on the Cocos2D forum. It is able to detect collisions of arbitrarily rotated and scaled sprites but can be expected to be noticeably slower than a pixel mask. I will discuss this solution in a future iDevBlogADay post.

The results will find their way into Kobold2D, to make the solutions readily available to all developers.

The Ernesto Corvi Pixel-Perfect CollisionMap Strategy

The pseudo-code approach posted by Ernesto involves creating a 32-Bit UIImage from a file and allocating a pixelMask (he calls it collisionMap) buffer to hold the colliding/not colliding states for each pixel in the image. Then its just a matter of iterating over the image pixels, masking out the alpha part to determine if the pixel is fully opaque, and if it is, the collision flag in the pixelMask is set.

This solution has a few needs for improvements. It’s rudimentary code that doesn’t account for Retina displays and -hd images and leaves the pixelMask as upside-down image like the UIImage. It doesn’t allow the user to specify a threshold for the alpha value (0 to 255 range), to be able to consider pixels which aren’t fully opaque. And the code doesn’t provide a solution for testing rectangle intersections of the pixel mask, let alone the intersection of two pixel masks. That’s what this post is about.

Introducing KKPixelMaskSprite

KKPixelMaskSprite is a reusable class inheriting from CCSprite that adds the pixelMask and several collision detection methods. By setting the USE_BITARRAY macro to 1 you can change the class to use a BitArray instead. Instead of storing unsigned char (BOOL) types it the BitArray stores bits individually, thus reducing memory consumption to 1/8th (or 12.5%). For example, a 512×512 pixel mask using BOOL (unsigned char) will require 256 KB of memory whereas the same pixel mask as a bit array would only require 32 KB of memory.

I chose to use the Bit Manipulation Library from Michael Dipperstein because it’s released under the LGPL license - the same license Cocos2D had used before it adopted the MIT License - and because it provides implementations for both C (used) and C++.

Let’s walk through the code that loads the image and allocates the pixelMask array:

Line 2 ensures that the -hd suffix is appended to the filename, if there’s an HD version of the image available and Retina display is enabled. Lines 6-8 get the image information and the resulting pixelMaskSize, which is simply the number of pixels in the image. Depending on the USE_BITARRAY macro the pixelMask is either declared as bit_array_t* pixelMask; (BitArray) or BOOL* pixelMask; (BOOL array).

Of note here is that I chose to use the BOOL type simply because it’s the native boolean data type in Objective-C. BOOL is a typedef to unsigned char so it’s using the same underlying data type as Ernesto’s code. Be aware that BOOL and bool (note the lowercase) are two different types! The lowercase bool is a 32-Bit integer.

With the pixelMask buffer setup and cleared, we can now scan the image’s pixels and determine if each pixel’s alpha value allows it to be added to the pixelMask or not. For clarity, the USE_BITARRAY macro and BitArray implementation parts are not shown from here on.

Lines 2-4 gain access to the raw pixel information in the image. This involves using several Core Foundation functions. The UIImage gives you access to the underlying Quartz CGImage through the CGImage property. From the CGImage a CGDataProvider is created which allows the image’s raw data to be copied to a CFDataRef.

CFDataRef is merely a pointer to an internal Core Foundation struct named __CFData. The details of this struct are not exposed to developers but it can be looked up in CFData.c on opensource.apple.com. The CFDataGetBytePtr function returns a pointer to the bytes stored in the __CFData struct. What remains is simply to cast the pointer to an UInt32 (a typedef for unsigned int) because the UIImage is an image with 32-Bits per pixel (RGBA8888).

What follows in lines 8-30 is a loop that inspects every pixel in the image to determine if that pixel should be added as a collision bit to the pixelMask or not. The first peculiarity starts with lines 11-17 which calculates the index into the pixelMask. By doing so it fixes the issue that UIImage images are upside down by adding bits to the pixelMask buffer in a bottom up manner while iterating over the imagePixels buffer from top to bottom.

In line 20 the alpha part (leftmost 8 bits) of each 32-Bit pixel value is masked out. This sets all the color bits (0-23) to 0 and leaves only the highest bits which contain the 8-Bit alpha value. If alphaValue is 0 the pixel is fully transparent and we can just move on with the next iteration. Otherwise lines 24 to 28 create the UInt8 (typedef for unsigned char) value containing the pixel’s alpha (0 to 255 range) which is then compared with the alphaThreshold. If the test succeeds, the corresponding bit in the pixelMask is set to YES. Finally lines 32-35 perform the necessary cleanup and release the image memory.

A KKPixelMaskSprite can be initialized with spriteWithFile and an optional alphaThreshold value:

Testing for collision of a point in the pixel mask

Testing if a bit at a specified x,y location in the pixel mask is set is computationally inexpensive, if not trivial. It simply requires calculating the index into the array, plus some bounds checks:

The only special consideration to make is that points can have fractional parts, but we must calculate the index based on integer values (lines 4-5). To allow for natural rounding of a floating point to integer values the simple trick of adding 0.5f is used. This ensures that every fraction value greater than 0.5f is increased to the next higher integer, and since casting to integer simply removes the fractional part, we end up with values of 1.0 to 1.4999 to be rounded down to 1 whereas values from 1.5 to 1.9999 will be rounded up to 2.

The bounds check in line 7 avoids calculating an index that is out of bounds, which might cause the app to crash. In line 12 the pixelMask index is calculated based on the trusted formula that maps a 2D position onto a 1-dimensional array. Finally the bit at that index is returned. Overall this test uses simple arithmetics and is blazingly fast.

But that’s only one part of the story. The pixelMaskBitAt method is actually a private method of the KKPixelMaskSprite class. As a user of the class you will be sending the pixelMaskContainsPoint message instead. I’ll explain why after the code sample:

Since we’re working with Cocos2D, we must consider the possibility that the sprite with the pixel mask is rotated or scaled, or both. The convertToNodeSpace method in line 4 takes care of that for us. And it performs another important task by ensuring that the point coordinate is relative to the sprite texture’s origin coordinate (lower left corner). The pixelMask has the width and height of the image, indexing it with screen coordinates (whose origin is at the lower left corner of the screen) would return incorrect results.

Line 6 also makes sure that the point is converted to a pixel coordinate by multiplying it with CC_CONTENT_SCALE_FACTOR(). The content scale factor is 2 on Retina devices with Retina display enabled, otherwise it’s 1. This assumes that if you enable Retina mode and run the app on a Retina device, corresponding -hd images will be provided for all pixel mask sprites.

Continue Reading Part 2 …

I had to split this post into two, due to a PHP limitation.

Please continue with the second post of this article to learn how the rectangle intersection and pixelMask with pixelMask collision detection is done.