20. Spatial Partition

为什么"20. Spatial Partition"从问题证据开始

你的战场上有几千个单位，每帧都要做碰撞检测：子弹打没打中人、人有没有撞到人。最直觉的实现是两两检测——每个单位和其他所有单位比对，N 个单位就是 N×(N-1)/2 次检测。代码今天能跑，但几千个单位时这个数字是几百万——帧率直接崩掉。大多数检测其实毫无意义（距离十万八千里的两个单位根本不可能碰撞）。

本页把"无模式基线"定义为"两两检测 O(N²)"的代码，然后引入空间分区作为候选机制，验证它是否真的让"检测次数"下降。通过条件是每次查询只检测可能相邻的候选集合——而不是与全世界比对。

🔮 先预测：5000 个单位两两检测要多少次，网格方案要多少次？

来源、版本与独立重写边界

本页用作者完整在线正文核对正式标题、设计分叉和时代语境，并以作者源码仓库交叉检查结构。仓库许可证明确正文、HTML与样式为 CC BY-NC-ND 4.0，示例程序等其他文件为 MIT；因此下列中文解释、图示、交互和代码均为独立教学重写，不翻译、拼接或改写受 ND 限制的原文表达。

本章机制与术语

理解 Spatial Partition 需要四个核心概念：

• 空间分区（spatial partition）：按位置把对象分组的索引结构——把"全世界搜索"变成"邻居搜索"。
• 网格（grid）：最简单的分区——把空间切成格子，对象登记到所在格。
• 邻格查询（neighbor query）：只检测同格与相邻格的对象——候选集大幅缩小。
• 动态更新（dynamic update）：对象移动后更新所属格——索引保持精确。

四个概念共同约束"按空间位置把对象分区，只查询可能相邻的候选集合"：任何结论都必须回到"检测次数、查询耗时、分区维护开销"三个可观察量。

💡 对着动画看：动画左右对比——左侧"暴力：两两检测 28 对"（红色连线，4 个单位全互连），右侧"网格：3×3 划分"（单位登记到格，绿色点），下方"只检测同格，邻格共 2 个"说明。读"绘制战线"一节时，想象战场上几千个单位被切进格子——每个单位只需和同格邻居比，而不是和所有人比。

官方结构逐项深读

20. Spatial Partition

Spatial Partition 的主张：用空间索引把"查找邻居"变快。对象按位置登记进分区结构（网格、四叉树、BVH），查询"谁在我附近"时只访问该位置的分区——候选集从"全部 N 个"缩到"同区几个"。它是空间索引在游戏里的应用：以"维护分区"的代价，换取"查询邻居"的 O(N²)→O(N) 飞跃。

Intent

意图：把"对象之间的关系查询"从全量扫描变成局部查询。碰撞检测、视野查询、最近敌人查找——这些"找邻居"的操作，如果每次都遍历全部对象，复杂度 O(N²)；空间分区把对象按位置分组后，查询只碰"该位置的组"，复杂度降到 O(N + 每组内对象数)。以索引维护成本换查询加速——查询频繁、对象众多时稳赚。

Motivation

战场的碰撞：5000 个单位两两检测 = 1250 万次——每帧做这么多次距离计算，帧率个位数。而且绝大多数检测注定失败（相距几十米的两个单位不可能碰撞）——这些计算全是浪费。空间分区让"可能碰撞"的对象先被筛出来：单位只在"同格 + 邻格"里找对手——5000 个单位的候选集缩到每格几个，检测次数降几个数量级。

Units on the field of battle

战场场景：骑士、弓箭手、箭矢散布在矩形战场上。每帧要回答的问题：这支箭射中了谁？（碰撞检测）、离我最近的敌人在哪？（寻路/AI）、谁在我视野内？（渲染裁剪）。三个问题本质相同——"找空间上的邻居"。暴力解法：每个对象问一遍"谁离我近"就遍历全世界。

Drawing battle lines

