《MMO 服务器开发》4.3 基准：三种 AOI 的 CPU 与带宽对照

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

// Brute 是「不做兴趣管理」的基线：所有实体放在一个 map 里，查询时线性
// 扫描全部实体做距离判断。它代表最朴素的做法——每个玩家都能看到全服
// 所有人，服务端每帧向所有人广播所有人的状态。它的存在是为了给真正的
// AOI 一个对照，量化兴趣管理省下的到底是时间还是带宽。
type Brute struct {
	pos map[EntityID]Vec2
}

func NewBrute() *Brute { return &Brute{pos: make(map[EntityID]Vec2)} }

func (b *Brute) Add(id EntityID, p Vec2)  { b.pos[id] = p }
func (b *Brute) Move(id EntityID, p Vec2) { b.pos[id] = p }
func (b *Brute) Remove(id EntityID)       { delete(b.pos, id) }

// NeighborsInRadius 是 O(N) 的全量扫描，没有任何空间剪枝。
func (b *Brute) NeighborsInRadius(id EntityID, r float64) []EntityID {
	self, ok := b.pos[id]
	if !ok {
		return nil
	}
	out := make([]EntityID, 0, 16)
	for other, p := range b.pos {
		if other != id && within(self, p, r) {
			out = append(out, other)
		}
	}
	return out
}

// file: internal/aoi/bench_test.go
// tier: B
// verify: go test ./internal/aoi/ -bench . -benchmem -count=5
package aoi

import (
	"math/rand/v2"
	"testing"
)

// 基准场景：N 个玩家均匀撒在 W×W 的逻辑地图上，AOI 半径 = GridSize = 8。
// 这个密度下每个玩家的兴趣集合约 6 人，接近真实 MMO 主城一屏的量级。
const (
	benchN = 5000
	benchW = 400.0
	benchR = 8.0
)

// benchPoints 用固定种子的 PCG 生成同一批坐标，保证三套 AOI 面对完全
// 相同的输入，也保证多次 -count 之间可比。
func benchPoints() []Vec2 {
	rng := rand.New(rand.NewPCG(1, 2))
	pts := make([]Vec2, benchN)
	for i := range pts {
		pts[i] = Vec2{X: rng.Float64() * benchW, Y: rng.Float64() * benchW}
	}
	return pts
}

var (
	sinkIDs []EntityID // 包级 sink：防止查询结果被编译器优化掉
	points  = benchPoints()
)

func newGridWorld() (*Grid, []EntityID) {
	g := NewGrid()
	ids := make([]EntityID, benchN)
	for i, p := range points {
		ids[i] = MakeEntityID(1, uint64(i))
		g.Add(ids[i], p)
	}
	return g, ids
}

func newCrossLinkWorld() (*CrossLink, []EntityID) {
	cl := NewCrossLink()
	ids := make([]EntityID, benchN)
	for i, p := range points {
		ids[i] = MakeEntityID(1, uint64(i))
		cl.Add(ids[i], p)
	}
	return cl, ids
}

func newBruteWorld() (*Brute, []EntityID) {
	br := NewBrute()
	ids := make([]EntityID, benchN)
	for i, p := range points {
		ids[i] = MakeEntityID(1, uint64(i))
		br.Add(ids[i], p)
	}
	return br, ids
}

// ---------- 查询：三种 AOI 对同一个玩家的半径查询 ----------

func BenchmarkGridQuery(b *testing.B) {
	g, ids := newGridWorld()
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		sinkIDs = g.NeighborsInRadius(ids[i%benchN], benchR)
	}
}

func BenchmarkCrossLinkQuery(b *testing.B) {
	cl, ids := newCrossLinkWorld()
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		sinkIDs = cl.NeighborsInRadius(ids[i%benchN], benchR)
	}
}

func BenchmarkBruteQuery(b *testing.B) {
	br, ids := newBruteWorld()
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		sinkIDs = br.NeighborsInRadius(ids[i%benchN], benchR)
	}
}

// ---------- 移动：每帧更新一个玩家坐标的成本 ----------

func BenchmarkGridMove(b *testing.B) {
	g, ids := newGridWorld()
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		// 每次挪 0.5 个逻辑单位，多数情况不跨格。
		g.Move(ids[i%benchN], Vec2{X: points[i%benchN].X + 0.5, Y: points[i%benchN].Y})
	}
}

func BenchmarkCrossLinkMove(b *testing.B) {
	cl, ids := newCrossLinkWorld()
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		cl.Move(ids[i%benchN], Vec2{X: points[i%benchN].X + 0.5, Y: points[i%benchN].Y})
	}
}

// TestAOISetSize 报告平均兴趣集合大小，供正文的带宽估算引用。
func TestAOISetSize(t *testing.T) {
	g, ids := newGridWorld()
	total := 0
	for _, id := range ids {
		total += len(g.NeighborsInRadius(id, benchR))
	}
	avg := float64(total) / float64(len(ids))
	t.Logf("avg AOI set size = %.2f (N=%d, W=%.0f, r=%.0f)", avg, benchN, benchW, benchR)
	if avg <= 0 || avg >= float64(benchN) {
		t.Fatalf("unexpected avg set size %.2f", avg)
	}
}

$ go test ./internal/aoi/ -bench . -benchmem -count=5 -run '^$'
BenchmarkGridQuery-10         1324948     889.3 ns/op    128 B/op    1 allocs/op
BenchmarkCrossLinkQuery-10     285885    4238.0 ns/op    129 B/op    1 allocs/op
BenchmarkBruteQuery-10          31296   38839.0 ns/op    128 B/op    1 allocs/op
BenchmarkGridMove-10         20798007      58.3 ns/op      0 B/op    0 allocs/op
BenchmarkCrossLinkMove-10       45294   26497.0 ns/op      0 B/op    0 allocs/op