游戏 AI / 系统课时

用空间分区减少邻居查询

用空间分区减少邻居查询

群体移动中,Separation、Alignment、Cohesion 都需要反复寻找附近单位。直接让每个 NPC 扫描所有其他 NPC,单位数量一大就会迅速拖慢帧率。本课用规则网格和空间哈希把搜索范围限制在附近格子,再对候选对象做精确距离判断。

学习目标

  • 理解全量邻居扫描为什么会形成平方级计算量
  • 能用规则网格与空间哈希缩小邻居候选集合
  • 能根据邻域半径选择网格尺寸,并处理格子边界问题

全量扫描为什么越来越贵

假设场景中有 NN 个 NPC,每个 NPC 都要检查其余 N−1N-1 个单位,单帧邻居查询大约需要 N(N−1)N(N-1) 次距离判断,因此整体复杂度接近 O(N2)O(N^2)。

100 个单位时约是一万级判断,1000 个单位时已经接近一百万级。更麻烦的是,真正位于感知半径内的通常只有少数几个,大量计算都浪费在相距很远的对象上。

空间分区的目标不是直接判断谁是邻居,而是先回答一个更便宜的问题:哪些对象有可能成为邻居?

网格如何缩小候选范围

把二维世界划分为固定大小的格子,每个 NPC 根据坐标进入对应格子。如果邻域半径与格子边长接近,查询一个 NPC 时通常只需要检查自己所在格以及周围八个格子。

规则网格把全场邻居扫描缩小为局部格子查询

如果格子边长为 cellSize,世界坐标 (x, y) 可以映射为整数格子坐标:floor(x / cellSize)、floor(y / cellSize)。空间哈希只是把这对整数坐标编码成可快速查找的键,并不要求真的建立完整二维数组。

选择格子尺寸时可先让 cellSize 接近常用邻域半径。格子太大,一个格子仍会装进大量单位;格子太小,则一次查询需要遍历更多格子。

用空间哈希实现邻居查询

下面示例使用 JavaScript Map 保存非空格子。查询分成两阶段:先从邻近格子取得候选对象,再使用真实欧氏距离过滤。这样即使两个单位处在相邻格子,也不会被误判为邻居。

js
class SpatialHashGrid {
  constructor(cellSize) {
    this.cellSize = cellSize;
    this.cells = new Map();
  }

  key(x, y) {
    const gx = Math.floor(x / this.cellSize);
    const gy = Math.floor(y / this.cellSize);
    return `${gx},${gy}`;
  }

  insert(agent) {
    const key = this.key(agent.x, agent.y);
    if (!this.cells.has(key)) this.cells.set(key, []);
    this.cells.get(key).push(agent);
  }

  queryCandidates(x, y, radius) {
    const gx = Math.floor(x / this.cellSize);
    const gy = Math.floor(y / this.cellSize);
    const range = Math.ceil(radius / this.cellSize);
    const result = [];

    // 只访问查询点附近可能与搜索圆相交的格子。
    for (let dx = -range; dx <= range; dx++) {
      for (let dy = -range; dy <= range; dy++) {
        const bucket = this.cells.get(`${gx + dx},${gy + dy}`);
        if (bucket) result.push(...bucket);
      }
    }
    return result;
  }

  queryNeighbors(agent, radius) {
    const radiusSq = radius * radius;
    return this.queryCandidates(agent.x, agent.y, radius).filter(other => {
      if (other.id === agent.id) return false;
      const dx = other.x - agent.x;
      const dy = other.y - agent.y;
      // 用平方距离避免每次执行 Math.sqrt。
      return dx * dx + dy * dy <= radiusSq;
    });
  }
}

const agents = [
  { id: "A", x: 2, y: 2 },
  { id: "B", x: 6, y: 3 },
  { id: "C", x: 12, y: 2 },
  { id: "D", x: 18, y: 8 },
  { id: "E", x: 35, y: 30 },
  { id: "F", x: 9, y: 8 },
  { id: "G", x: 50, y: 4 },
  { id: "H", x: -30, y: 20 },
  { id: "I", x: 80, y: 80 },
  { id: "J", x: 40, y: -25 }
];

const grid = new SpatialHashGrid(10);
for (const agent of agents) grid.insert(agent);

const current = agents[0];
const radius = 10;
const candidates = grid
  .queryCandidates(current.x, current.y, radius)
  .filter(agent => agent.id !== current.id);
const neighbors = grid.queryNeighbors(current, radius);

console.log(`all=${agents.length - 1}`);
console.log(`candidates=${candidates.length}`);
console.log(`neighbors=${neighbors.map(a => a.id).join(",")}`);

预期输出:

text
all=9
candidates=4
neighbors=B,F

这里全量扫描原本需要检查 9 个其他单位,空间分区先把候选集缩到 4 个,最终只有 B、F 位于半径 10 内。真实项目中单位越多、分布越稀疏,候选集缩减通常越明显。

动态单位还要维护格子归属

NPC 会持续移动,因此不能只在创建时插入网格。每次位置跨越格子边界时,应把它从旧桶移到新桶;否则查询结果会逐渐与真实位置脱节。

不必每帧无条件删除再插入。可以缓存单位上一帧的格子坐标,仅当新旧格子不同才更新桶。这样移动幅度较小时,大部分帧只需要一次格子坐标比较。

当群体规模只有几十个单位时,全量扫描往往已经足够简单;当单位达到数百甚至数千,并且邻域半径远小于整个地图尺寸时,网格或空间哈希才会真正体现价值。优化时应同时观察平均候选数,而不是只看理论复杂度。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用空间分区减少邻居查询

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通