KD树的应用与优化

Tim's Blog

在一张地图上，有600多个单位，每个单位之间都需要独立寻路，检测碰撞和寻找最近的敌方目标。当这一切需要在手机上流畅运行并尽可能快的在服务器进行模拟时，最简单的平方算法5,4已经不能满足需求。

怎样减少计算的复杂度呢？

通过观察，可以发现，在地图左上角的单位根本无需和地图右下角的单位进行碰撞检测，因为它们离的太远了。

所以，通过对战场进行空间划分，可以避免大量的无效计算。

一种简单的划分方法是，将战场沿着横纵坐标划分为7,2的格子，只对在相同格子内的战斗单元做碰撞检测。

这种方法在大部分情况下简单有效，然而有以下几点问题：

1. 当格子边长太大时，假设很多单位都聚集于一个或少数几个格子中，其实空间并没有有效划分
2. 当格子边长太小时，一个格子内的单位可能太少了，也不能对空间进行有效划分
3. 如果不查找附近的几个格子，可能或错过附近格子可能距离更近的单位
4. 这种方法的空间复杂度是，在格子数很多的情况下，内存开销会很高

KD树k−dimensionaltreek−dimensionaltree，也可称之为K维树，可以用更高的效率来对空间进行划分，并且其结构非常适合寻找最近邻居和碰撞检测。

对于2维空间，KD树可称为2D树，因为空间只有两个坐标轴；对于3维空间，KD树可称为3D树，空间中有三个坐标轴；以此类推……

对于不同维度的空间，KD树的构建思路完全一致。下面以二维空间为例。

KD树的本质是一个二叉树，即一个根节点，划分为左子树和右子树。所以KD树的构建无非是两个问题：根节点的选择，左右子树的划分规则。

以下是KD树的构建过程。

1. 选定一个轴，比如X轴，选择这个轴上的中位数的所在点为根节点
2. 所有X比中位数X小的，都划分为左子树；反之，则划分为右子树
3. 对于左右两个子树，重复第一步，但是需要把划分轴换成另外一个轴（Y）继续
4. 重复以上过程，直到所有点都加入KD树中

以上图举例，第一步对X轴进行划分，点7,2的X坐标7为所有X坐标的中位数，其被确立为根节点；X坐标比7小的点5,45,4、2,32,3、4,74,7被划分到左子树；X坐标比7大的点9,69,6、8,18,1被划分到右子树。

对于左子树5,4、2,32,3、4,74,7，对它们的Y轴进行划分，点5,45,4的Y坐标4为所有左子树的Y坐标的中位数，其被确立为左子树的根节点；Y坐标比4小的点2,32,3被划分为左子树；Y坐标比4大的点4,74,7被划分为右子树。

对于右子树9,69,6、8,18,1，和左子树同理，也是对Y轴进行划分。

此时所有点都已经加入到KD树中，创建结束。

一个直观的理解是，创建方式看起来有点像对空间横纵切蛋糕的方式，对于2D空间，第一刀沿着X轴将空间划分为两半，第二刀又沿着Y轴分别将已经划分好的两半再划分为两半，第三刀又继续沿着X轴进行划分……直到所有点都落入KD树中。

对于3D空间，则是沿着X->Y->Z->X此类的循环依次对空间进行对半分割。

寻找最近邻居

由于创建的方式不同，寻找最近邻居的算法也不尽相同。譬如：有一种KD树的创建方式，将所有点都视为叶子节点，分割节点只做分割用。

在本文的创建方式中，我们的叶子节点只是不能再往下进行分割的点。与网络中大部分所描述的KD树的寻找最邻近算法不同，我们的寻找最邻近不要求所有的查询点都为叶子节点。

以下是寻找最近邻居算法的描述：

