计算机游戏中的碰撞问题

Question

我有一个关于电脑游戏中检测粒子（或物体碰撞）的技术或方法的一般性问题。即使在像当前流行的愤怒的小鸟这样的简单示例中，程序如何实现游戏知道一个物体击中另一个物体并计算出其轨迹，同时该物体可以击中其他物体等等。我认为它不是不断检查游戏地图中所有对象的状态......感谢任何提示/答案，对于一个小白/通用问题很抱歉。

- Bober02

---

哇哦，太棒了，我以为这是一个相当愚蠢的问题，但它似乎引起了一些兴趣。非常感谢所有回复。 - Bober02

Answer 1

游戏，如愤怒的小鸟，使用物理引擎来移动物体并进行碰撞检测。如果您想了解更多有关物理引擎如何工作的信息，一个很好的起点是阅读Box2D。我不知道愤怒的小鸟使用的是哪个引擎，但Box2D被广泛使用且开源。

然而，对于较简单的游戏，您可能不需要物理引擎，因此碰撞检测相对简单，包括两个部分：

---

首先确定要在哪些对象之间进行碰撞检测。对于许多小型游戏来说，测试每个对象与其他所有对象的碰撞并不是一个坏主意。虽然你的问题对这种蛮力方法有所顾虑，但计算机非常擅长处理这种例行数学运算。

然而，对于更大的场景，您需要筛选掉那些距离玩家太远而无关紧要的对象。基本上，您将场景分成几个区域，然后首先测试角色所在的区域，然后测试该区域中的每个对象是否发生碰撞。

一种执行此操作的技术称为“四叉树”。您还可以使用二进制空间分割等其他技术。在这两种情况下，场景被分成许多较小的部分，您可以使用它们来组织场景。

---

第二部分是检测两个特定物体之间的碰撞。最简单的方法是通过距离检查; 只需计算两个物体之间的距离，如果它们足够接近，则它们会发生碰撞。

另一种简单的方法是在要测试的对象周围构建边界框。只需比较它们的坐标，就可以轻松检查两个框是否重叠。

现在，边界框只是矩形; 如果要碰撞的形状由任意多边形表示，则此方法可能变得更加复杂。通常，基本的几何知识就足够了，尽管全功能的物理引擎可以进一步详细地告诉您不仅发生了碰撞，而且还在何时以及如何发生了碰撞。

- num1

Answer 2

这是一个很难回答的问题，但这里有一个非常基本的二维伪代码示例作为一个非常基础的例子。

for-each sprite in scene:
  for-each othersprite in scene:
    if sprite is not othersprite & sprite.XY = othersprite.XY
       collision = true;
    else
       collision = false;

希望这足以激发你的思维！

补充说明：其他改进之一是假设XY周围的区域而不是精确位置，这样可以为具有大面积精灵的支持提供一种支持。

关于3D理论，我会给你一篇我之前读过的文章：

http://www.euclideanspace.com/threed/animation/collisiondetect/index.htm

- Russ Clarke

---

这将是一个O(n^2)算法，基本上还好，但我建议使用排序算法来加快速度，通过根据y或x进行排序，并仅检查周围的m值（在x+-width大于0时中断m）。这将在有很多精灵的情况下表现更好，尽管根据存储精灵的方式，可能会花费O(n^2)空间。 - LoveAndCoding

哦，绝对没错。我并没有说它很好或者非常高效，只是想给出一个实现的提示。 - Russ Clarke

这绝对是一个很好的起点。我以前用过那段代码来快速解决低精灵计数的问题。+1 - LoveAndCoding

Answer 3

num1的回答涵盖了我想说的大部分内容，因此我投了赞成票。但是还有一些修改/额外要点：

1）包围框实际上是测试碰撞的第二种最容易的方法。最简单的方法是距离检查；只需计算两个对象之间的距离，如果它们足够接近，则它们会发生碰撞。

2）为了优化碰撞测试（即BSP的替代方法），另一种常见的组织场景的方式是四叉树。在任何情况下，基本上您将场景分成区域，然后首先测试角色所在的区域，然后测试该区域中的每个对象是否发生碰撞。这样，如果关卡非常大，您不必针对关卡中的每个对象进行测试；您可以剔除太远离玩家而无关紧要的所有对象。

3）我更强调Angry Birds使用物理引擎来处理其碰撞。虽然距离检查和包围框对于大多数2D游戏来说都可以，但Angry Birds显然没有使用这两种简单的方法，而是依靠其物理引擎进行碰撞检测。我不知道该游戏使用的是哪个物理引擎，但Box2D被广泛使用并且是开源的。

- jhocking

---

这太棒了。你能否编辑我的答案，包括这些信息，并将其转换为社区答案？我还不太擅长这个stackoverflow的东西。 - num1

我无法将您的答案设为社区维基，只有您或管理员可以这样做。如果您在帖子底部点击“编辑”按钮，那么您会看到一个社区维基的复选框。当您勾选它后，我会将此额外信息编辑到答案中。 - jhocking