空间划分:网格、四叉树、八叉树、BVH 与 AOI

2609 字
13 分钟
空间划分:网格、四叉树、八叉树、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 排序,移动时沿链表移动并检查经过的实体。

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

空间划分:网格、四叉树、八叉树、BVH 与 AOI
https://xslab.cloud/posts/algorithms/spatial-partitioning/
作者
LuxFire
发布于
2026-10-14
许可协议
CC BY-NC-SA 4.0
相关文章 智能推荐
1
游戏 AI 决策:状态机、分层状态机、行为树、效用 AI 与 GOAP
游戏算法 游戏 AI 要解决什么问题;有限状态机的实现与状态爆炸;分层状态机;行为树的节点类型、执行状态、Tick 机制、黑板与中断,以及一个最小实现;效用 AI 的打分机制;GOAP 的目标、动作与规划;各种方案的对比与选择。
2
游戏中的随机:随机数生成器、权重随机、洗牌、伪随机分布与均匀采样
游戏算法 Unity 与 .NET 随机数生成器的区别、种子与可复现;权重随机的三种实现(线性、二分、别名法);Fisher-Yates 洗牌及其常见错误;洗牌袋;Dota 式的伪随机分布;在圆内、球面上均匀取点;正态分布与噪声;以及随机相关的服务器权威问题。
3
寻路算法:BFS、Dijkstra、A*、JPS、NavMesh 与流场
游戏算法 寻路问题的建模(网格、路点图、导航网格);BFS、Dijkstra、贪心与 A* 的区别;A* 的原理、启发函数的选择与可采纳性、完整实现;JPS 跳点搜索;Unity NavMesh、拐角算法与局部避障;大量单位的流场寻路;分层寻路;以及路径平滑和性能优化。
4
曲线与缓动:贝塞尔、Catmull-Rom、弧长参数化与缓动函数
游戏算法 游戏中曲线的用途;二次与三次贝塞尔曲线的公式、性质与德卡斯特里奥算法;经过所有点的 Catmull-Rom 样条与向心参数化;曲线上匀速运动的弧长参数化;沿曲线运动时的朝向;常用缓动函数与 AnimationCurve;以及 Unity Splines。
5
定时器的实现:从逐帧计时到最小堆与时间轮
游戏算法 游戏中定时器的需求;逐帧计时、协程、统一管理器三种基础做法的问题;用最小堆管理大量定时器;时间轮的原理、轮数计算与分层时间轮;时间源(缩放时间、真实时间、服务器时间)的选择;暂停、取消与回调中的注意事项。
随机文章 随机推荐
Profile Image of the Author
LuxFire
Hello, I'm LuxFire.
公告
欢迎来到我的博客!这是一则示例公告。
音乐
封面

音乐

暂未播放

0:00 0:00
暂无歌词
分类
标签
站点统计
文章
60
分类
6
标签
164
总字数
171,869
运行时长
0 天
最后活动
0 天前

文章目录