But ouch! This solution is not just hugely wasteful and unnecessarily slows down the physics collision code, it also introduces the well known problem of characters getting stuck even on flat surfaces.
This is in particular a problem for Box2D because its collision mechanic doesn’t work well with flat surfaces subdivided into smaller segments (rectangle shapes in this case).
A workable but still very awkward solution to work around this behavior is to create characters with bevelled edges at the character shape’s bottom at the risk of bopping characters as they walk about the map.
Lupines in the Moore Neighborhood
A good solution to generate physics collisions is to implement the Moore Neighborhood algorithm to generate chain shapes which are more suitable for tilemap collisions. The downside is that adding or removing individual blocking tiles at runtime requires updating the shapes – this is not implemented in this project.
Every flat surface, no matter how many tiles form the surface, will then consist of only one straight collision segment. Here’s a quick demo video of the project discussed in this post that shows the algorithm at work and the resulting “game”:
While researching the subject I found very little work done for cocos2d tilemaps. But I did find this page from the stone ages of the Internet which was instrumental in understanding the Moore Neighborhood algorithm, largely thanks to the animated GIFs.
The page also discusses the other contour tracing algorithms and examines their strengths and weaknesses. Without it, I would have probably spent a lot more time than 4 days on this problem, and as you can see at 5:00 in the video it’s still not quite perfect.
Tracing the contour tiles is one thing, but actually generating the line segments around the tiles correctly and properly closing them required an extra level of optimization I hadn’t initially anticipated.
Generate Physics Collision Shapes from Contours
The most important method is how the chain shapes are created after the map’s contours have been scanned and segments created for each contour:
// static body that gets the chain shapes added to it
b2Body* contoursBody = world->CreateBody(&bodyDef);
for (KTPointArray* segments in _contourMap.contourSegments)
NSUInteger vertexCount = 0;
b2Vec2 vertices; // Box2D allows for 8 vertices per shape
for (NSUInteger i = 0; i < segments.count; i++)
CGPoint point = segments.points[i];
vertices[vertexCount] = b2Vec2(point.x / PTM_RATIO, point.y / PTM_RATIO);
if (vertexCount == 8)
// last point becomes first point
vertexCount = 1;
vertices = vertices;
// create the last chain shape
if (vertexCount >= 2)
That code should be straightforward to adapt to Chipmunk, provided you know your way around Chipmunk. The contour tracing algorithm in KTContourMap is completely independent from Box2D, you’ll notice it doesn’t even have the .mm file extension.
There’s one assumption made by the KTContourMap, that is that the Tile with GID 150 is considered blocking.
You will need to change this for your own tilemap, and most likely adapt the code to allow the blocking test to check for multiple GIDs, or tiles with certain properties, or any other way you define blocking tiles in your tilemap. This is something I’ll improve before adding the contour mapping feature to KoboldTouch. I’m also considering to make this a build step so that when I get to work on streaming tilemaps the physics collision shapes can also be streamed and don’t have to be recalculated at runtime.
Deviating from the process
Since I’ve already spent double the time I allotted for this research, I will deviate a little from the usual tutorial style and just leave you with the video and project source code “as is”. This is actually the first time I missed my usual Thursday spot for iDevBlogADay articles, this one being 2 days late.
Feel free to ask questions in the comments or post modifications of the code – like every other code in my github repository this code is distributed under the MIT license.
|Follow @gaminghorror||Follow @kobold2d|