碰撞检测问题

Question

我是cocos2d-x的新手。

从开发一个简单的游戏开始，就像的“飞机战争”

当我实现碰撞检测时，有一个问题使我感到困惑。

• 假设是玩家的飞机，每次都可以发射50+子弹。
• 比50+敌人更多的是出现在屏幕上。

这意味着我必须做50 * 50倍检测每帧，2500倍！比赛的表现应该是下降..。

那么，如何优化碰撞检测呢？

Answer 1

我不能和Cocos2d说话，因为我不使用它。但一般的解决办法包括：

将您的游戏世界分解为区域

将你的世界分成100×100像素块。在每个对象的每一个帧的开头，计算出它重叠的块(注意复数)。如果你经常分裂你的世界，那应该很便宜。将对象添加到每个块中的对象列表中。

接着，再次遍历对象，这一次从块读取。测试与任何其他对象重叠的所有其他对象。

更复杂的划分策略可能包括四叉树或kd树。如果你的世界已经从本质上被分割开来(例如，对于某些类型的快速碰撞或可见性计算，你可以分成凸扇区)，那么你通常可以从这一点出发。

沿着排序列表迭代

选择任何你的世界最长的维度。为了论证起见，我们假设它比高得多，而且你不想费心去想对角线。

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

现在沿着列表进行迭代。对于列表中位于i位置的每个对象，请对照i+1、i+2等处的对象进行检查，直到到达最左边x位于最右侧的第一个对象为止。然后停止在i上考虑对象，允许循环滚到下一个对象。您正在考虑的对象绝对不能与您停止检查的对象以外的任何东西发生冲突，因为它们都有最左边的边沿，甚至在右边。

这是一种罕见的情况，插入排序可以是最快的排序，因为它是最优的- O(n) -如果应用到已经排序的列表，并且通常更接近最优，列表离排序越近。在一个游戏中，你的对象排序很可能只会在帧之间变化很小，所以如果它们是最后一个帧排序的话，它们很可能接近于排序这个帧。

然后不要直接跳到昂贵的测试

这两种方法都是广泛的阶段检测策略，可以防止在绝对不重叠的对象之间进行比较。即使你是对象对对象，你也应该考虑在做一个精确的像素检查之前做一些宽相位的事情。最简单的解决方法是包围球体--为每个物体求出一个中心和一个半径，然后作为第一次检查，计算出两个中心之间距离的平方(使用毕达哥拉斯，但不要超过距离的平方以避免这个昂贵的平方根)，并将其与两个半径之和的平方进行比较。如果这两个对象至少不是那么接近，那么它们就不能重叠，所以您可以跳过更精确的内容。

根据您的成本和几何的一般形状，您还可以考虑凸壳和分离轴(特别是如果您有足够快的机制来缓存上一次将任意两个给定对象分开的轴)。