核心目标：不要让每个对象检查所有其他对象。空间索引先把候选集缩小，再做精确距离、碰撞或视野判断。
为什么需要空间索引
若 n 个单位互相检查距离，朴素做法需要 O(n²) 次比较。1000 个单位可能接近一百万对。
空间结构利用“远处对象不可能相关”的事实，把查询限制在附近格子或层级节点。
Uniform Grid
世界被划分为固定大小格子。对象根据位置进入一个格子，查询半径时只检查覆盖范围内的格子。
适合：
- 地图尺度已知
- 对象分布较均匀
- 查询半径接近格子大小
- 2D 或平面 3D 游戏
Spatial Hash 示例
返回的是候选对象，还必须做精确距离检查。格子大小和查询半径不匹配时，需要访问更多格子。
动态对象如何更新
对象移动跨格时：
- 记录旧格坐标。
- 计算新格坐标。
- 相同时不处理。
- 从旧桶移除并加入新桶。
若全部对象每帧都高速移动，维护成本可能很高。可选择每若干帧重建、双缓冲，或只索引需要查询的对象。
Quadtree
四叉树递归把 2D 区域分成四块。适合分布不均、世界范围大、局部很密集的数据，例如：
- 2D 大地图可见性
- RTS 单位与兴趣区域
- 地图标记和编辑器选择
节点过度拆分会增加对象与分配。应设置最大深度、叶节点容量和合并阈值。
Octree
八叉树把 3D 空间分成八块。它适合真正三维分布，如飞行单位或体素区域，但内存与维护成本高于 Quadtree。
地面游戏通常先尝试 2D Grid 或 Quadtree，不要因为场景是 3D 就默认选择 Octree。
BVH 与 KD-Tree
- BVH：用层级包围盒组织对象，适合射线、可见性和静态几何。
- KD-Tree：按坐标轴递归切分，适合最近邻和静态点集。
动态频繁移动会触发重建或重新平衡。静态与动态对象可以使用不同索引。
选择表
结构 | 优点 | 代价 | 典型场景 |
Uniform Grid | 简单、连续、查询稳定 | 稀疏大世界浪费格子 | 塔防、2D、规则地图 |
Spatial Hash | 只创建用到的格子 | 哈希和桶管理 | 动态单位、无限地图 |
Quadtree | 适应 2D 密度变化 | 更新与树节点成本 | RTS、可见性 |
Octree | 完整 3D 层级 | 内存和维护更高 | 体素、飞行空间 |
不要重复实现物理引擎
Unity Physics 已经有 Broadphase。若需求只是 Collider 范围查询，优先使用：
Physics.OverlapSphereNonAlloc
- LayerMask
- 合理的碰撞层矩阵
自定义空间索引适合非物理数据、超大量逻辑单位、服务端模拟，或物理查询不能满足的特殊规则。
性能验证
- Profiler 中比较构建索引与查询成本。
- 记录每格平均和最大对象数。
- 检查候选数与最终命中数比例。
- 避免查询结果 List 每次分配。
- 大批量数值数据可烘焙进 Native 容器并用 Jobs 并行查询。
- 在最密集的真实关卡测试，而不是空场景。
常见坑
- 负坐标用整数截断而不是
FloorToInt。
- 移动物体没有从旧格移除。
- 把候选结果当成精确结果。
- 格子过大退化为全局扫描，过小导致跨格查询过多。
- 为少量对象引入复杂树结构。