Collision detection...

So I've been very busy doing the HTML5 version of GameMaker, and as I've been adding the collision code, it's becoming clear that the general way folk do collisions in GameMaker is pretty slow. This isn't to say that you can't do fast collisions in GameMaker, just that the way the samples are all written, it's no wonder some people find it painful and slow at times. So I thought I'd describe how I usually do collisions. Fo starters, I've only ever used what GameMaker calls "precise collisions" once in my whole career. And looking back on it, I could have easily gotten away without that as well; experience has it's advantages....

So first... what exactly does "precise collisions" mean? Well, simply put... it's using the pixel data in images to collide with other pixel data so that you only get a collision when actual pixels touch. Looking at the image of 2 circles here, you can see their bounding boxes collide, but the circles don't. What this means is that if you used a simple bounding box collision system, it would have triggered an event, while the precise collision wouldn't. Now, this may seem like a really obvious choice, if you use precise collisions, your getting them when actually happen. However... what does GameMaker have to do to determine that 2 random bitmaps have touched; because remember these shapes can be anything, but just circles.

Well, first... it has to loop through ALL instances of both these objects to find collisions with them. It does this simply by having 2 loops like this..

for( n=0; n<Obj1_Instance_Countl; n++) 
  {
     for( f=0; f<Obj2_Instance_Countl; f++) 
     {
       Test_Collisions( n, j );
     }
  }

Now, if you imagine all the collision events you have going on between different object types, you can see that this will burn up lots of time. One of the changes we'll make as time goes on, is to "bucket" sort instances. This means we'll only check for collisions of objects that are actually close to each other. But we don't do this yet....

So... once we have two instances that we need to test, what does Test_Collisions() actually do? Well, first thing it does is it checks the bounding boxes. This is a simple check and it allows an early out if they aren't even close.

if( bbox1.right < bbox2.left ) exit;
   if( bbox1.bottom < bbox2.top ) exit;
   if( bbox1.left > bbox2.right ) exit;
   if( bbox1.top > bbox2.bottom ) exit;

Now... if we were "just" doing box collisions, we'd be done... and an event would be thrown. However, because we want precise collisions, it gets more complex than that...

Next, the system works out the overlap between collision boxes (as shown in the next image). Now each "pixel" in the sprite can be treated as a TRUE/FALSE, meaning if it's not the background colour (in this case, white), then there IS a pixel there. So the image shown is two overlapping arrays. One holding a BLUE circle, and the other holding a RED circle. We then loop through the appropriate section (slowly) and see if we ever read 2 pixels from the same position. In this case,we don't. So no event has occurred.

Here's some pseudo code for the bitmap to bitmap collision detection...

for( y=YStartPos;y<YEndPos;y++)
  {
    for( x=XStartPos;x<xendpos;x++)
    {
      if(x < xSprite1Start) || (x> xSprite1End ) continue; 
      if(y < ySprite1Start) || (y> ySprite1End ) continue;
      if(x < xSprite2Start) || (x> xSprite2End ) continue;  
      if(y < ySprite2Start) || (y> ySprite2End ) continue;

      if(( CollisionMask1[ x+(y*width)]!=0 ) && ( CollisionMask2[ x+(y*width)]!=0 ) ){
           return TRUE;
      }
    }
  } 
return FALSE; 

Now, although this is simple pseudo code, you can see this isn't going to be quick! Even though it's been narrowed down to the overlapping sections, it's still having to loop through the whole thing before deciding that there is no collision! Now, if you have many of these, it's going to bring the PC to it's knees! Worse still... GameMaker wants you to use precise collisions by default. This is horrible.

Now, it's true that on very RARE occasions you do want precise collision checking; Lemmings walking on the background, or They Need to Be Fed walking around shapes, these are rare cases, and can usually be done different ways. Lemmings never did full sprite to background collision checking, in fact all it did was test a pixel at the feet of a lemming, into the mask. And you could do that directly in GML if you wanted to! In fact, Lemmings had a "1600x160" play area, and you could easily convert this to a 200x160 "BIT" per-pixel mask. This would in turn mean you'd need an array 32,000 bytes long. And that fits nicely! If you didn't want to go that far, you could have 160 arrays, each of 1600 bytes long. then have a controlling array with each of these as a line of the collision. You could then easily check this array in GML using the lemmings X and Y coordinate.

