Jump to content
  • Advertisement
Sign in to follow this  
chbrules

2D Collision Detection Theory

This topic is 4776 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was reading over any material I could find (some of the articles here too) on 2D collision detection. I understand to check the bounds of the bounding boxes and such, but my question is more along the lines of how to impliment this. How do I check over all these entities I have on the screen. Sure it's fine if you had 2 things on the screen, but what if I have like 50 or 100 things moving around needing to be checked? How do I tell the engine to do this effiently? I always seem to have trouble estimating the power of the computer, maybe I'm not thinking right. Do I have to check each entity against every other entity each loop? As well, I have a grid system for my maps that are 32x32px squares which are 1 unit. The player moves on a per-pixel basis though, so I can't just check easily who's occupying which square, they could be on 4 at once. Also, I have a clipping scheme to tell the engine if a certain unit can be walked on or not. Say I wanted a wall in the map, you shouldn't be able to pass through it of course. So I need to check against enemies, items on the ground in certain map unit coords, and the map's clipping map (2d array). Any ideas how I can efficiently impliment this as not to drain CPUs of their power? =/ FYI this is C++/SDL.

Share this post


Link to post
Share on other sites
Advertisement
There are a number of things you can do, depending on the amount of work you want to invest and the amount of optimization you want to achieve. The most basic step is just computing all possible collisions each frame, thus O(n^2) checks. With 100 objects this is still not very expensive, given that the individual checks are not very heavy.

Next, you could consider to check only in case some object move. You will gain the cost of computing collisions between static objects each frame. On the other hand, you might gain some double checks in case multiple objects move at the same time.

If you want more efficiency, you could create a spatial organisation of your scene. That is to say, you can store more information about the layout and then exploit it to improve efficiency. In its most basic form, you could keep with each entity the square it is in (and if this is not unique as you said, you could store which square it is mostly in or a list of squares it is in). This will limit collision checks for that entity to its square, or its square and the surrounding eight squares. You might even go further and use a global spatial organisation like a quadtree to do more efficient checking, but I think this will be overkill.

Greetz,

Illco

Share this post


Link to post
Share on other sites
Since you already have a map layout in place, you can record the objects occupying each tile of the map, and store these into a list, for each tiles. Objects could occupy several tiles, so they could be referenced in several places.

Then to check collisions for one object, go through the list of tiles it occupies and test collisions with other objects that also occupy the tile.

You also have to remember to avoid testing objects several times per frame, since two objects could potentially occupy two (or more) similar tiles. YOU can do that by inserting unique references objects into one list, and then test collisions by building up a list of potential colliders (referenced only once), and testing collisions with each of the potential colliders.


// insert object into map.
// - check the tiles overlapped by the object.
// - each of these tiles will haev a reference to the object
// - object will also store the list of tiles overlapped.
for(int i = 0; i < NumObjects; i ++)
{
Object.InsertIntoMap(Map);
}

// Check collisions for each object
for(int i = 0; i < NumObjects; i ++)
{
Objects.TextCollisions(Map);
}


void CObject::TestCollision(CMAp& Map)
{
// list of unique references of objects that overlaps the same
// tiles as our object.
CLinkedList<CObject*> m_lPotentialColliders;

// build list
for(int i = 0; i < m_lOverlappedTiles.Size(); i ++)
{
for(int j = 0; j < m_lOverlappedTiles.m_lOverlappingObjects.Size(); j ++)
{
CObject* pxObject = m_lOverlappedTiles.m_lOverlappingObjects[j];

// avoid ourselves. and see if we are already in the list
if (pxObject != this && !m_lPotentialColliders.Find(pxObject))
{
// add reference into the list.
m_lPotentialColliders.Insert(pxObject);
}
}
}

// test collsions with potential colliders one by one
for(int i = 0; i < m_lPotentialColliders.Size(); i ++)
{
TestCollisions(*m_lPotentialColliders);
}
}






That would be one way of doing it. It should be quite fast, since the lists in question will be very small. They will probably contain a reference to the terrain map and static objects (wall, paths, trees), references to players and NPC, projectiles, ... So list should not exceed 8 objects per tile in practical terms, and average 2-4.

try to avoid new/deletes for list nodes, and use pools of nodes. will be much faster. Also, when an object moves across the map, he is likely to move to a neighbouring tile, there are some optimisations to be done displacing objects on the map.

for AddUnique() function in the potential colliders list, it would be faster to sort the list (insertion sort) so you can check if an objects has been added already or not more quickly. However, the list are so small, it's probably not worth the hassle.

there is another method called sweep-and-prune, but it;s another story.

Oh, And I forget, still the same method, but instead of using a list of potential colliders, using timestamps to only test objects once. It would be faster (no sorting, no searching). But it's got shortcomings too.

Share this post


Link to post
Share on other sites
>_>

The complicated theory. =(

Well I guess I'll just have to keep at this and see what I'll get then. Thanks guys.

Share this post


Link to post
Share on other sites
Heres a real easy way to do things.

You find everything thats moving, and you test them against everything that can be collided against.

you can also try duel collision checks.

Ones a circle-Circle test.
The other is your pixel perfect test. (which is more expencive).

For the Circle-Circle test, you find the distance between the two objects, squared. (so instead of the usual sqr(x*x + y*y) you just have x*x + y*y.

you then check that against the sum of the two collision radii squared.

So, if you can collide with anything less then 20units away, and the other thing can collide with anything less then 10 units away, then

you find the manhatten distance between you:
xd = abs(x1 - x2);
yd = abs(y1 - y2);
man = xd*xd + yd*yd;

And you find the sum of the two collision radii squared.

csum = col1 + col2;
csum *= csum;
if (man < csum) {
//Test for pixel perfect collision.
}

You can also have a few other things, like a quad tree.
But they can be pretty hard.

Also note: This doesn't need any sqrts at all for this test :-)

Link for you

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by chbrules
>_>

The complicated theory. =(

Well I guess I'll just have to keep at this and see what I'll get then. Thanks guys.


well, if you are asking for ways of doing things faster than testing everything against everything, there isn't any easy way.

either you test everything against everything, and do a quick rejection test, or you need to organise your objects to limit the number of tests, and that involves varying amounts of pain. The gridbase approach is all right for grid-based games, like 2D shooters and whatnot. For a more general approach, sweep and prune, but that's slightly more complicated.

BTW, testing everything against everything is


for(int i = 0; i < Objects.Size(); i ++)
{
for(int j = i+1; j < Objects.Size(); j ++)
{
TestCollision(Objects, Objects[j]);
}
}


Share this post


Link to post
Share on other sites
Heres a dead simple collision detection algorithm. (o(n) where n is the number of moving objects. Probably < 10.)

Per object, you store a pointer to an object to the left, and to the right of them. (left being on the x axis.) as well as the object to the top of it.

Now, when doing collision detection (ONLY ON MOVING OBJECTS. this gives you really fast times), you do the following:

For object o to be tested.

find o.x - o.leftobject.x

if that is negitive (when x gets larger as you go left) then you have passed that object.

o.leftobject = o.leftobject.leftobject
o.leftobject.right = o

do the same with the right.

find o.x - o.rightobject.x
If thats positive (ie. your more right then your right object), then do basically the same thing as the above.

Also note: You need ends to your levels when your doing this.
Basically an object that goes from 0y to the sky at either end of your map.

You do a similar thing for the y axis.

Now, you have the 4 amounts (precalculated).

You then check if there under the thresholds.
If they all are, then you have collided with the object.

There you have it :-)

Edit: Mind-Typo
From,
Nice coder

[Edited by - Nice Coder on April 25, 2005 8:03:22 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!