《游戏服务端编程实践》7.1.3 实时区域广播

// file: ch07/world/aoi.go
// tier: L1
// verify: go test ./ch07/world/

package world

import (
	"errors"
	"sort"
	"sync"
)

var (
	ErrEntityExists   = errors.New("world: entity already exists")
	ErrEntityNotFound = errors.New("world: entity not found")
)

// CellSize 是 AOI 格子的边长，单位与逻辑坐标一致。格子过大会让广播量
// 膨胀，过小会让跨格事件过多，通常取玩家视野半径的一半到一倍。
const CellSize int64 = 50 * 100

// Cell 是 AOI 格子编号，与分区 ZoneID 是两套独立网格。
type Cell struct {
	X int64
	Y int64
}

func CellOf(p WorldCoord) Cell {
	return Cell{X: FloorDiv(p.X, CellSize), Y: FloorDiv(p.Y, CellSize)}
}

// GridAOI 用九宫格维护可见性。可见关系定义为格子切比雪夫距离不超过 1，
// 因此 A 能看见 B 时 B 也一定能看见 A，进入/离开集合可以双向复用。
type GridAOI struct {
	mu         sync.Mutex
	hysteresis int64
	pos        map[uint64]WorldCoord
	cell       map[uint64]Cell
	members    map[Cell]map[uint64]struct{}
	stealth    map[uint64]bool
}

// NewGridAOI 创建 AOI。hysteresis 是跨格抑制带宽度：实体越过格线但
// 不足该距离时仍留在原格，避免在边界来回走动导致反复进出。
func NewGridAOI(hysteresis int64) *GridAOI {
	if hysteresis < 0 {
		hysteresis = 0
	}
	return &GridAOI{
		hysteresis: hysteresis,
		pos:        make(map[uint64]WorldCoord),
		cell:       make(map[uint64]Cell),
		members:    make(map[Cell]map[uint64]struct{}),
		stealth:    make(map[uint64]bool),
	}
}

// Add 登记实体并返回它刚进入视野的实体集合（不含自己）。
func (g *GridAOI) Add(id uint64, p WorldCoord) ([]uint64, error) {
	g.mu.Lock()
	defer g.mu.Unlock()
	if _, ok := g.pos[id]; ok {
		return nil, ErrEntityExists
	}
	c := CellOf(p)
	g.pos[id] = p
	g.cell[id] = c
	g.addToCellLocked(id, c)
	return sortedIDs(g.visibleLocked(id)), nil
}

// Move 更新坐标并返回 enter/leave 两个集合。
// enter 是移动后新看见的实体，leave 是移动后看不见的实体。
// 返回集合从移动者视角计算；由于可见关系对称，未被隐身时它同时也是
// 其他玩家视角下的变化，可直接用于双向广播。
func (g *GridAOI) Move(id uint64, to WorldCoord) (enter, leave []uint64, err error) {
	g.mu.Lock()
	defer g.mu.Unlock()
	oldCell, ok := g.cell[id]
	if !ok {
		return nil, nil, ErrEntityNotFound
	}
	before := g.visibleLocked(id)
	g.pos[id] = to
	if next := g.cellForLocked(oldCell, to); next != oldCell {
		g.removeFromCellLocked(id, oldCell)
		g.cell[id] = next
		g.addToCellLocked(id, next)
	}
	after := g.visibleLocked(id)
	return diffIDs(after, before), diffIDs(before, after), nil
}

// Remove 移除实体并返回它离开前能看见的实体集合，调用方据此通知对方。
func (g *GridAOI) Remove(id uint64) ([]uint64, error) {
	g.mu.Lock()
	defer g.mu.Unlock()
	c, ok := g.cell[id]
	if !ok {
		return nil, ErrEntityNotFound
	}
	left := g.visibleLocked(id)
	g.removeFromCellLocked(id, c)
	delete(g.pos, id)
	delete(g.cell, id)
	delete(g.stealth, id)
	return sortedIDs(left), nil
}

