大型多人在线游戏的地图上同时存在成千上万个实体（玩家、怪物、NPC、掉落物），每个玩家真正关心的只有自己视野范围内的那一小部分。如果把所有人的位置每帧全量广播给所有人，服务器带宽和 CPU 都承受不住。于是有了 AOI（Area of Interest，兴趣区域） 算法：只维护、只通知”我视野里发生了什么”，并向上层触发 Enter/Leave 事件，供业务做显隐、战斗检测、音效触发等逻辑。
AOI 的经典实现有几种：全量广播、网格/九宫格、十字链表、跳表等。本文只讲 十字链表（也叫轴标记链表），对照一份真实的 Go 实现逐行分析，源码见 GitHub：beijian128/aoi。
一、核心思路
十字链表的核心思路是：把 3D 空间的可见性判断，拆成三个互相独立的一维区间判断。
每个实体在三维空间里有坐标 (x, y, z) 和视野半径 R（代码把视野建模为以自身为中心、边长 2R 的立方体）。实体 A 能看见实体 B，等价于在 X、Y、Z 三个轴上的区间都重叠：
A.MinX ≤ B.X ≤ A.MaxX
且 A.MinY ≤ B.Y ≤ A.MaxY
且 A.MinZ ≤ B.Z ≤ A.MaxZ
其中 Min = 自身坐标 - R，Max = 自身坐标 + R。三轴同时满足才可见，任何一轴不满足就不可见。
如果每个实体移动后都和其他实体做一次 O(N²) 的全量区间比较，性能不可接受。十字链表用”有序链表 + 交换时判定”把比较变成增量式：只有两个标记在链表里交换位置的那一刻，可见性才可能变化，其余时间不需要任何计算。
为什么叫”十字”：在 2D 场景里，X 轴和 Y 轴各维护一条按坐标排序的双向链表，两条链表互相垂直，形如十字，因此得名；扩展到 3D 就是三条轴链表。这份代码实现的是 3D 版，2D 版去掉 Z 轴即可。
三种标记（Marker）
每个实体在每个轴上挂 3 个链表节点：
MarkerMin：视野下界，坐标pos - R；MarkerMax：视野上界，坐标pos + R；MarkerPos：实体自身位置，坐标pos。
三条轴 × 三种标记 = 每个实体 9 个节点。节点携带”坐标值”和”所属实体”，链表始终按坐标值升序排列，一个实体三个节点在链表里的相对位置就编码了它与其他实体的空间关系。
二、数据结构
核心是四个结构：Marker（链表节点）、AxisList（单轴链表）、Entity（实体）、Manager（管理器）。
// MarkerType 节点类型
type MarkerType int
const (
MarkerMin MarkerType = 0 // 视野下界 (Watcher's View Start)
MarkerMax MarkerType = 1 // 视野上界 (Watcher's View End)
MarkerPos MarkerType = 2 // 实体位置 (Target's Body)
)
// Marker 链表节点
type Marker struct {
Type MarkerType
Axis int // 0:X, 1:Y, 2:Z
Val aoi.Float
Owner *Entity
prev *Marker
next *Marker
}
// AxisList 单向有序双向链表，Head/Tail 是 ±∞ 哨兵
type AxisList struct {
Head *Marker // -Inf
Tail *Marker // +Inf
}
// Entity 物理实体
type Entity struct {
ID aoi.EntityID
Pos [3]aoi.Float
Range aoi.Float // 视野半径（立方体半边长）
// 链表节点：[3个轴][3种类型]
Markers [3][3]*Marker
// ViewCounts：轴匹配计数器
// Key: TargetID，Value: 轴匹配数 (0-3)，== 3 时物理可见
ViewCounts map[aoi.EntityID]int
VisibleSet map[aoi.EntityID]bool
// Subscribers：订阅了我的视野的玩家
Subscribers map[aoi.PlayerID]*aoi.Player
}
// Manager AOI 管理器
type Manager struct {
axes [3]*AxisList
entities map[aoi.EntityID]*Entity
players map[aoi.PlayerID]*aoi.Player
eventCallback aoi.AOICallback
}
几个设计要点：
- 哨兵节点：每条轴链表初始化时放入
Head = -Inf和Tail = +Inf两个哨兵，永远不移动。所有真实节点都在两个哨兵之间，冒泡排序不需要判空、不会越界。 - 每实体 9 节点常驻：节点的内存和链表位置随实体移动而更新，不需要临时创建节点。
- 三层视野概念：
Entity.VisibleSet是物理层”真的看见”的集合（三轴全匹配）；Player.FinalView是逻辑层玩家聚合后的视野（用引用计数聚合多个下属单位的视野）。这层抽象在订阅机制一节会用到。
三、核心操作
3.1 添加实体
添加实体分两步：先在三条轴的链表尾部挂上 9 个节点，再调用 updateEntity 触发排序和视野计算。
func (m *Manager) AddEntity(id aoi.EntityID, pos *aoi.Position, rangeVal aoi.Float) {
x, y, z := pos.X, pos.Y, pos.Z
e := &Entity{
ID: id,
Pos: [3]aoi.Float{x, y, z},
Range: rangeVal,
ViewCounts: make(map[aoi.EntityID]int),
VisibleSet: make(map[aoi.EntityID]bool),
Subscribers: make(map[aoi.PlayerID]*aoi.Player),
}
vals := [3]aoi.Float{x, y, z}
for axis := 0; axis < 3; axis++ {
e.Markers[axis][MarkerMin] = &Marker{Type: MarkerMin, Axis: axis, Val: vals[axis] - rangeVal, Owner: e}
e.Markers[axis][MarkerMax] = &Marker{Type: MarkerMax, Axis: axis, Val: vals[axis] + rangeVal, Owner: e}
e.Markers[axis][MarkerPos] = &Marker{Type: MarkerPos, Axis: axis, Val: vals[axis], Owner: e}
// 简单插入到尾部前，依赖后面的 updateEntity 排序
list := m.axes[axis]
prev := list.Tail.prev
prev.next = e.Markers[axis][MarkerMin]
e.Markers[axis][MarkerMin].prev = prev
e.Markers[axis][MarkerMin].next = e.Markers[axis][MarkerPos]
e.Markers[axis][MarkerPos].prev = e.Markers[axis][MarkerMin]
e.Markers[axis][MarkerPos].next = e.Markers[axis][MarkerMax]
e.Markers[axis][MarkerMax].prev = e.Markers[axis][MarkerPos]
e.Markers[axis][MarkerMax].next = list.Tail
list.Tail.prev = e.Markers[axis][MarkerMax]
}
m.entities[id] = e
m.updateEntity(e, x, y, z) // 立即更新位置以触发正确排序和 AOI 计算
}
新实体的 9 个节点先按 Min → Pos → Max 的顺序连成一串挂在尾部，随后 updateEntity 把每个节点冒泡到正确位置，并在冒泡过程中触发 Enter/Leave 判定。新实体一入场，所有视野重叠的旧实体都会在交换瞬间收到通知。
3.2 移动实体：冒泡排序
实体移动时，9 个节点坐标都要更新。链表是有序的，直接改值会破坏顺序，代码用”冒泡”保持有序：节点值变大就向右交换，变小就向左交换，每次交换都是一次”擦肩而过”，立刻做穿透判定。
func (m *Manager) updateEntity(e *Entity, x, y, z aoi.Float) {
e.Pos = [3]aoi.Float{x, y, z}
newVals := [3]aoi.Float{x, y, z}
for axis := 0; axis < 3; axis++ {
m.updateMarker(e.Markers[axis][MarkerMin], newVals[axis]-e.Range)
m.updateMarker(e.Markers[axis][MarkerPos], newVals[axis])
m.updateMarker(e.Markers[axis][MarkerMax], newVals[axis]+e.Range)
}
}
func (m *Manager) updateMarker(node *Marker, newVal aoi.Float) {
node.Val = newVal
// 向右移动（值变大）
for node.next != nil && !node.next.Val.IsInf(0) && node.Val > node.next.Val {
other := node.next
m.swap(node, other) // node 换到 other 后面
m.checkCross(node, other, true)
}
// 向左移动（值变小）
for node.prev != nil && !node.prev.Val.IsInf(0) && node.Val < node.prev.Val {
other := node.prev
m.swap(other, node) // node 换到 other 前面
m.checkCross(node, other, false)
}
}
// swap 交换相邻节点：left -> right 变成 right -> left
func (m *Manager) swap(left, right *Marker) {
left.prev.next = right
right.prev = left.prev
right.next.prev = left
left.next = right.next
right.next = left
left.prev = right
}
实体每帧只移动一小段距离时，每个节点通常只冒泡几步。移动距离越大、实体密度越高，冒泡步数越多，这是十字链表的主要成本所在（见第六节）。
3.3 穿透判定 checkCross
checkCross 是整个算法的核心。两个节点在链表中交换位置，意味着一个实体的视野边界（Min/Max）越过另一个实体的位置（Pos），可见性可能翻转。
// checkCross 核心穿透逻辑
// mover: 正在移动的节点；passive: 被越过的节点
// movingRight: mover 的移动方向
func (m *Manager) checkCross(mover, passive *Marker, movingRight bool) {
if mover.Owner == passive.Owner {
return // 自己人的标记互相穿过，忽略
}
// 识别谁是 Watcher（Min/Max），谁是 Target（Pos）
var watcherNode, targetNode *Marker
if (mover.Type == MarkerMin || mover.Type == MarkerMax) && passive.Type == MarkerPos {
watcherNode, targetNode = mover, passive
} else if mover.Type == MarkerPos && (passive.Type == MarkerMin || passive.Type == MarkerMax) {
watcherNode, targetNode = passive, mover
} else {
return // 边界穿边界、Pos 穿 Pos，不影响可见性
}
watcher := watcherNode.Owner
target := targetNode.Owner
// 判定进入视野(Enter) 还是离开视野(Leave)
isEnter := false
if watcherNode.Type == MarkerMin {
if mover == watcherNode { // Min 动
isEnter = !movingRight // Min 往左是 Enter
} else { // Pos 动
isEnter = movingRight // Pos 往右是 Enter
}
} else { // watcher 是 MarkerMax
if mover == watcherNode { // Max 动
isEnter = movingRight // Max 往右是 Enter
} else { // Pos 动
isEnter = !movingRight // Pos 往左是 Enter
}
}
// ... 更新轴计数、触发 Enter/Leave（见 3.4）
}
判定逻辑可以整理成 8 行矩阵：
| 穿过场景 | 移动方向 | 事件 | 直观含义 |
|---|---|---|---|
| Min 越过 Pos | 向右 | Leave | 视野缩小，目标被挤出视野下界 |
| Min 越过 Pos | 向左 | Enter | 视野扩大，目标进入视野下界 |
| Max 越过 Pos | 向右 | Enter | 视野扩大，目标进入视野上界 |
| Max 越过 Pos | 向左 | Leave | 视野缩小，目标被挤出视野上界 |
| Pos 越过 Min | 向右 | Enter | 目标移动，进入观察者视野 |
| Pos 越过 Min | 向左 | Leave | 目标移动，离开观察者视野 |
| Pos 越过 Max | 向右 | Leave | 目标移动，跑出观察者视野 |
| Pos 越过 Max | 向左 | Enter | 目标移动，从另一侧进入视野 |
口诀：只看”边界是否越过位置”。Min/Max 是观察者的边界，Pos 是目标的实体位置，两者交叉意味着这一轴的区间关系从重叠翻转为不重叠（或反之）。只有”边界 vs 位置”的交叉有意义，边界穿边界、位置穿位置不改变任何区间关系，直接忽略。
3.4 轴计数器
一次交换只代表某一轴的区间关系翻转，可见性需要三轴同时成立。代码用增量计数实现：每个实体的 ViewCounts 记录”我对目标在几个轴上匹配”，每发生一次 Enter 判定 +1、Leave 判定 -1，计数从 2 变 3 时触发”物理进入视野”，从 3 变 2 时触发”物理离开视野”。
delta := -1
if isEnter {
delta = 1
}
oldC := watcher.ViewCounts[target.ID]
newC := oldC + delta
if newC <= 0 {
delete(watcher.ViewCounts, target.ID) // 清零时顺手删除，防止 map 泄漏
newC = 0
} else {
watcher.ViewCounts[target.ID] = newC
}
if oldC < 3 && newC == 3 {
// 物理 Enter：三轴全部重叠
watcher.VisibleSet[target.ID] = true
m.notifySubscribers(watcher, target.ID, true)
} else if oldC == 3 && newC < 3 {
// 物理 Leave：有一轴不再重叠
delete(watcher.VisibleSet, target.ID)
m.notifySubscribers(watcher, target.ID, false)
}
一次移动会引发多次交换、多轴翻转，但 Enter/Leave 事件只在”三轴全匹配/失配”的临界点触发一次，天然去重，上层业务不会收到冗余的进出通知。
四、事件与订阅机制
4.1 Enter/Leave 回调
物理层发现可见性翻转后，沿订阅关系把事件推给逻辑层的玩家。玩家用 FinalView（引用计数 map）聚合自己的视野，只有当”某个单位 0 → 1″时才真正触发 OnEnter，”1 → 0″时才触发 OnLeave：
func (m *Manager) notifySubscribers(source *Entity, targetID aoi.EntityID, isEnter bool) {
delta := -1
if isEnter {
delta = 1
}
for _, player := range source.Subscribers {
m.refCountChange(player, targetID, delta)
}
}
func (m *Manager) refCountChange(p *aoi.Player, targetID aoi.EntityID, delta int) {
oldVal := p.FinalView[targetID]
newVal := oldVal + delta
if newVal <= 0 {
delete(p.FinalView, targetID)
} else {
p.FinalView[targetID] = newVal
}
if m.eventCallback != nil {
if oldVal == 0 && newVal > 0 {
m.eventCallback.OnEnter(p.ID, targetID)
} else if oldVal > 0 && newVal <= 0 {
m.eventCallback.OnLeave(p.ID, targetID)
}
}
}
这里解决的实际问题是：一个玩家可能控制多个单位（或者一个单位的视野被多个玩家订阅），同一个目标可能同时被多个下属单位看见。用引用计数而不是布尔值，可以正确区分”第一个单位看见了”和”最后一个单位也看不见了”这两个临界点，事件既不重复也不漏发。
4.2 订阅机制
玩家 Subscribe(player, entity) 之后，该实体每次可见性变化都会推给这个玩家；取消订阅则移除贡献并结算一次 Leave。典型用途：队伍视野同步、任务目标追踪、关注列表——只订阅关心的实体，避免全量事件风暴。
五、复杂度分析
设实体总数为 N：
- 内存：每个实体 9 个节点，共 O(N)，与地图尺寸无关。这是它与网格法最大的区别——网格法的内存随地图面积/格子数增长，十字链表只随实体数增长。
- 添加/删除：挂载节点 O(1)，随后冒泡到正确位置，平均 O(1)~O(N)。
- 移动：每个轴 3 个节点各自冒泡，最坏 O(6N)（每个节点穿过半条链表），实际远小于此——实体通常只移动一小段距离。
- 判定成本：只在节点交换时触发，单次交换 O(1)，避开了移动时 O(N²) 的全量比较。
选型建议：实体数量少到中等、各实体视野半径差异大、需要精细 Enter/Leave 事件的场景，十字链表合适；实体极多且视野均匀的 2D 场景，网格/九宫格往往更简单高效。两者也可混用。
六、优化方向
- 跳表（Skip List）：把单链表换成跳表，插入/查找从 O(N) 降到 O(log N)，是十字链表最常见的升级方向。代价是实现复杂度上升，”交换时判定”的增量逻辑需要重写为”插入前后对比”。
- 批量移动：游戏逻辑帧里先收集所有实体的新位置，统一更新链表再统一处理事件，减少链表操作的抖动。
- 事件合并/防抖：demo 里用了一个 20ms 的防抖定时器，把一帧内的多次 Enter/Leave 合并成一次网络推送。
- 局部更新：视野半径变化（如 Buff 加视野）就是 Min/Max 节点坐标变化，直接复用 updateMarker，无需特殊处理。
七、可视化演示
源码仓库带一个 3D 演示：在 3d/ 目录下 go test 启动，浏览器访问 http://localhost:8081。场景里 100 个 NPC 在 500×500×500 的立方体里随机游走，玩家用 W/A/S/D/R/F 移动，视野半径 80。绿色实体在视野内，红色在视野外，点击实体可订阅/取消订阅。演示用 WebSocket 每 50ms 推一次全量位置，视野变化通过防抖后的 view_update 消息推送——NPC 一进视野就变绿，一离开就变红。
小结
十字链表把 3D 空间可见性拆成三条一维有序链表，用”标记 + 冒泡 + 交换瞬间判定”把 Enter/Leave 事件做成增量式，复杂度与交换次数成正比，内存只和实体数相关。它不是最简单的 AOI 方案，但视野半径可以每个实体各不相同，事件能精确到”哪一刻谁看见谁”，与订阅机制天然契合。按 Marker → swap → checkCross → ViewCounts → refCountChange 的顺序理解一遍，再看任何语言的十字链表实现都很快。
参考与扩展阅读
- 源码仓库：github.com/beijian128/aoi（Go 实现，含 2D 九宫格与 3D 十字链表两套实现及可视化演示）
- 《游戏中 AOI 视野算法》总结四种主流方案：blog.csdn.net/ybn6775/article/details/81701167
- 《分析游戏开发中 AOI 的实现思路》讲清了十字链表的二维几何含义：blog.csdn.net/m0_73915763/article/details/132586363
- 《深入探索 AOI 算法》从全量广播到十字链表的演进脉络：zhuanlan.zhihu.com/p/201588990
