游戏中有哪些看上去很简单，但实际上需要极高技术力或是极高成本的细节？ 第1页

游戏里有一个即使是小学生也会做,但博士生都未必做的好的问题.

它是如此常见,几乎出现在除了<<nekopara>>外的所有的FPS游戏和绝大部分的RTS中.

如果你打游戏发现你的CPU烫的可以煎牛排,那么当中恐怕有一半的热量和这玩意多多少少有所关联.

它导致了海量的bug,包括但不限于五毛特效级别的穿模,人物或别的物体奇怪的舞蹈及鬼畜,血条消失术及瞬间移动和突然上天,都是因为它难以处理或处理不好.

但它听起来看上去真的超简单,我甚至不用堆些专业术语大家都看得懂,但在你没有真正把这玩意做出来之前,你对这玩意所述的一切算法和理论的不屑,都是在"云".

说了那么多,那么这玩意到底是啥,其实真也不是啥高大上的东西,这玩意叫碰撞检测.简单来说,就是判断游戏里两个物体有没有碰撞.我们先来举个最简单的栗子

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也非常的常见并且优化困难,避免需要耗费巨大的代价,我们同样举个栗子

在上图中,一辆车装上了一个球,因为时间粒度关系,当碰撞发生时,车已经嵌入到球当中了,这个时候碰撞已经发生,按照"真实的物理引擎"计算,车应该受到一个立即的反作用力,并速度方向应该立即变为反方向

但是,因为碰撞存在能量损失,因此,回退的速度会比撞击时的瞬时速度更慢,导致了在下一次游戏循环时,车仍然没有脱离球的范围,这导致了物理引擎认为,车第二次撞上了球(实际碰撞只发生了一次),于是车又改变了速度方向,再次撞入了球,因为速度再次衰减,所以车就和这个球粘上了,如果两者状态不改变将并永远不会脱离

这就导致了两个物体黏在一块,两边反复抖动,最终导致了神奇的鬼畜现象,如果碰撞是有伤害的,那么就会导致粘滞发生后不久就会瞬间爆炸

写了那么多,但其实碰撞检测有关的东西远不止上面说的那么点,游戏引擎开发的事儿,说多了都是泪,很多东西看上去很简单.但经验告诉我常常是理想很丰满现实很骨感.在做出来之前一切的感觉只是感觉

毕竟: 少说废话,放码过来

放个广告，欢迎游戏开发大佬入驻

@DBinary 大佬回答了关于游戏世界中碰撞问题所引发的各种 bug，我在几天前编了台球的程序，全部遇到了……

基本思路

我并没有按照拉普拉斯妖（ ）的方式编写程序：给定台球桌上所有球的位置、动量，然后一次性预言接下来一切的运动，直至所有球速度为零（由于摩擦力），然后继续下一杆球的撞击…… 我没有这么大的野心。 我采取的思路非常简单粗暴，设置“普朗克时间”、“普朗克长度”，然后使用非常局部性的判断：如果两颗运动的球（至少有一者速度不为零），相距小于所谓的“普朗克长度”，那么我们就判断为两者发生碰撞。依据人视觉的暂留效应，使用 、、 等初级绘图函数快速绘图的方式，实现动画效果，其中的时间间隔为 左右，此即为“普朗克时间”。

优缺点

优点是算法上容易实现，效果还可以，相对来说比较丝滑。只是 说实话运行速度一直为人诟病，所以遇到“多球运动”还是免不了慢下来。另外，由于“普朗克时间”内的运动的不确定性——在这个短暂的时间间隔内，复杂的运动是无法判断的，并且可能会发生碰撞时间先后颠倒的错误，但是我们都不得而知。感觉这个很类似于量子力学中的“测不准原理”。 不过，即便按照拉普拉斯的哲学理念去编写程序，由于计算机自身天然的离散性（或者干脆说量子性），截断误差依然会影响桌面小球的运动，并且随着运动的复杂性增加，误差是不可避免的。 所以，更完美的思路，既不是鼠目寸光，也不是高瞻远瞩，而是取其中道。不过，我本来就是一个玩家的心态，就不挑战这一艰难的任务了。 这个程序还是有一点点 ，这个在诸位玩耍的时候慢慢体会吧（邪魅一笑~）

注：其实这个 就是 @DBinary 文中所写“鬼畜碰撞”，我称之为“量子纠缠”。

感想

我和以前云大师弟 @littleNewton 探讨了这个问题，大佬的一句话高度概括了此类游戏的： 台球游戏简直是计算机格论发展史的缩影。 （原话大概如此，我先记录下来，后面确认一下） 师弟顺便和我介绍了计算机领域的圣杯级别的问题 、 、 ……原来这不仅是我的困惑，也是计算机几代人的困惑。作为外行人的我感到受益匪浅。后来我们由聊了聊很多学习方面的困惑，学科之间的分野、数学证明的执着等等。 谈话中间，我半开玩笑地说： “说不定我们这个世界也是一段使用相同算法的程序呢。”

哦对了，原贴里有代码——

---

  luo-cheng-11-75 网友的相关建议: 
      

我说一个简单的：角色怎么样自然地走路？

在Motion Matching这个技术发展成熟之前，我们大部分的游戏中角色动作都是由状态机决定的，什么叫状态机呢？状态机就是我们预先定义了一些节点作为状态，比如跑，跳，下蹲，发呆。当我们传进用户输入的时候（比如按下了跑的按钮），那么角色将从一个状态转移到另一个状态，这个输入称为状态转移函数，也就是我们预定的一些规则，比如当角色在发呆的时候，按下跑的按钮，角色就转换为奔跑的状态。这张图是一个简单的角色移动的动画状态机：