// SetStealth 切换隐身。隐身只影响别人能否看见该实体，不影响该实体
// 观察别人。返回需要收到变更的相邻实体：开启时是 leave 名单，
// 关闭时是 enter 名单。
func (g *GridAOI) SetStealth(id uint64, on bool) ([]uint64, error) {
	g.mu.Lock()
	defer g.mu.Unlock()
	if _, ok := g.pos[id]; !ok {
		return nil, ErrEntityNotFound
	}
	if g.stealth[id] == on {
		return nil, nil
	}
	g.stealth[id] = on
	c := g.cell[id]
	seen := make(map[uint64]struct{})
	for dx := int64(-1); dx <= 1; dx++ {
		for dy := int64(-1); dy <= 1; dy++ {
			for other := range g.members[Cell{X: c.X + dx, Y: c.Y + dy}] {
				if other != id {
					seen[other] = struct{}{}
				}
			}
		}
	}
	return sortedIDs(seen), nil
}

// Visible 返回 id 当前能看见的实体，保持与 Move 的 enter/leave 同视角。
// 隐身只影响别人看不看得见 id，不影响 id 观察别人。
func (g *GridAOI) Visible(id uint64) []uint64 {
	g.mu.Lock()
	defer g.mu.Unlock()
	return sortedIDs(g.visibleLocked(id))
}

// Observers 返回能看见 id 的实体；id 隐身时为空。
func (g *GridAOI) Observers(id uint64) []uint64 {
	g.mu.Lock()
	defer g.mu.Unlock()
	c, ok := g.cell[id]
	if !ok || g.stealth[id] {
		return nil
	}
	out := make(map[uint64]struct{})
	for dx := int64(-1); dx <= 1; dx++ {
		for dy := int64(-1); dy <= 1; dy++ {
			for other := range g.members[Cell{X: c.X + dx, Y: c.Y + dy}] {
				if other != id {
					out[other] = struct{}{}
				}
			}
		}
	}
	return sortedIDs(out)
}

// Position 返回实体真实坐标；AOI 格子可能因抑制带而暂时滞后。
func (g *GridAOI) Position(id uint64) (WorldCoord, bool) {
	g.mu.Lock()
	defer g.mu.Unlock()
	p, ok := g.pos[id]
	return p, ok
}

// Cell 返回实体当前所在的 AOI 格子。
func (g *GridAOI) Cell(id uint64) (Cell, bool) {
	g.mu.Lock()
	defer g.mu.Unlock()
	c, ok := g.cell[id]
	return c, ok
}

func (g *GridAOI) visibleLocked(id uint64) map[uint64]struct{} {
	out := make(map[uint64]struct{})
	c, ok := g.cell[id]
	if !ok {
		return out
	}
	for dx := int64(-1); dx <= 1; dx++ {
		for dy := int64(-1); dy <= 1; dy++ {
			for other := range g.members[Cell{X: c.X + dx, Y: c.Y + dy}] {
				if other == id || g.stealth[other] {
					continue
				}
				out[other] = struct{}{}
			}
		}
	}
	return out
}

func (g *GridAOI) cellForLocked(cur Cell, p WorldCoord) Cell {
	next := CellOf(p)
	if next == cur {
		return cur
	}
	m := g.hysteresis
	if m > 0 {
		left := cur.X*CellSize - m
		right := (cur.X+1)*CellSize + m
		bottom := cur.Y*CellSize - m
		top := (cur.Y+1)*CellSize + m
		if p.X >= left && p.X < right && p.Y >= bottom && p.Y < top {
			return cur
		}
	}
	return next
}

func (g *GridAOI) addToCellLocked(id uint64, c Cell) {
	set, ok := g.members[c]
	if !ok {
		set = make(map[uint64]struct{})
		g.members[c] = set
	}
	set[id] = struct{}{}
}

func (g *GridAOI) removeFromCellLocked(id uint64, c Cell) {
	set, ok := g.members[c]
	if !ok {
		return
	}
	delete(set, id)
	if len(set) == 0 {
		delete(g.members, c)
	}
}

func sortedIDs(set map[uint64]struct{}) []uint64 {
	out := make([]uint64, 0, len(set))
	for id := range set {
		out = append(out, id)
	}
	sort.Slice(out, func(i, j int) bool { return out[i] < out[j] })
	return out
}

func diffIDs(a, b map[uint64]struct{}) []uint64 {
	out := make(map[uint64]struct{})
	for id := range a {
		if _, ok := b[id]; !ok {
			out[id] = struct{}{}
		}
	}
	return sortedIDs(out)
}

cd .local/checks/gs-practice-lab && gofmt -l ch07/world && go vet ./ch07/world/ && go test ./ch07/world/ -count=1

ok  	gspractice/ch07/world	0.266s