多人游戏与网络同步 / 系统课时

空间分区怎样缩小同步计算

空间分区怎样缩小同步计算

空间分区的目的不是改变谁该同步,而是让服务器先在局部桶里找候选对象,再做精确相关性判断。这样可以把“遍历全地图”改成“只查玩家附近的格子”,尤其适合对象很多、查询半径远小于世界尺寸的场景。

学习目标

  • 理解均匀网格如何把全量对象扫描缩小为局部候选查询。
  • 实现一个可运行的网格索引,并验证候选数与最终相关对象数。
  • 识别格子大小、移动对象迁移和大范围对象带来的边界问题。

从全量扫描变成局部候选集

最直接的相关性判断会让每个玩家遍历世界中的全部 NN 个对象,再逐个计算距离或规则,单次查询成本近似为 O(N)O(N)。空间分区先按位置把对象放进桶中,玩家查询时只访问与兴趣范围相交的桶,再对桶内候选做精确判断。

均匀网格是一种常见的粗筛结构。若一次查询只触碰 kk 个格子,格子里合计有 CC 个候选对象,那么主要工作就从遍历 NN 个对象变成访问少量格子并检查 CC 个候选。空间分区只减少候选生成成本,不能替代最终的距离、阵营、权限或玩法相关性判断。

均匀网格把全地图扫描缩小为局部候选查询

网格查询必须守住的规则

对象进入网格时,可用 Math.floor(x / cellSize) 和 Math.floor(y / cellSize) 得到格子坐标。查询时不要写死“周围九宫格”,而应根据兴趣范围的最小、最大坐标计算需要访问的格子区间;当查询半径变化时,这种写法仍然正确。

格子只负责粗筛。圆形兴趣范围查询到的是与其包围盒相交的格子,因此候选中一定会混入圆外对象,必须再做精确距离判断。动态对象跨越格子边界时也要从旧桶删除并插入新桶,否则索引会产生漏查或重复。

用可运行示例验证候选缩小

下面仍使用 1000×1000 世界、10000 个对象和半径 50 的玩家兴趣范围。网格边长设为 100,查询先找与兴趣范围包围盒相交的格子,再做圆形距离过滤。

js
const worldSize = 1000;
const step = 10;
const cellSize = 100;
const player = { x: 500, y: 500 };
const radius = 50;

const objects = [];
const grid = new Map();

function key(cx, cy) {
  return `${cx},${cy}`;
}

function addToGrid(obj) {
  const cx = Math.floor(obj.x / cellSize);
  const cy = Math.floor(obj.y / cellSize);
  const k = key(cx, cy);
  if (!grid.has(k)) grid.set(k, []);
  grid.get(k).push(obj);
}

for (let x = 0; x < worldSize; x += step) {
  for (let y = 0; y < worldSize; y += step) {
    const obj = { x, y };
    objects.push(obj);
    addToGrid(obj);
  }
}

// 先用查询包围盒确定需要访问的格子,再做精确圆形过滤。
const minCellX = Math.floor((player.x - radius) / cellSize);
const maxCellX = Math.floor((player.x + radius) / cellSize);
const minCellY = Math.floor((player.y - radius) / cellSize);
const maxCellY = Math.floor((player.y + radius) / cellSize);

const candidates = [];
let scannedCells = 0;

for (let cx = minCellX; cx <= maxCellX; cx++) {
  for (let cy = minCellY; cy <= maxCellY; cy++) {
    scannedCells++;
    candidates.push(...(grid.get(key(cx, cy)) ?? []));
  }
}

const relevant = candidates.filter((obj) => {
  const dx = obj.x - player.x;
  const dy = obj.y - player.y;
  return dx * dx + dy * dy <= radius * radius;
});

console.log(`all objects: ${objects.length}`);
console.log(`scanned cells: ${scannedCells}`);
console.log(`grid candidates: ${candidates.length}`);
console.log(`relevant objects: ${relevant.length}`);

预期输出

text
all objects: 10000
scanned cells: 4
grid candidates: 400
relevant objects: 81

最终相关对象仍是 81 个,说明空间分区没有改变查询语义;但精确距离判断从 10000 次缩小到 400 个候选。真实项目里的收益还取决于玩家数量、对象分布和索引维护成本,因此应以性能采样而不是这个比例直接推算线上加速倍数。

格子大小与索引维护怎么取舍

格子过大时,一个桶会装进太多对象,候选集再次膨胀;格子过小时,单次查询要访问更多桶,移动对象也会更频繁地跨桶。实践中可先让格子边长与典型兴趣半径处于同一量级,再通过候选数、桶访问数和更新次数共同调参。

动态对象只有在格子坐标变化时才需要迁移桶;生成、销毁和瞬移也必须同步维护索引。尺寸远大于单格的对象可以登记到多个格子,或放入单独的粗筛结构,避免只按中心点登记后被漏查。

当地图对象很少、兴趣范围几乎覆盖全图,或绝大多数对象本来就位于玩家附近时,空间分区收益会很有限。此时瓶颈更可能在序列化、带宽、发送频率或客户端处理,应先看采样数据再决定是否继续细化空间索引。

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

目录与阅读设置

阅读设置

17

记录一个想法

空间分区怎样缩小同步计算

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

登录哪都通