Collision Detection - The best approach to learn

AceBlkwell

All,

I’m looking at learning about collision detection. I've been watching videos and such. While there may be more than two approaches, two were talked about more often than others, pixel perfect and bounding box. Pixel perfect sounds like the better of the two. Is there a preference by Allegro programmers and are they radically different in complexity to learn. Should I learn one to learn the other? Thanks.

DanielH

"Best" is subjective.

In my tile-based games, I've done both pixel-perfect and bounding-box. For most cases, pixel-perfect is <B>overkill</b> and not needed.

If you do a pixel-perfect then create a secondary bitmap mask with pixels set to 0 or 1. if pixel is 1 then solid and check against that.

I've also done approaches where I split a single tile hit-box into multiple boxes and do bounding box on those boxes. For instance I have a 16x16 pixel tile. I an integer mask to split the hit-boxes into 16 4x4 pixel boxes. When I do my check I check the integer mask.

Something like this. (off the top of my head, so may not be exactly correct)

#SelectExpand
  1//these define my tile size. I prefer multiples of two so I can use shifting.
  2bool check_hit(int p, int x, int y, int tile_size, int box_count)
  3{
  const int BOX_SIZE = (TILE_SIZE / BOX_COUNT);
  const int BOX_SHIFT 2
  int m = 1;
  7
  if (p == 0) return false;
  9
  for (int j = 0; j < BOX_SIZE; ++j)
  {
      for (int i = 0; i < BOX_SIZE; ++i)
      {
          // checks if bit set for that box
          // then checks if x and y are in that box
          if ((p & m) && x >= (i << BOX_SHIFT) && x < ((i << BOX_SHIFT) + BOX) && 
                         y >= (j << BOX_SHIFT) && y < ((j << BOX_SHIFT) + BOX))
          {
              return true;
          }
          m <<= 1;
      }
  }
 24
  return false;
 26}

AceBlkwell

Hey Thanks Daniel. I think I'll look at bound boxes first. Just to get an idea of how this works. The reason I thought pixel perfect would be truer to the collision was remembering my old quarter arcade days. Sometimes while playing you would try to get your ship or character to slip through a tight area but it would blow up even though it was visually clear your character hadn't made contact. It was the box the image was held in. Was frustrating.

However, given that no will probably play anything I code, I guess I don't need to be too exact .

Thanks for the example.

DanielH

Yes, it's more accurate, but there is a processing cost. Most games don't care. Bounding box works in most cases.

That being said, nothing wrong with doing it and modern computers are fast enough to handle it no problem. Best way to learn as well.

Try both methods.

Do you know much about physics? I want to make a tile based game where I give my tiles edge planes and test box and circle collisions against those. It's one of those things I want to do just to see if I can do it.

AceBlkwell

You sound like me in that you try stuff just to see if you can. Since my games and what not pale in comparison to modern day stuff, I tend to write for myself. Just to see if I can learn to use a mouse, or have a moving star background etc. To this point, all my games have been, you move, computer moves, you move..etc I've never had simultaneous movement. That's why I'm looking at collision detection.

And no, I didn't fair will with physics in college. Partly, because I'm a little slow and partly because our entry level class was being taught by the dean of the college. but mostly because I'm slow

DanielH

Just remember - pixel access to video bitmaps is slow. Lock bitmaps, do comparison, unlock bitmaps.

LennyLen

Also worth looking into, as it's easy to implement: if you have circular objects, and you know their centre and radius then you can calculate the distance between their centres and if that's less than the sum of the radii then you have a collision.

Edgar Reynaldo

Ace, forget about learning every game programming technique there is. Use the work of others to make your life easier. There are tons of collision libraries out there like Chipmunk, Box2D, and others for simple collisions in 2D. If you try to program everything else you will blink and miss the next 10 years of your life trying to reinvent everything you see out of curiosity. Curiosity killed the cat. Use one of your nine lives to seek out other software libraries that will do the work for you. Then study them and see how they do what they do. It's better than trying to reinvent physics in a computer all by your self.

Godspeed bro.

Edgar 8-)

AceBlkwell

Thanks all for the help,

Edgar, good advice. I think I'm going to take it. At 60, who knows if I'll have 10 more years. Serious, I'll probably investigate how it works just to learn something different, but I'm going to look into the names you suggested for actual
implementation.

Thread #618925. Printed from Allegro.cc