🔒 Locked

collision detection with multiple characters

Started by jimiwa Nov 16, 2004 at 9:37 AM 11 replies 1.4k views

Original Post

Nov 16, 2004 at 9:37 AM

I'm doing a side scrolling game and I was wondering about collision detection. I'm going to have a lot of characters on the screen and I'm going to want to know if they collide with each other. I assume I should make a check collision function in each of my character classes. I want to see if they collide with each other. It would seem troublesome to check each one against each other A.collide(B) A.collide(C) A.collide(D) A.collide(E) A.collide(F) A.collide(G) A.collide(H) A.collide(I) A.collide(J) B.collide(C) B.collide(D) etc.. I would have to call so many collide functions, is there a simpler way to do this?

oliii

Nov 16, 2004 at 9:49 AM

for (int i = 0; i < NumObjects-1; i ++){   for(int j = i+1; j < NumObjects; j ++)   {        ObjectPtr->Collide(ObjectPtr[j]);   }}bool CObject::Collide(CObject* ObjectPtr){  ....  ....}

Ajare

Nov 16, 2004 at 2:49 PM

What Oliii is saying is that no, there isn't a simpler way to do it. You can cut down the number of tests by using space partitioning, but 2d aabb collision detection is so fast that it might actually be slower.

Apocryphiliac

Nov 16, 2004 at 2:59 PM

In most 2D side scrollers, you don't care about enemies off screen so you could check that (which you've probably already done to see if the character should be rendered). Additionally, if you want pixel-perfect collision you might benefit from checking bounding boxes first.

graveyard filla

Nov 16, 2004 at 3:27 PM

a clever trick leavoia showed me, which makes sure you only check each character againt each character a single time. that is check A against B, but not B against A.

 for (int i = 0; i < NumObjects; i ++){   for(int j = 0; j < NumObjects; j ++)   {        if(ObjectPtr > ObjectPtr[j])          continue;        ObjectPtr->Collide(ObjectPtr[j]);   }}

basically you compare the pointer value - since this is guarenteed to be unique, you just do a simple > comparison - this means that A is checked against B, but not vise versa. if you dont have pointers, just use the & sign to get the memory address.

Arcibald Wearlot

Nov 16, 2004 at 3:54 PM

hmm the pointer thinghy seems a bit too tricky to me.. i prefer oliii's way

leiavoia

Nov 16, 2004 at 9:32 PM

Quote:
Original post by Arcibald Wearlot
hmm the pointer thinghy seems a bit too tricky to me.. i prefer oliii's way

The "pointer thinghy" that GF posted is exactly the same as Oliii's except it has a permutation check so you don't check the same collision objects against each other twice in the same go.

kaysik

Nov 16, 2004 at 9:44 PM

Quote:
Original post by graveyard filla
a clever trick leavoia showed me, which makes sure you only check each character againt each character a single time. that is check A against B, but not B against A.

*** Source Snippet Removed ***

There is a much easier way - just start j at i+1

// loop through all items except the very last onefor (int i = 0; i < (NumObjects-1); i++){   // check object i against the remaining items   for(int j = i+1; j < NumObjects; j ++)   {      ObjectPtr->Collide(ObjectPtr[j]);   }}

You gota make sure to deal with both objects in the Collide() function though.

leiavoia

Nov 16, 2004 at 10:10 PM

That works with nice tight loop like that but for more complex systems it may not. My system pulls out lists of objects from quadtree nodes and does checking against those objects like this:

foreach active object:
- get a list of all objects in the quadtree node i occupy
- test collision against them all (one of which is guaranteed to be myself, all the rest may have already tested themselves against myself, but as a lonely object in the world, how am i to know?)

oliii

Nov 17, 2004 at 2:42 AM

There is nothing wrong with the pointer trick (or handle / guid, if you store handles in the objects), which is useful if you have multiple references of an object in your nodes (quadtree, uniform grid, ect...). You may then as well use a colltest counter in each objects to avoid testing the same pairs several times.

If you don't sort your objects, and just store them in a list, the nested loops is the simplest method.

leiavoia

Nov 17, 2004 at 10:37 AM

Quote:
Original post by oliii
You may then as well use a colltest counter in each objects to avoid testing the same pairs several times.

That's what the pointer trick does. "IF (A > B) { FAIL }" will reject not only collisions with myself but also limit collisions to once-per-pair since BA will pass but AB will fail.

oliii

Nov 17, 2004 at 6:13 PM

not necessary.

For example, in a grid, if you have object A covering 4 separate nodes, and B covering 3 nodes, then you can potentially do A against B 3 times, if the three nodes of B are also covered by A.

leiavoia

Nov 17, 2004 at 7:06 PM

I see. I have my quadtree set up so that i do not place objects into multiple nodes (they go in the parent node). I made it that way for specifically that reason. I'm not sure if it's a better or worse solution than having a "collided flag", but it works and i have bigger fish to fry at the moment (like not sliding off &@$#! slopes)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.