Collision detection with a grid

Forums Programming cocos2d support (graphics engine) Collision detection with a grid

This topic contains 3 replies, has 3 voices, and was last updated by  slembcke 2 years, 4 months ago.

Viewing 4 posts - 1 through 4 (of 4 total)
Author Posts
Author Posts
November 27, 2011 at 12:00 pm #237139

FBryant
Participant
@fbryant

Checking if 2 objects are in the same grid cell (before checking proximity) is a great way to improve performance. However it does have a flaw which I’m seeing frequently enough to be annoying:

If 2 small speeding objects are near the edge of a cell, their areas may be colliding but because they’re in different cells the collision won’t be detected.

Does anyone have a simple solution for this? I’ll admit it’s an unlikely occurance but in the style of my game it’s not THAT rare and I don’t want any misses. Thanks!

November 27, 2011 at 12:16 pm #356177

FBryant
Participant
@fbryant

Not sure if its the ideal solution but if anyone’s interested I just checked if the objects were in the same cell OR the cell next door, and just made the grid cells smaller to compensate.

November 27, 2011 at 1:22 pm #356178

Stephen Morris
@stephenmorris

@FBryant What you are looking for, and what you have implemented, was a nearest-neighbour search. When you check each cell, if there are any objects within it check each neighbouring cell. If there is a resulting detection, tag it within an array so you don’t waste cycles recalculating previous collisions.

November 27, 2011 at 4:18 pm #356179

slembcke
Administrator
@slembcke

Check all the cells that the bounding box overlaps. That’s how Chipmunk’s old spatial hash worked. Performance is generally terrific and spatial hashes are relatively easy to code. https://github.com/slembcke/Chipmunk-Physics/blob/master/src/cpSpaceHash.c

Viewing 4 posts - 1 through 4 (of 4 total)

You must be logged in to reply to this topic.