在Python/Pyglet中分离轴定理

Question

我想用Pyglet在Python中制作一个（各种）Asteroids的克隆。我想我会尽量想出一点幻想，并实施分离轴定理来进行碰撞。我有它的工作，但问题是，它是非常缓慢。我测试了玩家射击的子弹与屏幕上的小行星之间的双重for-loop碰撞，我认为这是二次时间，但帧速率从大约60到30 fps下降到大约6个小行星和6个子弹在屏幕上看起来非常慢，即使是非优化的碰撞检测方式。

因此，我运行了一个分析器来确定程序在哪里，确切地说，在程序被挂起。它似乎挂在了我将形状顶点转换为世界空间的方法中（我定义了围绕原点的形状并使用OpenGL代码转换为绘制的世界空间，我相信这是正确的方式）。我从OpenGL抓取变换矩阵，将它变成一个NumPy数组，然后将每个顶点乘以这个矩阵以获得变换的顶点。值得注意的是，我每做一次碰撞检查都会这样做：我曾经使用过XNA，当我在那里实施SAT时（我也在那里制作了一个小行星克隆），顶点也在原点周围定义，然后您必须转换他们使用世界矩阵。

围绕（0,0）存储顶点并转换每个调用，还是只存储变换的顶点最好？我觉得算法不应该这么慢，所以我愿意打赌我搞砸了一些东西。如果我更擅长剖析（我对它很不熟悉），我可能能够获得更全面的图片，但我希望你们可以有一些想法。

下面是带有Shape类的文件的直接链接，其中包含所有碰撞逻辑：shape.py。 profiler似乎标记为瓶颈的具体方法是__get_transformed_verts。显然，你也可以从那里获得整个回购，但要注意，还有很多没有评论的交易。

Answer 1

正如Nico在评论中所建议的那样，快速获得较好加速度的方法是先检查较简单的几何图形。对于一个小行星克隆，我猜测一个圆圈将会很适合（或3D的球体）。如果圆圈（至少足够大以覆盖实际形状）不重叠，则不需要进行更昂贵的几何测试。

如果您有很多对象，您可能会希望避免每帧进行n * n次测试。看看空间分区结构/算法。 2D中大量移动对象的最简单方案是网格。然后，您只需测试属于相同或相邻网格单元的对象以进行碰撞。

我注意到的另一件事：您每次测试碰撞时都会生成变换的顶点。对于圆圈测试不合格的每个对象，每个时间步（帧）仅生成一次会更快。