四叉树优化碰撞检测

对于简单的2D游戏，碰撞检测在游戏开发是一个极其重要部分

如果暴力的去逐帧遍历所有的对象来检验碰撞，由于对象因场景而定可能非常多，在那种极端情况下执行效率有多低可想而知,即O(N^2)

就我们肉眼来看，假设游戏中只有主角一个角色，而其他的对象实体仅仅是偶尔会碰到的路障，其他部分仅仅是贴图，如果我们逐帧的检测所有对象是不是有些没必要？

因此，一种很容易就能想到的优化碰撞检测的方法就是减少不必要的需要碰撞检测的对象，以减少计算量

基于以上目的，我们需要对2D平面内的对象进行划分，以区分是否需要进行碰撞检测

在这里我们引入四叉树的概念

和上图所示一样，对于二维平面，我们将他分割成四个象限，每个区间都有一定的节点容量(容量指对象个数)，当节点容量达到最大值后，节点递归的再划分成四个子象限

对于某个对象，我们将之插入某点时，首先会查询当前区域是否存在子区，如果存在的话再递归的查询直至不存在子区，将之插入该区域(其实有点类似与从属的感觉)

对于碰撞检测，我们逐帧的检测目标对象所属区域象限下的所有的其他的对象

我们很容易得到结论，这是一种牺牲空间以换取时间效率的方法，不过在时间性能上的优化足以忽略空间性能的让步