gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Fast collision detection algorithm?

#4713 - Alunze - Mon Apr 07, 2003 9:29 pm

I was wondering, what fast algorithms do you know to detect if two rectangle-shaped collision boxes have collided?

Thanks in *Advance* >_6

#4715 - tepples - Mon Apr 07, 2003 9:52 pm

Alunze wrote:
what fast algorithms do you know to detect if two rectangle-shaped collision boxes have collided?

Are you talking about testing one rectangle against another rectangle, or are you talking about searching a long list of rectangles for any pair that overlaps?

The former is easy. Given top1 < bottom1, left1 < right1, top2 < bottom2, left2 < right2:

if(top1 >= bottom2 || top2 >= bottom1 || left1 >= right2 || left2 >= right1)
no collision
else
collision

The latter is theoretically O(n^2) and requires all sorts of tricks (such as the "sector method") to keep the constant factor down.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#4721 - Alunze - Mon Apr 07, 2003 10:46 pm

Ok. I was referring to the former, thanks for the tip :D.

#4724 - sgeos - Mon Apr 07, 2003 11:12 pm

I see how that works. How does one find the area of overlap?

-Brendan

#4726 - Malefactor - Mon Apr 07, 2003 11:33 pm

First you have to figure out which one is lower and rightmost
if sprite 2 is lower AND rightmost it would be

(top1 + height1 - top2) * (left1 + width1 - left2)

its a simple length times width equation, you just have to find the lenght and width of the part that's overlapping first.

if they had the same width and are at the same x postion you only need to find the lenght of overlap, so it would be

(top1 + height1 - top2) * width

Just out of curiosity, why do you need the area?
_________________
[Images not permitted - Click here to view it]

#4728 - sgeos - Tue Apr 08, 2003 12:02 am

[quote="Malefactor"]Just out of curiosity, why do you need the area?[/quote]

Bad wording on my part. I want to define the region of overlap. Then that can be used for collision detection, etc.

-Brendan

#4733 - tepples - Tue Apr 08, 2003 5:23 am

What you want is the intersection of two rectangles.
Code:

if(top1 > top2)
  top1 = top2;
if(left1 > left2)
  left1 = left2;
if(bottom1 < bottom2)
  bottom1 = bottom2;
if(right1 < right2)
  right1 = right2;

Now the intersection, or region of overlap, of the two rectangles is in top1, left1, bottom1, right1.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#4996 - HuangYZ - Thu Apr 17, 2003 2:12 am

here is my code,I think it is faster.

Code:

typedef struct Rect{
int top,bottom,left,right;
}Rect;

bool Collision(Rect rc1,Rect rc2)
{
   if(rc1.right < rc2.left || rc1.left > rc2 .right )
   return FALSE;

   if(rc1.bottom < rc2.top || rc1.top  > rc2 .bottom )
   return FALSE;   
   
   return TRUE;         
}

#5018 - DekuTree64 - Thu Apr 17, 2003 4:23 pm

Yes, that is fast, but it would probably be even faster if you use pointers instead of passing the full Rect. So it would be more like
Code:

bool Collision(Rect *rc1,Rect *rc2)
{
   if(rc1->right < rc2->left || rc1->left > rc2->right )
   return FALSE;

   if(rc1->bottom < rc2->top || rc1->top  > rc2->bottom )
   return FALSE;   
   
   return TRUE;         
}


So in ASM, it would just put the addresses of those 2 rects in r0 and r1, and never even touch the stack. That is, if GCC has any brains whatsoever, which it often doesn't^^

#5032 - sgeos - Thu Apr 17, 2003 11:08 pm

> and never even touch the stack.

Potentially dumb question. What happens when you use all the stack and try to push more onto it?

-Brendan

#5035 - tepples - Thu Apr 17, 2003 11:29 pm

sgeos wrote:
What happens when you use all the stack and try to push more onto it?

You overwrite the global variables in IWRAM and probably crash your program. (This is assuming the default linker setup that puts .data, .bss, and the stack in IWRAM.)
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.