title: An efficient way to simulate many particle collisions?
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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 <a href="https://stackoverflow.com/questions/6811721/efficient-algorithm-for-collisions-in-2d-game">this</a> 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.</p>
  
  <p>So now: Even if this approach will work performance wise (getting say 40fps), can anybody think of a way to avoid unnecessary collision checks?</p>
  
  <p>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...</p>
  
  <p>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.</p>
  
  <p><strong>Edit:</strong> 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.</p>
  
  <p><strong>Edit2:</strong> I found a good and very helpful paper on the simulation of particle collision <a href="http://www.cg.informatik.uni-siegen.de/data/Publications/2004/GH2004.pdf" rel="noreferrer">here</a>. Hopefully it might help some People that are interested in more depth.</p>