您认为描述用于在 2D 环境中进行碰撞检测的算法或技术的最佳资源（书籍或网页）是什么？
我只是渴望学习不同的技术来制作更复杂、更高效的游戏。
borrego
问问题
8518 次
5 回答
14
Collision detection is often a two phase process. Some sort of "broad phase" algorithm for determinining if two objects even have a chance of overlapping (to try to avoid n^2 compares) followed by a "narrow phase" collision detection algorithm, which is based on the geometry requirements of your application.
Sweep and Prune is a well established efficient broad phase algorithm (with a handful of variants that may or may not suit your application) for objects undergoing relatively physical movement (things that move crazy fast or have vastly different sizes and bounding regions might make this unsuitable). The Bullet library has a 3d implementation for reference.
Narrow phase collision can often be as simple as "CircleIntersectCircle." Again the Bullet libraries have good reference implementations. In 3d land when more precise detection is required for arbitrary objects, GJK is among the current cream of the crop - nothing in my knowledge would prevent it from being adapted to 2d (but it might end up slower than just brute forcing all your edges ;)
Finally, after you have collision detection, you are often in need of some sort of collision response. Box 2d is a good starting point for a physical response solution.
于 2008-09-18T00:32:31.440 回答
2
就个人而言，我喜欢Paul Bourke的作品。
此外，Paul Nettle 曾经写过有关该主题的文章。他有一个完整的 3D 碰撞检测库，但您可能对这些库背后的想法更感兴趣（非常适用于 2D）。为此，请参阅使用 Ellipsoids 的游戏的一般碰撞检测。
于 2008-08-27T20:24:58.060 回答
1
Christer Ericson (ISBN: 1-55860-732-3) 的《实时碰撞检测》一书是最近 (2005) 的一本广受好评的书，它应该会给你一些很好的答案。
它从您需要了解的一些数学的基本入门开始，然后进入碰撞检测中常用的各种类型的边界体（球体、轴对齐边界框、定向边界框）。
接下来要讨论的是许多用于检测各种基元组合之间碰撞的算法，例如线、三角形、球体、多边形、平面、边界体积等。
同样重要的是涵盖了一些主要的空间划分和对象组织方法（体积层次结构、BSP 树、八叉树等）。这从本质上加快了碰撞检测，因为它允许您细分对象，这样您就可以避免对象之间不必要的比较（例如，我从我的数据结构中知道对象 A 距离对象 B 太远，所以我什至不会这样做距离检查）。
它还包括一些关于如何实际检查移动对象（间隔等）之间碰撞的内容，但请注意，尽管这是一本相当大的书并且涵盖了材料，但它是用于碰撞检测，而不是解决或响应。所以它将帮助您确定两个对象是否发生了碰撞，而不是真正如何处理它，即如何解决它。相交测试通常会为您提供做出此类决定所需的数据，但就编写求解器的一般问题而言，该求解器使用碰撞检测例程来检测碰撞，然后决定如何处理它们，这本书不包括那深入。
于 2008-09-02T17:53:24.820 回答
0
如果您的对象表示为 2D 空间中的点，您可以使用线交点来确定两个对象是否发生碰撞。您可以使用类似的逻辑来检查一个对象是否在另一个对象内（因此即使它们的任何一条线当前不相交，它们也会发生碰撞）。做这件事的数学很简单，任何基本几何的教科书都应该涵盖。不过，检测一个物体是否完全穿过一个物体可能会有点棘手。
于 2008-08-27T20:29:25.787 回答