collision-detection - 碰撞检测及其效率

Question

你究竟是如何实现碰撞检测的？所涉及的费用是多少？不同的平台(c/c++、java、cocoa/iphone、flash、directX)对计算碰撞有不同的优化。最后，是否有库可以为我做这件事，或者我可以为我选择的平台解释一些库？

据我了解，您需要遍历碰撞图并找到有问题的区域，然后将输入的事物(例如 Sprite )与有问题的区域中的像素类型进行比较。我了解非常基本的想法，但我不了解底层实现，甚至不了解更高级别的实现。似乎这种类型的检测或任何与此相关的检测都非常昂贵。瓷砖 map ？位数组？这些是如何从图像创建的(我猜是循环和做事)？

我问这个问题的原因是为了更好地了解幕后的效率并准确了解正在发生的事情。链接、引用或示例将非常有帮助。我知道这个问题有点冗长，因此非常欢迎任何帮助或引用。谢谢!

Answer 1

检查我的这个关于 simple bounding box collision detection 的答案.

碰撞检测是一个巨大的话题，但主要有两个领域。宽相位和窄相位检测。宽相位既快速又脏，如果通过，您将进入窄相位检测。窄相反过来更复杂，在深度检测中。即使在宽相位检测中检测到碰撞，物体也可能没有与任何物体发生碰撞。

在游戏中保持高效的关键是，如果你不需要，就不要工作。换句话说，如果您不必执行碰撞检测，则不要。我的意思是想象一个像 GTA4 这样的游戏。这太疯狂了，而且如果您要检查世界上的每个对象与其他对象，游戏就会像幻灯片一样运行。可以使用多种方法，但最好的方法是限制检查数量。这里通过使用 quad 来 split 世界/oct/binary/树或其他一些 spatial indexing算法。这意味着只检查附近的物体，因此游戏运行得更快，因为只检查可能的物体是否发生碰撞。

"How are these created from an image(I would guess looping and doing stuff)?"

是和否。每像素碰撞检测属于窄相位检测，成本较高。在大多数游戏中根本不需要它。拿一个通用的 FPS。如果你在双腿之间射击一个敌人，说，它有时被归类为命中，这不是像素完美的，但它的效果已经足够好了。

对于 2D 游戏，您会知道 Sprite 的大小，因此任何计算都将使用边界体积。 3D 游戏也是如此，只是这个边界体积现在是三维的。您可以将复杂的形状/模型分解为更多的边界体积。这个过程比检查像素要快得多。然而，有时需要逐像素检测。这一切都取决于游戏的类型。

至于好的链接，我会把你指向 Gamedev.net .这是一个很好的入门网站，应该涵盖广泛的主题。 nice tutorial ，向您展示可以应用的进一步概念是基于名为 N 和 N+ 的游戏的开发。总而言之，游戏是一种体验和幻觉。在任何时候，如果游戏程序员可以简化以加快开发或游戏速度，我们都会接受。