Generate Tilemap Physics Collision Shapes with Cocos2D

On June 1, 2013, in idevblogaday, by Steffen Itterheim

Screen Shot 2013-05-31 at 00.59.01 You have a tilemap and you want physics collisions on it? The solution seems obvious: create a rectangle shape for every blocking tile.

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:

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.

The project and source code for this articles are available on github.

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.


This article was brought to you by ...

I very much enjoy the learning process, the pushing of boundaries (mine and yours and that of technology), having the freedom to pursue whatever is on my mind, to boldly program what no one has programmed before, and to write about what I've learned. Help me help you by browsing the products in the Learn Cocos2D Store.

7 Responses to “Generate Tilemap Physics Collision Shapes with Cocos2D”

  1. George says:

    Hi Steffen,
    Firstly I would like to thank you for the immense contribution you have made to Cocos2d literacy. You’ve have the learning process a lot simpler for a good number of us.
    Basically, I’ve been trying for the past few days to call a method when a particular CCAnimationFrame displays in a CCAnimation sequence. You might have seen my post on stackoverflow (http://stackoverflow.com/questions/17611628/calling-a-method-when-a-particular-ccanimationframe-is-displayed-using-ccanimati). I would really appreciate it if you could assist me in solving this issue, I’ve been at it for a while and I’m not making much headway. Thanks in advance.

    • Have you tried the notifications as suggested?
      Otherwise you can always override the setDisplayFrame method and check which sprite frame was set, and if it matches the one that should send a message, send a message. 😉

      • George says:

        Yes, I have tried the notifications but I was having issues with:

        1. define my nsdictionary for accessing 3rd frame
        2. linking the nsdictionary to the selector in addObserver

        Basically I’ve not been able to get beyond the code I posted in the in the question.
        I think overriding the setDisplayFrame method could be a simpler approach. How can I do this?

  2. Getzuma says:

    Hi,

    nice tutorial.. I’ve been wondering this too long, and now you have done this. And it looks good! But the only problem to me is that it’s written in Objective-C (somehow I understand it but there’s many things different compared to C++, and my mind just goes apepoop) could you somehow provide that chain shape generation and the contour tracing in C++? =) I would be very grateful for such thing. :)

  3. synth says:

    Hi!

    First of all, thanks for the explanation! I find it a bit difficult to understand, because you explain only in parts.

    Just to make sure I got it correctly:

    1. Use Moore to detect outer block of “block bunches”. Many of those outer blocks go to a segment. Many segemts go to the ContourMap
    2. –>Loop through Segments in the ContourMap
    3. —–> Loop through Blocks in those segments, get all vertices, bundle each 8 of them to a ChainShape, put many ChainShapes to a
    4. Magic happens in Box2D as it “unclutters” (kind of) random polygons and creates a clean outer shape with as few vertices as possible?

    Did I understood 4 right? Because I didn’t find a solution to obtain a polygon-shape out of the pox shape.

    Best,
    synth