碰撞检测问题

Question

我的cocos2d-x是全新的。
从开发一个简单的游戏，这是像“飞机大战”

一个问题，当我实现了碰撞检测迷惑我刚开始。

• 假设球员的平面能火50+子弹每 时间。
• 超过50+敌人出现在屏幕上。
  

这意味着我必须做50 * 50次检测的每一帧，倍！ 比赛中的表现应该坠落

所以，我怎么能优化碰撞检测？

Answer 1

我不能说Cocos2d，因为我不使用它。但总的解决方案包括：

打破你的游戏世界分解成地区

例如将你的世界划分为100x100像素块。在每个对象的每个帧的开始处确定哪些块（注意复数）会重叠。如果你定期划分你的世界，这应该很便宜。将您的对象添加到每个块中的对象列表中。

接下来，再次运行您的对象，这次从块中读取。针对与对象重叠的任何其他对象重叠的所有其他对象进行测试。

更复杂的分割策略可能包括四叉树或kd树。如果你的世界已经内在地分裂了（例如，对于某些类型的快速碰撞或能见度计算，凸出的扇区），那么你可以经常搭载它。

迭代一起排序列表

选择任何尺寸你的世界是最长的一起。比方说，为了论证的缘故，它是宽于高的，而且你不想考虑对角线。

然后通过开始x位置来排序所有对象。

现在沿列表进行迭代。对于列表中位置为i的每个对象，请将其与i+1,i+2等中的对象进行核对，直到找到其最左边的x超出最右边的第一个对象。然后停止考虑i处的对象并允许循环滚动到下一个对象。你正在考虑的对象绝对不能与你停止检查的对象之外的任何对象发生碰撞，因为它们的最左边甚至更靠右。

这是极少数情况下插入排序可以是最快的排序，因为它是最优的 - O（n） - 如果应用于已经排序的列表，并且通常更接近最佳，列表越接近排序。在一个游戏中，你的对象排序可能在帧之间只有一点变化，所以如果他们排序的最后一帧，他们很可能接近排序这个帧。

不要那么直接跳转到昂贵的测试

这些都是广泛的相位检测策略，防止绝对不重叠的对象之间的比较。即使一旦你反对对象，你应该考虑在做一个精确的像素检查之前做一些广泛的东西。最简单的解决方案是包围球 - 制定出为每个对象一个中心和半径然后作为第一检查工作出来的两个中心之间的距离的平方（使用毕达哥拉斯但不超越所述距离的平方，以避免昂贵的方根），并将其与两个半径之和的平方进行比较。如果两个物体至少没有那么近，那么它们就不能重叠，所以你可以跳过更精确的东西。

根据你的成本和你的几何形状一般你也可以考虑凸包分离轴（特别是如果你有一个足够快的机制来缓存哪个轴分开的任何两个给定对象的最后时间）。