聊聊游戏中的AOI

发表于 | 分类于
本文字数: 5.1k | 阅读时长 ≈ 24 分钟

200413-head-aoi

AOI (Area Of Interest) 算法应该算是游戏的基础核心了，AOI 进出事件会触发很多的业务事件。简单来说，地图上的每个玩家都在一个 AOI 区域内，当玩家状态发生改变时 (如移动，动作行为等) ，需要该将玩家的信息广播给 AOI 区域内的所有玩家，而这些玩家收到这条广播消息时，就要做出对应的响应状态。

以 25x25 的地图为例，地图上的每个点表示一个玩家，假设目标玩家所在的位置为坐标 (16, 9) :

1

以玩家的进入游戏，移动，离开游戏设计接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
type AOIStrategyManager interface {
    // 进入游戏
    Enter(player *Player)

    // 游戏内移动
    Move(player *Player, tx, ty int)

    // 离开游戏
    Leave(player *Player)

    // 当前AOI信息
    Info()
}

全局查找

这是最简单的方案，我们可以获取到地图坐标中的所有玩家，然后判断每个玩家是否在目标玩家的通知范围内，如果在的话，就对该玩家发送消息。

假设我们设定的范围为 10x10，那么浅黄色范围中的所有玩家都是我们需要通知的：

2

判断距离的方式也很简单：|x-16|<=5 && |y-9|<=5

