数据结构与算法 - AOI

2022-10-08

全文 ≈ 2.2k字 | 预计阅读时长 8分钟

AOI（Area Of Interest）翻译过来称为“感兴趣的区域”，用于计算玩家与玩家（或其他 Entity）之间彼此进入、离开、移动视野的算法。通俗的解释比如，玩家离开某个地图时，计算出需要通知的其他玩家。

AOI 模块是多人联机游戏服务器中很重要的功能模块之一，AOI 模块的“好”与“坏”会很大程度上影响服务器的性能。

思路

当一个玩家进入场景后，首先要计算出场景中的其他所有玩家并放进对象集合（又称观察者集合），之后该玩家的进入、移动、离开或其他行为都将会一一通知该集合内的玩家，并且每个玩家都需要维护这样一个对象集合。

Watchers 观察者集合，即能够看到我的其他玩家或实体。

需要注意的是，该对象集合内的玩家列表会随着玩家的行为发生变化，在玩家离开场景后清空对象集合。

全场景同步

即每个玩家都能看到进入该场景的所有玩家，那么所有进入该场景的玩家发生行为，AOI 场景管理器都会通知其他玩家。比如，我从地图 0,0 移动至地图 10,10 这样的行为。

进入

玩家[pp]进入地图 0,0
玩家[wl]进入地图 2,20
       通知玩家[pp]进入视野
玩家[sd]进入地图 0,4
       通知玩家[pp]进入视野
       通知玩家[wl]进入视野

移动

1
2
3

玩家[sd]进行移动 0,4 -> 0,5
       通知玩家[pp]进行移动
       通知玩家[wl]进行移动

离开

1
2
3

玩家[sd]离开地图
       通知玩家[pp]离开地图
       通知玩家[wl]离开地图

但如果地图场景大、玩家数量多的场景下问题就凸显出来，服务器通信量将会十分巨大（玩家与玩家之间）。比如，在一款叫《绝地求生》的游戏中最大的地图是 8km*8km，假如两个玩家相距 6km，这两个玩家彼此之间还需要通信吗？

限制玩家视野

为了提高服务器运行效率，所以需要对玩家的可视范围（视野）进行一定限制，从而减少通信量。即每个玩家都只能看到视野内的其他玩家，当发生行为时也只会同步信息给这些玩家。

比如，当每个玩家都只有 5 视野单位时：

进入

玩家[pp]进入地图 0,0
玩家[wl]进入地图 2,20
玩家[sd]进入地图 0,4
       通知玩家[pp]进入视野

移动

1
2
3

玩家[sd]进行移动 0,4 -> 1,20
       通知玩家[pp]离开视野
       通知玩家[wl]进入视野

离开

1 2	玩家[sd]离开地图通知玩家[wl]离开地图

对玩家进行了视野限制后，消息量会大幅下降。但因为会对场景内所有玩家进行暴力查找，所以检索效率并不高。

九宫格

把地图网格化后，限制玩家的视野范围为 9 个格子。如图：

一般设计是玩家的手机屏幕显示为 4/9 格子，但真实视野为 1 ～ 9 网格，所以服务器只需要同步消息给玩家可视范围内的 9 个网格其他玩家。

进入

根据玩家坐标计算格子，把玩家加入到格子。通知九宫格内的玩家，有玩家进入场景。

移动

格子无变化，仅通知移动行为给九宫格内的玩家。
格子有变化，对格子进行交集、并集运算。并集，离开格子并通知格子内玩家离开行为，加入新格子并通知格子内玩家进入行为。交集，仅通知移动行为。

离开

根据玩家坐标计算格子，把玩家从格子移除。通知九宫格内的玩家，有玩家离开场景。

灯塔

灯塔是在九宫格的基础上进行优化，在把地图网格化的基础上划分区域（比如 4 个网格组成一个区域），每个区域有一个管理者：灯塔，这个管理者知晓当前区域的全部玩家。如图：

每个灯塔维护两个对象集合：Watchers（观察者集合）、Markers（被观察者集合）。

进入

根据玩家坐标计算出灯塔，把玩家加入到灯塔的 Markers。通知该灯塔所有 Watchers，有玩家进入场景。找出该玩家视野内所有灯塔，把玩家加入到灯塔的 Watchers，同时把这些 Watchers 和玩家互相加进对方的视野列表。

移动

灯塔无变化，仅通知移动行为给玩家视野列表内的玩家。
灯塔有变化，对灯塔列表进行交集、并集运算。并集，从离开灯塔的 Watchers、Markers 移除该玩家，新进入灯塔的 Watchers、Markers 添加该玩家。交集，仅通知移动行为。
对移动前后灯塔的 Watchers 进行并集运算。从离开的 Watchers 互相从对方的视野列表内移除，新进入的 Watchers 互相加进对方的视野列表。

