游戏空间划分技术

【前言】

空间划分主要是为了降低搜索比较量，如果不采用空间划分，暴力遍历也是可以求解的，但耗时过长。通过空间划分将全局搜索简化为为局部搜索，大大降低搜索量。

搜索出来后最终还要是一一比较，比较的是距离（这里的距离通常指欧式距离），将当前点和目标点做距离计算。

在游戏中，存在静态和动态物体，动态物体可能会更改空间划分

【均匀网格（Uniform Grid）】

原理：将空间划分为固定大小的网格单元，每个单元记录其中的物体

划分方式：3D空间中可以去掉y方向，只按照xz方向做划分，xz一般等长；如果y方向高度差很大，也可以考虑增加y方向上的空间划分。

特点：

知道某个物体的位置，可以直接通过（x/xcellsize,z/zcellsize)计算出该物体所在的网格单元Id，继而可以得到单元各内的所有物体或者该物体的邻近物体
可以得到物体相对于网格单元中心点的位置
固定空间划分是不考虑物体的，因此，不同网格单元可能包含相同的多个物体
如果某一网格单元内的物体密集，仍需要遍历非常多的物体，效率降低
预先划分好空间后，不可以在运行时重新划分

应用：场景流式加载区域划分、地图特色区域划分、寻路网格划分

对存在动态物体的应用场景：

一是网格单元较大，动态物体始终在网格单元内；二是根据物体位置每帧动态计算所在网格单元Id，如果Id改变，做移除和添加操作

优点：实现简单，查询速度快

缺点：密集时效率低，无法动态调整空间、

拓展：层次网格划分

【四叉树（Quadtree）与八叉树（Octree）】

原理：递归细分空间（四叉树为2D四等分，八叉树为3D八等分），直到满足终止条件（如物体数量或深度限制）

划分方式：与二叉树作为对比，四叉树有四个子节点，八叉树有八个子节点，通常四叉树用于二维，八叉树用于三维

四叉树每次将空间四等分，根节点对应整个空间，第二层节点对应四分之一空间，第三层对应16分之一的空间，以此递归细分，当某个子空间满足终止条件时，将不再继续细分该子空间

特点与对比

四叉树只有叶子节点才会存储所包含的物体，中间节点不包含
同样的，由于等分空间，必然存在一个物体会同时处于多个子空间的情况
查询确定物体处于哪个空间时（即区域查询），每次都需要从根节点依次往下寻找到叶子节点。显而易见，比均匀网格的查询速度不是一个量级的
以数量作为终止条件时，可以保证物体密集时的搜索效率，对比而言，均匀网格在物体密集时效率低
四叉树叶子节点的空间大小与物体分布有关，物体分布密集，会有多个小空间，物体分布稀疏，会有一个大空间。在某些情景下，需要设置小的空间，对均匀网格而言，可能会存在非常多的没有任何物体的网格，这会导致内存浪费

应用：开放世界地形管理（四叉树）、3D场景的碰撞检测优化（八叉树）、视锥裁剪

四叉树的基本操作

插入：根据物体的位置，从根节点找到叶子节点，极为该物体所在的子空间，将物体插入该节点。在静态构建时，可以继续分割该节点。动态插入时，可以不分割，或该节点物体到一定数量再分割
删除：找到物体所在的节点，从节点中删除该物体。如果节点没有任何物体了，也可以删除该节点
查询：输入一个位置或区域，获取位置所属的子空间内的所有物体；或者查询某个区域内是否存在该物体
更新（修改）：动态物体的位置改变时，可以检查动态物体是否超出了当前子空间的范围，如果超出了，先删除，再重新插入

对动态物体：需要根据物体的所处的叶子节点做删除和添加操作，按照预先构建时的标准，可能导致叶子节点物体数量超过限制或过少，必须重新对子空间做划分或合并。

存在多个动态物体时，可能会导致四叉树部分节点不断重新构建，影响性能。

为了避免频繁的重建树结构，在运行时可采用松散的树结构:即调整叶子节点的划分和合并上下限，或扩散叶子节点的空间，允许重叠，以降低重建的频率

优点：动态适应物体分布，减少冗余计算

缺点：树结构维护成本较高，频繁更新可能影响性能

拓展：同二叉树一样,死叉树保持树的平衡，四叉树的查询效率才会更高。因此，在构建四叉树时，不必完全等分，可以根据空间内物体分布情况自适应划分，保证每个子空间内物体数量均等，以确保树的平衡。

开源实现：

https://github.com/Nition/UnityOctree

https://github.com/marijnz/NativeQuadtree

https://github.com/splitice/QuadTrees

【KD树（k-dimensional Tree）】

原理：沿不同维度轴递归分割空间，交替选择分割维度

划分方式：KDTree的最终目的是构建一个二叉树,每次选择维度是相当于将所有数据点划分为左右两部分，成为二叉树当前节点的足有子树。如果数据点是三维的，通常最简单的划分方式是按照xyz交替取中位数做分割点和分割方向：

将所有数据点先按照x轴坐标做排序，找到中位数，其所在的点是根节点Root，将数据分为左右两部分Left、Right,整体待分数据-1
分别对左右两个部分，按照y轴坐标排序，找到中位数据，其所在的点就是根节点的左右子节点，此后左边部分Left又可以被分为两个部分，右边部分Right也可以被分为两个部分，整体待分数据-2
对剩余的四个部分，按照z轴坐标排序，找到中位数，得到根据y轴排序找到的节点的左右子节点，整体待分数据-4。如果剩余部分只剩下一个数据，说明其就是子节点，不必再分。如果剩下部分没有数据，表明子节点为空。
循环按照xyz轴进行划分，直到待分数据为0

特点和对比：

因为是按照维度轴划分的，维度轴是互相垂直的，分割出来的是方形空间，如果是二维的，那么分割出来的空间就是矩形
可以高效查询多维数据
KDTree是以数据点为界限划分空间的，已知的数据点都位于空间边缘分割线上，二叉树的节点会包含数据点，而四叉树是以固定的间隔做空间划分的，只有叶子节点才会包含数据点。
KDTree的空间是所有数据点构成的空间，而四叉树是在现有空间再有数据
KDTree中任意数据点位置改为可能会导致重建，而四叉树允许部分数据点位置改变，也即KDTree重建成本更高
KDTree搜索到最后可以得到邻近的点，而四叉树得到的一堆点

应用：最近邻搜索和范围搜索；群体动态避障中搜索邻近会可能会发生碰撞的对象；AI获取周围一定范围内的可拾取物品；

对动态物体：动态物体位置改变需要重建

优点:高效的多维数据查询

缺点：动态场景中重构成本高

拓展：在二叉树中，左右子树尽可能平衡，高度尽可能低，搜索效率就越高。因此，在建立KDTree时，要尽可能保证树的平衡，其关键在与每个划分时选择哪个轴。不一定xyz的交替顺序，可以根据数据的聚合程度选择分隔轴

开源实现：

https://github.com/codeandcats/KdTree

https://github.com/mathnet/mathnet-spatial

https://github.com/jlblancoc/nanoflann

https://github.com/mariusmuja/flann

SciPy库的 cKDTree