algorithm - An efficient way to simulate many particle collisions?

Question

I would like to write a small program simulating many particle collisions, starting first in 2D (I would extend it to 3D later on), to (in 3D) simulate the convergence towards the Boltzmann distribution and also to see how the distribution evolves in 2D.

I have not yet started programming, so please don't ask for code samples, it is a rather general question that should help me get started. There is no problem for me with the physics behind this problem, it is rather the fact that I will have to simulate at least 200-500 particles, to achieve a pretty good speed distribution. And I would like to do that in real time.

Now, for every time step, I would update first the position of all the particles and then check for collisions, to update the new velocity vector. That, however, includes a lot of checkings, since I would have to see if every single particle undergoes a collision with every other particle. I found this post to more or less the same problem and the approach used there was also the only one I can think of. I am afraid, however, that this will not work very well in real time, because it would involve too many collision checks.

So now: Even if this approach will work performance wise (getting say 40fps), can anybody think of a way to avoid unnecessary collision checks?

My own idea was splitting up the board (or in 3D: space) into squares (cubes) that have dimensions at least of the diameters of the particles and implement a way of only checking for collisions if the centres of two particles are within adjecent squares in the grid...

I would be happy to hear more ideas, as I would like to increase the amount of particles as much as I can and still have a real time calculation/simulation going on.

Edit: All collisions are purely elastic collisions without any other forces doing work on the particles. The initial situation I will implement to be determined by some variables chosen by the user to choose random starting positions and velocities.

Edit2: I found a good and very helpful paper on the simulation of particle collision here. Hopefully it might help some People that are interested in more depth.

Answer 1

If you think of it, particles moving on a plan are really a 3D system where the three dimensions are x, y and time (t).

Let's say a "time step" goes from t0 to t1. For each particle, you create a 3D line segment going from P0(x0, y0, t0) to P1(x1, y1, t1) based on current particle position, velocity and direction.

Partition the 3D space in a 3D grid, and link each 3D line segments to the cells it cross.

Now, each grid cell should be checked. If it's linked to 0 or 1 segments, it need no further check (mark it as checked). If it contains 2 or more segments, you need to check for collision between them: compute the 3D collision point Pt, shorten the two segments to end at this point (and remove link to cells they doesn't cross anymore), create two new segments going from Pt to newly computed P1 points according to the new direction/velocity of particles. Add these new line segments to the grid and mark the cell as checked. Adding a line segment to the grid turn all crossed cells to unchecked state.

When there is no more unchecked cells in your grid, you've resolved your time step.

EDIT

• For 3D particles, adapt above solution to 4D.
• Octrees are a nice form of 3D space partitioning grid in this case, as you can "bubble up" checked/unnchecked status to quickly find cells requiring attention.