游戏中碰撞检测分为两个阶段:broad phase 和 narrow phase。接下来要介绍的就是broad phase。在broad phase这个阶段,我们的主要任务是将屏幕上的物体进行筛选,筛选出最可能发生碰撞的物体集合。我们就需要一个这样的算法去将屏幕上可能和不可能发生碰撞的物体区分开来。
四叉树
四叉树是一个每个父节点都具有四个子节点的树状数据结构。我们将屏幕划分为四个区域,用于区分处于不同位置的物体,四叉树的四个节点正合适表示这四个区域。
方便起见将四块区域命名为象限一、二、三、四。
我们将完全处于某一个象限的物体存储在该象限对应的子节点下,当然,也存在跨越多个象限的物体,我们将它们存在父节点中,如下图所示:
如果某个象限内的物体的数量过多,它会同样会分裂成四个子象限,以此类推:
四叉树并不是一个碰撞引擎,它只是一种减少碰撞候选者的算法,所以在利用四叉树得到碰撞候选元素后,还需要去检测这些候选元素与目标元素是否发生碰撞
检索功能: 给出一个物体对象,该函数负责将该物体可能发生碰撞的所有物体选取出来。该函数先查找物体所属的象限,该象限下的物体都是有可能发生碰撞的,然后再递归地查找子象限...