实现示例(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 地图大小25x25：x坐标范围[0,25]，y坐标范围[0,25]
// 玩家视野范围10x10
var visibleArea = 5

type AOIManager struct {
    Players map[int]*manager.Player
}

func NewAOIManager(ps map[int]*manager.Player) *AOIManager {
    return &AOIManager{Players: ps}
}

func (m *AOIManager) Enter(player *manager.Player) {
    // 玩家进入地图
    m.Players[player.Id] = player

    // 发送消息
    for _, p := range m.getPlayers(player) {
        p.ReceiveEnterMessage(player)
    }
}

func (m *AOIManager) Move(player *manager.Player, tx, ty int) {

    // 移动前视野范围内玩家列表
    fps := m.getPlayers(player)

    player.X = tx
    player.Y = ty
    // 移动后视野范围内玩家列表
    tps := m.getPlayers(player)

    // 此处获取差集交集可以优化，此处是对玩家列表处理，可以调整成对格子列表处理
    // 获取差集，玩家离开视野
    for _, p := range util.PlayerExcept(fps, tps) {
        p.ReceiveLeaveMessage(player)
    }

    // 获取交集，玩家移动
    for _, p := range util.PlayerIntersect(fps, tps) {
        p.ReceiveMoveMessage(player)
    }

    // 获取差集，玩家进入视野
    for _, p := range util.PlayerExcept(tps, fps) {
        p.ReceiveEnterMessage(player)
    }
}

func (m *AOIManager) Leave(player *manager.Player) {
    // 从地图上删除玩家
    delete(m.Players, player.Id)

    // 发送离开消息
    for _, p := range m.getPlayers(player) {
        p.ReceiveLeaveMessage(player)
    }
}

func (m *AOIManager) Info() {
    fmt.Println("全局玩家:")
    for _, p := range m.Players {
        fmt.Printf("[玩家%d](%d, %d). ", p.Id, p.X, p.Y)
    }
    fmt.Println()
}

// 获取玩家视野范围内的所有玩家
func (m *AOIManager) getPlayers(player *manager.Player) (players []*manager.Player) {
    for _, p := range m.Players {
        if p.Id != player.Id && math.Abs(float64(p.X-player.X)) <= float64(visibleArea) && math.Abs(float64(p.Y-player.Y)) <= float64(visibleArea) {
            players = append(players, p)
        }
    }
    return
}

九宫格

这种方案是将整张地图按照格子划分，每个格子里记录了处于该格子内的所有玩家列表，当玩家状态改变时，需要通知该玩家所在格子以及周围最多8个格子内的玩家。在这种情况下，我们可以避免每次都循环全部玩家。

假设我们设定的格子为 5x5，那么整张地图共可以分成 25个格子，绿色格子为目标玩家所在格子，而浅绿色格子为周围8个格子，所有需要通知的玩家处于这9个格子中：

3

以玩家移动，进入，离开为例：

  • 进入：根据目标玩家坐标计算出玩家所在格子，将该玩家添加到该格子中，并且将消息发送给九宫格内的玩家

  • 离开：根据目标玩家坐标计算出玩家所在格子，将该玩家从该格子中删除，并且将消息发送给九宫格内的玩家

  • 移动：

    • 在本格子内移动：对九宫格内的玩家发送移动消息
    • 从格子A移动到格子B：假设玩家移动到了 (14, 9) (如下图)，这种情况下，玩家从格子8移动到了格子7，那么需要对格子7，8，12，13，2，3内的玩家发送移动消息，对格子11，6，1内的玩家发送进入视野消息，而对格子14，9，4内的玩家发送离开视野消息

    4

代码示例(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
// 地图大小25x25：x坐标范围[0,25]，y坐标范围[0,25]
// 格子大小5x5，x方向5个格子 y方向5个格子 格子高度5 宽度5
// 格子ID为[0,24]
var (
    gridCountX = 5
    gridCountY = 5

    mapMinX = 0
    mapMaxX = 25

    mapMinY = 0
    mapMaxY = 25

    gridWidth  = (mapMaxX - mapMinX) / gridCountX
    gridHeight = (mapMaxY - mapMinY) / gridCountY
)

type AOIManager struct {
    Grids map[int]*Grid
}

func NewAOIManager(ps map[int]*manager.Player) *AOIManager {
    m := &AOIManager{
        Grids: make(map[int]*Grid),
    }

    // 生成格子ID
    for y := 0; y < gridCountY; y++ {
        for x := 0; x < gridCountX; x++ {
            gid := y*gridCountX + x

            m.Grids[gid] = NewGrid(gid, mapMinX+x*gridWidth, mapMinX+(x+1)*gridWidth, mapMinY+y*gridHeight, mapMinY+(y+1)*gridHeight)
        }
    }

    for _, p := range ps {
        gid := m.getGid(p.X, p.Y)
        m.Grids[gid].Players[p.Id] = p
    }

    return m
}

func (m *AOIManager) Enter(player *manager.Player) {
    m.Grids[m.getGid(player.X, player.Y)].Players[player.Id] = player

    for _, p := range m.getPlayers(player) {
        p.ReceiveEnterMessage(player)
    }

}

func (m *AOIManager) Move(player *manager.Player, tx, ty int) {
    // 获取移动前的所属格子
    fgid := m.getGid(player.X, player.Y)
    // 获取移动后的所属格子
    tgid := m.getGid(tx, ty)

    // 获取移动前的格子列表
    fps := m.getPlayers(player)

    player.X = tx
    player.Y = ty
    // 获取移动后的格子列表
    tps := m.getPlayers(player)

    // 前后所属格子不同，删除后添加
    if fgid != tgid {
        delete(m.Grids[fgid].Players, player.Id)

        m.Grids[tgid].Players[player.Id] = player
    }

    // 差集，发送离开视野消息
    for _, p := range util.PlayerExcept(fps, tps) {
        p.ReceiveLeaveMessage(player)
    }

    // 交集，发送移动消息
    for _, p := range util.PlayerIntersect(fps, tps) {
        p.ReceiveMoveMessage(player)
    }

    // 差集，发送进入游戏消息
    for _, p := range util.PlayerExcept(tps, fps) {
        p.ReceiveEnterMessage(player)
    }
}

func (m *AOIManager) Leave(player *manager.Player) {
    delete(m.Grids[m.getGid(player.X, player.Y)].Players, player.Id)

    for _, p := range m.getPlayers(player) {
        p.ReceiveLeaveMessage(player)
    }
}

func (m *AOIManager) Info() {
    for _, g := range m.Grids {
        fmt.Printf("格子%d:", g.Id)
        for _, p := range g.Players {
            fmt.Printf("[玩家%d](%d,%d),", p.Id, p.X, p.Y)
        }
        fmt.Println()
    }
}

// 获取九宫格内的所有玩家
// 获取顺序为玩家所属格子(8)-7-2-12-9-4-14-3-13
func (m *AOIManager) getPlayers(player *manager.Player) (players []*manager.Player) {

    gid := m.getGid(player.X, player.Y)

    var grids []*Grid
    grids = append(grids, m.Grids[gid])

    // 获取x方向格子索引
    idx := gid % gridCountX
    // 获取y方向格子索引
    idy := gid / gridCountX

    // 左边界判断
    // 如果格子左边有格子，判断该格子上方和下方是否有格子
    if idx-1 >= 0 {
        grids = append(grids, m.Grids[gid-1])

        if idy-1 >= 0 {
            grids = append(grids, m.Grids[gid-1-gridCountX])
        }

        if idy+1 < gridCountY {
            grids = append(grids, m.Grids[gid-1+gridCountX])
        }
    }

    // 右边界判断
    // 如果格子右边有格子，判断该格子上方和下方是否有格子
    if idx+1 < gridCountX {
        grids = append(grids, m.Grids[gid+1])

        if idy-1 >= 0 {
            grids = append(grids, m.Grids[gid+1-gridCountX])
        }

        if idy+1 < gridCountY {
            grids = append(grids, m.Grids[gid+1+gridCountX])
        }
    }

    // 下边界判断
    if idy-1 >= 0 {
        grids = append(grids, m.Grids[gid-gridCountX])
    }

    // 上边界判断
    if idy+1 < gridCountY {
        grids = append(grids, m.Grids[gid+gridCountX])
    }


    // 获取格子内的所有玩家
    for _, g := range grids {
        for _, v := range g.Players {
            if v.Id != player.Id {
                players = append(players, v)
            }
        }
    }
    return
}

// 根据坐标获取格子ID
// 格子边界上的坐标只会在一个格子内
// 计算方式：(y-地图最小Y坐标)/格子高度*X方向格子数量+(x-地图最小X坐标)/格子宽度
func (m *AOIManager) getGid(x, y int) int {
    // 如果坐标处于地图边界 特殊处理
  // 可以定义玩家可移动区域，在这种情况下，玩家就无法到达边界
    if x == mapMaxX {
        x = x - 1
    }
    if y == mapMaxY {
        y = y - 1
    }
    return (y-mapMinY)/gridHeight*gridCountX + (x-mapMinY)/gridWidth
}

// 格子信息
type Grid struct {
    Id      int
    MinX    int
    MaxX    int
    MinY    int
    MaxY    int
    Players map[int]*manager.Player
}

func NewGrid(id, minX, maxX, minY, maxY int) *Grid {
    return &Grid{
        Id:      id,
        MinX:    minX,
        MaxX:    maxX,
        MinY:    minY,
        MaxY:    maxY,
        Players: make(map[int]*manager.Player),
    }
}

灯塔兴趣列表

这种方案可以看做是九宫格方案的扩展。以九宫格为例，在每个九宫格中心建立一个灯塔，灯塔需要维护该灯塔范围内的所有玩家，以及对该灯塔感兴趣的玩家，同时每个玩家本身也会维护一个需要通知的玩家列表，可以看出来，对比九宫格，少了计算九宫格内的所有玩家的操作，这是一种以空间换时间的方式。

每个橙色的点表示一个灯塔，管理范围为每个5x5的格子(绿色区域)，而玩家视野范围为10x10(浅黄色区域)，可以看到每个玩家最多被4个灯塔观察，而浅绿色区域则为4个灯塔的观察者所在区域集合：

5

以玩家移动，进入，离开为例：

  • 进入：根据目标玩家坐标计算出玩家所属灯塔，将玩家添加到该灯塔管理的玩家列表，如果灯塔上绑定了观察者，则通知观察者有玩家进入。然后找出玩家视野内的所有灯塔，将自身绑定为灯塔的观察者，同时将灯塔的观察者列表发送给玩家，添加至玩家维护的玩家列表。
  • 离开：根据目标玩家坐标计算出玩家所属灯塔，将玩家从该灯塔管理的玩家列表中删除，如果灯塔上绑定了观察者，则通知观察者有玩家离开。然后找出玩家视野内的所有灯塔，解除灯塔的观察者绑定，同时将灯塔的观察者列表发送给玩家，从玩家维护的玩家列表中移除。
  • 移动：
    • 玩家视野内的灯塔没有变动：不做灯塔操作，对玩家维护的玩家列表发送移动消息
    • 玩家视野内的灯塔发生变动：对旧灯塔执行对象离开逻辑，对新灯塔执行对象进入逻辑，前后视野交集内的灯塔不需要执行解绑和绑定操作，仅发送移动消息

可以看到灯塔的视野越小，在碰撞检测时过滤的无效对象就越多，整张地图灯塔的数目也就越多，消耗的内存就越大，而且对象进出灯塔的计算量就越多，而灯塔的视野越大，在碰撞检测时能过滤的无效对象就越少，如果只有一个灯塔的情况，那就是全局查找方式了。

云风的博客中还提到了另一种优化方式，使用六边形灯塔代替方形灯塔，在这种情况下，每个玩家最多只会被3个灯塔观察。

代码示例(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
// 地图大小25x25：x坐标范围[0,25]，y坐标范围[0,25]
// 灯塔大小5x5
// 玩家视野范围10x10
var (
    gridCountX = 5
    gridCountY = 5

    mapMinX = 0
    mapMinY = 0

    mapMaxX = 25
    mapMaxY = 25

    gridWidth  = (mapMaxX - mapMinX) / gridCountX
    gridHeight = (mapMaxY - mapMinY) / gridCountY

    visibleArea = 5
)

type AOIManager struct {
    Towers map[int]*Tower
}

func NewAOIManager(ps map[int]*manager.Player) *AOIManager {
    m := &AOIManager{
        Towers: make(map[int]*Tower),
    }

    for y := 0; y < gridCountY; y++ {
        for x := 0; x < gridCountX; x++ {
            tid := y*gridCountX + x

            m.Towers[tid] = NewTower(tid, float64(gridWidth)/2+float64(mapMinX+x*gridWidth), float64(gridHeight)/2+float64(mapMinY+y*gridHeight))
        }
    }

    for _, p := range ps {
        m.Enter(p)
    }

    return m
}

func (m *AOIManager) Enter(player *manager.Player) {
    // 获取灯塔ID
    tid := m.getTowerId(player.X, player.Y)
    // 将玩家交给灯塔管理
    m.Towers[tid].Markers[player.Id] = player

    // 获取玩家可见范围内的灯塔列表
    tids := m.getTowerIds(player.X, player.Y)
    for _, tid := range tids {
        tower := m.Towers[tid]
        for k, v := range tower.Watchers {
            if v.Id == player.Id {
                continue
            }
            _, exist := player.Players[k]
            if !exist {
                player.Players[k] = v

                // 发送玩家进入消息
                v.ReceiveEnterMessage(player)

                v.Players[player.Id] = player
            }
        }
        tower.Watchers[player.Id] = player
    }
}

func (m *AOIManager) Move(player *manager.Player, tx, ty int) {

    ftids := m.getTowerIds(player.X, player.Y)
    ttids := m.getTowerIds(tx, ty)

    ftid := m.getTowerId(player.X, player.Y)
    ttid := m.getTowerId(tx, ty)

    player.X = tx
    player.Y = ty

    // 修改玩家所属灯塔
    if ttid != ftid {
        delete(m.Towers[ftid].Markers, player.Id)

        m.Towers[ttid].Markers[player.Id] = player
    }

    // 玩家视野范围内灯塔没变，仅做移动操作
    if util.IntEqual(ftids, ttids) {
        for _, p := range player.Players {
            p.ReceiveMoveMessage(player)
        }
        return
    }

    fps := m.getTowerWatchers(ftids)
    tps := m.getTowerWatchers(ttids)

    for _, tid := range util.IntExcept(ftids, ttids) {
        tower := m.Towers[tid]
        // 将玩家从灯塔观察者移除
        delete(tower.Watchers, player.Id)
    }

    for _, p := range util.PlayerExcept(fps, tps) {
        // 从玩家列表移除
        delete(p.Players, player.Id)

        _, exist := player.Players[p.Id]
        if exist {
            delete(player.Players, p.Id)

            p.ReceiveLeaveMessage(player)
        }
    }

    for _, p := range player.Players {
        p.ReceiveMoveMessage(player)
    }

    for _, tid := range util.IntExcept(ttids, ftids) {
        tower := m.Towers[tid]

        // 将玩家添加到灯塔观察者
        tower.Watchers[player.Id] = player

        // 将灯塔观察者交给玩家维护
        for k, v := range tower.Watchers {
            if v.Id == player.Id {
                continue
            }
            _, exist := player.Players[k]
            if !exist {
                player.Players[k] = v

                // 发送玩家进入消息
                v.ReceiveEnterMessage(player)

                v.Players[player.Id] = player
            }
        }
    }
}

func (m *AOIManager) Leave(player *manager.Player) {
    // 获取灯塔ID
    tid := m.getTowerId(player.X, player.Y)
    // 将玩家从灯塔管理移除
    delete(m.Towers[tid].Markers, player.Id)

    // 获取玩家可见范围内的灯塔列表
    tids := m.getTowerIds(player.X, player.Y)
    for _, tid := range tids {

        tower := m.Towers[tid]
        // 将玩家从灯塔观察者移除
        delete(tower.Watchers, player.Id)

        // 从玩家列表移除
        for _, p := range player.Players {
            // 从玩家列表移除
            delete(p.Players, player.Id)

            p.ReceiveLeaveMessage(player)
        }
    }
}

func (m *AOIManager) Info() {
    for _, t := range m.Towers {
        fmt.Printf("灯塔%d(%f,%f):\n", t.Id, t.X, t.Y)
        fmt.Print("管理对象:\n")
        for _, p := range t.Markers {
            fmt.Printf(" [玩家%d](%d,%d):", p.Id, p.X, p.Y)
            for _, p1 := range p.Players {
                fmt.Printf("->[玩家%d](%d,%d)", p1.Id, p1.X, p1.Y)
            }
            fmt.Println()
        }
        fmt.Printf("\n观察者对象:\n")
        for _, p := range t.Watchers {
            fmt.Printf(" [玩家%d](%d,%d)\n", p.Id, p.X, p.Y)
        }
        fmt.Println()
    }
}

// 根据坐标获取格子(灯塔)ID
// 格子边界上的坐标只会在一个格子内
// 计算方式：(y-地图最小Y坐标)/格子高度*X方向格子数量+(x-地图最小X坐标)/格子宽度
func (m *AOIManager) getTowerId(x, y int) int {
    // 如果坐标处于地图边界 特殊处理
    if x == mapMaxX {
        x = x - 1
    }
    if y == mapMaxY {
        y = y - 1
    }
    return (y-mapMinY)/gridHeight*gridCountX + (x-mapMinY)/gridWidth
}

// 判断坐标是否在灯塔范围内
func (m *AOIManager) inTower(tid, x, y int) bool {
    minX := math.Max(float64(x-visibleArea), float64(mapMinX))
    maxX := math.Min(float64(x+visibleArea), float64(mapMaxX))
    minY := math.Max(float64(y-visibleArea), float64(mapMinY))
    maxY := math.Min(float64(y+visibleArea), float64(mapMaxY))

    return minX <= m.Towers[tid].X && m.Towers[tid].X <= maxX && minY <= m.Towers[tid].Y && m.Towers[tid].Y <= maxY
}

// 根据灯塔坐标获取灯塔上的所有观察者
func (m *AOIManager) getTowerWatchers(towerIds []int) (players []*manager.Player) {
    pmap := make(map[int]*manager.Player)
    for _, tid := range towerIds {
        tower := m.Towers[tid]
        for k, v := range tower.Watchers {
            pmap[k] = v
        }
    }

    for _, v := range pmap {
        players = append(players, v)
    }
    return
}

// 根据玩家坐标获取视野范围内的所有灯塔
func (m *AOIManager) getTowerIds(x, y int) (towerIds []int) {

    tid := m.getTowerId(x, y)

    towerIds = append(towerIds, tid)

    idx := tid % gridCountX
    idy := tid / gridCountX

    if idx-1 >= 0 {
        if m.inTower(tid-1, x, y) {
            towerIds = append(towerIds, tid-1)
        }

        if idy-1 >= 0 && m.inTower(tid-1-gridCountX, x, y) {
            towerIds = append(towerIds, tid-1-gridCountX)
        }

        if idy+1 < gridCountY && m.inTower(tid-1+gridCountX, x, y) {
            towerIds = append(towerIds, tid-1+gridCountX)
        }
    }

    if idx+1 < gridCountX {
        if m.inTower(tid+1, x, y) {
            towerIds = append(towerIds, tid+1)
        }

        if idy-1 >= 0 && m.inTower(tid+1-gridCountX, x, y) {
            towerIds = append(towerIds, tid+1-gridCountX)
        }

        if idy+1 < gridCountY && m.inTower(tid+1+gridCountX, x, y) {
            towerIds = append(towerIds, tid+1+gridCountX)
        }
    }

    if idy-1 >= 0 && m.inTower(tid-gridCountX, x, y) {
        towerIds = append(towerIds, tid-gridCountX)
    }

    if idy+1 < gridCountY && m.inTower(tid+gridCountX, x, y) {
        towerIds = append(towerIds, tid+gridCountX)
    }

    return
}

type Tower struct {
    Id int

    X float64

    Y float64

    Watchers map[int]*manager.Player

    Markers map[int]*manager.Player
}

func NewTower(id int, x float64, y float64) *Tower {
    return &Tower{
        Id:       id,
        X:        x,
        Y:        y,
        Watchers: make(map[int]*manager.Player),
        Markers:  make(map[int]*manager.Player),
    }
}

十字链表

所谓十字链表，即把地图坐标轴中的 X 和 Y 轴看成是2个链表，将玩家的 X 坐标按照从小到大插入 X 链表，将玩家的 Y 坐标按照从小到大插入 Y 链表，查询时根据玩家的坐标分别从2个链表中取出范围内的所有玩家，对两个玩家列表做交集，即为我们需要发送消息的玩家列表。

以玩家A(10, 3)，玩家B(4, 18)，玩家C(17, 24) 为例，则 X 链表为：B(4) - A(10) - C(17)，Y 链表为：A(3) - B(18) - C(24)，假设目标玩家D的坐标为(16, 9)，通知范围为7：根据D坐标分别查找 X 链表和 Y 链表，然后根据对应坐标向前向后查找范围在7之内的玩家( X 链表中查找到的玩家为AC，Y 链表中查找到的玩家 A )，然后对两个玩家集合取交集(结果为玩家 A )，然后对交集中的所有的玩家发送消息。

代码示例(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
// 地图大小25x25：x坐标范围[0,25]，y坐标范围[0,25]
// 玩家视野范围10x10
var visibleArea = 5

type AOIManager struct {
    XList *list.List
    YList *list.List
}

func NewAOIManager(ps map[int]*manager.Player) *AOIManager {
    m := &AOIManager{
        XList: list.New(),
        YList: list.New(),
    }
    for _, p := range ps {
        m.insertList(p)
    }

    return m
}

func (m *AOIManager) Enter(player *manager.Player) {
    // 插入XY链表
    m.insertList(player)

    // 发送进入游戏消息
    for _, p := range m.getPlayers(player) {
        p.ReceiveEnterMessage(player)
    }
}

func (m *AOIManager) Move(player *manager.Player, tx, ty int) {

    fps := m.getPlayers(player)

    m.removeList(player)

    player.X = tx
    player.Y = ty
    tps := m.getPlayers(player)

    m.insertList(player)

    for _, p := range util.PlayerExcept(fps, tps) {
        p.ReceiveLeaveMessage(player)
    }

    for _, p := range util.PlayerIntersect(fps, tps) {
        p.ReceiveMoveMessage(player)
    }

    for _, p := range util.PlayerExcept(tps, fps) {
        p.ReceiveEnterMessage(player)
    }

}

func (m *AOIManager) Leave(player *manager.Player) {
    m.removeList(player)

    for _, p := range m.getPlayers(player) {
        p.ReceiveLeaveMessage(player)
    }
}

func (m *AOIManager) Info() {
    fmt.Print("X链表信息:")
    for e := m.XList.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        fmt.Printf(" -> [玩家%d](%d, %d)", ep.Id, ep.X, ep.Y)
    }
    fmt.Println()
    fmt.Print("Y链表信息:")
    for e := m.YList.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        fmt.Printf(" -> [玩家%d](%d, %d)", ep.Id, ep.X, ep.Y)
    }
    fmt.Println()
}

func (m *AOIManager) Get(pid int, list2 *list.List) *manager.Player {
    var player *manager.Player
    for e := list2.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        if ep.Id == pid {
            player = ep
            break
        }
    }
    return player
}

// 查找玩家视野内的玩家列表
// 分别查询X，Y链表玩家，然后对两个玩家列表取交集
func (m *AOIManager) getPlayers(player *manager.Player) (players []*manager.Player) {
    // 获取X链表视野内的玩家，判断条件|x1-x|<visibleArea
    var xps []*manager.Player
    for e := m.XList.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        if ep.Id != player.Id && math.Abs(float64(ep.X-player.X)) <= float64(visibleArea) {
            xps = append(xps, ep)
        }
    }

    // 获取Y链表视野内的玩家，判断条件|y1-y|<visibleArea
    var yps []*manager.Player
    for e := m.YList.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        if ep.Id != player.Id && math.Abs(float64(ep.Y-player.Y)) <= float64(visibleArea) {
            yps = append(yps, ep)
        }
    }

    // 获取2个玩家列表交集
    return util.PlayerIntersect(xps, yps)
}

// 将玩家从XY链表中移除
func (m *AOIManager) removeList(p *manager.Player) {
    // 从X链表移除
    for e := m.XList.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        if ep.Id == p.Id {
            m.XList.Remove(e)
            break
        }
    }

    // 从Y链表移除
    for e := m.YList.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        if ep.Id == p.Id {
            m.YList.Remove(e)
            break
        }
    }
}

// 将玩家插入到XY链表
// XY链表按照从小到大排列
func (m *AOIManager) insertList(p *manager.Player) {
    // 插入X链表
    xDone := false
    for e := m.XList.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        if ep.X > p.X {
            m.XList.InsertBefore(p, e)
            xDone = true
            break
        }
    }
    // 没有找到，插入X链表末端
    if !xDone {
        m.XList.PushBack(p)
    }

    // 插入Y链表
    yDone := false
    for e := m.YList.Front(); e != nil; e = e.Next() {
        ep := e.Value.(*manager.Player)
        if ep.Y > p.Y {
            m.YList.InsertBefore(p, e)
            yDone = true
            break
        }
    }
    // 没有找到，插入Y链表末端
    if !yDone {
        m.YList.PushBack(p)
    }
}

参考

灯塔AOI简易实现
AOI服务的设计与实现