But what about normal games? Shooters and platformers? These should never use precise collision detection, there is simply no need. First, when you use precise collision detection, there is no room for error on the behalf of the player. Everything must be perfect. The can't stray even a pixel into a baddie or background block. From a gaming perspective, this is horrible. There should always be a little room for error, because as humans, we simply aren't that precise when controlling games. Joysticks/keys aren't good enough, and our judgement isn't nearly good enough. So this means players end up either being over cautious and not pushing near baddies/backgrounds; or they simply get frustrated and give up.

So whats the best solution? Well, personally I've always either stuck with box or radial collisions. Both these mehods are fast, and simple to implement, and when you use things like buckets to gether objects together, you can also cut down on what you have to check in the first place! For those that don't know... "buckets", are a simple way of grouping objects/instances together into groups. For collision, we tend to have a grid of buckets and place objects into whatever "bucket" cell they touch. This means if you want to check collisions, you no longer have to check everything to everything... just everything in the surrounding buckets. This is much, much quicker.

So... how do you define a "fair" bounding box? I normally try and create a box that is completly "contained" within an enemy, this helps avoid cases (like the 2 circles above) where players die without ever touching baddies at all. Players are MORE than willing to forgive cases where you run into objects a little, but they are very unforgiving of cases where they die without hitting anything. So, as shown in the player character on the left, the yellow box is well within the player, but it's also more than enough to get killed, by baddies or bullets. Theres also no rule saying this is the bounding box you would use to collide with the background... so chances are you'll have something that doesn't let to player get to far inside the background. Whatever looks and feels nice is all you need; if the gun goes into the background, it doesn't really matter....

Now, while I've said I'd use box or radial, one thing I wouldn't do myself.. is use a bounding box check like the one above. The reason for this is that "IFs" are slow, so if you can minimise them, all the better! So I use a trick that I learnt from Dave Jones when he was doing Blood Money; I use a box center, with a 1/2 width and 1/2 height.

Now remember that these boxes are INSIDE sprites, so they will probably be well inside each other, meaning the player knows his goose is about to be cooked. So, in this case, you can see the 1/2 width and 1/2 heights are 16x32 and 20x20, while the distance to centers are 25x35. So how do I work out theres a collision?

This is pretty simple... so I'll do X, and you'll easily see how Y works. I simply subtract the 2 X coordinates, and this gives the distance between centers (in this case 25 pixels), and if that distance is less than both 1/2 widths added together, (16pix+20pix) then we have a collision! What this does, is lets us do the X check with only 1 IF. Looking at the code below you'll notice abs(), and normally you would have to do an IF in there, but if you're sneeky, can do abs() without an IF.

So for a simple bounding box, this is probably the quickest way, and you can see the code below is nice and simple. In fact, it's fair to say I always prefer having a center and width/height collision, but that may well just be the way my brain works!

   if( (halfwidth1+halfwidth2) < abs(x1-x2) ) exit;
   if( (halfheight1+halfheight2) < abs(y1-y2) ) exit;

Now, while this is fine for standard sprite-2-sprite collision, what about sprite to background? Well, GameMaker has a handy function move_outside_solid(), but when you have precise collisions, it will sit in a loop doing collision checks over and over as it slowly (at whatever "step" speed you've given) until your sprite is move outside of whatever collisions have occured. This is a horrible function, particually if you have look back at whats involved in doing even a single "precise" collision check.

Again, I've never needed this... For "tilemap" style background, I always collide to the tile array, and then move myself out of a background collision. So how do i do that? Well... If you use tiles that are a power of 2 (8, 16, 32 etc...) then it's an easy thing to move to a tile boundary. For example, If I collide with a 32x32 tile at X=64 and Y=32, and my 32x32 instance coordinate is 56,12 ( so it's overlapping by 24,12), then all I need to do to move the instance OUT of collision, is AND it with $$FFFFFFE0. This removes the lower "fraction" bits, just like doing:

   x = x-(x%32);

Now... even if you were to keep the system GameMaker currently uses, it would still be much quicker by not using "precise" collisions, but still slower than a normal "pro" would use. Now, I could go on and on about how to do efficiant collision detection, but really... I should really do a post on each method, and you would then easily see what system was best for you particualr case.. but lets see how much time I have. :)

So final words... Well, GameMaker is often accused of being slow, but in fact, on a modern PC it's a pretty quick system for 2D games. However, because of the fairly nice commands like the complex collision systems it has built in, it's very easy to abuse them, and think theres nothing wrong with your code... however, being a good coder is all about knowing the code thats being run, even if it's not yours! If it's your game, it's your problem, and GameMaker has all the tools you need to make a the game great.