Monday, 20th September 2010

# Collisions

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 as below does not work.

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

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. 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:

Attachment | Size |
---|---|

particle_tutorial_8.txt | 3.92 KB |

## Comments

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.

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

(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.

Oh, wonderful, thanks!

And yes, it works very well now!

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.

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.

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

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.

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

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?

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.

the momentum is not conserved

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!

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.

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

Regarding the normal angle, you said

"To reflect the angle of the particles on this surface, we subtract theircurrent 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

normalangle, 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..

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 :)

## Post new comment