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

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

它是如此常见,几乎出现在除了<<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,那么这两个圆就没碰在一起,如果你是码农你可能会用 $d^{2}$ 和 $(r_1+r_2)^2$ 来比较,这样就可能不用计算一次可能更耗时的开平方,不过没关系,这无关痛痒,这仍然超简单的是不.没关系,显然大部分游戏中只有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,我们就需要计算 $\sum_{i=1}^{n-1}{i}$ 次碰撞,比如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中出现了一堵墙