九宫格 AOI 的实现与广播优化

MMO AOI 兴趣区域算法 · 2024-06-01

九宫格是 MMO 里最经典的 AOI 方案：把地图划分为固定大小的格子， 玩家的视野 = 以自己所在格子为中心的 3×3 区域。

格子的划分

设格子边长为 $s$，则坐标 $(x, y)$ 所在格子为：

格子边长 $s$ 一般取略大于最大视距的值，保证 3×3 覆盖完整视野。

核心数据结构

type GridKey = `${number},${number}`;

class AoiGrid {
  private cells = new Map<GridKey, Set<number>>(); // grid -> entityIds

  private key(cx: number, cy: number): GridKey {
    return `${cx},${cy}`;
  }

  enter(id: number, cx: number, cy: number) {
    const key = this.key(cx, cy);
    let cell = this.cells.get(key);
    if (!cell) this.cells.set(key, (cell = new Set()));
    cell.add(id);
  }

  leave(id: number, cx: number, cy: number) {
    this.cells.get(this.key(cx, cy))?.delete(id);
  }

  /** 以 (cx, cy) 为中心的九宫格内全部实体 */
  queryAround(cx: number, cy: number): number[] {
    const result: number[] = [];
    for (let dx = -1; dx <= 1; dx++) {
      for (let dy = -1; dy <= 1; dy++) {
        result.push(...(this.cells.get(this.key(cx + dx, cy + dy)) ?? []));
      }
    }
    return result;
  }
}

移动时的差量同步

玩家跨格移动时，视野变化 = 新九宫格与旧九宫格的对称差， 只需对”新进入视野”和”离开视野”的实体发同步包：

flowchart LR
    A[玩家跨格移动] --> B[计算新旧九宫格]
    B --> C[差集: 新出现实体]
    B --> D[差集: 消失实体]
    C --> E[发送 Enter 包]
    D --> F[发送 Leave 包]

方案对比

实践中九宫格 + 差量广播足以支撑大多数 MMORPG 的同屏需求， 真正的瓶颈往往在移动广播的频率控制而不是 AOI 查询本身。