Collision detection with slow frame rate

Question

I have no knowledge of collision detection algorithms but I'm trying to play around with collision in a particle system in Python for educational purposes.

The way I'm detecting collision right now seems very inefficient. Probably the slowest algorithm out there:

• Loop through all particles (which are circles defined by radius) in my particle list (via a for loop), call the current particle p
• On every iteration, compare p to every other particle (another for loop)
• Detect collision

With the method above, some of my particles aren't even detecting collisions when the particle count is high and FPS is low. Is there a way to prevent this in my current method or will I have to implement another, more efficient one (which is probably the way to go)?

Answer 1

The usual technique to improve efficiency is to put all objects in some kind of space partition data structure in order to limit the number of pairs to something approaching O(n) rather than O(n^2), which is what you have now. Quadtrees and k-d trees are two candidates. Nodes in these trees represent regions of space. Only pairs of objects contained in or intersecting the same region need to be checked.

To avoid missing collisions, comparing points isn't sufficient. Rather, check for intersections of line segments from previous to current positions for each particle. Consequently, you want a "edge" quadtree or kd-tree.

One other thing to consider is whether to build one space partition and update it between frames or rebuild the partition from scratch for each frame. The former is much more complicated and may not result in better speed. Try the latter first.