Almost all games rely on the software being able to detect when objects have hit together. This could be a missile hitting an alien, a player running into a wall, or character picking up a health bonus. Our code has to monitor the position of all of the objects on our game screen and then calculate when one is overlapping with another. This whole topic is called collision detection.
There are lots of different techniques for collision detection. In general the different techniques create a compromise between the speed and processing power required to calculate collisions and the accuracy of the collisions they are detecting. In other words if you’re not too concerned about an alien exploding even if you haven’t quite hit it we can use a very fast collision detection technique that makes sure your game doesn’t slow down when you have hundreds of aliens on the screen. If you decide to use a complex collision detection it will be very accurate but it may slow your game down.
In this coding tutorial I’ll take you through the bounding box collision detection algorithm, or more accurately the axis aligned bounding box algorithm AABB.
In this technique we convert our onscreen objects such as the player ship, missiles, obstacles, etc. into simple squares and rectangles. These squares and rectangles tightly surround the on-screen object to form these bounding boxes – boxes which show the extent and size of the object. Once we have a series of boxes we simply have to work out when they overlap.
To calculate overlaps we first need to have some data about each box. Usually we’ll have the screen coordinates of the top right hand corner in the bottom left-hand corner, two diagonally opposite corners. Depending on how you store the data for each of your onscreen objects you should be able to work these out. For example, you might be storing the insertion point of the object as screen coordinates and then have a height and width in pixels. You can use the insertion point as one corner and then add the height and width to get the coordinates of the diagonally opposite corner.
The important point is is that your corner information is for the same two corners for each object.
Once we’ve got this corner information we simply need to perform four comparison checks to detect if the two objects are overlapping. These comparisons are split into pairs which check for a left-to-right overlap and an up down overlap.
For the left-to-right overlap consider to boxes that are side-by-side but not overlapping.
As the right hand box slides towards the left hand box, eventually the two closest edges will touch.
If we compare the X coordinates for each of these two sides we can create the following rule.
Similarly we can do this for a box placed to the left of another and then moving right, and for both the upwards and downwards collisions. In general this then gives us the following four conditions which must all be met for any to boxes to be colliding.
Note: you need to check on the way the coordinates work in our system. The tests above assume a normal XY coordinate system. Most graphics systems use an inverted Y axis, i.e. zero at the top, Y increasing as you move down the screen. Use the sliding box example as above to work out the conditions for each overlap in your system.
I’ve added a little test programme below to show this algorithm working. This is programmed using TIC80 in a language called Lua. The code is listed underneath the demo. Again note that TIC80 uses the inverted Y axis. If you look at the collision detection code you’ll see the amended tests.
This method of collision detection is great if your objects fit nicely into squares or rectangles. It’s very fast to calculate and places very little load on the processor so you won’t have to worry about slowdowns. However, if you have very irregularly shaped objects that don’t fill the rectangle you’ll get false hits when one box overlaps with a blank area within your bounding box.
Due to the speed of this type of collision detection even if you need a more complex algorithm you can use this method to very quickly filter out objects which have definitely not collided. This means that you have far fewer checks which have to use your more complex code which puts more load on your processor. We can refer to these two stages as course collision detection and fine collision detection.
So bounding box collision detection is the simplest algorithm. Make sure you check out the other tutorials in this collision detection series to find out more about this very important topic.
Click on the demo below and then use the cursor keys on your keyboard to move the blue box.