把章节变成可单步观察的过程
分类：算法 / 游戏逻辑常用模式
先说结论
空间划分先按位置缩小候选范围，再做精确距离或碰撞判断。九宫格适合分布较均匀、查询半径接近格子大小的对象；四叉树会在局部密集处继续切分，适合密度变化较大的空间。
一万对象的候选缩减
世界大小：1000 x 1000
格子大小：10 x 10，共 10,000 个格子
对象数量：10,000，均匀时平均每格约 1 个
查询一个对象附近九宫格：平均检查约 9 个候选这只是均匀分布下的教学估算。若 5,000 个对象都挤在同一格，九宫格仍可能检查数千个候选；空间划分不会自动解决极端热点。
空间划分解决什么问题
空间划分解决的是：
不要为了找附近对象，遍历整个世界。例如玩家释放一个半径 5 米的技能，需要找到附近敌人。最直接的写法是遍历所有敌人：
foreach (var enemy in allEnemies)
{
float distance = Vector3.Distance(playerPos, enemy.Position);
if (distance <= 5f)
{
result.Add(enemy);
}
}如果只有几十个敌人，这样没问题。
但如果场景里有很多对象：
500 个怪物
2000 个掉落物
大量子弹
频繁触发的 AOE 查询每次都遍历全部对象就会变贵。
空间划分的思路是：
先用空间结构缩小候选范围。
再对候选对象做精确距离判断。也就是：
先粗筛，再精筛。跟着代码完成一次九宫格查询
先把实体类型放进 Entity.cs：
using System.Numerics;
record Entity(string Name, Vector2 Position);固定每格边长为 5，把世界坐标转换成格子坐标：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
const float cellSize = 5f;
static (int X, int Y) ToCell(Vector2 position, float cellSize)
{
return (
(int)MathF.Floor(position.X / cellSize),
(int)MathF.Floor(position.Y / cellSize));
}
Dictionary<(int X, int Y), List<Entity>> grid = new();第一步：实体进入网格
void Insert(Entity entity)
{
(int X, int Y) cell = ToCell(entity.Position, cellSize);
if (!grid.TryGetValue(cell, out List<Entity>? bucket))
{
bucket = new List<Entity>();
grid.Add(cell, bucket);
}
bucket.Add(entity);
}
Insert(new Entity("A", new Vector2(2, 1))); // Cell (0,0)
Insert(new Entity("B", new Vector2(7, 1))); // Cell (1,0)
Insert(new Entity("C", new Vector2(20, 20))); // Cell (4,4)此时字典只保存实际有对象的格子：
(0,0) -> [A]
(1,0) -> [B]
(4,4) -> [C]第二步：只收集周围九格候选
Vector2 center = new(1, 1);
(int X, int Y) centerCell = ToCell(center, cellSize);
List<Entity> candidates = new();
for (int y = centerCell.Y - 1; y <= centerCell.Y + 1; y++)
{
for (int x = centerCell.X - 1; x <= centerCell.X + 1; x++)
{
if (grid.TryGetValue((x, y), out List<Entity>? bucket))
candidates.AddRange(bucket);
}
}
Console.WriteLine(string.Join(", ", candidates.Select(e => e.Name)));
// A, BC 位于 (4,4)，粗筛阶段已经排除。示例里的 Select 只用于打印；高频查询可以用普通循环避免额外枚举器或分配。
第三步：候选不等于命中
float radius = 5f;
float radiusSquared = radius * radius;
List<Entity> result = new();
foreach (Entity candidate in candidates)
{
float distanceSquared = Vector2.DistanceSquared(
center, candidate.Position);
if (distanceSquared <= radiusSquared)
result.Add(candidate);
}
Console.WriteLine(string.Join(", ", result.Select(e => e.Name)));
// AB 虽然在相邻格，但离查询中心 6 米，因此精筛后被排除。完整状态变化是：
世界里 3 个对象
-> 九格粗筛得到 A、B 两个候选
-> 距离平方精筛只留下 A如果查询半径大于格子边长，只检查九格就可能漏掉目标。通用写法应根据 ceil(radius / cellSize) 计算需要扩展多少圈；九宫格只是“查询范围最多跨一格”时的特例。
九宫格查找
九宫格查找通常基于固定网格。
先把地图切成一格一格：
+---+---+---+---+
| | | | |
+---+---+---+---+
| | P | | |
+---+---+---+---+
| | | E | |
+---+---+---+---+每个单位登记到自己所在的格子里。
查询玩家附近目标时，只检查玩家所在格子和周围 8 个格子：
[ ][ ][ ]
[ ][P][ ]
[ ][ ][ ]这就是九宫格查找。
它的核心不是“九个格子里的对象都命中”，而是：
九个格子里的对象只是候选对象。最后仍然要做距离判断：
float radius = 5f;
float radiusSqr = radius * radius;
foreach (var enemy in nearbyEnemies)
{
Vector3 offset = enemy.Position - playerPos;
if (offset.sqrMagnitude <= radiusSqr)
{
result.Add(enemy);
}
}为什么用距离平方
判断对象是否在半径内时，可以写：
Vector3.Distance(a, b) <= radius但 Vector3.Distance 会计算真实距离，内部需要开根号。
如果只是比较远近，不需要真实距离，可以比较距离平方：
float radiusSqr = radius * radius;
if ((a - b).sqrMagnitude <= radiusSqr)
{
// 在范围内
}因为：
距离 <= 5等价于：
距离平方 <= 25一句话：
只比较范围时，用距离平方。
需要显示真实距离时，才算 Distance。进阶：空间 Hash
固定网格不一定要真的创建一张二维数组。
如果地图很大，或者坐标可能有负数，可以用字典保存有对象的格子：
Dictionary<Vector2Int, List<Unit>> grids;把世界坐标转换成格子坐标：
int gx = Mathf.FloorToInt(position.x / cellSize);
int gy = Mathf.FloorToInt(position.z / cellSize);
Vector2Int cell = new Vector2Int(gx, gy);然后把单位放到对应格子：
grids[cell].Add(unit);这种用坐标算 key，再用字典保存格子的方式，就是常见的空间 Hash 思路。
它适合：
大地图
动态单位
稀疏分布
不想提前创建整张网格四叉树是什么
四叉树是另一种空间划分方式。
它把一个二维区域不断切成 4 块：
+---------+---------+
| 左上 | 右上 |
| NW | NE |
+---------+---------+
| 左下 | 右下 |
| SW | SE |
+---------+---------+如果某个区域里的对象太多，就继续把这个区域切成 4 块。
所以四叉树的核心是：
对象多的地方切得更细。
对象少的地方保持粗粒度。它主要适合：
地图很大
对象分布很不均匀
静态或半静态对象较多
查询范围相对局部例如：
静态碰撞物粗筛
地图资源点查找
场景装饰物裁剪
编辑器框选对象
大地图局部范围查询四叉树节点结构
一个四叉树节点通常包含：
Bounds：当前节点管理的矩形范围
Units：当前节点保存的对象
Children：4 个子节点
Depth：当前深度
Capacity：当前节点最多容纳多少对象
MaxDepth：最多切多少层伪代码可以理解成：
public sealed class QuadTreeNode
{
private readonly Rect bounds;
private readonly int depth;
private readonly int maxDepth;
private readonly int capacity;
private readonly List<Unit> units = new();
private QuadTreeNode[] children;
}四叉树什么时候切分
通常有两个限制：
每个节点最多放多少对象。
树最多切到多深。例如：
一个节点最多放 8 个对象。
最多切 5 层。当某个节点对象数量超过 8，并且还没到最大深度，就切成 4 个子节点。
原来的对象会重新分配到子节点里。
结构会变成：
Root
├── 左上
├── 右上
├── 左下
└── 右下如果左上区域对象还是很多，左上继续切：
Root
├── 左上
│ ├── 左上-左上
│ ├── 左上-右上
│ ├── 左上-左下
│ └── 左上-右下
├── 右上
├── 左下
└── 右下这就是四叉树的自适应划分。
插入对象
插入对象时，从根节点开始：
如果对象不在当前节点范围内，跳过。
如果当前节点有子节点，尝试插入子节点。
如果没有子节点，先放到当前节点。
如果当前节点对象太多，就切分并下放对象。伪代码：
void Insert(Unit unit)
{
if (!bounds.Contains(unit.Position))
{
return;
}
if (children != null)
{
QuadTreeNode child = GetChild(unit.Position);
child.Insert(unit);
return;
}
units.Add(unit);
if (units.Count > capacity && depth < maxDepth)
{
Split();
MoveUnitsToChildren();
}
}如果对象是一个点，这个逻辑比较简单。
如果对象是一个有大小的矩形，例如建筑、大怪物、碰撞盒，它可能跨多个子区域。
常见处理方式是：
能完整放进某个子节点，就放进子节点。
不能完整放进任何一个子节点，就留在当前节点。这样可以避免同一个对象被重复插入多个节点。
查询范围
查询时通常传入一个矩形范围。
例如玩家在 (10, 10)，技能半径是 5，可以先构造一个包围盒：
x: 5 ~ 15
y: 5 ~ 15查询流程：
从 Root 开始。
如果当前节点范围和查询范围不相交，直接跳过。
如果相交，检查当前节点里的对象。
如果有子节点，继续递归查询子节点。伪代码：
void Query(Rect searchArea, List<Unit> result)
{
if (!bounds.Overlaps(searchArea))
{
return;
}
foreach (var unit in units)
{
if (searchArea.Contains(unit.Position))
{
result.Add(unit);
}
}
if (children == null)
{
return;
}
foreach (var child in children)
{
child.Query(searchArea, result);
}
}如果最终需要圆形范围，还要再做一次距离平方判断：
float radiusSqr = radius * radius;
foreach (var unit in candidates)
{
if ((unit.Position - center).sqrMagnitude <= radiusSqr)
{
result.Add(unit);
}
}所以四叉树查询也分两步：
四叉树找候选对象。
距离判断确认最终命中对象。四叉树为什么能加速
直接遍历是：
每次查询都检查所有对象。四叉树查询是：
只进入和查询范围相交的节点。
跳过大量无关区域。例如你只查地图左上角附近的对象，四叉树可以跳过右半张地图、下半张地图的大量节点。
它快的原因不是单次距离判断更快，而是：
减少需要判断的对象数量。四叉树的常见坑
第一，动态对象维护成本高。
对象移动后，可能需要：
从旧节点移除。
插入新节点。
必要时重新分裂或合并节点。如果大量子弹、怪物每帧都在移动，维护四叉树本身可能很麻烦。
第二，树不能无限切。
要限制：
最大深度
最小区域大小
每个节点容量否则节点太多，递归成本和内存成本都会上升。
第三，频繁分裂和合并会抖动。
如果对象数量总是在阈值附近变化，节点可能反复拆分、合并。
工程实践中常见做法是：
只分裂，不频繁合并。
定期重建整棵树。
静态对象用四叉树，动态对象用网格。第四，矩形粗筛不等于圆形命中。
四叉树通常用矩形范围查询，但技能范围经常是圆形。
所以仍然要做最终距离判断。
九宫格和四叉树的区别
九宫格 / 空间 Hash 是固定切法：
所有格子一样大。四叉树是动态切法：
对象多的区域切得更细。
对象少的区域保持粗。可以这样理解：
九宫格：规则地铺格子。
四叉树：哪里拥挤，哪里继续切小。工程选择上：
动态单位多、高频移动：优先九宫格 / 空间 Hash。
静态对象多、分布不均：可以考虑四叉树。怎么选
如果只是做：
怪物感知
AOE 找目标
自动拾取
附近单位粗筛
移动单位高频查询优先考虑九宫格或空间 Hash。
如果是：
超大地图
对象分布很不均匀
静态或半静态对象较多
需要跳过大片空区域可以考虑四叉树。
最重要的收获
空间划分的本质是：
先缩小候选范围，再做精确判断。九宫格适合：
规则网格下的高频动态对象查询。四叉树适合：
大空间里对象分布不均的自适应查询。四叉树不是“更高级的九宫格”，而是服务于另一类问题：
让空间划分跟着对象密度变化。