Shape collision detecten thats easy on the CPU

Member
Posts: 22
Joined: 2008.10
Post: #1
Hi!

I'm developing a platformer for the iPhone and I would really like for my game to have a level design that allows lots shapes rather than just squares, like this:
[Image: d11614dd66f037aa4dc2b767c988aa42.png]

All i want is to be able to run jump and run up/down hill, no fancy physics or anything.

This is what i thougt of:

The hit map is a 2d array concisting of bools, where true means ground and false means air. Maybe i could lower the resolution of this hit map to half of the resolution of the screen to save memory? Then i take the four corners of the object and check the array at the corresponding coords if that specific "pixel" is "ground". If so, a collision is detected.

Is this a good way to do it or is there a better way?
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #2
It's a decent start. What you are describing is similar to using signed distance fields (SDF) for collision detection. With SDF instead of an array of bools, you store an array of floats. The float specifies how far in or out of the surface you are. By sampling all the locations around the sample point you can figure out which direction and how far you need to push to get the point out of the SDF. Pretty easy and fast. The hard part of course is generating the SDF values, though it's easy enough to brute force it, and you only have to do it once so this is not a huge deal.

The drawbacks of SDFs are that they can require a large amount of memory and that you need to sample more than just the corners of an object to make sure that you didn't miss any small shapes from passing through an edge on your box.

To be clear, an array of bools will only get you as far as collision detection, but you would still need to figure out a collision response. Making the two work together is often the tricky part and SDFs can give you both.

As a shameless plug, I will also mention my open source physics library, Chipmunk, and it's main competition Box2D as being good choices as well. They will provide you with more than just collision detection if you decide you want it.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 22
Joined: 2008.10
Post: #3
Ah that sounds pretty smart! Smile

What i had in mind with the bool table was to just backtrack the object pixel by pixel until it was in the clear. Would that be to heavy on the CPU? Like you say, SDF:s sounds like a big load on the memory. So will the big memory usage compensate fpr the less CPU load you think?

I've stumbeled upon some physics engines that seemed intereseting, but it seemed like overkill to just use them for collision detecting. Does theese libraries scale or will they use up unnecessary CPU if i just use them for simple collision detection? Dont know much about physics engines :/

Thanks!
Quote this message in a reply
Member
Posts: 260
Joined: 2005.05
Post: #4
If your ground is as smooth as the one you show, maybe a spline representation would be simple and compact? Or even a simple function of x?
Quote this message in a reply
Member
Posts: 59
Joined: 2007.12
Post: #5
Maybe you can express the ground as a polygon (a bunch of line segments). It's rather easy (and well documented), and with some pruning it should be fast enough. Also collision response becomes a lot easier.
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #6
Quote:What i had in mind with the bool table was to just backtrack the object pixel by pixel until it was in the clear

That wouldn't work well, if a character was running from the left to the right entering that bump would make him backtrack back to the left (not up as is more natural)

For smooth curves like that one look into bezier curves.

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Hog
Member
Posts: 151
Joined: 2002.09
Post: #7
if you don't have overhangs you can just do basic heightmap collision.
Quote this message in a reply
Member
Posts: 22
Joined: 2008.10
Post: #8
Najdorf: Yea, i'll check if the space slighly above the object is in the clear first to compensate for that Smile

Well the smoothness of the hitarea isn't that critical, as long as the graphics are smooth i dont think you can tell if the object sinks down in the ground a pixel or two so a beizer will be a little over the top i think. I'll defenatley check out polygons!

Thanks!
Quote this message in a reply
Apprentice
Posts: 12
Joined: 2008.11
Post: #9
You might have already thought of this, but if the collision detection required is as simple as detecting a floor position, you could always store away the Y position of each X position (or slices of 3 or 4 pixels width) in an array, and then look them up when needed.

I used this approach for a little app I wrote which had a little boat bobbing up and down on a stormy sea. Worked like a charm.

D.
Quote this message in a reply
Member
Posts: 22
Joined: 2008.10
Post: #10
That's really clever! Im currenly looking into Chipmunk as i got a few ideas of taking advantage of the physics to make my game cooler Smile Thanks everyone!
Quote this message in a reply
Member
Posts: 22
Joined: 2008.10
Post: #11
Well I've run into some problems with the Chipmunk framework, might aswel continue here Smile
I copied the moon buggy example into my iphone project and it compiles and everything but it dies upon collision :/ I've not madeany graphic representation but i printed out the y pos of the "chassi" so i can see that it falls. Then suddenly the app dies and i get mumbo jumbo debug info. By printing out messages throught my application I tracked the error to a function called:
cpHashSetEach, but cant find where this function is declared in the framework!

Anyone has any idea of where to look? And is there a way to get xcode to print out some debugging info? I really dont get the debugger in xcode.

Thanks in advance! (sorry for typos and bad language, my movie is about to start Wink
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #12
I'll look into this tomorrow as it came up somewhere else today too. I haven't looked at the Moon Buggy code in ages, so it's entirely possible that it's broken.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 22
Joined: 2008.10
Post: #13
The moon buggy works fine in the c-project though. I use the cocos2d framework for iPhone and got Chipmunk along with it, maybe i should try downloading the source from your site? Let me know it you want to look at my files or something! Appreciate your help!
Quote this message in a reply
Member
Posts: 22
Joined: 2008.10
Post: #14
If it could be to any help, I created a brand new cocoa app-project and downloaded the source fresh and copyed the moonbuggy code and now when the app terminates it highlights this line: (cCollision.c:338)

collisionFunc cfunc = colfuncs[a->klass->type + b->klass->type*CP_NUM_SHAPES];

Hope it helps!
Quote this message in a reply
Member
Posts: 22
Joined: 2008.10
Post: #15
Skorche: No luck figuring this out?
Quote this message in a reply
Post Reply