Collision detection Revisited part 2 – Bounding Box much faster


Being kinda bothered with the performance of the bounding box routine I gave out last time, I decided to play around with the performance. What eventually came out of it is a much improved and faster version.

So, a long time ago, Pythagoras came up with a formula to calculate the distance between two objects. The Pythagoras theorem. For those who need to be reminded of it (like I did), the formula is square root (A squared + B squared) = C squared.

Today, I’m going to butcher it. Time to get out the code cleaver.

If we know the center points to two objects and the radius of the objects, we can calculate if the objects touch by knowing if the objects centers subtracted from one another are less than their radius.

You can go through some calculations to find this, the problem with using the Pythagoras theorem is that calculating square root can be computationally expensive.

Here’s where the butchering comes into play. Let’s eliminate the square root and the power function of the calculation.

We just want the distance between the two objects minus their radius.

How do we do the speedups and optimizations? The calculations are short and simple. We also removed the calculations from the If conditions. Short and simple usually means speed.

I feel a function coming on (while I smile gleefully).

void obsticleCollision3 (unsigned char playerX, unsigned char playerY, unsigned char level, unsigned char x1[], unsigned char y1[])
    unsigned char xx1,yy1;
    unsigned char obsticleX, obsticleY;
    unsigned char iterator;
    unsigned char attribute;
    unsigned char objectRadius;
    unsigned char differenceX,differenceY;

    xx1 = (obsticleX * 16) + 8;		
    yy1 = (obsticleY * 16) + 8;

    objectRadius = 15;
    for (iterator = 0; iterator < 90; iterator ++)
        obsticleX = x1[iterator];
        obsticleY = y1[iterator];
        attribute = tileAttribute[iterator];

        //center point of the tiles
        xx1 = (obsticleX * 16) + 8;
        yy1 = (obsticleY * 16) + 8;
        differenceX = abs(playerX - xx1);
        differenceY = abs(playerY - yy1);

        if ((differenceX < objectRadius) && (differenceY < objectRadius))
            zx_border(6);//collision detected

        if (attribute == 99) break;// break out of the loop earlier if we encounter 99

Our calling function


Say Whaaaa!

It’s spot on also. And as you can tell by my excitement (believe me I am). It’s pretty fast also. This might be the one I’m going with. Now, of course, this will still have some of the same weakness as the other bounding box, as in the more objects you add, the slower it will be. It’s not as fast as the tile-based detection, but the difference seems to be negligible for now.

I still am going to experiment with other collision detection routines, but I have a good feeling about this one.

Love, peace and taco grease.


Author: andydansby

I'm a hobbyist coder working with the ZX Spectrum. Living in New York state near the Syracuse area. I grew up in Virgina. The first computer my parents bought for me was a Timex Sinclair 2068.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s