2.7.4　四叉树搜索算法

四叉树搜索算法类似二叉树的多维度版本，类似在一维数组上将数组分成4部分进行查找，但也仅限于此。四叉树的理念是空间划分，把一个二维空间划分成多个部分来存放，它的数据结构与二叉树一样，只是扩展了子节点的个数，每个节点有4个子节点，这4个子节点代表父节点的4个象限区块，4个子节点加起来代表完整的父节点，以此类推，每个节点可以有子节点，一旦有就得4个一起有，除非是末尾的叶子节点，这就相当于是一个完美二叉树的变形，即完美四叉树，我们可以用一个数组来表示完美四叉树的结构。

在实际运用中，四叉树主要运用在2D平面空间的搜索上，虽然其他领域也有用到，但平面上空间划分更适合它。我们可以把一个2D矩形平面想象成4个大小相等的矩形，共有4个子节点，就共有4个矩形方块，其中子节点即这4块中每块又再次分成相等大小的4块，直到分到定义的最小块为止，最小块大小可自定义，这样就将一个大的平面矩形划分成了都能用四叉树表示的结构，每一块都有自己的父节点和子节点。

使用这样的数据结构表示一个平面里的所有方块内容，好处是能牢牢掌控每个小平面里的内容变化。当有元素加入这个平面，即加入这个四叉树的数据结构中时，会先计算它的坐标在树中的索引，这就相当于在四叉树中搜索某个节点，从最大4块的x、y大小范围开始依次往下推导，直到推导到最小区块的节点上为止，这样就能得到该坐标所在的节点。

形成四叉树数据结构后，就可以根据这个数据结构查找节点上的元素了。比如在某个位置上可以查找到与它在相同块内的所有其他元素，即给出某个坐标后，就能根据四叉树以此类推，最终找到最小块的那个节点，这样就可以获取该块上所有其他元素的信息。我们可以想象，使用这种四叉树的方式把地图分成3级，每级4块矩形图上都保存着相关元素的信息，这样就可以快速从1、2、3级地图上得到某方块内所有元素的信息。

四叉树在游戏项目中的用法包括二维平面上的有效碰撞检测搜索范围、地形的有效展示范围、在地图上查找某方块上的人或事及二维平面的寻路网格构建等。