0
\$\begingroup\$

I read many variants today and get some knowledge in general, so here is a steps of mine thoughts in pictures (horrible paint.net ones).

We need to develop grid system, so we check only thing near, perform simple check to cut out deep check, and at - last deep check like per-pixel collision check.

  1. Step 1 - Let p1, p2 are some sprites lets first just check with circle collision - because large distance between p1, p2 this fails and of course so we don't need test more deeply. But if we have not 2, but 20 objects, why we need to even circle test something so far outside of our view.

  2. Step 2 - Add basic column system, now we don't bother with p2 if it's in a column far from p1 column, so we even don't do circle test. But p3 is in the same col, so let do circle test, which of course will fail.

  3. Step 3 - Lets improve column system to the grid system with grid cell size just like p1, p2, p3 collision boxes, so we cut out things much top or below p1. And this is all great until comes BIG OBJs which is some kind of platforms. They are much bigger then grid cell.

enter image description here

Circle test for will be successful, but deep check for whole big obj will fail

And that the part I can't get.

How do I store the grid position of big object? Like 4 grid coords for big object vertexes? And if one of them close to p1 do circle check for centre of big object then a deep one if succeed? Am I do it wrong?

My possible solution:

enter image description here

\$\endgroup\$
1
  • \$\begingroup\$ your solution link is broken \$\endgroup\$
    – Jimmy
    Commented Jul 9, 2012 at 19:29

4 Answers 4

Reset to default
2
\$\begingroup\$

Personally, I think you should do away with the grid system. Since you have all circles, you should add the radii of two circles together. If the distance between two circle's center points is equal to or less than the radii calculation, you have a collision.

Other option for keeping a grid system: Instead of checking to see if another object (such as P3) is in the same row and column as your current object (P1), you should check if P3 lies within P1's grid(s) position(s) and also check to see if P3 lies within neighboring grid positions to P1, or positions surrounding them. Then if it's in the same row/column or in a neighboring one, you could check for circle collision. This all depends on how you setup your rectangles for your objects. Many people actually put their rectangles outside of the object rather than inside so that the whole circle (plus a small amount of surrounding area) will collide. This will not always result in a perfect collision, but could give you a more desirable result since other objects won't be inside your object.

\$\endgroup\$
0
\$\begingroup\$

This collision implementation seems backwards, in all honesty, but maybe you may have specific reasons for it.

Is there any particular reason why your first pass is to check if circles are touching? As far as I know, finding collisions between circles can be taxing because of the use of square roots.

Instead, you could use a bounding box for every object on the grid. The box dimensions are dictated by the greatest x and y dimension of an arbitrarily-oriented object.

During every frame, you check to see if there are any collisions between the bounding boxes (which shouldn't be too bad performance and complexity-wise). If there is a collision, you then perform a sub-check of two objects in question and see if the ACTUAL objects are colliding.

\$\endgroup\$
2
  • \$\begingroup\$ You don't need to take the square roots.. you can compare squared lengths. Circle vs. circle tests are about even with AABB tests when it comes to performance (even slightly faster). But generally it's best to chose the shape that closely encompasses the majority of the shapes you use in the game.. so if you have lots of rectangular objects, it's more efficient to use AABB tests instead of circle vs. circle, because it will trigger a in-depth collision test much less frequently... \$\endgroup\$
    – bummzack
    Commented Jul 9, 2012 at 21:55
  • \$\begingroup\$ Thanks for the info. I forgot about the distance squared comparison. However, this problem set, according to what you're saying, could still benefit from a conversion to AABB because the majority of the shapes seem to be rectangles. \$\endgroup\$
    – SWPhantom
    Commented Jul 9, 2012 at 22:43
0
\$\begingroup\$

You should take a look at quad trees. Its a common datastructure to store spatial data in cells. When you do the collision testing, you simply test against the objects in the same cell... I use the same datastructure for rendering. I pass the rect that defines the viewport into a selection method of the tree and receive a list of cells. Now i just have to render all sprites from those nodes...

When the object spans over multiple cells ,you can add it to both cells. Just make sure to remove the duplicates ,when you use the results from the selection method. I'm currently on my phone, so I have no code examples here ,but a quick google for quadtree should help.

\$\endgroup\$
0
\$\begingroup\$

Big or small, if an object exceeds one pixel it could show up in multiple grid squares. You have to put it in multiple lists.

\$\endgroup\$

You must log in to answer this question.