How do I create collision detections for my bouncing balls?

Question

I have coded an animation (in python) for three beach balls to bounce around a screen. I now wish to have them all collide and be able to bounce off each other. I would really appreciate any help that can be offered.

import pygame
import random
import sys
class Ball:


    def __init__(self,X,Y):

        self.velocity = [1,1]
        self.ball_image = pygame.image.load ('Beachball.jpg'). convert()
        self.ball_boundary = self.ball_image.get_rect (center=(X,Y))
        self.sound = pygame.mixer.Sound ('Thump.wav')
        self.rect = self.ball_image.get_rect (center=(X,Y))

if __name__ =='__main__':

    width = 800
    height = 600
    background_colour = 0,0,0
    pygame.init()
    window = pygame.display.set_mode((width, height))
    pygame.display.set_caption("Bouncing Ball animation")
    num_balls = 3
    ball_list = []
    for number in range(num_balls):
        ball_list.append( Ball(random.randint(10, (width - 10)),random.randint(10, (height - 10))) )
    while True:
        for event in pygame.event.get():
                print event 
                if event.type == pygame.QUIT:
                        sys.exit(0)
        window.fill (background_colour)

        for ball in ball_list:
                if ball.ball_boundary.left < 0 or ball.ball_boundary.right > width:
                        ball.sound.play()
                        ball.velocity[0] = -1 * ball.velocity[0]
                if ball.ball_boundary.top < 0 or ball.ball_boundary.bottom > height:
                        ball.sound.play()
                        ball.velocity[1] = -1 * ball.velocity[1]

                ball.ball_boundary = ball.ball_boundary.move (ball.velocity)
                window.blit (ball.ball_image, ball.ball_boundary)
        pygame.display.flip()

Answer 1

Collision detection for arbitrary shapes is usually quite tricky since you have to figure out if any pixel collides.

This is actually easier with circles. If you have two circles of radius r1 and r2, a collision has occurred if the distance between the centers is less than r1+r2.

The distance between the two centers (x1,y1) and (x2,y2) can be calculated and compared as:

d = sqrt((y2-y1) * (y2-y1) + (x2-x1) * (x2-x1));
if (d < r1 + r2) { ... bang ... }

Or, as jfclavette points out, square roots are expensive so it may be better to calculate using just simple operations:

dsqrd = (y2-y1) * (y2-y1) + (x2-x1) * (x2-x1);
if (dsqrd < (r1+r2)*(r1+r2)) { ... bang ... }

The tricky bit comes in calculating the new movement vectors (the rate at which (x,y) changes over time for a given object) since you need to take into account the current movement vectors and the point of contact.

I think as a first cut, you should just reverse the movement vectors to test if the collision detection works first.

Then ask another question - it's better to keep individual questions specific so answers can be targeted.

Answer 2

Detecting collisions was covered well by Pax's answer. With respect to having objects bounce off one another, I suggest checking out the following links concerning elastic collisions, inelastic collisions, and coefficients of restitution.

EDIT: I just noticed that this was covered in another SO question, albeit not specifically for Python. You should also check there for some good links.

Answer 3

Detecting a collision is only the first step. Let's break that down.

The fastest thing to do is calculate their square bounding boxes and see if those collide. Two of the sides need to cross (top of 1 and bottom or 2, and left of 1 and right of 2, or vice versa) in order for the bounding boxes to overlap. No overlap, no collision.

Now, when they do overlap, you need to calculate the distance between them. If this distance is more than the sums of the radii of the balls, then no collision.

Okay! We have two balls colliding. Now what? Well, they have to bounce off each other. Which way they bounce depends on a few factors.

The first is their elasticity. Two rubber balls bouncing off each other rebound differently than two glass balls.

The second is their initial velocity. Inertia states that they'll want to keep going in mostly the same direction they started in.

The third is the mass of the balls. A ball with smaller mass will rebound off a much larger mass with a higher velocity.

Let's deal with the second and third factors first, since they are intertwined.

Two balls will rarely hit exactly dead on. Glancing blows are far more likely. In any case, the impact will happen along the normal of the tangent where the balls collide. You need to calculate the vector component of both along this normal given their initial velocities. This will result in a pair of normal velocities that both balls will bring to the collision. Add up the sum and store it somewhere handy.

Now we have to figure out what each ball will take away from it. The resulting normal velocity of each ball is inversely proportional to the given ball's mass. That is to say, take the reciprocal of each ball's mass, add both masses together, and then parcel out the resultant normal velocity away from the collision based on the ratio of the ball's mass to the sum of the reciprocal of both ball's masses. Then add the tangential velocity to this, and you get the resultant velocity of the ball.

Elasticity is mostly the same, except it requires some basic calculus due to the fact that the balls are still moving even as they compress. I'll leave it to you to find the relevant math.

Answer 4

@Pax: Your d-squared version is still computing d. It should read as follows:

dsqrd = (y2-y1) * (y2-y1) + (x2-x1) * (x2-x1)
if (dsqrd < (r1+r2)*(r1+r2)) { ... bang ... }

Answer 5

I asked a similar question awhile ago:

Ball to Ball collision detection and handling.

Got some good responses there too.

Answer 6

I think there is somehthing simpler that you guys are missing espeically considering he's using pygame.

Calling the get_rect function can set probably boundraies for the images and Rect that is created, is used for calculating the position of the image and if there are more than one object in the animation, it can be used for detecting collisions.

colliderect & rect can be used, problem is i have no idea how you would implement it especially for an unkown number of balls.

Keeping in mind it's python.

Answer 7

This doesn't answer you question but you could do the same thing in 3D via python with panda www.panda3d.org.

Like pygame it also has smart ways to do collision detection.

Answer 8

Back in the good old times when CPU cycles were a premium coders used a simple trick to detect collision: they used such colours that they could tell from the pixel colour if it was background or an object. This was done on at least some C64 games.

Don't know if you are willing to go this route, though..

Answer 9

First you need to check collision with rect.colliderect(other_rect)

after that if they are colliding, you can check pixel perfect collision. So you don't mess with object's radius or shape.

For pixel perfect collision checking, I use Masks: Make both mask objects with mask.from_surface, then put them to Mask.overlap function.