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 个邻近网格，再精确计算