logologologologo
  • home
  • learn to code
    • Space Invaders – Beginner’s Course
    • Asteroids – Beginner’s Level 2
    • Snake – a Beginner’s Challenge
  • learn to make
    • Arduino Tutorials
  • blog
    • Computer Science
    • Coding
      • Collision Detection
    • Retro Gaming
    • Computer Games for Vision Therapy
  • contact me
Bounding Box Collision Detection
Bounding Box Collision Detection (AABB) – Game Coding Tutorial
3rd January 2020
ZX Spectrum Jetpac – Retro Game Deconstruction
12th January 2020
Published by Bob at 5th January 2020
Categories
  • BytesNBits Blog
  • Coding
  • Collision Detection
Tags
Bounding Ball Collision Detection

Bounding Ball Collision Detection – Game Coding Tutorial

In my previous tutorial we had a look at bounding box collision detection. We saw this was a great and fast way of getting fairly accurate collision detection providing that our objects more or less fitted into a rectangular area. But what of our objects aren’t rectangular or if they need to rotate. Quite often our bounding box solution ends up with either parts of the object sticking outside the box, or areas of our box which are empty, not containing an actual part of the object. In these situations we need a new solution.

bounding box fails

Bounding ball collision detection uses circles (balls) to surround our objects. Again we need to design our sprites and graphics so that they more or less fill their bounding ball. But once we’ve done this we are able to rotate them without parts coming outside our bounding lines.

Bounding Ball encloses shape

To calculate if we have a collision we need to work out the distance between our objects. To do this we need to know the position of each object and the radius of its bounding ball.

Ball position and radius

Usually the position of the object tells us the centre of the sprite or graphic. To calculate the distance between objects we simply need to apply Pythagoras theorem.

Distance between objects

d = sqrt( (x2 – x1)2 + ( y2 – y1)2 )

Once we know the distance between objects we can compare this with the minimum distance between the two objects before they collide. This minimum distance is simply the sum of the two radii of the bounding balls.

r1 + r2

If the distance between the objects is less than or equal to this minimum distance then the objects have collided.

if (d <= (r1 + r2) )
// collision

As always we are trying to minimise the number of calculations needed to detect the collision. To get the actual distance between objects we need to use a square root function. This is quite costly in terms of processing power. We can get rid of this function by simply replacing it with a single multiplication. Instead of comparing the actual pixel distances, we can compare the squares of distances.

From Pythagoras we can quickly get the square of the distance between the objects by adding the squares of the X coordinate and Y coordinate separations. If we then square the minimum distance required between the objects we can compare this with the square of the separation to detect the collision. So our square root function gets replaced by multiplying the minimum distance by itself.

d2 = (x2 – x1)2 + ( y2 – y1)2 

r2 = (r1 + r2) * (r1 + r2)

if ( d2 <= r2 )
// collision

With this optimisation our bounding ball collision detection only requires three multiplications, two additions and a comparison. It’s not quite as fast as the bounding box algorithm but it’s still very fast and therefore very suitable for course collision detection where we use a fast but slightly less accurate algorithm to work out which objects are close enough to collide before committing to one of our more accurate collision detection algorithms which requires much more processing power.

If you have a look at the demos below I’ve created a simple bounding ball collision detection example where you can move one of the circles and make it collide with the other circle.

The second demo is taken from the Asteroids programming course where we use the bounding ball algorithm to filter out asteroids which are too far away from any of the bullets before committing to the crossing number algorithm which accurately detects if a point has moved inside the polygon of the asteroid. I’ve slowed the demo down so you can see everything happening in real time. If you fire a bullet as an asteroid you’ll see the asteroid turn red once the bullet has entered the asteroids bounding ball. You should then see the bullet continue towards the asteroid until it actually crosses into the shape.

TIC80 Bounding Ball Collision Detection Demo

Click on the demo below and then use the cursor keys on your keyboard to move the blue circle.

Asteroids Using  Ball Collision Detection for Course Detection Demo

Click on the demo below and then use the cursor keys on your keyboard to rotate and up to thrust. Z is the fire key.

Code for Lesson Bounding Ball Collision Detection Demo

Share
4
Bob
Bob

Related posts

The best computer language for beginners
8th November 2020

The Best Computer Language for Beginners


Read more
Vision Therapy Flappy Bird
15th February 2020

Flappy Bird for Binocular Vision Suppression Training


Read more
Asteroids for vision therapy
15th February 2020

Asteroids for Binocular Vision Suppression Training


Read more

Comments are closed.

  • Privacy Policy
  • Contact Me
© 2020 Bytes N Bits
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.Ok