《MMO 服务器开发》4.2 十字链表 AOI 从零实现

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

// xnode 是十字链表的节点：一个实体同时挂在「按 X 有序」与「按 Y 有序」两条
// 双向链表上，四条边 xPrev/xNext/yPrev/yNext 构成一个「十」字。整张表由
// 两个哨兵头 headX / headY 各领一条环状链表。
type xnode struct {
	id           EntityID
	p            Vec2
	xPrev, xNext *xnode
	yPrev, yNext *xnode
}

// CrossLink 是十字链表 AOI。两条链表各带一个哨兵头，按坐标单调不减排列；
// 查询时沿 X 链左右推进取「X 带」，沿 Y 链左右推进取「Y 带」，两带取交，
// 再按圆形半径收尾。它不需要预先设定格边长，能自适应任意密度分布。
type CrossLink struct {
	headX *xnode
	headY *xnode
	index map[EntityID]*xnode
	mark  map[EntityID]int // 查询复用：记录某实体是否落在本次 X 带内
	stamp int
}

func NewCrossLink() *CrossLink {
	cl := &CrossLink{
		headX: &xnode{},
		headY: &xnode{},
		index: make(map[EntityID]*xnode),
		mark:  make(map[EntityID]int),
	}
	cl.headX.xPrev, cl.headX.xNext = cl.headX, cl.headX
	cl.headY.yPrev, cl.headY.yNext = cl.headY, cl.headY
	return cl
}

// Add 把一个实体挂进两条链表。
func (cl *CrossLink) Add(id EntityID, p Vec2) {
	if _, ok := cl.index[id]; ok {
		cl.Move(id, p)
		return
	}
	n := &xnode{id: id, p: p}
	cl.index[id] = n
	insertX(cl.headX, n)
	insertY(cl.headY, n)
}

// Move 先摘后挂。十字链表的移动是 O(n) 的（要沿链表重新找位置），这是它
// 的主要代价；格点法用格坐标 O(1) 定位，这是它在均匀分布下更快的原因。
func (cl *CrossLink) Move(id EntityID, p Vec2) {
	n, ok := cl.index[id]
	if !ok {
		cl.Add(id, p)
		return
	}
	cl.unlink(n)
	n.p = p
	insertX(cl.headX, n)
	insertY(cl.headY, n)
}

// Remove 从两条链表摘掉实体。
func (cl *CrossLink) Remove(id EntityID) {
	n, ok := cl.index[id]
	if !ok {
		return
	}
	cl.unlink(n)
	delete(cl.index, id)
}

// Len 返回当前实体数，供测试断言链表完整性。
func (cl *CrossLink) Len() int { return len(cl.index) }

func (cl *CrossLink) unlink(n *xnode) {
	n.xPrev.xNext, n.xNext.xPrev = n.xNext, n.xPrev
	n.yPrev.yNext, n.yNext.yPrev = n.yNext, n.yPrev
}

// insertX 把 n 按 X 坐标插进 head 领的链表，保持单调不减。
func insertX(head, n *xnode) {
	for x := head.xNext; x != head; x = x.xNext {
		if x.p.X >= n.p.X {
			n.xNext, n.xPrev = x, x.xPrev
			x.xPrev.xNext, x.xPrev = n, n
			return
		}
	}
	tail := head.xPrev
	n.xNext, n.xPrev = head, tail
	tail.xNext, head.xPrev = n, n
}

// insertY 把 n 按 Y 坐标插进 head 领的链表，保持单调不减。
func insertY(head, n *xnode) {
	for y := head.yNext; y != head; y = y.yNext {
		if y.p.Y >= n.p.Y {
			n.yNext, n.yPrev = y, y.yPrev
			y.yPrev.yNext, y.yPrev = n, n
			return
		}
	}
	tail := head.yPrev
	n.yNext, n.yPrev = head, tail
	tail.yNext, head.yPrev = n, n
}

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

