空间划分:网格、四叉树、八叉树、BVH 与 AOI
一、为什么需要空间划分
游戏中大量的问题都是”找出附近的东西”:
- 技能范围内有哪些敌人?
- 哪些物体可能互相碰撞?
- 离玩家最近的道具是哪个?
- 哪些玩家在我的视野内,需要同步给我?
最直接的做法是遍历所有对象逐个判断。1000 个单位两两检测碰撞,就是约 50 万次比较,每帧都做显然不行。
空间划分的思路是:把空间组织成某种结构,查询时只检查目标附近的那一小部分对象,把 O(n) 的查询变成接近 O(1) 或 O(log n),把 O(n²) 的两两检测大幅减少。
二、均匀网格
把世界划分成大小相同的格子,每个格子记录其中的对象:
+----+----+----+----+| | A | | |+----+----+----+----+| | B C| D | | 查询 C 附近的对象:+----+----+----+----+ 只检查 C 所在的格子和周围 8 个格子| | | | E |+----+----+----+----+- 插入、删除、移动:根据坐标直接算出格子编号,O(1)。
- 范围查询:只检查与范围相交的几个格子。
- 格子大小:通常取对象大小或常用查询半径的量级。太大则每格对象多,太小则一个对象跨很多格、查询时要检查很多格。
空间哈希:世界很大、对象稀疏时,大部分格子是空的,开一个大数组浪费内存。改用字典,以 (格子 x, 格子 y) 为 key,只存储有对象的格子。
适合:对象大小相近、分布比较均匀、频繁移动的场景,比如弹幕、大量小怪、粒子。实现最简单,移动的更新开销最小,很多时候是最实用的选择。
不适合:对象分布极不均匀(大量对象挤在少数格子里),或者大小差距很大。
三、四叉树与八叉树
原理
从整个世界的范围开始,一个节点中的对象超过一定数量时,就把这个节点平均分成四块(2D 四叉树),对象分配到子节点中,子节点可以继续细分:
+---------+---------+| | | * || * +----+----+| | ** | * |+---------+----+----+| | || | * || | |+---------+---------+对象密集的区域被划分得更细,稀疏的区域保持较大的节点八叉树是 3D 版本,每次分成八块。
- 查询时,从根节点开始,只进入与查询范围相交的子节点,大块的无关区域被直接跳过。
- 平均查询复杂度约为 O(log n + k),k 是结果数量。
- 自适应:对象密集的地方划分得细,稀疏的地方划分得粗,比均匀网格更适合分布不均的场景。
有大小的对象
对象不是一个点,而是一个矩形。如果它跨越了子节点的边界,就放不进任何一个子节点,只能留在父节点中。问题是靠近边界的小物体会堆积在很高的层级上,降低查询效率。
松散四叉树(Loose Quadtree):把每个节点的边界向外扩大(比如扩大为两倍),对象只要中心在节点内、且整体在扩大后的边界内即可放入,大大减少了卡在上层的情况。
实现
public class QuadTree<T>{ const int Capacity = 8; // 一个节点最多存放的对象数,超出则分裂 const int MaxDepth = 6;
readonly Rect _bounds; readonly int _depth; readonly List<(Rect rect, T item)> _items = new(); QuadTree<T>[] _children;
public QuadTree(Rect bounds, int depth = 0) { _bounds = bounds; _depth = depth; }
public void Insert(Rect rect, T item) { if (_children != null) { int index = ChildIndex(rect); if (index >= 0) { _children[index].Insert(rect, item); return; } }
_items.Add((rect, item)); // 没有子节点,或者跨越了子节点边界:留在当前节点
if (_children == null && _items.Count > Capacity && _depth < MaxDepth) { Split(); for (int i = _items.Count - 1; i >= 0; i--) // 把能放进子节点的对象下放 { int index = ChildIndex(_items[i].rect); if (index < 0) continue; _children[index].Insert(_items[i].rect, _items[i].item); _items.RemoveAt(i); } } }
public void Query(Rect area, List<T> results) { if (!_bounds.Overlaps(area)) return; // 不相交,整个分支跳过 foreach (var (rect, item) in _items) if (rect.Overlaps(area)) results.Add(item); if (_children != null) foreach (var child in _children) child.Query(area, results); }
void Split() { float w = _bounds.width / 2, h = _bounds.height / 2, x = _bounds.x, y = _bounds.y; _children = new QuadTree<T>[] { new(new Rect(x, y, w, h), _depth + 1), new(new Rect(x + w, y, w, h), _depth + 1), new(new Rect(x, y + h, w, h), _depth + 1), new(new Rect(x + w, y + h, w, h), _depth + 1), }; }
int ChildIndex(Rect r) { for (int i = 0; i < 4; i++) { var b = _children[i]._bounds; if (r.xMin >= b.xMin && r.xMax <= b.xMax && r.yMin >= b.yMin && r.yMax <= b.yMax) return i; } return -1; }}查询结果放进调用方传入的 List 中,调用方可以复用这个 List,避免每次查询都分配内存。
动态对象
对象移动后,可能离开了原来所在的节点:
| 做法 | 适合 |
|---|---|
| 移除后重新插入:记录每个对象所在的节点,移动后如果超出了节点范围,从原节点移除,再从根节点重新插入 | 移动的对象较少 |
| 每帧重建整棵树 | 大部分对象都在移动。重建一次是 O(n log n),有时比大量的移除和插入更简单、更快 |
| 静态和动态分开 | 地形、建筑放一棵树,只建一次;移动的单位放另一个结构(比如网格) |
四、其他结构
| 结构 | 原理 | 特点 | 典型用途 |
|---|---|---|---|
| BVH(层次包围盒) | 按对象分组:把相近的对象用一个包围盒框起来,再把包围盒逐层合并成树 | 每个对象只出现在一个叶子中;包围盒贴合对象,适合大小差异大的对象;动态版本(动态 AABB 树)支持高效的移动更新 | 物理引擎的粗检测、射线检测、光线追踪 |
| KD 树 | 交替沿 x、y(、z)轴,在中位数处一分为二 | 最近邻查询很快;构建后不适合频繁修改 | 静态点集的最近邻查找 |
| 排序扫描(Sweep and Prune) | 把所有对象的包围盒投影到一个轴上并排序,只有投影区间重叠的才可能碰撞 | 物体移动较少时,每帧只需对上一帧的顺序做少量调整,非常快 | 物理引擎的粗检测 |
空间划分(网格、四叉树)与对象划分(BVH)的区别:空间划分把空间切开,一个大对象可能跨越多个区域;对象划分按对象分组,每个对象只属于一个节点,但不同节点的包围盒可能重叠。
五、在游戏中的应用
| 问题 | 做法 |
|---|---|
| 碰撞检测的粗检测 | 先用空间划分找出可能碰撞的对象对,再对这些对做精确检测(粗检测 + 精检测) |
| 技能范围、AOE | 查询范围的包围盒得到候选,再做精确的形状判断(圆、扇形、矩形) |
| 最近的目标 | 从目标所在的格子开始,一圈圈向外扩大搜索,找到后再检查一圈,确认没有更近的 |
| 视锥剔除 | 八叉树或 BVH 中,整个节点都在视锥外就跳过 |
| 网络同步的范围 | 见下文 AOI |
Unity 中的选择:如果对象本身就有 Collider,Physics.OverlapSphere 等查询内部已经使用了物理引擎的粗检测结构,直接用即可。自己实现空间划分,适合不使用物理引擎的大量对象,比如纯数据驱动的弹幕、ECS 中的单位、服务器上的逻辑。
六、AOI:MMO 中的视野管理
AOI(Area of Interest,兴趣区域):服务器只把玩家视野范围内的其他实体同步给他。一张地图上有几千个玩家,不可能把所有人的移动都发给每个人。
AOI 系统要高效地回答:一个实体移动后,谁进入了它的视野,谁离开了它的视野。
九宫格
地图划分成网格,格子大小约等于视野半径。玩家的视野就是自己所在的格子加上周围的 8 个格子。
移动前:视野是以 (2,2) 为中心的九个格子移动到 (3,2):视野是以 (3,2) 为中心的九个格子
离开视野的格子 = 旧九宫格 - 新九宫格 → 通知"这些实体离开了"进入视野的格子 = 新九宫格 - 旧九宫格 → 通知"这些实体进入了"实现简单、性能稳定,是最常用的方案。缺点是视野是方形的,精度受格子大小限制。
十字链表
所有实体分别按 x 坐标和 y 坐标排序,串成两条有序链表。实体移动时,在链表中向前或向后移动到新位置,沿途经过的实体就是可能进入或离开视野的实体。
- 视野半径可以因人而异,精度高;
- 实体密集时,移动一次要在链表中经过很多节点,开销会上升。
常见追问
为什么需要空间划分? 避免每次查询都遍历所有对象,把范围查询和碰撞检测的开销从 O(n) 或 O(n²) 降下来,只检查目标附近的对象。
均匀网格和四叉树怎么选? 对象大小相近、分布均匀、频繁移动时用网格,简单且更新快;分布不均、需要自适应时用四叉树。
四叉树的原理是什么? 节点中的对象超过上限时把区域分成四块,对象下放到子节点;查询时只进入与查询范围相交的节点。
有大小的对象跨越边界怎么办? 留在父节点中;或者使用松散四叉树,把节点边界扩大,减少对象卡在上层的情况。
动态对象在四叉树中怎么更新? 超出所在节点范围时移除并重新插入;大部分对象都在移动时,每帧重建整棵树;或者静态和动态对象分开管理。
BVH 和四叉树有什么区别? 四叉树划分空间,大对象可能跨越多个区域;BVH 按对象分组,每个对象只在一个叶子中,包围盒可以重叠,适合物理引擎和射线检测。
MMO 的 AOI 怎么实现? 九宫格:按视野半径划分网格,移动时用新旧九宫格的差集得出进入和离开视野的实体;或者十字链表:按 x、y 排序,移动时沿链表移动并检查经过的实体。
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!