离开

根据玩家坐标计算出灯塔，把玩家从该灯塔的 Markers 中移除。通知该灯塔所有 Watchers，有玩家离开场景。
找出该玩家视野内所有灯塔，把玩家从这些灯塔的 Watchers 中移除，同时把该玩家和视野列表内的所有玩家互相把对方从视野列表内移除。

一般设计上灯塔坐标是需要转换的，类似于 Redis Cluster 的 slot 机制，通过转换玩家坐标来判断灯塔归属。

func (r *Aoi) transPos(x, y uint) (uint, uint) {
    x = uint(math.Floor(float64(x) / float64(r.TowerWidth)))
    y = uint(math.Floor(float64(y) / float64(r.TowerHeight)))
    return x, y
}

func (r *Aoi) getTower(x, y uint) *Tower {
    x, y = r.transPos(x, y)
    tower, ok := r.Towers[x][y]
    if !ok {
        fmt.Printf("灯塔[异常]不存在的灯塔: %d,%d \n", x, y)
        return nil
    }
    return tower
}

十字链表

把 X、Y 轴分别以链表的形式存储，将玩家的坐标分别写入 X、Y 链表。需要注意的是：两个链表的排序方式必须一致，比如都按照X、Y从小到大。当玩家进入场景后根据当前坐标分别取出 X、Y 链表视距内的玩家列表取交集，这就是当前玩家视野范围内的其他玩家们。至于是进入、移动还是离开这些逻辑都和九宫格、灯塔其实是一样的。

定义 2 个链表

type Aoi struct {
    list         map[uint32]*node
    xList        *node
    yList        *node
    VisibleRange uint
}

type node struct {
    Id     uint32
    xPrev  *node
    xNext  *node
    yPrev  *node
    yNext  *node
    x, y   uint
    player *entity.Player
}

查找邻居节点

func (r *Aoi) findNeighbors(targetNode *node, model string) map[uint32]*node {
    // 感兴趣的邻居
    neighbors := make(map[uint32]*node, 0)
    // 向后找
    for cur := targetNode.xNext; cur != nil; cur = cur.xNext {
        // 当前节点已经超出范围
        if cur.x-targetNode.x > r.VisibleRange {
            break
        }
        // y轴不符合
        if abs(int(cur.y-targetNode.y)) > int(r.VisibleRange) {
            continue
        }
        neighbors[cur.Id] = cur
    }
    // 向前找
    for cur := targetNode.xPrev; cur != nil; cur = cur.xPrev {
        // 当前节点已经超出范围
        if targetNode.x-cur.x > r.VisibleRange {
            fmt.Println(targetNode.x, cur.x)
            break
        }
        // y轴不符合
        if abs(int(targetNode.y-cur.y)) > int(r.VisibleRange) {
            continue
        }
        // 已存在
        if _, ok := neighbors[cur.Id]; ok {
            continue
        }
        neighbors[cur.Id] = cur
    }
    return neighbors
}

进入、移动及离开地图与其他方式一样

func (r *Aoi) addX(newNode *node) {
    var (
        prev *node
        cur  *node
    )
    for cur = r.xList; cur != nil; cur = cur.xNext {
        // 插入cur之前
        if cur.x > newNode.x {
            // 根节点
            if cur.xPrev == nil {
                r.xList = newNode
            } else {
                newNode.xPrev = cur.xPrev // 当前节点的前置节点作为新节点的前置节点
                cur.xPrev.xNext = newNode // 新节点成为当前节点的前置节点的后置节点
            }
            cur.xPrev = newNode // 新节点作为当前节点的前置节点
            newNode.xNext = cur // 当前节点作为新节点的后置节点
            break
        }
        prev = cur
    }
    // 插入尾部
    if prev != nil && cur == nil {
        prev.xNext = newNode
        newNode.xPrev = prev
    }
}

func (r *Aoi) addY(newNode *node) {
    var (
        prev *node
        cur  *node
    )
    for cur = r.yList; cur != nil; cur = cur.yNext {
        // 插入cur之前
        if cur.y > newNode.y {
            // 根节点
            if cur.yPrev == nil {
                r.yList = newNode
            } else {
                newNode.yPrev = cur.yPrev // 当前节点的前置节点作为新节点的前置节点
                cur.yPrev.yNext = newNode // 新节点成为当前节点的前置节点的后置节点
            }
            cur.yPrev = newNode // 新节点作为当前节点的前置节点
            newNode.yNext = cur // 当前节点作为新节点的后置节点
            break
        }
        prev = cur
    }
    // 插入尾部
    if prev != nil && cur == nil {
        prev.yNext = newNode
        newNode.yPrev = prev
    }
}

最后

附上示例：aoi