看起来似乎还不错也挺简单的对吧？那么问题在哪里呢？

第一，当角色动画从一个状态转移到另一个状态的时候，怎么样产生一个平滑自然的动作过度？传统的状态机方法，往往是在当前状态到目标动作间，创建一个简单粗暴的线性插值，又或者直接停止当前动画的片段播放，转而播放目标动作的动画片段。这两种方法都会产生一个问题：角色动作非常生硬。比如角色上一秒正在向前奔跑，玩家突然按下了后退键，这时候角色应该如何行动？真实世界中的人可能会先伸出一只脚刹停，然后转身，再反向发力奔跑。但是如果使用动画状态机，往往角色的动作并没有这个过度，而是一瞬间从向前跑变成了向后跑的姿势，这就是角色动作中不自然的地方，玩家或许说不上来为什么，但是他们感觉得到。

第二，当角色的动画状态增加的时候怎么办？根据我们前面的描述，状态转移函数其实是人为指定的规则，当状态增加时，也就意味这新的规则需要被传入，比如我们自然而然的知道，人跳在空中的时候，是不能转移到奔跑状态的，而是要先落地，但是这些规则计算机并不知道，所以需要人为指定，假设一个游戏中，角色除了发呆，奔跑，跳跃，还有爬墙，甩绳子，开枪，拳击这些状态（通常的第一人称类游戏，往往都有不下几十个状态），那么理论上设计者需要考虑任意两个状态之间有无转换，如何转换，那么其设计的复杂度会迅速提升，于是动画师就需要浪费大量的时间用于制定这些运动规则。

育碧最早开始了motion matching的尝试，所谓motion matching，其核心思想是，不再人为指定角色动作之间的转换，而是单纯地指定目标动作，而从当前动作到目标动作之间的插帧，则由计算机从动作数据库中自动找出一个最佳匹配，或者根据已有的动作数据，基于插值生成一个新的，最合理的动作。那么如何衡量一个动作的合理性呢？这里我们可以引入非常多的“约束”，这个“约束”可能是基于用户的输入（比如按向后跑的键，强制要求角色掉头）；可能是角色当前的速度、加速度；可能是角色的IK（反向动力学）数据（比如一个角色正在上楼，下一个动作脚尖必须贴在楼梯地面上）；可能是物理引擎的碰撞检测反馈（比如下一秒角色碰到了一个比较矮的栏杆，必须低头才能通过）。

如果我们把角色身上所有骨骼最终的位置、朝向看作一系列的变量，上面提到的约束看作是这些变量组成的等式或不等式，将基于动捕录制好的所有动作张成的线性空间看作这个约束的解空间，那么这个问题就变成了对于有限个变量和约束条件，在解空间内搜索最佳解的问题。于是动画师们基于经验去指定规则的方案，就变成了一个纯粹的数学物理问题。

我们来看看基于motion matching这一思想实现的角色动作：

即使是怎么走路这么简单的问题，为了解决好也仍然需要大量的努力。所以真正了不起的技术往往都藏在这些不起眼的细节中。

=================================================

补充一篇今年Siggraph 2020的新paper^[1]，仍然由育碧带来。这次育碧尝试了把神经网络和传统Motion Matching方案结合起来，在Motion Matching的基础框架下，把其中某些步骤的计算（需要消耗大量内存和计算量的）通过trained NN kernel来替换。这样既保证了学习的启发性（大量减少训练时长，同时保证结果的可预测性），又能够加速运行时的速度，减少存储开销。

具体视频效果看这里：

参考

1. ^LEARNED MOTION MATCHING https://montreal.ubisoft.com/en/learned-motion-matching-2/

---

  huang-xiang-38 网友的相关建议: 
      

从道理来说，早减晚增本身是没啥毛病的，毕竟只是个选项，丰俭由人。

大家怕的是某些人通过这些选项，再加点私货。而且这个说法和推迟退休一起出来，由不得大家多想。

按照目前的舆论情况，如果你敢允许早退减拿，估计只要不在体制内的人就统统早退了，反正也没啥规定领了社保就不能接着打工，对吧？甚至还可以把原来交给社保的那块放自己口袋。

所以，让你早退减拿是不可能的，忽悠大家晚退多拿的可能性比较大。

---

  gameDogHu3 网友的相关建议: 
      

女王:求求题主放过我，我可不敢有什么政绩。。。

---

  lancelu 网友的相关建议: 
      

商场运营方的本质是物业公司，

想各种办法吸引人流过来，接着招商，目的是收取租金，然后涨租金。

所以这个问题的本质，是来福士想要吸引的大批顾客群体，他们是不是在意棒棒入内。

如果他们其实希望棒棒不入内，那么来福士不过是个手套防火墙而已，抵挡了来自网络和外界的骂名。

如果他们反对禁止棒棒不入内，那么就算没有这个报道一段时间后来福士自己也会被用脚投票的顾客教做人。

商场是否以为棒棒影响了形象不重要，最终用户怎么想的才重要，想想谁掏钱？

所以，到底是顾客有这样的需求而商场才这么去干？还是商场自以为是的猜测了顾客的需求呢？这只有顾客自己知道了。

---

---