《MMO 服务器开发》4.1 九宫格 AOI 从零实现

// file: internal/aoi/types.go
// tier: L1
// verify: go test ./internal/aoi/
package aoi

// EntityID 是场景内实体的唯一句柄：高 16 位是场景/实例号，低 48 位是
// 实例内自增序号。卷二所有玩法系统复用这个口径（见共享类型表）。
type EntityID uint64

const (
	entitySeqBits = 48
	entitySeqMask = (uint64(1) << entitySeqBits) - 1
)

// MakeEntityID 把实例号与实例内序号拼成一个 EntityID。
func MakeEntityID(instance uint16, seq uint64) EntityID {
	return EntityID(uint64(instance)<<entitySeqBits | (seq & entitySeqMask))
}

// Instance 取回高 16 位的实例号。
func (e EntityID) Instance() uint16 { return uint16(e >> entitySeqBits) }

// LocalSeq 取回低 48 位的实例内序号。
func (e EntityID) LocalSeq() uint64 { return uint64(e) & entitySeqMask }

// Vec2 是服务器侧的逻辑坐标（浮点），与客户端像素坐标分离。
type Vec2 struct{ X, Y float64 }

// GridSize 是九宫格的格边长（逻辑单位），全卷统一为 8.0。
const GridSize = 8.0

// within 判断 b 是否落在以 a 为圆心、r 为半径的圆内（闭区间）。
// 比较距离平方，省掉一次开方。
func within(a, b Vec2, r float64) bool {
	dx, dy := a.X-b.X, a.Y-b.Y
	return dx*dx+dy*dy <= r*r
}

// file: internal/aoi/grid.go
// tier: L1
// verify: go test ./internal/aoi/
package aoi

import "math"

// cell 是九宫格里的一个格坐标。
type cell struct{ X, Y int }

// cellOf 把逻辑坐标映射到格坐标。用 Floor 保证负坐标也正确落格。
func cellOf(p Vec2) cell {
	return cell{X: int(math.Floor(p.X / GridSize)), Y: int(math.Floor(p.Y / GridSize))}
}

// Grid 是九宫格 AOI：世界按 GridSize 切格，每个格维护一个实体集合。
// 查询「谁在我附近」只需扫描自己所在格与相邻 8 格（九宫格），复杂度与
// 世界总人数无关，只与局部密度有关。
type Grid struct {
	cells map[cell]map[EntityID]Vec2 // 格 -> (实体 -> 当前位置)
	where map[EntityID]cell          // 实体 -> 当前所在格，移动时 O(1) 定位
}

func NewGrid() *Grid {
	return &Grid{
		cells: make(map[cell]map[EntityID]Vec2),
		where: make(map[EntityID]cell),
	}
}

// Add 把一个实体放进它所在格。重复 Add 同一 ID 会先摘掉旧记录。
func (g *Grid) Add(id EntityID, p Vec2) {
	if old, ok := g.where[id]; ok {
		g.detach(old, id)
	}
	c := cellOf(p)
	m := g.cells[c]
	if m == nil {
		m = make(map[EntityID]Vec2)
		g.cells[c] = m
	}
	m[id] = p
	g.where[id] = c
}

// Move 更新实体位置：若跨格则从旧格摘下、挂到新格；同格内只改坐标。
func (g *Grid) Move(id EntityID, p Vec2) {
	old, ok := g.where[id]
	if !ok {
		g.Add(id, p)
		return
	}
	nc := cellOf(p)
	if nc == old {
		g.cells[old][id] = p
		return
	}
	g.detach(old, id)
	m := g.cells[nc]
	if m == nil {
		m = make(map[EntityID]Vec2)
		g.cells[nc] = m
	}
	m[id] = p
	g.where[id] = nc
}

// Remove 把实体从格子里摘掉。
func (g *Grid) Remove(id EntityID) {
	if c, ok := g.where[id]; ok {
		g.detach(c, id)
	}
}

func (g *Grid) detach(c cell, id EntityID) {
	m := g.cells[c]
	delete(m, id)
	if len(m) == 0 {
		delete(g.cells, c) // 空格子及时回收，避免地图越大内存越胀
	}
	delete(g.where, id)
}

// Neighbors 返回九宫格内的其它实体（不含自己）。这是「九宫格 AOI」的核心查询。
func (g *Grid) Neighbors(id EntityID) []EntityID {
	c, ok := g.where[id]
	if !ok {
		return nil
	}
	out := make([]EntityID, 0, 16)
	for dx := -1; dx <= 1; dx++ {
		for dy := -1; dy <= 1; dy++ {
			for other := range g.cells[cell{c.X + dx, c.Y + dy}] {
				if other != id {
					out = append(out, other)
				}
			}
		}
	}
	return out
}

