Particle Collision Optimization

This is just something that I had in the back of my head. I assumed it would speed things up and, well, it definitely did.

The problem is a bunch of particles which are supposed to repel only at a close distance, usually for something like fluid approximation, maybe just basic physics, I don’t know. I just wanted to do it. Anyway, it was all I did today (given my wonderful strep throat), and the results are promising:

The red line is is the number of frames per second (peaks at 175, after first five seconds only drops down to 109) and the blue line is the number of particles in the system. The method used is done by solving the new velocity of all particles (given any close interactions), repelling them, solving the new velocity at that position then going back to the original position and using an average of the two new accelerations/velocities, so this is with four system passes (now that I think about it, I could probably combine two…); however, this is not the purpose of it all.

If every point were checked with every other point, the number of distance checks would be N*N, or at 1,500 particles, 2.25 million. My system seems to only have to perform at most 8 per particle (though it could be anywhere from 0 to infinity). The system is divided into a grid and only adjacent grid blocks are tested for distance.

And finally, it working:

The blue dots are particles, the red blocks grid sections. The grid blocks get more red the more particles that are in them (I probably should have disabled grid rendering before benchmarking this… d’oh). Eventually the screen would fill and the ones that leave would be deleted (quite efficiently, I might add). As you can see, each particle testing only adjacent grid blocks probably averages… what, 6? Awesomeness, if you ask me. The grid size is also a parameter, including the grid location. The particle processing functions are callbacks. IE I set the first function, iterate the system, set the second function to move the particles, iterate, etc.

My only sadness comes from the fact that if the repel distance (AKA interaction distance) is greater that the size of one grid block, nothing outside the adjacent 9 cells will be considered. This might be useful for a RTS game engine. It is fast and makes it easy to find objects near one another (though it is limited).

This was done using a quad-core Q6600 CPU at 3.1 GHz, though because it is only single-threaded for now it utilizes 25% of that and the memory use peaked at no greater than 11mb. Double precision was used.

Oh man sneezing with strep throat sucks.

Tags: c plus plus, c++, Programming, rts, searching, sorting, strep throat