// NeighborsInRadius 返回圆形半径内的其它实体。
//
// 分两趟：先沿 X 链从自己向两侧走，把 |dx| <= r 的节点标进本次的 X 带；
// 再沿 Y 链走，只把「既在 X 带里、又落在圆内」的节点收进结果。两带取交
// 用 mark + 自增的 stamp 实现：每趟查询换一个 stamp 就等价于清空了上次
// 的标记，于是查询不用反复分配 map。
func (cl *CrossLink) NeighborsInRadius(id EntityID, r float64) []EntityID {
	n, ok := cl.index[id]
	if !ok {
		return nil
	}
	self := n.p
	cl.stamp++
	// X 带：从节点沿 X 链向两侧走，直到 |dx| > r 为止。
	for x := n.xPrev; x != cl.headX && self.X-x.p.X <= r; x = x.xPrev {
		cl.mark[x.id] = cl.stamp
	}
	for x := n.xNext; x != cl.headX && x.p.X-self.X <= r; x = x.xNext {
		cl.mark[x.id] = cl.stamp
	}
	// Y 带：沿 Y 链走，落在 X 带里且距离在圆内的才是最终结果。
	out := make([]EntityID, 0, 16)
	for y := n.yPrev; y != cl.headY && self.Y-y.p.Y <= r; y = y.yPrev {
		if cl.mark[y.id] == cl.stamp && within(self, y.p, r) {
			out = append(out, y.id)
		}
	}
	for y := n.yNext; y != cl.headY && y.p.Y-self.Y <= r; y = y.yNext {
		if cl.mark[y.id] == cl.stamp && within(self, y.p, r) {
			out = append(out, y.id)
		}
	}
	return out
}

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

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

// TestCrossLinkMatchesGrid 用同一批随机点分别喂给十字链表与九宫格，
// 逐个实体比对半径查询结果——两种结构语义相同，结果必须完全一致。
func TestCrossLinkMatchesGrid(t *testing.T) {
	rng := rand.New(rand.NewPCG(7, 11))
	cl := NewCrossLink()
	g := NewGrid()
	const n = 500
	for i := 0; i < n; i++ {
		id := MakeEntityID(1, uint64(i))
		p := Vec2{X: rng.Float64() * 100, Y: rng.Float64() * 100}
		cl.Add(id, p)
		g.Add(id, p)
	}
	for i := 0; i < n; i++ {
		id := MakeEntityID(1, uint64(i))
		got := ids(cl.NeighborsInRadius(id, 8))
		want := ids(g.NeighborsInRadius(id, 8))
		if !eq(got, want) {
			t.Fatalf("id %d: crosslink=%v grid=%v", i, got, want)
		}
	}
}

func TestCrossLinkMoveAndRemove(t *testing.T) {
	cl := NewCrossLink()
	a := MakeEntityID(1, 1)
	b := MakeEntityID(1, 2)
	cl.Add(a, Vec2{X: 0, Y: 0})
	cl.Add(b, Vec2{X: 50, Y: 50})
	if got := ids(cl.NeighborsInRadius(a, 8)); len(got) != 0 {
		t.Fatalf("far: %v", got)
	}
	cl.Move(b, Vec2{X: 3, Y: 4})
	if got := ids(cl.NeighborsInRadius(a, 8)); !eq(got, []uint64{uint64(b)}) {
		t.Fatalf("near: %v", got)
	}
	cl.Remove(b)
	if got := ids(cl.NeighborsInRadius(a, 8)); len(got) != 0 {
		t.Fatalf("after remove: %v", got)
	}
	// 链表完整性：全部移除后两条环状链表应只剩哨兵自指。
	cl.Remove(a)
	if cl.Len() != 0 {
		t.Fatalf("index not empty: %d", cl.Len())
	}
	if cl.headX.xNext != cl.headX || cl.headX.xPrev != cl.headX {
		t.Fatal("X list not empty after removing all")
	}
	if cl.headY.yNext != cl.headY || cl.headY.yPrev != cl.headY {
		t.Fatal("Y list not empty after removing all")
	}
}