空间分区

意图

把对象存进按位置组织的数据结构，以便高效地找到它们。（Game Programming Patterns — spatial-partition）

机制

一组对象，每个都有空间位置。把它们存进按位置组织的空间数据结构，就能高效地查询某位置处或附近的对象。对象位置变化时，更新空间数据结构，使它仍然能找到该对象。（Game Programming Patterns — spatial-partition）

书中的例子是战场上的单位找身边的敌人攻击：两两检查是 $O(n^2)$；把战场划成固定大小的格子，每个格子存一个单位链表，单位只需要和同格（以及相邻格，处理贴着边界的情况）的单位比较。单位移动跨格时，从旧格的链表移到新格。（Game Programming Patterns — spatial-partition）

书中要点（Game Programming Patterns — spatial-partition）：

• 动机：游戏世界有空间感，除了物理，音频引擎会让远处的声音更小，在线聊天可能只限附近玩家，于是引擎经常要回答“这个位置附近有哪些对象”。
• 一维的启发：如果战场简化成一条战线，把单位按位置排序后用二分查找，找出所有交战单位就从 $O(n^2)$ 降到 $O(n \log n)$（鸽巢排序甚至能到 $O(n)$）。本模式就是把“按位置组织数据”推广到多维。
• 看似更慢：从两层循环变成“格子 + 两层单位”的三层循环，但内层两层的单位少了很多，足以抵消；格子太小时外层循环开销就显出来了。
• 双向链表：跨格移动时只需改几个指针就能摘下、插入，单位多且每帧移动时很重要。作者说明书中刻意不用标准库容器是为了讲清细节，实际代码请用现成的集合。
• 攻击距离：单位位置完全相同才交战是“作弊”的简化；有攻击距离时，不同格子里的单位也可能够得着，所以还要查相邻格，但只查八个邻居中的四个，原因和内层循环从当前单位之后开始一样：避免同一对单位被比较两次（A 找到 B、B 又找到 A）。查哪一半无所谓。若攻击距离大于格子，还得往外扫多圈。

下面是整理者的粗略估算（书中未给出公式）：设战场被分成 $k$ 个格子，单位均匀分布，则每格约 $n/k$ 个单位，只算同格比较时，两两检查的次数从 $O(n^2)$ 降到大约

但单位全挤在一个格子里时，又退化回 $O(n^2)$，这是书中明确指出的，也是后面讨论“平衡”的原因。

下图表示固定网格的查询过程：先把位置映射到格子，再只检查该格及相邻格中的对象。

flowchart LR
  P["单位位置 (x, y)"] --> C["格子坐标 = (⌊x / 格宽⌋, ⌊y / 格高⌋)"]
  C --> L["该格的单位链表"]
  C --> N["相邻格的单位链表"]
  L --> T["逐个距离检查"]
  N --> T

查询的开销只取决于这几个格子里有多少对象，与全场总数无关。

何时使用

有一组带位置的对象，并且按位置查找对象的查询多到影响了性能。它既常用于存放会移动的游戏对象，也常用于存放静态的美术资源和关卡几何；复杂的游戏往往对不同内容各用一个空间分区。（Game Programming Patterns — spatial-partition）

取舍与坑（Game Programming Patterns — spatial-partition）

• $n$ 越大越值得；$n$ 很小时可能不值得折腾。
• 对象移动时要重组数据结构，既增加代码复杂度又花 CPU，要确认划算。作者的比喻：想象一个键会自己变化的哈希表。
• 额外的簿记结构要占内存，是用内存换速度。

设计决策（Game Programming Patterns — spatial-partition）

各种空间结构其实都是一维数据结构在多维上的推广：网格是持久化的桶排序，BSP、k-d 树、BVH 是二叉搜索树，四叉树和八叉树是 trie（前缀树）。（Game Programming Patterns — spatial-partition）

代码草图（C++）

按书中示例整理：

class Unit {
  friend class Grid;
public:
  Unit(Grid* grid, double x, double y)
  : grid_(grid), x_(x), y_(y), prev_(NULL), next_(NULL) {
    grid_->add(this);                     // 创建时放入网格
  }
  void move(double x, double y) { grid_->move(this, x, y); }
private:
  double x_, y_;
  Grid* grid_;
  Unit* prev_;                            // 同格双向链表
  Unit* next_;
};

class Grid {
public:
  Grid() {                                // 清空网格
    for (int x = 0; x < NUM_CELLS; x++)
      for (int y = 0; y < NUM_CELLS; y++) cells_[x][y] = NULL;
  }
  void add(Unit* unit);
  void move(Unit* unit, double x, double y);
  void handleMelee();
  void handleCell(int x, int y);
  void handleUnit(Unit* unit, Unit* other);

