多人游戏与网络同步 / 系统课时
空间分区怎样缩小同步计算
空间分区怎样缩小同步计算
空间分区的目的不是改变谁该同步,而是让服务器先在局部桶里找候选对象,再做精确相关性判断。这样可以把“遍历全地图”改成“只查玩家附近的格子”,尤其适合对象很多、查询半径远小于世界尺寸的场景。
学习目标
- 理解均匀网格如何把全量对象扫描缩小为局部候选查询。
- 实现一个可运行的网格索引,并验证候选数与最终相关对象数。
- 识别格子大小、移动对象迁移和大范围对象带来的边界问题。
从全量扫描变成局部候选集
最直接的相关性判断会让每个玩家遍历世界中的全部 个对象,再逐个计算距离或规则,单次查询成本近似为 。空间分区先按位置把对象放进桶中,玩家查询时只访问与兴趣范围相交的桶,再对桶内候选做精确判断。
均匀网格是一种常见的粗筛结构。若一次查询只触碰 个格子,格子里合计有 个候选对象,那么主要工作就从遍历 个对象变成访问少量格子并检查 个候选。空间分区只减少候选生成成本,不能替代最终的距离、阵营、权限或玩法相关性判断。

网格查询必须守住的规则
对象进入网格时,可用 Math.floor(x / cellSize) 和 Math.floor(y / cellSize) 得到格子坐标。查询时不要写死“周围九宫格”,而应根据兴趣范围的最小、最大坐标计算需要访问的格子区间;当查询半径变化时,这种写法仍然正确。
格子只负责粗筛。圆形兴趣范围查询到的是与其包围盒相交的格子,因此候选中一定会混入圆外对象,必须再做精确距离判断。动态对象跨越格子边界时也要从旧桶删除并插入新桶,否则索引会产生漏查或重复。
用可运行示例验证候选缩小
下面仍使用 1000×1000 世界、10000 个对象和半径 50 的玩家兴趣范围。网格边长设为 100,查询先找与兴趣范围包围盒相交的格子,再做圆形距离过滤。
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}`);预期输出
all objects: 10000
scanned cells: 4
grid candidates: 400
relevant objects: 81最终相关对象仍是 81 个,说明空间分区没有改变查询语义;但精确距离判断从 10000 次缩小到 400 个候选。真实项目里的收益还取决于玩家数量、对象分布和索引维护成本,因此应以性能采样而不是这个比例直接推算线上加速倍数。
格子大小与索引维护怎么取舍
格子过大时,一个桶会装进太多对象,候选集再次膨胀;格子过小时,单次查询要访问更多桶,移动对象也会更频繁地跨桶。实践中可先让格子边长与典型兴趣半径处于同一量级,再通过候选数、桶访问数和更新次数共同调参。
动态对象只有在格子坐标变化时才需要迁移桶;生成、销毁和瞬移也必须同步维护索引。尺寸远大于单格的对象可以登记到多个格子,或放入单独的粗筛结构,避免只按中心点登记后被漏查。
当地图对象很少、兴趣范围几乎覆盖全图,或绝大多数对象本来就位于玩家附近时,空间分区收益会很有限。此时瓶颈更可能在序列化、带宽、发送频率或客户端处理,应先看采样数据再决定是否继续细化空间索引。