《MMO 服务器开发》12.3 兴趣过滤与带宽预算

// file: internal/sync/aoi.go
// tier: L1
// verify: go test ./internal/sync/ -run 'TestAOIInterest|TestGridMoveIsIncremental|TestInterestDeterministic|TestFanoutReport' -v

package sync

import "math"

// Grid is a uniform spatial hash over dense entity handles. Entity IDs are
// expected to be 0..N-1; the grid keeps its state in flat slices so the working
// set is a contiguous block of memory rather than N map buckets. That choice is
// what makes the 12.3 benchmark's cache story measurable instead of hand-waved.
type Grid struct {
	cell   float32
	cols   int32
	heads  []int32   // cell -> first entity in that cell, -1 when empty
	next   []int32   // entity -> next entity in the same cell
	cellOf []int32   // entity -> current cell index
	xs, ys []float32 // entity -> position
}

// NewGrid builds a grid with `cell`-sized cells over a square world `cols`
// cells on a side, sized for `n` dense entities.
func NewGrid(n int, cols int32, cell float32) *Grid {
	g := &Grid{
		cell:   cell,
		cols:   cols,
		heads:  make([]int32, int(cols)*int(cols)),
		next:   make([]int32, n),
		cellOf: make([]int32, n),
		xs:     make([]float32, n),
		ys:     make([]float32, n),
	}
	for i := range g.heads {
		g.heads[i] = -1
	}
	for i := range g.next {
		g.next[i] = -1
	}
	for i := range g.cellOf {
		g.cellOf[i] = -1
	}
	return g
}

func (g *Grid) index(p Vec2) int32 {
	cx := int32(math.Floor(float64(p.X / g.cell)))
	cy := int32(math.Floor(float64(p.Y / g.cell)))
	if cx < 0 {
		cx = 0
	}
	if cy < 0 {
		cy = 0
	}
	if cx >= g.cols {
		cx = g.cols - 1
	}
	if cy >= g.cols {
		cy = g.cols - 1
	}
	return cy*g.cols + cx
}

// Move relocates entity id to p, returning true when it changed cell. Only a
// cell change touches the bucket lists; a move inside the same cell is a plain
// position write.
func (g *Grid) Move(id uint32, p Vec2) bool {
	g.xs[id], g.ys[id] = p.X, p.Y
	ni := g.index(p)
	if g.cellOf[id] == ni {
		return false
	}
	g.unlink(id)
	g.cellOf[id] = ni
	g.next[id] = g.heads[ni]
	g.heads[ni] = int32(id)
	return true
}

func (g *Grid) unlink(id uint32) {
	ci := g.cellOf[id]
	if ci < 0 {
		return
	}
	if g.heads[ci] == int32(id) {
		g.heads[ci] = g.next[id]
		g.next[id] = -1
		return
	}
	for h := g.heads[ci]; h != -1; h = g.next[h] {
		if g.next[h] == int32(id) {
			g.next[h] = g.next[id]
			g.next[id] = -1
			return
		}
	}
}

// Interest appends every entity within `radius` of id (excluding id) to dst and
// returns it. Cells are scanned row-major, so the order is deterministic.
func (g *Grid) Interest(id uint32, radius float32, dst []uint32) []uint32 {
	cx := int32(math.Floor(float64(g.xs[id] / g.cell)))
	cy := int32(math.Floor(float64(g.ys[id] / g.cell)))
	span := int32(math.Ceil(float64(radius / g.cell)))
	x0, y0 := g.xs[id], g.ys[id]
	r2 := float64(radius) * float64(radius)
	for yy := cy - span; yy <= cy+span; yy++ {
		if yy < 0 || yy >= g.cols {
			continue
		}
		row := yy * g.cols
		for xx := cx - span; xx <= cx+span; xx++ {
			if xx < 0 || xx >= g.cols {
				continue
			}
			for e := g.heads[row+xx]; e != -1; e = g.next[e] {
				if uint32(e) == id {
					continue
				}
				dx := float64(g.xs[e] - x0)
				dy := float64(g.ys[e] - y0)
				if dx*dx+dy*dy <= r2 {
					dst = append(dst, uint32(e))
				}
			}
		}
	}
	return dst
}

// Bytes is the grid's working-set size in bytes. The benchmark reports it so
// the reader can compare it against this machine's cache instead of guessing.
func (g *Grid) Bytes() int {
	return (len(g.heads)+len(g.next)+len(g.cellOf))*4 + (len(g.xs)+len(g.ys))*4
}

// file: internal/sync/fanout_test.go
// tier: B
// verify: go test ./internal/sync/ -run TestFanoutReport -v -count=1

package sync

import (
	"testing"
	"time"
)

// splitmix64 is a deterministic PRNG. The benchmark must be reproducible, so it
// never touches math/rand's global state or the clock.
func splitmix64(x uint64) uint64 {
	x += 0x9e3779b97f4a7c15
	z := x
	z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9
	z = (z ^ (z >> 27)) * 0x94d049bb133111eb
	return z ^ (z >> 31)
}

// TestFanoutReport is the 12.3 baseline (tier B). It builds a world larger than
// this machine's L2, warms the query path, then measures the interest set size
// and the resulting per-client and total fanout for three radii.
func TestFanoutReport(t *testing.T) {
	const (
		n        = 1_000_000
		cols     = 256
		cell     = 32
		samples  = 20000
		tickRate = 20
		dirtyPct = 0.10
		deltaB   = 13 // 5 B entry header + 8 B for a moved position
	)
	g := NewGrid(n, cols, cell)

	for i := 0; i < n; i++ {
		r := splitmix64(uint64(i))
		side := float64(cols) * float64(cell)
		p := Vec2{X: float32(float64(r%1_000_003) / 1_000_003 * side),
			Y: float32(float64((r>>20)%1_000_003) / 1_000_003 * side)}
		g.Move(uint32(i), p)
	}
	t.Logf("working set: %.1f MB over %d entities (grid: heads+next+cellOf+pos)",
		float64(g.Bytes())/(1<<20), n)

	// Sample clients spread across the world so the measurement is not biased
	// toward one corner. Each sample id steps by a large odd stride, wrapped
	// back into range so the handle stays valid.
	const stride = uint32(499979)
	buf := make([]uint32, 0, 4096)

	for _, radius := range []float32{32, 64, 128} {
		id := uint32(0)
		for i := 0; i < 2000; i++ { // warm up the cache, discard the result
			buf = g.Interest(id, radius, buf[:0])
			id = (id + stride) % n
		}
		var total int64
		start := time.Now()
		for i := 0; i < samples; i++ {
			buf = g.Interest(id, radius, buf[:0])
			total += int64(len(buf))
			id = (id + stride) % n
		}
		nsPerQuery := float64(time.Since(start).Nanoseconds()) / samples
		mean := float64(total) / samples
		perClient := mean * dirtyPct * deltaB * tickRate
		fanout := perClient * n
		t.Logf("radius=%3.0f  mean interest=%7.1f  query=%6.0f ns  per-client=%8.1f B/s  fanout=%8.1f MB/s",
			radius, mean, nsPerQuery, perClient, fanout/(1<<20))
	}

	// Sanity: the 3x3 span for radius 32 at cell 32 must not be empty.
	if len(g.Interest(0, 32, nil)) == 0 {
		t.Fatal("interest set is empty; density or grid sizing is wrong")
	}
}