k-NN(k nearest neighbors)
我在一个场景中,有100k个小怪,我需要得到1k个与我最近的单位,如何快速查找?
四叉树
四叉树适用于二维场景,将空间递归划分成四个象限,按区域把单位放进去。
树基本结构
- 根节点:覆盖整个场景范围
- 每个节点最多存放一定数量的对象(例如 8~16 个)
- 超过阈值时分裂成 4 个子节点
- 对象根据坐标放入对应的子节点
查找最近 1k 个单位的步骤
- 从根节点开始,把查询点所在的区域优先搜索
- 对当前节点里的对象计算距离,维护一个最大堆或固定大小的候选列表
- 对子节点递归搜索,但只进入那些有可能包含更近对象的区域
- 对每个子节点,先检查该节点包围盒到查询点的最小距离
- 如果该最小距离已经比当前第 1k 近的距离大,就可以剪枝跳过该子节点
- 继续搜索直到所有可能更近的区域都处理完
网格 / 空间哈希(Spatial Hash Grid)
- 把场景分成固定大小的格子,每个格子维护一个对象列表。查询时只检查当前格子和相邻格子,速度快,非常适合均匀分布。
- 把格子坐标哈希成桶,适合大范围、动态移动对象。插入、删除、查询都是常数级别,维护简单。也可以看成“网格划分+哈希映射”。
- 查询时只访问与自身相邻的若干格子
- 适合均匀分布、实时更新频繁的场景
k-d 树
- 构建过程的时间复杂度是 O(N log N)。对于100k个小怪,这是一次性的、完全可以接受的开销。
- 构建完后,这棵树在这一帧内是静态的。
- 适合静态点集或少量动态更新
- 递归按 x/y 轴交替划分空间
查找最近 1k 个单位的步骤
最近邻查询类似二叉树剪枝
- 从根节点开始,比较你的位置和当前节点在分割轴上的坐标。
- 如果你在节点的左边,就优先进入左子树;如果在右边,就优先进入右子树。像普通二叉树查找一样,一路向下,直到到达一个叶子节点。
- 当你从递归中返回,开始回溯到父节点时,执行最关键的“剪枝”判断。
- 核心问题: “另一半子树所代表的空间区域,有没有可能存在比我当前找到的第1000个邻居更近的点?”
- 判断方法: 计算你的位置到当前节点“分割面”的垂直距离 d_plane。
- 如果 d_plane ≥ radius: 这意味着另一半子树的整个空间,都比你当前最远的邻居还要远。因此,你完全不需要进入那个子树进行搜索! 这就是“剪枝”。
- 如果 d_plane < radius: 意味着另一半子树的空间与你的“搜索球”有交集,里面可能存在更近的点。因此,你必须进入这个子树,重复上面的递归搜索过程。
BVH (Bounding Volume Hierarchy) / 包围盒层级
- 每个节点是一个包围一组物体的盒子(AABB/OBB等)
- 子节点是把物体集合拆成两组(常见二叉),再分别求包围盒。
- 划分不要求等分空间,通常按数据分布和代价(如 SAH)自适应构建。
查找最近 1k 个单位的步骤
- 初始化: 将所有100k个小怪(或它们的精确位置)看作“物体”,放入一个列表中。
- 递归构建:
- 终止条件: 如果当前列表中的物体数量小于等于某个阈值(比如8),则创建一个叶子节点。这个叶子节点的AABB是紧紧包裹这几个物体的包围盒,节点内部存储这些物体的引用。然后返回。
- 选择最长的轴: 计算当前列表中所有物体的AABB,找到这个AABB最长的轴(X, Y, 或 Z)。
- 排序与划分: 沿着这个最长的轴,根据物体重心的坐标,对列表中的所有物体进行排序。找到中位数,将列表一分为二。
- 创建子节点:
- 对第一半的物体,递归调用构建过程,创建一个左子节点。
- 对第二半的物体,递归调用构建过程,创建一个右子节点。
- 创建父节点: 创建一个新的中间节点,它的AABB是其左、右两个子节点AABB的并集(即一个能同时包裹住左右两个子包围盒的新包围盒)。这个中间节点的子节点就是刚刚创建的左右子节点。
这个过程从包含所有物体的根节点开始,一直递归下去,直到所有物体都被分配到叶子节点中。构建完成后,你就有了一个完整的BVH树。
- K-近邻查询 (每帧执行的核心算法)
一个容量为 K (这里是1000) 的最大优先队列 (Max-Priority Queue),我们称之为“结果集 (resultSet)”。 - 作用: 用来存储到目前为止找到的 K 个最近邻居。
- 特性: 队列的“顶部” i.e. queue.peek() 永远是这 K 个中距离你最远的那个。当你尝试加入一个新邻居时,如果它比最远的那个更近,最远的就会被自动“踢”出去。
一个最小优先队列 (Min-Priority Queue),我们称之为“待办列表 (todoList)”。
- 作用: 用来存储接下来需要检查的 BVH 节点。
- 特性: 队列的“顶部”永远是距离你最近的那个节点/AABB盒。这保证了我们总是优先探索最有希望找到近邻的区域。
具体算法
假设你的位置是 myPosition,要查找 K=1000 个最近邻。
- 初始化:
创建一个空的、容量为1000的 resultSet (最大优先队列)。
创建一个空的 todoList (最小优先队列)。
将 BVH 的根节点以及你到根节点AABB的最近距离 d_box (初始时这个距离是0,因为你在场景内)作为一个元组 (rootNode, d_box) 加入 todoList。
将“最大搜索半径 radius” 初始化为无穷大。
开始循环搜索: 当 todoList 不为空时,持续循环:
a. 取出最优节点: 从 todoList 中取出距离最近的节点 (currentNode, dist_box)。
b. 核心剪枝:
从 resultSet 中获取当前已找到的最远邻居的距离(如果 resultSet 已满),这个距离就是我们当前的最大搜索半径 radius。
如果 dist_box ≥ radius: 这意味着 todoList 中所有剩下的节点(因为它们比 currentNode 更远)以及它们包含的所有物体,都不可能比我们已经找到的第K个邻居更近。搜索可以提前结束! 跳出循环。
c. 处理节点:
如果 currentNode 是一个叶子节点:
遍历该叶子节点包含的所有实际物体。
对于每个物体,计算你到它的精确距离 d_obj。
尝试更新结果集: 将这个物体和它的距离 d_obj 加入 resultSet。如果 resultSet 已满且 d_obj 更近,优先队列会自动T出最远的那个。
重要: 每当 resultSet 被更新后(特别是当它首次满员时),需要更新 radius 为 resultSet 中新的最大距离。这个 radius 会不断缩小,从而让步骤 b 的剪枝变得越来越强大。
如果 currentNode 是一个中间节点:
获取它的左、右两个子节点。
对于每一个子节点:
计算你到这个子节点AABB的最近距离 d_child_box。
如果 d_child_box < radius: 这意味着这个子节点的区域内可能存在更近的邻居,我们必须探索它。将这个子节点和它的距离 (childNode, d_child_box) 加入 todoList。
如果 d_child_box ≥ radius,则直接忽略这个子节点及其整个分支(又一次剪枝!)。
完成: 当循环结束时,resultSet 中存储的就是最终的1000个最近邻居。
倒排桶 / 桶排序距离
- 先用距离近似值分桶,再只对近距离桶内对象精确排序
- 适合距离范围已知、精度需求不高的场景
粗略筛选 + 精确排序
- 先用简单空间划分得到一小部分候选对象
- 然后在候选集中排序取前 1k
- 例如:先找 5x5 个邻近网格,再精确计算