绘制"战线"：把战场切成格子（网格分区）——每个单位知道自己属于哪个格。查询"谁离我近"变成"查同格和邻格"——战线从"全世界"缩到"周围一圈"。格子是空间分区最直观的形态：切法简单、查询直接、维护容易。它的效果取决于对象分布——分布均匀时每格几个对象，查询极快；挤在一起时单格对象多，退化为局部暴力。

The Pattern

模式结构：分区结构（网格：格子数组；或树：四叉树/BVH）→ 登记（对象插入到其位置对应的分区）→ 查询（给定位置/范围，返回同区及邻区的候选对象）→ 更新（对象移动后，若跨区则从旧区移除、插入新区）。关键权衡：分区粒度（格子太粗→每格人多查询慢；太细→维护开销大、跨区频繁）——按对象大小与分布调。

When to Use It

何时用空间分区：对象数量大且需要频繁的邻居查询（碰撞检测、AI 寻路、渲染裁剪）、查询收益 > 维护成本（对象众多且查询频繁）。何时不用：对象少（几十个两两检测无压力，分区是多余开销）、对象分布极度不均（全挤一格里，分区退化为暴力）、对象移动极其频繁（维护分区比查询还贵）。判断标准："N 多大、查询多频繁"——大到两两检测扛不住就用。

Keep in Mind

空间分区的注意点：分区维护有成本（对象跨区要摘旧插新——移动频繁时开销显著）；查询结果要二次验证（分区给出"候选集"，还要精确距离检测确认——格子里的对象不一定真碰撞）；内存与结构复杂度（分区结构本身要维护、要调试）。作者提醒：分区是"空间换时间"，结构选型（网格 vs 树）影响巨大。

Sample Code

示例代码：Grid 类——Cell cells[COLS][ROWS]，每个 Cell 是对象列表（链表/vector）。insert(obj) 按位置算格索引插入；remove(obj) 从所在格移除；query(area) 遍历 area 覆盖的格收集候选。单位移动：先 remove 再按新位置 insert。查询"谁在箭矢周围"= 查箭矢所在格 + 相邻格。

A sheet of graph paper

"一张坐标纸"：网格分区的本质就是把世界当成坐标纸——每个格子是坐标纸的一格，对象落在哪格就登记到哪。查询时以"某格为中心画个圈"，只翻圈内几格。网格的格子大小是核心参数：格子 ≈ 对象大小（每个格通常最多一个对象）时最优——太大了每格装多个对象查询退化，太小了跨格频繁维护开销大。

A grid of linked units

网格的存储：每格一个对象链表——Cell { Unit* head; }，单位内嵌 next 指针串成链。插入 O(1)（链头插入）、移除 O(1)（双向链摘节点）。用链表而非数组是因为对象频繁进出格子（动态性）——链表增删 O(1) 且对象地址不变（指针稳定，适合对象池/实体持有）。格子 = 链表数组。

Entering the field of battle

单位入场：进入战场时 insert 到所在格。之后每帧移动，若跨过格线就 remove + insert（更新登记）。跨格判定：对象位置是否还在旧格的范围内——不在则换格。这个"维护"成本是空间分区的代价：每个移动的单位每帧检查一次格归属，跨格时做一次链表操作——O(1) 摊销。

A clash of swords

交战检测：一个单位要"找攻击目标"——查自己所在格 + 相邻 8 格（3×3 邻域）收集候选，再精确距离判定。候选集从"全部单位"缩到"周围几格"——这是空间分区的核心收益。注意：候选格里的对象还需要精确检测（分区管"可能"，不管"确定"）——两层过滤：分区粗筛 + 距离精筛。

Charging forward

冲锋场景：一个单位快速移动——一帧内跨过多个格子。若只按"帧末位置"登记，中间穿过的格子的单位可能"错过"（本应碰撞却没检测到）。解法：沿路径逐格更新（移动时沿途经过的格都检查）或扩大查询范围（查询覆盖移动前后的范围）。这是空间分区的经典边界问题：快速对象 vs 格子粒度。