  static const int NUM_CELLS = 10;
  static const int CELL_SIZE = 20;
private:
  Unit* cells_[NUM_CELLS][NUM_CELLS];
};

void Grid::add(Unit* unit) {
  int cellX = (int)(unit->x_ / Grid::CELL_SIZE);   // 世界坐标 → 格子下标
  int cellY = (int)(unit->y_ / Grid::CELL_SIZE);
  unit->prev_ = NULL;                              // 插到该格链表头
  unit->next_ = cells_[cellX][cellY];
  cells_[cellX][cellY] = unit;
  if (unit->next_ != NULL) unit->next_->prev_ = unit;
}

void Grid::move(Unit* unit, double x, double y) {
  int oldCellX = (int)(unit->x_ / Grid::CELL_SIZE);
  int oldCellY = (int)(unit->y_ / Grid::CELL_SIZE);
  int cellX = (int)(x / Grid::CELL_SIZE);
  int cellY = (int)(y / Grid::CELL_SIZE);
  unit->x_ = x;
  unit->y_ = y;
  if (oldCellX == cellX && oldCellY == cellY) return;   // 没跨格

  if (unit->prev_ != NULL) unit->prev_->next_ = unit->next_;   // 从旧格摘下
  if (unit->next_ != NULL) unit->next_->prev_ = unit->prev_;
  if (cells_[oldCellX][oldCellY] == unit) cells_[oldCellX][oldCellY] = unit->next_;
  add(unit);                                                   // 加入新格
}

void Grid::handleMelee() {
  for (int x = 0; x < NUM_CELLS; x++)
    for (int y = 0; y < NUM_CELLS; y++) handleCell(x, y);   // 书中此处仍是早先的 handleCell(cells_[x][y])
}

void Grid::handleUnit(Unit* unit, Unit* other) {
  while (other != NULL) {
    if (distance(unit, other) < ATTACK_DISTANCE) handleAttack(unit, other);
    other = other->next_;
  }
}

void Grid::handleCell(int x, int y) {
  Unit* unit = cells_[x][y];
  while (unit != NULL) {
    handleUnit(unit, unit->next_);                          // 同格其他单位
    // 只查一半邻居，避免重复比较
    if (x > 0 && y > 0) handleUnit(unit, cells_[x - 1][y - 1]);
    if (x > 0) handleUnit(unit, cells_[x - 1][y]);
    if (y > 0) handleUnit(unit, cells_[x][y - 1]);
    if (x > 0 && y < NUM_CELLS - 1) handleUnit(unit, cells_[x - 1][y + 1]);
    unit = unit->next_;
  }
}

UE 与理论页中的对应

• 空间数据结构理论 → 空间数据结构：RTR4 第 19 章详细讲了 BVH、BSP（轴对齐的 k-d 树与多边形对齐两种）、八叉树与松散八叉树。该页的分类（空间细分型与包围型、规则细分与不规则细分）可以和上表的“扁平/层次”“固定/自适应”对照着读。
• 按网格划分世界 → 世界分区：世界分区把整个世界按可配置的运行时网格划分为单元格 (Cell)，由流送源按距离加载或卸载。这是固定网格思想用于“按位置决定加载什么”，查询对象是单元格而不是单个 Actor。
• 网络层的空间网格 → 复制图：复制图用空间网格节点按格子存放可能被看到或听到的 Actor，客户端相机所在格子的持久列表可以直接用；该页自己也指出，这正是空间数据结构中网格划分的思想在网络层的应用。
• 四叉树 → 水体系统：UE 水体用四叉树网格做 LOD。

GEA 的视角：碰撞检测中的空间划分（卷 II 14.3.6）

• GPP 的空间分区模式用于"按位置查找附近对象"；GEA 第 14 章说明碰撞引擎出于同样的原因使用空间哈希、空间细分或层次包围体：暴力两两测试是 $O(n^2)$（卷 II 14.3.6）。层次结构的好处是同一分支中的对象不可能与兄弟分支中的对象碰撞（卷 II 14.3.6.2）。
• GEA 还给出本页没有的一种宽相方案：扫描剪除，即沿三条主轴对 AABB 端点排序，利用帧间相干性把排序降到期望 $O(n)$。Havok、ODE、PhysX 的宽相都用它（卷 II 14.3.6.3）。
• 详见 碰撞检测系统。