1. 建立一个空的栈S
2. 对于给定的查询点P，沿着根节点遍历整个KD树，直到不能再遍历为止，将每个遍历的点都入栈（Push）
3. 遍历的过程非常简单，对于KD树中的点和这个点的划分坐标，如果查询点比这个点的划分坐标大，则继续遍历这个点的右子树，否则遍历这个点的左子树
4. 若栈非空，开始循环，设最邻近距离为无穷大
5. 将栈顶的点P弹出（Pop），计算查询点与之的距离Dist，如果Dist小于最邻近距离，则更新最近邻距离为Dist，同时更新最邻近点为P
6. 判断点P的划分轴，若查询点到划分轴的距离小于最近邻距离，则说明在划分轴的另外一侧还可能存在更邻近的点，需要在划分轴的另一侧的根节点再执行一次遍历，将每个遍历的点都入栈（Push）
7. 若栈为空，则终止循环，返回结果

以上算法用到了栈来模拟递归，避免了递归的函数深层调用和返回的开销。

其平均复杂度为，与相比，如果N为600，理论上的最大提升为 倍，N越大，KD树的效率提升越大。

KD树之所以如此高效的原因在于第六步，也就是剪枝。

如上图所示，在已经搜索到B时，发现其到B的距离，要比到A的右子树的平面距离还更短，所以整个A的右子树都被剪枝，一下子剪去了一半的点。

在计算距离时，有一种初学者做法为直接算出欧氏距离，里面包含了开方运算。

其实在任何只需要比较距离长短，而不需要精确知道距离具体数值的场合，用距离的平方来避免开方运算是一个提升效率的常用手段。

因为KD树的自身数据结构原因，使得KD树的插入和删除操作较为复杂，而且容易让KD树变得不平衡。所以一般做法倾向于在点的坐标发生改变时，重建整个KD树。

在构建KD树的时候，选择坐标轴中位数的算法非常微妙。一种最简单的做法是对所有的点按照坐标轴进行排序，然后选择排好序的列表的中间点即可。

一次排序的平均复杂度为，也就是在每一次划分时，我们都需要排一次序来获取中位数点，这显然是不够高效的。

Median of medians

一种解决方案是 Median of medians算法来选择中位数，此算法的思路和快排类似。

通过随机选择一个浮标pivotpivot，来将序列进行划分，比浮标的坐标小的点，划分到小端列表；比浮标的坐标大的点，则划分到大端列表。

若小端列表的个数正好可以确定中位数点，则直接返回浮标点为中位数点；如果不够，则需要再去大端列表中再去划分，直到最终能确定中位数点为止；反之，则在小端列表中进行划分……

以上是Quickselect的划分方式，最坏复杂度为，即每次划分，小端或大端都只划分了一个元素，其平均复杂度为。

Quickselect的效率低源于划分的不均衡，Median of medians为了确保均衡，算法如下：

1. 将所有元素分为N/X组，每组有X个元素，最后一组不足X也没关系
2. 对所有组进行排序，找到每组的中位数
3. 递归调用此算法，找到所有这些组的中位数列表的中位数M
4. 在Quickselect的划分过程中，用M来进行划分

这个算法在X=5时，可以证得最坏复杂度为。

上述中位数算法实现起来太复杂，很容易出错，在实际开发中我选择了Russell A. Brown提出的预先排序算法。

即预先对所有坐标轴的点进行排序，比如2D空间，就需要排两次序，一次X轴，一次Y轴，然后后续就不需要排序了。

其原理是在已经排好序后，后续的操作无非是对左右序列的重新划分，此时并不需要重新排序，而只需一次线性遍历，将前一次的划分的结果对下一次划分的坐标轴的序列进行重新填充即可。

详细解释请参考论文，作者在文章里解释的很充分和详细。

这个算法需要注意的地方是：不允许出现所有坐标完全一致的两个点，对于有硬碰撞的游戏来说，可以规避掉此种情况，所以可以放心使用。

缓存，GC友好

一条优化的金科玉律就是：缓存一切后面要大量重复用到的计算结果。

在KD树创建并不频繁，且需要大量查找时，缓存点与点之间的距离，这样可以避免很多重复的距离计算。

在KD树重建很频繁时，很多KD树的节点会被创建出来，应该给这些节点设立一个缓存池，以避免频繁的内存开辟和垃圾回收。

又譬如在计算最邻近时，不要临时创建一个栈，而是使用之前的栈，只是把栈的内容清空即可，这样对GC很友好。