An efficient way to simulate many particle collisions?

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.

A good high level example of spatial division is to think about the game of pong, and detecting collisions between the ball and a paddle.

Say the paddle is in the top left corner of the screen, and the ball is near the bottom left corner of the screen...

--------------------
|▌                 |
|                  |
|                  |
|     ○            |
--------------------

It's not necessary to check for collision each time the ball moves. Instead, split the playing field into two right down the middle. Is the ball in the left hand side of the field? (simple point inside rectangle algorithm)

  Left       Right
         |
---------|----------
|▌       |         |
|        |         |
|        |         |
|     ○  |         |
---------|----------
         |

If the answer is yes, split the the left hand side again, this time horizontally so we have a top left and a bottom left partition.

   Left       Right
          |
 ---------|----------
 |▌       |         |
 |        |         |
-----------         |
 |        |         |
 |     ○  |         |
 ---------|----------
          |

Is this ball in the same top-left corner of the screen as the paddle? If not, no need to check for collision! Only objects which reside in the same partition need to be tested for collision with each other. By doing a series of simple (and cheap) point inside rectangle checks, you can easily save yourself from doing a more expensive shape/geometry collision check.

You can continue splitting the space down into smaller and smaller chunks until an object spans two partitions. This is the basic principle behind BSP (a technique pioneered in early 3D games like Quake). There is a whole bunch of theory on the web about spatial partitioning in 2 and 3 dimensions.

http://en.wikipedia.org/wiki/Space_partitioning

In 2 dimensions you would often use a BSP or quadtree. In 3 dimensions you would often use an octree. However the underlying principle remains the same.