CODEWITHSUNDEEP
pythonalgorithmloopscollision-detection
Scene
Scene

Reputation: 509

Collision detection with slow frame rate

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:

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)?

Upvotes: 0

Views: 195

Answers (1)

Gene
Gene

Reputation: 46960

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.

Upvotes: 1

Related Questions