DBinary，画画的，专画可爱的东西 阅读原文 游戏里有一个即使是小学生也会做，但博士生都未必做的好的问题。 它是如此常见，几乎出现在除了<>外的所有的 FPS 游戏和绝大部分的 RTS 中。 如果你打游戏发现你的 CPU 烫得可以煎牛排，那么当中恐怕有一半的热量和这玩意多多少少有所关联。 它看上去真的超简单，我甚至不用堆些专业术语大家都看得懂，但在你没有真正把这玩意做出来之前，你对这玩意所述的一切算法和理论和不屑，都是在"云"。 说了那么多，那么这玩意到底是啥，其实真也不是啥高大上的东西，这玩意叫碰撞检测。简单来说，就是判断游戏里两个物体有没有碰撞。我们先来举个最简单的栗子 ObjectA 和 ObjectB 是游戏世界中的两个圆，如何判断它们有没有碰撞，你可能开始骂我了，因为只要长了眼睛就能看出来这两个圆没碰在一起。但可惜我们不能靠眼睛这么玩，计算机有计算机的玩法，当然，这仍然很简单。 设 Object A 的圆心坐标为（x1，y1）半径为 r1，设 Object B 的圆心坐标为（x2，y2）半径为 r2，然后我们计算圆心之间的距离 d 和 r1+r2，如果 d<=r1+r2，那么这两个圆毫无疑问是碰撞在一起的，如果 d>r1+r2，那么这两个圆就没碰在一起，如果你是码农你可能会用和来比较，这样就可能不用计算一次可能更耗时的开平方，不过没关系，这无关痛痒，这仍然超简单的是不。 没关系，显然大部分游戏中只有 2 个 Object 的情况毕竟是少数，显然我们需要考虑 2 个以上 Object 的情况，比如说 3 个： 那么，如何判断这三个 Object 相互之间有没有碰撞关系呢，其实这也不是事儿，比如说上面三个 Object，我们只需要依据两两碰撞的办法，分别判断 A 和 B，A 和 C，B 和 C 之间有没有碰撞在一起就行了，我相信很大一部分初学了 C 语言，想做一个弹幕游戏大部分就使用了上面这个办法。 但如果我们把 Object 数量加到 4 个，问题就来了。我们发现 2 个 Object 的时候，我们只需要计算一次碰撞判断，有 3 个 Object 的时候，这个计算增加到了 3 次，如果这个 Object 增加到了 4 个，那我们就需要计算 A-B，A-C，A-D，B-C，B-D，C-D 一共是 6 次碰撞检测计算。 当然，6 次对于计算机来说这并不算什么，依据这种算法碰撞次数如果游戏中有 n 个 Object，我们就需要计算 次碰撞，比如 101 个 Object 我们需要计算 100+99+98+97+……1，共计 5050 次碰撞，当然对 CPU 来说这仍然不算什么。但如果这个游戏是一个多人大型战场类游戏，你发现阵地上有 1000 发炮弹在到处飞时，你就可以闻到 CPU 的香气了。 当然，要解决上面这个问题依然不是什么很难的事情，比如下面这种情况，一个游戏场景中有 4 个 Object： 我们把整个游戏世界均等分为 4 份 显然，我们可以先给游戏世界里的 Object 分个类，首先 A 和 B 在第一个区域，C 和 D 在第 4 个区域，显然的，不同区域之间的 Object 显然是不会碰撞在一起的，于是，我们只需要 2 次碰撞计算就可以得出碰撞结果了。这个算法又叫四叉树碰撞检测算法，按树结构的理解是，我们建立了一个有四个子节点的树结构，然后把游戏里的对象划分进去，没关系，反正其算法的原理大致就是一个分治的思想，不管怎么说，这确实很好地优化了碰撞检测的时间复杂度。 到这一步，你呵呵一乐，就这？也没见多复杂啊，放心，相当一部分码农的理论也就到了这一步，所以成就了很多的"云码农"，坐好，现在我们开始加速了。 某天你和你的基（姬）友相约上线吃鸡，图上每一个圆点代表着一个人，显然区域 4 肥得流油导致很多玩家纷纷下饺子，那么这个时候，四叉树分割的算法显然就不能发挥其最大的优势了，毕竟大部分的节点都分布在了区域 4 中： 你说，这好办啊，兵来将挡水来土掩，我们对区域 4 再进行一次四叉树分割不就好了 你看，问题很好的解决了，这不也没啥大不了的不是，你甚至表示如果区域 4 里的 object 再多一点，你可以再分一次 当你说到这句话的时候，你恐怕现在心里也有点发虚了，因为你注意到上面的分割算法中，有些 Object 是横跨了多个区域的 就比如上图中两个用蓝色框框框出来的那两个 Object，它们横跨了两个区域，这也就意味着，你必须对这两个 Object 进行分片。也就是说，四叉树的多个叶子需要同时存储这个 Object 的节点，实际上四叉树算法看上去很美，实际上对 Object 的分类实际上也是做了一次碰撞检测，当然横跨 2 个区域的情况并不是那么极端，假如现在一个玩家他变身成了奥特曼，变成了一个无比庞大的 Object（如下图的蓝色区域）： 你发现，这个时候四叉树的优化对这个节点毫无作用，你还需要承担这个节点分割带来的额外性能开销，出现了一个负优化的结果，那么这个时候你该怎么办呢？这个时候恐怕有人会说，把这个那么大的 object 存储在四叉树的父节点不就行了，我们不分片，只要这个 Object 占据了所有子节点的区域，那么就将它存储在父节点中。 当然，如果只是"云代码"的话，上面的处理是成立的，但是实际要做的话，上面的处理是沙雕的，没法搞的，纸上谈兵的。因为在四叉树的分类中，节点是一个一个添加进去的，你无法控制这个四叉树什么时候会进行进一步的划分，比如上面这个蓝色 Object 现在它当然占据了整个地图的所有节点，但是当最右下角的区域出现越来越多新的 Object 不得不进行进一步分片时，你就会发现这个蓝色的 Object 在父节点中待不下去了。 好了，一旦出现这个情况，这个大型 Object 不再能待在覆盖所有子节点中的父节点了，你将不得不再对这个大型的 Object 进行一次额外开销的分片计算，然后再将它重新分发到各个子节点中。如果这种非常大的 Object 还很多的话，你发现你还不如一开始就将它进行分片呢。但这个办法并非不可取，如果你知道你游戏里这种比较大的 Object 并不多，这种父节点存储法也许真能对碰撞的复杂度进行优化，所以这仍然是我们说的，不同情况不同考虑，真以为四叉树就长这个样能解决所有的碰撞处理算法，抱歉，不存在的。 好了，到这里现在开始，碰撞检测我就要只提问题不说解决办法了，为啥，因为难啊，不同情况需要依据游戏的情况进行不同情况的优化，我只是向你展示的是，碰撞检测并不像看上去那么简单。它仍然存在一堆问题需要你去解决。 那么我们再举个栗子： 问，上图中现在 ObjectA 是一个子弹，ObjectB 是一个怪兽，ObjectA 和 ObjectB 发生了碰撞，碰撞了几次？ 你可能很疑惑为什么我问了这样一个问题，但它确实是四叉树分片带来的又一个问题，如果 A，B 进行了分片，那么首先在分片过程中，A 和 B 因为分片同时存在了四叉树分割的两个区域中，这意味着在四叉树的最终计算结果中，它将在两个不同的区域都发生了碰撞，碰撞了两次，如果不将重复的碰撞结果进行剔除，那么，这个怪兽将会承受这个子弹带来的双倍伤害，当然怪兽这样都得偷着乐了，要是子弹和它刚好在四叉树的中间区域也就是横跨了四个区域，那么它将承受因为四叉树优化带来的四倍伤害。那么，你会如何剔除重复碰撞呢，当然，你得好好想想这个问题，不然你的四叉树优化，可能又是个负优化。 截至目前，你看虽然我们讨论的是碰撞检测，仅仅一个四叉树就带来了那么多乱七八糟的问题了，没关系，我们现在讨论的还是算法方面的，如果你实际操刀写代码的话，你有没有想过四叉树是一个动态的结构，我们如何给四叉树的节点分配内存呢， malloc？new？ 用了你就傻了，如果一个游戏里有 100 个 object，那么创建四叉树结构至少需要 100 次分配节点，这也就意味着你很可能需要向系统申请 100 次节点的内存，然后再用 100 次 delete 或者 free 释放掉，真的，你还不如不用四叉树呢，内存的分配与释放，可能比你直接计算碰撞还要慢，而且还能带来一堆内存碎片和缓存命中带来的一堆问题。 于是你不得不重新接管内存的管理方式比如使用一个内存池来对这个四叉树结构进行管理，得，我们成功将碰撞检测这一个算法上的问题上升到了内存管理上的另一个问题，而且这两个问题你都得好好解决。因为不同类型的游戏，类似上面四叉树的空间划分算法还有很多，同时也带来了更多海量的问题， 你会发现你很难找到一个万金油类型的碰撞检测算法，依据这个游戏的不同，你得分类考虑，然后在性能与游戏体验上找到一个平衡点，当然目前很多的游戏引擎并不需要你考虑这些碰撞算法，显然的，如果使用通用的算法，你就得在性能与空间上付出点代价。 到这里你可能吐了一口气，原来还真是有些麻烦啊，抱歉，上面的东西考虑的只能说是凑活能用，其实只是冰山一角。 因为游戏世界里的 Object，不是长的都是规规矩矩的一个圆。 有这样的： 还有这样的： 当然，不规则几何的碰撞检测还只是"碰撞检测"，还没上升到"碰撞"问题的处理上来，比如隧穿效应和 PUBG 里的名场面粘滞效应。 现在我们再来聊聊游戏世界是如何运行的，游戏世界的时间和我们现实世界的时间有所不一样，例如一辆汽车在高速公路上飞驰一秒钟，那么你可以得出它在 0.12345 秒时，这辆车的位置与状态，但如果这辆车跑在游戏世界中，这恐怕就办不到了。 在游戏世界中，时间是离散的，一个称作游戏循环的逻辑结构控制着游戏世界的运行，一个称作时间粒度的变量是游戏世界时间运行的最小单位，在大多数情况下这个单位不会被进一步的细分。 在每个游戏循环中，会对游戏世界中的每一个对象进行一次更新（当然有时会对视口外或一些静态对象优化），举个栗子，如果游戏世界的时间粒度是 10ms，那么，游戏世界将会计算 10ms，20ms，30ms……时游戏世界中对象的状态。 正因为这种运行方式，你会发现游戏世界的模拟并不能直接使用一些连续的函数来描述，例如游戏中弹道的计算或者抛物线方程，在游戏世界中未必好使，这类方程在现实中计算十分方便，毕竟我们可以直接用微积分等手段来计算出具体时间时的位置，速度，但在游戏中引用这类方程大多控制不便不利于优化设计复杂，这涉及一个将连续函数离散化的问题，因此，在一个游戏循环中，比如 10ms-20ms 这段时间里，在游戏世界中我们大多将这段时间的受力或者速度当做一个恒定的值因此你会发现，如果你要控制一个物体做抛物线运动，其最终的落点和你使用抛物线方程的落点最终会有所不一样，可以这么说，尽管 PUBG 游戏如何宣称这是一款真实的物理引擎，其最终都只是一个广告词，它与真实世界的模拟仍然有诸多的差别。 这类离散的差别也导致了一些很有意思的 bug，其中一个便是遂穿效应，例如在上面的图中，10ms 和 20ms 中出现了一堵墙。 那么，这个碰撞根本不会发生，就好像汽车穿过了这堵墙一样，如果要避免这种情况，要么把墙体的宽度变宽点，要么就减少时间粒度比如控制在 5ms。 放大墙体宽度 减少时间粒度 但正如你所知道的一样，因为每次循环都需要对游戏中所有需要更新的物体进行一次计算，因此，减少时间粒度所耗费的性能损耗往往是非常明显的，在大多数情况下，游戏设计人员会刻意减少游戏里物体的速度或者说使用第一种办法把物体做的厚一点。 另一个很有意思的 bug 是粘滞，这也是碰撞检测方面的 bug，在众多即使是 3A 大作的游戏中，这个 bug 也非常的常见并且优化困难，避免需要耗费巨大的代价，我们同样举个栗子。 在上图中，一辆车装上了一个球，因为时间粒度关系，当碰撞发生时，车已经嵌入到球当中了，这个时候碰撞已经发生，按照"真实的物理引擎"计算，车应该受到一个立即的反作用力，并速度方向应该立即变为反方向： 但是，因为碰撞存在能量损失，因此，回退的速度会比撞击时的瞬时速度更慢，导致了在下一次游戏循环时，车仍然没有脱离球的范围，这导致了物理引擎认为，车第二次撞上了球（实际碰撞只发生了一次），于是车又改变了速度方向，再次撞入了球，因为速度再次衰减，所以车就和这个球粘上了，如果两者状态不改变将并永远不会脱离： 这就导致了两个物体黏在一块，两边反复抖动，最终导致了神奇的鬼畜现象，如果碰撞是有伤害的，那么就会导致粘滞发生后不久就会瞬间爆炸： 出自天天吃鸡 出自天天吃鸡 写了那么多，但其实碰撞检测有关的东西远不止上面说的那么点，游戏引擎开发的事儿，说多了都是泪，很多东西看上去很简单。但经验告诉我常常是理想很丰满现实很骨感。在做出来之前一切的感觉只是感觉。 阅读原文
