Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more

Tech

The Hazards Of Precise Collision Detection

Posted by Mark Alexander on 27 December 2013

Over the years working with GameMaker it's become clear that the general way people do collisions is pretty slow when it comes to performance. This isn't to say that you can't do fast collisions in GameMaker Studio 2, it's just that with the way some commonly used examples are written, it's no wonder some people find them slow and performance heavy at times. So in this tech blog we'll describe an alternative way to do collisions.

To start with we're going to look at the so-called "precise collisions". We don't recommend this method of collision detection for a reason, which we'll outline in a moment. Before we do that, however, let's discuss exactly what precise collisions are.


Precise Collisions

So , to start with, what exactly does "precise collisions" mean? Well, simply put, when enabled it'll use the actual pixel data in images to collide with other pixel data so that you only get a collision when pixels "touch".

Circle Collision Example

Looking at the above image of 2 circles, you can see their bounding boxes collide, but the pixels of the circles don't. What this means is that if you used a simple bounding box collision system, then it would have triggered a collision event, while using a precise collision wouldn't. Now, this may seem like a really obvious choice, if you use precise collisions, your getting a collision event only when they actually collide. However... what does GameMaker Studio 2 have to do to determine that 2 random bitmaps have touched? Remember these shapes can be anything, not just circles...

Well, first GameMaker has to loop through all instances of both these objects to find collisions with them. It does this essentially by having 2 loops like this (this is greatly simplified, as more goes on under the hood, but it gets the idea across):