// NeighborsInRadius 在九宫格基础上再按圆形半径过滤，得到更精确的兴趣集合。
// 半径不超过格边长时，扫 9 格就够；半径更大时按 ceil(r/GridSize) 扩圈。
func (g *Grid) NeighborsInRadius(id EntityID, r float64) []EntityID {
	c, ok := g.where[id]
	if !ok {
		return nil
	}
	self := g.cells[c][id]
	k := int(math.Ceil(r / GridSize))
	out := make([]EntityID, 0, 16)
	for dx := -k; dx <= k; dx++ {
		for dy := -k; dy <= k; dy++ {
			for other, p := range g.cells[cell{c.X + dx, c.Y + dy}] {
				if other != id && within(self, p, r) {
					out = append(out, other)
				}
			}
		}
	}
	return out
}

// file: internal/aoi/watcher.go
// tier: L1
// verify: go test ./internal/aoi/
package aoi

// Watcher 在九宫格之上维护「每个实体已经看见谁」的差集。移动时它把
// 「新进入视野」与「离开视野」算出来，正好对应协议的 CmdAoiAdd 0x0203
// 与 CmdAoiRemove 0x0204——AOI 结构只回答「谁在附近」，Watcher 才回答
// 「这一帧要补发哪些进出事件」。
type Watcher struct {
	grid  *Grid
	known map[EntityID]map[EntityID]struct{}
}

func NewWatcher() *Watcher {
	return &Watcher{grid: NewGrid(), known: make(map[EntityID]map[EntityID]struct{})}
}

// Add 把一个实体放进九宫格，并初始化它的已知集合。
func (w *Watcher) Add(id EntityID, p Vec2) {
	w.grid.Add(id, p)
	if w.known[id] == nil {
		w.known[id] = make(map[EntityID]struct{})
	}
}

// Move 更新位置，返回该实体本次新看见（added）与不再看见（removed）的实体。
// 顺序不保证稳定，调用方若需要确定性可自行排序。
func (w *Watcher) Move(id EntityID, p Vec2) (added, removed []EntityID) {
	w.grid.Move(id, p)
	cur := make(map[EntityID]struct{})
	for _, other := range w.grid.Neighbors(id) {
		cur[other] = struct{}{}
		if _, ok := w.known[id][other]; !ok {
			added = append(added, other)
		}
	}
	for other := range w.known[id] {
		if _, ok := cur[other]; !ok {
			removed = append(removed, other)
		}
	}
	w.known[id] = cur
	return added, removed
}

// Remove 把实体彻底移出。别人对它的「看见」会在各自下次 Move 时自然收敛。
func (w *Watcher) Remove(id EntityID) {
	w.grid.Remove(id)
	delete(w.known, id)
}

// file: AoiGrid.java
// tier: L2J
// verify: docker run --rm -v "$HOME/.aegis-java/ch04:/w" -w /w eclipse-temurin:21-jdk sh -c "javac AoiGrid.java && java AoiGrid"
// AoiGrid.java — JDK 21，九宫格 AOI 的 Java 对照实现，算法与 Go 版一致。
import java.util.*;

public final class AoiGrid {
    static final double GRID = 8.0;

    public static void main(String[] args) {
        int n = 5000; double w = 400.0, r = 8.0;
        Random rnd = new Random(12345);
        HashMap<Long, HashMap<Long, double[]>> cells = new HashMap<>();
        HashMap<Long, int[]> where = new HashMap<>();
        for (int i = 0; i < n; i++) {
            double x = rnd.nextDouble() * w, y = rnd.nextDouble() * w;
            int cx = (int) Math.floor(x / GRID), cy = (int) Math.floor(y / GRID);
            cells.computeIfAbsent(key(cx, cy), z -> new HashMap<>()).put((long) i, new double[]{x, y});
            where.put((long) i, new int[]{cx, cy});
        }
        long sink = 0;
        for (int warm = 0; warm < 5; warm++)          // 预热：让 JIT 稳定
            for (int i = 0; i < n; i++) sink += neighbors(cells, where, i, r).size();
        long best = Long.MAX_VALUE;
        for (int round = 0; round < 20; round++) {
            long t0 = System.nanoTime();
            for (int i = 0; i < n; i++) sink += neighbors(cells, where, i, r).size();
            best = Math.min(best, System.nanoTime() - t0);
        }
        System.out.printf("ns/query=%.0f  avgSet=%.2f%n",
                (double) best / n, (double) sink / (5L * n + 20L * n));
    }

    static long key(int x, int y) { return ((long) x << 32) ^ (y & 0xffffffffL); }
    static List<Long> neighbors(HashMap<Long, HashMap<Long, double[]>> cells, HashMap<Long, int[]> where, long id, double r) {
        int[] c = where.get(id);
        double[] self = cells.get(key(c[0], c[1])).get(id);
        List<Long> out = new ArrayList<>(16);
        double r2 = r * r;
        for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++) {
                var cell = cells.get(key(c[0] + dx, c[1] + dy));
                if (cell == null) continue;
                for (var e : cell.entrySet()) {
                    if (e.getKey() == id) continue;
                    double ddx = self[0] - e.getValue()[0], ddy = self[1] - e.getValue()[1];
                    if (ddx * ddx + ddy * ddy <= r2) out.add(e.getKey());
                }
            }
        return out;
    }
}