《游戏服务端架构·核心系统与契约》4.1 AOI 选型：九宫格、十字链表与空间索引

每秒消息数 ≈ 在线实体数 N × 平均可见实体数 K × 同步频率 f
每秒字节数 ≈ 每秒消息数 × 单条消息字节数 B

// file: internal/aoiindex/aoiindex.go
// tier: L1
// verify: go test ./internal/aoiindex/
package aoiindex

import (
	"errors"
	"fmt"
	"math"
	"sort"
)

var (
	ErrCellSize    = errors.New("aoiindex: cell size must be positive")
	ErrEmptyID     = errors.New("aoiindex: empty entity id")
	ErrDuplicateID = errors.New("aoiindex: entity already placed")
	ErrNotPlaced   = errors.New("aoiindex: entity is not placed")
)

// Point is a continuous world position. The grid converts it to an integer
// cell with math.Floor, so negative coordinates are valid and a cell is
// half-open: [x*size, (x+1)*size).
type Point struct{ X, Y float64 }

// Cell is an integer grid coordinate.
type Cell struct{ X, Y int }

// Delta describes one AOI update. See and Unsee are the subject's gained and
// lost neighbours; SeenBy and UnseenBy are the entities whose view of the
// subject changed. Lists are sorted by id so callers can diff and log them.
type Delta struct {
	Subject  string
	See      []string
	Unsee    []string
	SeenBy   []string
	UnseenBy []string
}

// Empty reports whether the update changed nobody's view.
func (d Delta) Empty() bool {
	return len(d.See)+len(d.Unsee)+len(d.SeenBy)+len(d.UnseenBy) == 0
}

// Grid is a uniform spatial hash. Visibility is defined as the 3x3 block of
// cells around the subject, which keeps the common query a local map walk.
type Grid struct {
	cellSize float64
	cells    map[Cell]map[string]struct{}
	at       map[string]Cell
	pos      map[string]Point
}

// NewGrid builds an empty grid. Cell size is a product decision: too small
// multiplies cells and events, too large makes the 3x3 neighbourhood noisy.
func NewGrid(cellSize float64) (*Grid, error) {
	if cellSize <= 0 || math.IsNaN(cellSize) || math.IsInf(cellSize, 0) {
		return nil, ErrCellSize
	}
	return &Grid{
		cellSize: cellSize,
		cells:    make(map[Cell]map[string]struct{}),
		at:       make(map[string]Cell),
		pos:      make(map[string]Point),
	}, nil
}

// CellOf maps a position to its half-open cell.
func (g *Grid) CellOf(p Point) Cell {
	return Cell{X: int(math.Floor(p.X / g.cellSize)), Y: int(math.Floor(p.Y / g.cellSize))}
}

// Neighborhood returns the 3x3 block in a deterministic order. Duplicate cells
// cannot occur, so callers may use the result directly for fanout estimates.
func Neighborhood(c Cell) []Cell {
	out := make([]Cell, 0, 9)
	for y := c.Y - 1; y <= c.Y+1; y++ {
		for x := c.X - 1; x <= c.X+1; x++ {
			out = append(out, Cell{X: x, Y: y})
		}
	}
	return out
}

// Visible returns the ids currently sharing the 3x3 neighbourhood with id.
func (g *Grid) Visible(id string) ([]string, error) {
	c, ok := g.at[id]
	if !ok {
		return nil, fmt.Errorf("%w: %s", ErrNotPlaced, id)
	}
	return g.visibleAt(c, id), nil
}

func (g *Grid) visibleAt(c Cell, exclude string) []string {
	out := make([]string, 0, 8)
	for _, n := range Neighborhood(c) {
		for other := range g.cells[n] {
			if other != exclude {
				out = append(out, other)
			}
		}
	}
	sort.Strings(out)
	return out
}

// Place inserts a new entity and reports who can already see it. Placing the
// same id twice is a caller bug, not an update; use Move for updates.
func (g *Grid) Place(id string, p Point) (Delta, error) {
	if id == "" {
		return Delta{}, ErrEmptyID
	}
	if _, ok := g.pos[id]; ok {
		return Delta{}, fmt.Errorf("%w: %s", ErrDuplicateID, id)
	}
	c := g.CellOf(p)
	g.pos[id] = p
	g.at[id] = c
	if g.cells[c] == nil {
		g.cells[c] = make(map[string]struct{})
	}
	g.cells[c][id] = struct{}{}
	visible := g.visibleAt(c, id)
	return Delta{Subject: id, See: visible, SeenBy: visible}, nil
}

// Move updates a position. Moving inside one cell changes no view; crossing a
// cell boundary produces the full symmetric difference of the two 3x3 blocks.
func (g *Grid) Move(id string, p Point) (Delta, error) {
	if _, ok := g.pos[id]; !ok {
		return Delta{}, fmt.Errorf("%w: %s", ErrNotPlaced, id)
	}
	oldCell := g.at[id]
	newCell := g.CellOf(p)
	if oldCell == newCell {
		g.pos[id] = p
		return Delta{Subject: id}, nil
	}
	oldVisible := g.visibleAt(oldCell, id)
	delete(g.cells[oldCell], id)
	if len(g.cells[oldCell]) == 0 {
		delete(g.cells, oldCell)
	}
	g.pos[id] = p
	g.at[id] = newCell
	if g.cells[newCell] == nil {
		g.cells[newCell] = make(map[string]struct{})
	}
	g.cells[newCell][id] = struct{}{}
	newVisible := g.visibleAt(newCell, id)
	see, unsee := diff(oldVisible, newVisible)
	return Delta{Subject: id, See: see, Unsee: unsee, SeenBy: see, UnseenBy: unsee}, nil
}

// Remove deletes an entity. Its old neighbours lose sight of it; the subject
// itself no longer has a view, so only Unsee and UnseenBy carry ids.
func (g *Grid) Remove(id string) (Delta, error) {
	c, ok := g.at[id]
	if !ok {
		return Delta{}, fmt.Errorf("%w: %s", ErrNotPlaced, id)
	}
	visible := g.visibleAt(c, id)
	delete(g.cells[c], id)
	if len(g.cells[c]) == 0 {
		delete(g.cells, c)
	}
	delete(g.pos, id)
	delete(g.at, id)
	return Delta{Subject: id, Unsee: visible, UnseenBy: visible}, nil
}

// Fanout counts entities in the 3x3 block around p, including any entity at p.
// It is the cheap estimate used before sending a map event.
func (g *Grid) Fanout(p Point) int {
	n := 0
	for _, c := range Neighborhood(g.CellOf(p)) {
		n += len(g.cells[c])
	}
	return n
}

// Len is the number of placed entities.
func (g *Grid) Len() int { return len(g.pos) }

func diff(old, next []string) (added, removed []string) {
	inOld := make(map[string]bool, len(old))
	for _, id := range old {
		inOld[id] = true
	}
	inNext := make(map[string]bool, len(next))
	for _, id := range next {
		inNext[id] = true
		if !inOld[id] {
			added = append(added, id)
		}
	}
	for _, id := range old {
		if !inNext[id] {
			removed = append(removed, id)
		}
	}
	return added, removed
}

$ cd .local/checks/gsarch-lab
$ gofmt -l internal/aoiindex
$ go vet ./internal/aoiindex/...
$ go test -count=1 ./internal/aoiindex/
ok  	gsarchlab/internal/aoiindex