At arm's length

"手臂长度"比喻：查询范围 = 对象的"作用半径"（攻击距离、视野距离）。网格查询的半径决定扫几圈格——半径小（近战）扫 3×3，半径大（远程）扫 5×5 甚至更大。查询半径与格子大小共同决定候选集规模——半径固定时格子越小候选越少但维护越贵。设计时让"作用半径 ≈ 格子的几倍"是个合理起点。

Design Decisions

三个关键设计决策：分区是层次还是扁平（网格 vs 树）、分区是否依赖对象集合（固定网格 vs 自适应）、对象是否只存在分区里（分区是唯一索引 vs 另有主列表）。前者决定结构形态，后两者决定一致性——下面三节展开。

Is the partition hierarchical or flat?

分区结构：扁平网格（固定格子数组——实现简单、查询直接，但对象分布不均时格子利用率差：空格浪费、密集格拥挤）与层次结构（四叉树/BVH——树随对象分布自适应，密集区域细分区、空旷区域粗分区，内存高效但实现复杂、动态更新难）。作者建议：对象分布均匀用网格，分布差异大用树——多数游戏场景网格够用。

Does the partitioning depend on the set of objects?

分区是否自适应：固定分区（格子大小固定，不随对象变化——实现简单、查询稳定，但对象全挤一角时格子浪费）与自适应分区（分区随对象分布调整——四叉树自动细分密集区，内存与查询都高效，但动态对象增删时树要调整）。作者建议：固定网格起步（简单可靠），对象分布极度不均时再上自适应树。

Are objects only stored in the partition?

对象存储：分区是唯一存储（对象只活在格子链表里——遍历世界 = 遍历格子，内存紧凑，但"无序遍历所有对象"变复杂）与分区是辅助索引（对象在主列表，分区只存引用——遍历主列表简单，但两份存储要同步、内存翻倍）。作者建议：分区做唯一存储（游戏世界遍历常按空间进行：渲染按区域、碰撞按区域——分区即世界）。

See Also

• Object Pool：对象池管"对象的生命周期"，空间分区管"对象的位置关系"——池中的对象可挂进分区结构（内嵌链表节点）。
• Data Locality：分区把空间上相近的对象分组——若它们还连续存储（分区数组），数据局部性也受益。
• 四叉树/八叉树：网格的层次升级版——场景密度不均时用树形分区。

可迁移实现或计算骨架

initial state -> 世界切格 -> 对象 insert 到所在格 -> 移动时跨格则 remove+insert -> 查询只扫同格+邻格
fault injection -> 两两检测 O(N²)
pass condition -> 查询候选集缩小、检测次数下降、维护开销可接受
reset -> initial state

对应实现要点：网格大小 ≈ 对象大小；格子用链表（单位内嵌 next）；移动跨格做 remove+insert；查询覆盖作用半径的格子范围；候选做二次精确检测。该骨架只保存实验合同；真实项目还要固定网格粒度、查询半径与快速对象策略，并保留基线实现以便回退。

本章练习与节点验证矩阵

术语复核

练习答案参考

练习判据即答案：每个练习的"验证判据"列给出了通过标准——先自己动手，再对照判据核验。

术语复核与本章回顾

掌握"20. Spatial Partition"意味着能从"两两检测让数千单位帧率崩掉"出发，解释空间分区、网格、邻格查询与动态更新四者的关系，再用"检测次数、查询耗时、分区维护开销"三个可观察量推翻或保留实现。若三个判据不能同时满足，本章仍未通过。

一句话回顾：世界切格、对象归格、查询只碰邻格——几千个单位不再是"谁都要比过全世界"，而是"只看周围一圈"，O(N²) 就此谢幕。

阅读导航

← 上一页：19. Object Pool · 下一页：《游戏编程模式》全书总复习 → ← 上一页：19. Object Pool · 下一页：《游戏编程模式》全书总复习 →