KD树的应用与优化 agile Posted on Jun 18 2023 算法 > 本文由 [简悦 SimpRead](http://ksria.com/simpread/) 转码， 原文地址 [wuzhiwei.net](https://wuzhiwei.net/kdtree/) > 分享对算法，游戏开发，解决问题的一些思考和代码实现 KD 树的应用与优化 ========== Posted on [2017/09/10](https://wuzhiwei.net/kdtree/) · [6 Comments](https://wuzhiwei.net/kdtree/#comments) 引子 -- 在一张地图上，有 600 多个单位，每个单位之间都需要独立寻路，检测碰撞和寻找最近的敌方目标。当这一切需要在手机上流畅运行并尽可能快的在服务器进行模拟时，最简单的平方算法  已经不能满足需求。 怎样减少计算的复杂度呢？ 通过观察，可以发现，在地图左上角的单位根本无需和地图右下角的单位进行碰撞检测，因为它们离的太远了。 所以，通过对战场进行空间划分，可以避免大量的无效计算。 一种简单的划分方法是，将战场沿着横纵坐标划分为  的格子，只对在相同格子内的战斗单元做碰撞检测。 这种方法在大部分情况下简单有效，然而有以下几点问题： 1. 当格子边长太大时，假设很多单位都聚集于一个或少数几个格子中，其实空间并没有有效划分 2. 当格子边长太小时，一个格子内的单位可能太少了，也不能对空间进行有效划分 3. 如果不查找附近的几个格子，可能或错过附近格子可能距离更近的单位 4. 这种方法的空间复杂度是，在格子数很多的情况下，内存开销会很高 [KD 树](https://en.wikipedia.org/wiki/K-d_tree) $k-dimensional tree$，也可称之为 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,4$、$2,3$、$4,7$被划分到左子树；X 坐标比 7 大的点 $9,6$、$8,1$被划分到右子树。 对于左子树 $5,4$、$2,3$、$4,7$，对它们的 Y 轴进行划分，点 $5,4$的 Y 坐标 4 为所有左子树的 Y 坐标的中位数，其被确立为左子树的根节点；Y 坐标比 4 小的点 $2,3$被划分为左子树；Y 坐标比 4 大的点 $4,7$被划分为右子树。 对于右子树 $9,6$、$8,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](https://en.wikipedia.org/wiki/Median_of_medians) 算法来选择中位数，此算法的思路和快排类似。 通过随机选择一个浮标 $pivot$，来将序列进行划分，比浮标的坐标小的点，划分到小端列表；比浮标的坐标大的点，则划分到大端列表。 若小端列表的个数正好可以确定中位数点，则直接返回浮标点为中位数点；如果不够，则需要再去大端列表中再去划分，直到最终能确定中位数点为止；反之，则在小端列表中进行划分…… 以上是 [Quickselect](https://en.wikipedia.org/wiki/Quickselect) 的划分方式，最坏复杂度为，即每次划分，小端或大端都只划分了一个元素，其平均复杂度为。 Quickselect 的效率低源于划分的不均衡，Median of medians 为了确保均衡，算法如下： 1. 将所有元素分为 N/X 组，每组有 X 个元素，最后一组不足 X 也没关系 2. 对所有组进行排序，找到每组的中位数 3. 递归调用此算法，找到所有这些组的中位数列表的中位数 M 4. 在 Quickselect 的划分过程中，用 M 来进行划分 这个算法在 X=5 时，可以[证得](https://en.wikipedia.org/wiki/Median_of_medians#Proof_of_O.28n.29_running_time)最坏复杂度为。 #### 预先排序 上述中位数算法实现起来太复杂，很容易出错，在实际开发中我选择了 Russell A. Brown 提出的[预先排序算法](http://jcgt.org/published/0004/01/03/paper.pdf)。 即预先对所有坐标轴的点进行排序，比如 2D 空间，就需要排两次序，一次 X 轴，一次 Y 轴，然后后续就不需要排序了。 其原理是在已经排好序后，后续的操作无非是对左右序列的重新划分，此时并不需要重新排序，而只需一次线性遍历，将前一次的划分的结果对下一次划分的坐标轴的序列进行重新填充即可。 详细解释请参考论文，作者在文章里解释的很充分和详细。 这个算法需要注意的地方是：不允许出现**所有坐标完全一致**的两个点，对于有硬碰撞的游戏来说，可以规避掉此种情况，所以可以放心使用。 ### 缓存，GC 友好 一条优化的金科玉律就是：缓存一切后面要大量重复用到的计算结果。 在 KD 树创建并不频繁，且需要大量查找时，缓存点与点之间的距离，这样可以避免很多重复的距离计算。 在 KD 树重建很频繁时，很多 KD 树的节点会被创建出来，应该给这些节点设立一个缓存池，以避免频繁的内存开辟和垃圾回收。 又譬如在计算最邻近时，不要临时创建一个栈，而是使用之前的栈，只是把栈的内容清空即可，这样对 GC 很友好。 参考资料 ---- * [k-d tree in Wikipedia](https://en.wikipedia.org/wiki/K-d_tree) * [Building a Balanced k-d Tree in O$kn log n$ Time](http://jcgt.org/published/0004/01/03/paper.pdf) * [How to use a KdTree to search](http://pointclouds.org/documentation/tutorials/kdtree_search.php) * [Median of medians](https://en.wikipedia.org/wiki/Median_of_medians) Posted in [Alogrithm](https://wuzhiwei.net/category/alogrithm/), [DataStructure](https://wuzhiwei.net/category/datastructure/), [Game Develop](https://wuzhiwei.net/category/game-develop/) Tagged [KD 树](https://wuzhiwei.net/tag/kd%e6%a0%91/), [优化](https://wuzhiwei.net/tag/%e4%bc%98%e5%8c%96/), [性能](https://wuzhiwei.net/tag/%e6%80%a7%e8%83%bd/), [算法](https://wuzhiwei.net/tag/%e7%ae%97%e6%b3%95/) 设计模式 C# 知识树整理——内存探索