Collisions

20 Sep 2010 Code on Github

Introduction

In the previous tutorial we allowed the user to interact with the particles, but the particles didn't interact with one another. Now it's time to make them more tangible. In this tutorial, we will:

Test whether any two particles have collided
Make particles that have collided bounce
Prevent colliding particles from sticking to one another

Things start to get complex once we have multiple particles interacting with one another. In fact, it's mathematically impossible to solve the equations describing three or more interacting objects. In our simulation we'll have to make some simplifications, which we make it 'inaccurate', however, it should still represent a reasonable approximation to reality.

Collision testing

Firstly, we want to check whether any two particles overlap with one other, so we need to compare every particle with every other of particle. We can do this with a nested for loop. Since we already have one loop going through the particle array, we can use that.

for i, particle in enumerate(my_particles):
    particle.move()
    particle.bounce()
    for particle2 in my_particles[i+1:]:
        collide(particle, particle2)
    particle.display()

Note that the second loop is not a full loop; if we had two full loops, we'd compare every particle to every other particle twice over (and compare each particle to itself). Instead, we compare each particle with every particle with a higher index than it in the array. We therefore need to know the index of the current particle which we can get using enumerate. We use this value (i) to slice the my_particle array from i + 1 to the end to construct the second loop.

Now we need to actually define the collide() function. The first thing the function has to do is to test whether the two particles have collided. This is very simple as the particles are circles. We simply to measure the distance between them (using math.hypot() again) and test whether this value is less than their combined radius.

def collide(p1, p2):
    dx = p1.x - p2.x
    dy = p1.y - p2.y
    
    distance = math.hypot(dx, dy)
    if distance < p1.size + p2.size:
        print 'Bang!'

So far all that happens when two particles collide is that we print 'Bang!'. I'll complete the function as soon as I get a chance.

The angle of collision

When two particles collide, we want them bounce off each other. Theoretically, when two circular particles collide they contact at an infinitely small point. The angle of this point is the tangent of the particle at this point. As the diagram below I hope shows, this angle is perpendicular to the line that joins the centre of the two particles.

We can treat the collision as though the particles were bouncing off a flat surface with the angle of the tangent. We can find the angle of the tangent with the following code:

tangent = math.atan2(dy, dx)

To reflect the angle of the particles on this surface, we subtract their current angle from two times the tangent. I'll have to explain the logic behind this at a later date. It's at this point that knowing the angle that our particle is travelling starts to become useful.

p1.angle = 2 * tangent - p1.angle
p2.angle = 2 * tangent - p2.angle

Then we need to exchange the speeds of the two particles as they transfer their energy to on another. We can do this in a single line by constructing a tuple.

(p1.speed, p2.speed) = (p2.speed, p1.speed)

Note that writing the exchange as two lines does not work. The reason this doesn't work, as you may have realised, is that when we come to assign p2.speed on the second line, we are assigning it to the new value of p1.speed, which we have already made equal to p2.speed. Constructing an tuple, which is immutable, allows us to avoid this problem.

p1.speed = p2.speed
p2.speed = p1.speed

(Don't do this.)

I would then add some code to reduce the energy of both particles as a result of the collision.

p1.speed *= elasticity
p2.speed *= elasticity

Sticky problem

If you run the simulation now, you'll probably find that the particles stick to one another, and can even get stuck in mid air. The reason for this is that we have a discrete simulation (i.e. the time between updating the particle positions is not infinitely small). This introduces errors, which, for the most part, aren't important (though you should be aware of them).

What's happening is that when a particle collision is detected, the particles have actually overlapped slightly. When we alter their angle and speed then move them, we can't be sure that the particles are no longer overlapping (particularly because of drag, gravity and elasticity also altering their movement). If they still overlap then they will 'bounce' back the way they came, towards each other. They can then get trapped in a loop of 'internal bouncing', which gradually reduces their speed to nothing.

To avoid this problem we add some code into the collide() function to fudge the fact that the particles should have bounced before they overlapped. We calculate the angle between the two particles (which is 90 degrees to the tangent) and move the particles along this angle one pixel. We could work out exactly how far to move the particles along this angle, but I don't think it's worth the extra calculation. The code below moves the particles away from one another by a sufficiently large amount, and seems to work pretty well.

angle = 0.5 * math.pi + tangent
p1.x += math.sin(angle)
p1.y -= math.cos(angle)
p2.x -= math.sin(angle)
p2.y += math.cos(angle)

Now the particles should bounce off one another cleanly

Comments (20)

Nathan Chapman on 16 Dec 2010, 1:33 a.m.

Thanks for these tutorials, I've been following through and they're very good.

One thing though: above where you have the code the "fudge" the collision happening before the particles intersected, I'm throwing an error whereby it doesn't know what "angle" is.

p1.x += math.sin(angle)
p1.y -= math.cos(angle)
p2.x -= math.sin(angle)
p2.y += math.cos(angle)

Here is throws the following error if I run that code exactly:

NameError: global name 'angle' is not defined

What have I missed / done wrong?

Thanks, Nathan.

Peter on 16 Dec 2010, 1:10 p.m.

No, sorry, that's my fault. Looks like I forgot to say to add the line:

33. angle = 0.5 * math.pi + tangent
(Add after the line defining the tangent.)

If you look at the attached file below the video, it will give you the final program, which should work. I'll update the tutorial to include it.

Nathan Chapman on 18 Dec 2010, 12:16 a.m.

Oh, wonderful, thanks!

And yes, it works very well now!

nf3 on 29 Jan 2011, 1:29 a.m.

hi, advancing in this great tutorial :)

found another error. line 108 in 'collision testing' reads:

108. collide(particle1, particle2)