for (i = 0; i < Obj1_Instance_Count; ++i;) 
    {
    for (j=0; j < Obj2_Instance_Count; ++j;)
        {
        Test_Collisions(i, 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 processor time. So, once we have two instances that we need to test, what does Test_Collisions() actually do? Well, the 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, essentially:

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 bounding box collisions, then we'd be done and a collision event would be thrown (or not). However, because we want precise collisions, it gets more complex than that.

Close Up Per-Pixel View Example

Consider the above image. The collision system has worked out the overlap between collision boxes, and now each pixel in the sprite can be treated as either true or false depending on whether it has a colour or not. This basically means that if it's not the background colour (in this case, white), then there is a pixel there. So the image shown can be represented as two overlapping arrays - one holding the blue circle pixels, and the other holding the red circle pixels. We can then loop through the this section and see if we ever read 2 pixels from the same position

Here is just a small section of code for the bitmap to bitmap collision detection:

for (var i = l; i <= r; i++)
    {
        for (var j = t; j <= b; j++)
        {
            var xx = Math.floor(((cc1 * (i - _x1) + ss1 * (j - _y1)) * _scale1x + this.xOrigin));
            var yy = Math.floor(((cc1 * (j - _y1) - ss1 * (i - _x1)) * _scale1y + this.yOrigin));
            if ((xx < 0) || (xx >= this.width)) continue;
            if ((yy < 0) || (yy >= this.height)) continue;

            if (this.maskcreated)
            {
                if (!this.colmask[_img1][xx + (yy * this.width)]) continue;
            }

            xx = Math.floor(((cc2 * (i - _x2) + ss2 * (j - _y2)) * _scale2x + _pSpr.xOrigin));
            yy = Math.floor(((cc2 * (j - _y2) - ss2 * (i - _x2)) * _scale2y + _pSpr.yOrigin));
            if ((xx < 0) || (xx >= _pSpr.width)) continue;
            if ((yy < 0) || (yy >= _pSpr.height)) continue;

            if (_pSpr.maskcreated)
            {
                if (!_pSpr.colmask[_img2][xx + (yy * _pSpr.width)]) continue;
            }
            return true;
        }
    }

Although this code is relatively simple to understand, you can see this isn't going to be quick to run! Even though it's been narrowed down to just the overlapping bounding boxes, it's still having to loop through the whole area before deciding that there is no collision, and if you have many of these, then it's going to bring the device running the game to it's knees...

Now, it's true that on very rare occasions you may want precise collision checking; like in "Lemmings" for walking on the background, or in "They Need to Be Fed" to walk around shapes, but usually this can be done in different ways. Lemmings - for example - never actually does full sprite to background collision checking, and in fact all it does is test a single pixel at the feet of a lemming, against the mask (background) sprite. You could do that directly in GML if you wanted to, just using collision_point(), or, more efficiently,converting the play area into a bit mask array and then checking that for collisions.


Other Collision Methods

But what about most games? Shooters and platformers and RPGs etc...? These should never use precise collision detection, as there is simply no need. First, when you use precise collision detection, there is no room for error on behalf of the player - everything must be perfect! The can't stray even a pixel into an enemy or background block otherwise they'll take a hit or be "stuck". From a gaming perspective, this is horrible, and there should always be a little room for error as players simply aren't that precise when controlling games. Joysticks/keys aren't good enough, and our judgement and reactions aren't nearly good enough either. So this means players end up either being over cautious and not getting near enemies and background elements, or they simply get frustrated and give up.

So whats the best solution? Generally, just stick to box or radial collisions. Both these methods are fast and simple to implement, and when you use things like buckets to gather objects together, you can also cut down on what you have to check in the first place! "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 completely "contained" within an enemy, this helps avoid cases where players die without ever touching enemies 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 below, the yellow box is well within the player, but it's also more than enough to get killed, by enemies or bullets.

Bounding Box Inside Player Sprite

There's also no rule saying this is the bounding box you would have to use to collide with the background, and the so chances are you'll have something that doesn't let to player get too far inside any background objects like walls. The thing to keep in mind is that whatever looks and feels nice is all you need - if the player gun goes into the wall a little, it doesn't really matter!


Simple Bounding Box Collisions

You can optimise bounding box collisions further using some simple maths. Consider the following image:

Simplified Bounding Box Collisions

Here you have each collision mask with a bounding box center (origin) and the edges defined as half width half height from the center. So, in this case, you can see the 1/2 width and 1/2 heights are 16x32 and 20x20, while the distance to the centers are 25x35. So how do I quickly work out if there's a collision?

This is pretty simple and we'll explain how to do it for the X axis only as once you grasp how it works, you can easily adapt it for the Y axis. You're going to need to subtract the two X coordinates of the instances in the collision to get the distance between bounding box centers (in this case 25 pixels), and if that distance is less than both half-widths added together, (16px + 20px) then we have a collision! What this means is that you can now do a collision check on the given axis with only a single if check.

So for a simple bounding box check, this is probably the quickest way, and you can see the code below is nice and simple (although it does depend on you having the origin of the bounding box always at the center, but this is a minor inconvenience considering the speed gains it gives):

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

While the above is fine for standard sprite-to-sprite collision, what about sprite to background? Well, GameMaker Studio 2 has a function move_outside_solid() which is often used for collisions with "walls" or "platforms", but it's a far from perfect solution, and when you have precise collisions enabled, this function it will sit in a loop doing collision checks over and over as it slowly moves the instance outside of whatever collisions have occurred. This is pretty horrible, particularly if you have look back at whats involved in doing even a single "precise" collision check. There are alternatives though...


Tilemap Collisions

For tilemap style backgrounds, you can use the GameMaker Studio 2 tilemap functions, as outlined in this article by Brendan Wayland:

You can also "roll your own" collision system using some clever bit-wise maths if you use tiles that are a power of 2 (8, 16, 32 etc...) . For example, If I collide with a 32x32 tile at (64, 32), and my 32x32 instance coordinate is (56,12) - so it's overlapping by (24,12) - then all you need to do to move the instance OUT of collision, is bitwise AND it with $$FFFFFFE0. This removes the lower "fraction" bits, just like doing:

x = x - (x % 32);

Summary

Even if you are going to keep the using the built in collision system GameMaker currently uses, it is obviously much quicker to not using "precise" collisions, but still slower than a "pro" programmer would use. However, on a modern PC GameMaker Studio 2 is pretty quick for 2D games, especially compared to previous iterations of the product. However, because of the fairly simple functions built into GML, it's very easy to abuse them, and think there's nothing wrong with your code... BUT, being a good programmer is all about knowing the code that's being run, even if it's not yours! So now you know a bit more about what GameMaker does to deal with collisions, and hopefully we've shown you some extra coding tools to create your own collision system that suits the game you are making while being the most efficient possible.

Back to Top