游戏 AI / 系统课时
用空间分区减少邻居查询
用空间分区减少邻居查询
群体移动中,Separation、Alignment、Cohesion 都需要反复寻找附近单位。直接让每个 NPC 扫描所有其他 NPC,单位数量一大就会迅速拖慢帧率。本课用规则网格和空间哈希把搜索范围限制在附近格子,再对候选对象做精确距离判断。
学习目标
- 理解全量邻居扫描为什么会形成平方级计算量
- 能用规则网格与空间哈希缩小邻居候选集合
- 能根据邻域半径选择网格尺寸,并处理格子边界问题
全量扫描为什么越来越贵
假设场景中有 个 NPC,每个 NPC 都要检查其余 个单位,单帧邻居查询大约需要 次距离判断,因此整体复杂度接近 。
100 个单位时约是一万级判断,1000 个单位时已经接近一百万级。更麻烦的是,真正位于感知半径内的通常只有少数几个,大量计算都浪费在相距很远的对象上。
空间分区的目标不是直接判断谁是邻居,而是先回答一个更便宜的问题:哪些对象有可能成为邻居?
网格如何缩小候选范围
把二维世界划分为固定大小的格子,每个 NPC 根据坐标进入对应格子。如果邻域半径与格子边长接近,查询一个 NPC 时通常只需要检查自己所在格以及周围八个格子。

如果格子边长为 cellSize,世界坐标 (x, y) 可以映射为整数格子坐标:floor(x / cellSize)、floor(y / cellSize)。空间哈希只是把这对整数坐标编码成可快速查找的键,并不要求真的建立完整二维数组。
选择格子尺寸时可先让 cellSize 接近常用邻域半径。格子太大,一个格子仍会装进大量单位;格子太小,则一次查询需要遍历更多格子。
用空间哈希实现邻居查询
下面示例使用 JavaScript Map 保存非空格子。查询分成两阶段:先从邻近格子取得候选对象,再使用真实欧氏距离过滤。这样即使两个单位处在相邻格子,也不会被误判为邻居。
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(",")}`);预期输出:
all=9
candidates=4
neighbors=B,F这里全量扫描原本需要检查 9 个其他单位,空间分区先把候选集缩到 4 个,最终只有 B、F 位于半径 10 内。真实项目中单位越多、分布越稀疏,候选集缩减通常越明显。
动态单位还要维护格子归属
NPC 会持续移动,因此不能只在创建时插入网格。每次位置跨越格子边界时,应把它从旧桶移到新桶;否则查询结果会逐渐与真实位置脱节。
不必每帧无条件删除再插入。可以缓存单位上一帧的格子坐标,仅当新旧格子不同才更新桶。这样移动幅度较小时,大部分帧只需要一次格子坐标比较。
当群体规模只有几十个单位时,全量扫描往往已经足够简单;当单位达到数百甚至数千,并且邻域半径远小于整个地图尺寸时,网格或空间哈希才会真正体现价值。优化时应同时观察平均候选数,而不是只看理论复杂度。