python - 帧速慢的碰撞检测(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.

(我不了解碰撞检测算法，但出于教育目的，我正在尝试在Python的粒子系统中处理碰撞。)

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

  (遍历我的粒子列表中的所有粒子（由半径定义的圆）（通过for循环），调用当前粒子p)

• On every iteration, compare p to every other particle (another for loop)

  (在每次迭代中，将p与每个其他粒子进行比较（另一个用于循环）)

• 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.

(使用上述方法，当粒子数较高而FPS较低时，我的某些粒子甚至无法检测到碰撞。)

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

(在我目前的方法中是否有办法防止这种情况发生？还是我必须实施另一个更有效的方法（可能是这样做的方法）？)

  ask by Sean Xie translate from so

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.

(提高效率的常用技术是将所有对象置于某种空间分区数据结构中，以将对的数量限制为接近O（n）而不是O（n ^ 2）（这就是您现在拥有的）。)

Quadtrees and kd trees are two candidates.

(四叉树和kd树是两个候选对象。)

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 .

(因此，您需要“边缘” 四叉树或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.

(首先尝试后者。)