Bounding Box Collision Detection

Bounding Box Collision Detection

Kitikonti553

Member #9,556

February 2008

I am totally lost on this topic. Could someone please explain to me exactly how this is done? Ive seen algorithms, but im clueless as to how they work.

ixilom

Member #7,167

April 2006

Basically you treat your sprites as rectangles and you check the coordinates and size to see if they intersect eachother or not.
Sorry if thats too vague, I'm pretty much still sleeping as I just got to work 8-)

___________________________________________
Democracy in Sweden? Not since 2008-Jun-18.
<someone> The lesbians next door bought me a rolex for my birthday.
<someone> I think they misunderstood when I said I wanna watch...

Neil Black

Member #7,867

October 2006

You just give each collidable object a bounding box, which is a rectangle that is just large enough for the object to fit inside. Then you run a check to see if any bounding boxes collide with each other. Consider this code:

1// Player is an object that contains an integer x and an integer y that
2// store the player's position
3 
4// Wall is an object that contains an integer x and an integer y that
5// store the wall's position
6 
7// note that both the player and the wall are size 32 pixels by 32 pixels
8 
9if(Player.x >= wall.x && Player.x <= wall.x + 32) // if the player's x position is
10                                                  // inside the wall's x position
11{
12   if(Player.y >= wall.y && Player.y <= wall.y + 32) // run the same check for the
13                                                     // y coordinate.
14   {
15      return true;
16   }
17}
18 
19// this checks collision for the upper left corner of the player object,
20// you also need to check the other three corners of the player object,
21// which are (Player.x, Player.y + 32), (Player.x + 32, Player.y), and
22// (Player.x + 32, Player.y + 32)

Note that this method only works with bounding boxes that are the same size. I had a problem in programming class that dealt with differently sized rectangles, and the only method I found for solving it was very inefficient. Basically I checked every single pixel in one rectangle to see if it collided with the other rectangle. Not something I would recommend trying in a game because of speed issues. I would be very interested in learning a fast way of checking collision of two differently sized rectangles.

Edgar Reynaldo

Major Reynaldo

May 2007

For each dimension of each box check whether it's endpoints are contained on the line segment of the other box. If any of the 4 checks per dimension are true it overlaps on that dimension. If this is true for all dimensions, the rectangles overlap. This will work for rectangles of different sizes as well and accounts for cases where the larger rectangle completely overlaps the other.

Alternatively check whether the left edge of r2 is less than or equal to the right edge of r1 and the right edge of r2 is greater than or equal to the left edge of r1. As long as they're both true , it overlaps on the x dimension. Perform a similar check for the other dimensions. If they overlap on all dimensions then they are occupying at least some of the same space. This will work for objects of differing size as well.

Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide
King Piccolo will make it so Then I could just flip it with some sweet, sweet matrix math. In either case, I’ll ride this wagon until the wheels fall off. Thanks to those that keep it running

Kitikonti553

Member #9,556

February 2008

Thank you replying. I think Im getting it now; except for your code Neil Black, when i tried using that method, my boxes kept getting sucked to the bottom right corner of my screen o.e

moon_rabbits

Member #8,469

March 2007

struct Box{
  int x, y, w, h; // position and size (width, height)
};

Box box1, box2; 

bool BoundingBoxCheck()
{
   if(box1.x > (box2.x+box2.w)) return false; // box1 is too far right, no collision
   else if((box1.x+box1.w) < box2.x) return false; // box1 is too far left, no collision
   else if(box1.y > (box2.y+box2.h)) return false; // box1 is too far down, no collision
   else if((box1.y+box1.h) < box2.y) return false; // box1 is too far up, no collision
   else return true; // there is a collision
}

This is a basic bounding box check. If any of the if statements are satisfied, then there is no way the boxes can be overlapping because they are too far left, right, up, down, etc. If none of them are, that means there is an overlap somewhere.

This can be easily implemented with BITMAPs in allegro, and it works with differently sized bounding boxes. Unfortunately, it's not as precise with certain sprites with a lot of "magic pink" in them. Further, it doesn't detect where the collision happened, only that it did. Although I'm sure it wouldn't be too hard to add that to the code.

Neil Black

Member #7,867

October 2006

Quote:

For each dimension of each box check whether it's endpoints are contained on the line segment of the other box.

I don't understand how this works. It seems like there could be overlaps that would be missed.

Edgar Reynaldo

Major Reynaldo

May 2007

594871 594872

If any endpoint of either line is within the boundaries of the other line then they have to be overlapping in that dimension. However , the algorithm moon_rabbits put up is much faster and just as accurate for checking overlaps. I always seem to take the long way 'round somehow.

~~Edit~~
Added picture where one line's endpoints both exceed the endpoints of the other line. Which both algorithms work for.

Paul whoknows

Member #5,081

September 2004

This is what I use:

inline bool collide(int x1, int y1, int x2, int y2, int xx1, int yy1, int xx2, int yy2)
{
     if (x2 <= xx1) return false;
     else if (x1 >= xx2) return false;
     else if (y2 <= yy1) return false;
     else if (y1 >= yy2) return false;
     else return true;
}

____

"The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner.

Neil Black

Member #7,867

October 2006

Quote:

If any endpoint of either line is within the boundaries of the other line then they have to be overlapping in that dimension.

That's what I took your second method to mean, which I understood perfectly. The first one is the one I was having trouble with.

Edgar Reynaldo

Major Reynaldo

May 2007

Same thing really , just checking for it in different ways.
The second method takes one to two inequality checks per dimension and is just the inverse of what moon_rabbits and Paul whoknows posted while the first method has anywhere from 2 to 8 inequality checks per dimension which is wasteful.

Neil Black

Member #7,867

October 2006

The way you worded the first one confused me. I get it now.

Neil Walker

Member #210

April 2000

#define check_bb_collision(x1,y1,w1,h1,x2,y2,w2,h2) (!( ((x1)>=(x2)+(w2)) || ((x2)>=(x1)+(w1)) || ((y1)>=(y2)+(h2)) 
|| ((y2)>=(y1)+(h1)) ))

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

Paul whoknows

Member #5,081

September 2004

Neil, that's nice! but which one is faster? yours or my "inlined" version? I am not sure

____

"The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner.

Neil Walker

Member #210

April 2000

There's only one way to find out... FIGHT!!!!

(apologies for the Harry Hill there, it just slipped out.)

But who knows, There probably isn't much difference (unless the compiler decides not to inline your function) between the inline and define, but I don't know how the compiler will optimise your comparison against mine, which is slightly different.

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

someone972

Member #7,719

August 2006

If you want a function that allows you to project the object out, you can use the one I made for mrukki. It has an okay explanation and may not be very efficient, but it works.

EDIT: Link fixed (Thanks Neil Black.)

______________________________________
As long as it remains classified how long it took me to make I'll be deemed a computer game genius. - William Labbett
Theory is when you know something, but it doesn't work. Practice is when something works, but you don't know why. Programmers combine theory and practice: Nothing works and they don't know why. -Unknown
I have recklessly set in motion a chain of events with the potential to so-drastically change the path of my life that I can only find it to be beautifully frightening.

Neil Black

Member #7,867

October 2006

Quote:

(I don't know how to link to a post)

Click the part that says "Posted on 04/02/2008 6:01 PM" (or whatever the date and time are) on the post you want to line to. The url in your address bar will be a direct link to that post.