but it should be

108. collide(particle, particle2)

because the outer loop delivers 'particle', not 'particle1'

ps. in another comment you refer to a link with the complete code, but i cant see it (on Firefox). Anyway, I find it better to follow the tutorial typing or pasting things in place, because it makes me pay more attention.

Peter on 29 Jan 2011, 3:27 p.m.

Thanks, I've fixed it. I appreciate you taking the time to go through it all. It is definitely better that simply copying and pasting the code. And it's a good test to see whether I've actually written about all the changes (I think I sometimes rearrange code without mentioning it).

Between the video and the comments there should be an attachment of the final code called particle_tutorial_8.txt. I can see it in Firefox, I'm not sure why you can't.

Peter on 6 Feb 2011, 11:50 a.m.

Sorry, I realised that the permissions were set so only I could see the attached files, they should now be visible.

Charlie on 18 Feb 2012, 7:18 a.m.

Thanks very much for these great tutorials. Really appreciate them a lot and hope you wlll keep adding to these python based tutorials.

Thanks again.

Peter on 19 Feb 2012, 4:50 p.m.

Thanks Charlie. I have ideas for quite a few more Python tutorials, I just need to find time to write them.

Jatra on 3 Oct 2012, 10:06 p.m.

When i run particle_tutorial_7, the circles have only the boundaries as color blue. but when i run particle_tutorial_8, the entire circle including the inside is blue. where did this change come from?

Peter on 3 Oct 2012, 11:19 p.m.

The change is in the Particle class where self.thickness changes from 1 to 0. I decided it was easier to see the particles that way, I should have mentioned it somewhere.

HenryChen on 15 Nov 2012, 11:45 a.m.

the momentum is not conserved

Andy on 16 May 2013, 9:12 p.m.

Hi Peter,

I know this was a while ago, but you said : "To reflect the angle of the particles on this surface, we subtract their
current angle from two times the tangent. I'll have to explain the
logic behind this at a later date."

Well, this was the only step I didn't understand, and it's the only one you didn't explain! Could you help me out?

Thank you very much. Your tutorials present well-explained, elegant solutions to many problems that I've been banging my head against in Python for a while now. The amount of time I spent struggling with the signs of arctan(x) and its special case x=0 is frankly upsetting, but of course - atan2()! Python has a simple solution for everything. I love it!

Peter on 7 Jul 2013, 7:45 p.m.

Hi Andy,

You're right. I meant to properly explain this ages and I still haven't gotten around to it. One of these days I'll go back through this tutorial and finish off, I hope.

I also spent a lot of time messing about with signs and special cases before discovering atan2. It's clearly a common enough problem that they made a specific function for it.

Adam on 12 Feb 2014, 2:47 p.m.

Hi Peter,

Great tutorial. I'm trying to build a molecular fluid dynamics simulation at the moment, and your work here is tremendously helpful. (For example, before I found your tutorial I spent about two hours struggling with atan before finding atan2. I was trying to come up with a solution to "sticky collisions" when I found your tutorial. Major time saver!)

One problem I am running into that you don't address is collision detection efficiency for large numbers of particles. I am currently doing this as a nested loop over all pairs, just as you suggest. This is a O(n^2) algorithm that quickly uses up available processing power for large n.

It turns out that there has been a lot of work done to improve collision detection, resulting in two main alternatives, "sweep and prune" and "regular grid". These techniques can tremendously reduce processing time for large numbers of particles, approaching O(n log(n)) or O(n), respectively.

If you are interested in this, http://umumble.com/blogs/algorithm/403/ is a great place to start. My own simulation will require 1000+ particles, so such an algorithm will be necessary for me. It may be of interest to some of your other readers as well!

Thanks for your great work,
Adam

MestreLion on 8 Aug 2014, 4:40 a.m.

Regarding the normal angle, you said "To reflect the angle of the particles on this surface, we subtract their
current angle from two times the tangent. I'll have to explain the
logic behind this at a later date"

Actually this is quite trivial to explain: physics say the exit and entry angles are symmetrical to the tangent angle (and thus also symmetrical to the normal angle). So IN-N = N-OUT, which means OUT = 2N - IN. And that's where those formulas came from:

p1.angle = 2*tangent - p1.angle

p2.angle = 2*tangent - p2.angle

Just a note: If I understood correctly, what you called "tangent angle" is actually the normal angle, as the distance between the circle centers (used to calculate it) is the normal of the reflection line (the line tanget to the circles). They are perpendicular to each other, so the either one works, but it's nice to have a consistent nomenclature.

MestreLion on 8 Aug 2014, 12:47 p.m.

Peter , your articles are amazing! Elegant solutions, pythonic style, congrats!!! And thanks a LOT!

(that math.hipot() was sweet! So much better than spawning sqrt(x**2 + y**2) everywhere :)

Anonymous on 3 May 2015, 4:58 a.m.

The 3-body problem is solvable... And so is the n-body problem...

Anonymous on 5 May 2015, 9:57 p.m.

I keep getting an attribute error in the collide function:

p2.pos_x -= math.sin(angle)
AttributeError: 'float' object has no attribute 'pos_x'

Anonymous on 15 Dec 2016, 3:09 p.m.

Doesn't this only work if the circles are both moving "towards" the tangent line?

How should a circle react if it is already moving away from the line? For example, in a rear-end collision, this algorithm wouldn't apply, right?

I'm trying to figure out how to deal with these types of collisions and I'm going crazy.

TheRainHarvester on YouTube on 4 Sep 2019, 11:33 p.m.

The "angle of collision diagram" makes no sense because it means car #1 could t-bone another car 2, and car 2 wouldn't be affected.

Pygame physics simulation