我正在搜索有关碰撞检测优化的信息。
有一个物体（圆圈）从点a移动到点b。该物体具有半径r，并且场中也存在许多障碍物（圆圈）。
我有一个算法（函数）来检查圆和胶囊之间的碰撞，我现在为每个障碍调用此函数：
for-each (o : obstacles)
if collide(o, Capsule(a,b,r))
return true;
return false;
许多障碍物距离移动物体非常远，并且可以通过碰撞检测功能进行检查来忽略它们。
我的问题是：
是否有解决方案忽略用碰撞检测功能检查所有障碍物？像最近邻搜索还是KD树？
编辑：所有障碍物具有相同的半径。
作为第一步，您可以忽略不在某个框架/框中的所有障碍。
例如。所有具有y坐标的障碍物（障碍物形状的y-最低点）大于a和b的最大y坐标+可以忽略移动物体半径的相同距离。类似于较低的y边界和x边界。而不是一个盒子，你可以进一步分支成两个（更多）盒子。例如，购买将a-b的距离分成两个距离并对（a，（b-a）/ 2），/（b-a）/ 2，b）中的每一个进行上述过程。
但这一切都取决于与碰撞程序相比，这些值的比较效率。
您可以简单地使用网格，其中每个单元格都容纳接触该单元格的所有障碍物。现在只检查胶囊接触的碰撞细胞。此外，您也可以使用四叉树，但根据我的经验，网格通常足够，并且还具有在障碍物移动时可以轻松快速更新的优势。
评论马丁的回答：
我做了一个像Box(a.x-R, a.y-R, b.x+R, b.y+R)的盒子，其中R是ObjectRadius + ObstacleRadius，然后放下不在这个盒子里面的每个障碍物。在图中，只会检查带有黄点的障碍物：
我可以推荐怪物曲线，例如希尔伯特曲线。它是像数据结构一样的四叉树或kd树，它将2d复杂度降低到1d问题。在每个帧中，您可以从开始构建怪物曲线，这样可以删除或插入四叉树或kd树。它还有一些更好的2d平铺属性，但在您的情况下可能不需要。
您可以尝试在代码中实现空间分区。通过将每个对象/障碍物划分为覆盖整个空间或地图的每个框。通过这样做，您可以将障碍分为几个部分。因此，只需检查一小部分内的碰撞，就可以大量减少碰撞检查。如果您的障碍物没有移动，您只需要为每个障碍物进行一次此分区。如果它们正在移动，则必须每次更新每个障碍物的分区[重新组合]。
空间分区技术已经存在了很长一段时间，这里有一个链接可以帮助您实现。