-
11-zinx-Golang-MMO服务器-AOI算法实现
一、AOI算法简介
- 什么是AOI：游戏的AOI(Area Of Interest)算法应该算作游戏的基础核⼼了，许多逻辑都是因为AOI进出事件驱动的，许多⽹络同步数据也是因为AOI进出事件产⽣的。因此，良好的AOI算法和基于AOI算法的优化，是提⾼游戏性能的关键；为此，需要为每个玩家设定⼀个AOI，当⼀个对象状态发⽣改变时，需要将信息⼴播给全部玩家，那些AOI覆盖到的玩家都会收到这条⼴播消息，从⽽做出对应的响应状态
- 功能实现
- 服务器上的玩家或 NPC 状态发⽣改变时，将消息⼴播到附近的玩家
- 玩家进⼊NPC警戒区域时，AOI 模块将消息发送给NPC，NPC再做出相应的AI反应
- AOI兴趣点：通俗的理解是视野的广播范围
二、网络法实现AOI算法
- 假设我们有一个2D的地图
- 对于8编号格子的AOI兴趣点是围绕8格子周围的格子（2，3，4，7，9，12，13，14）
- 对于8编号格子的AOI兴趣点是围绕8格子周围的格子（2，3，4，7，9，12，13，14）
- 场景相关数值计算
- 场景⼤⼩： 250*250 ， w(x轴宽度) = 250，l(y轴⻓度) = 250
- x轴格⼦数量：nx = 5；y轴格⼦数量：ny = 5
- 格⼦宽度: dx = w / nx = 250 / 5 = 50；格⼦⻓度: dy = l / ny = 250 / 5 = 50
- 格⼦的x轴坐标：idx；格⼦的y轴坐标：idy
- 格⼦编号：id = idy *nx + idx (利⽤格⼦坐标得到格⼦编号)
- 格⼦坐标：idx = id % nx , idy = id / nx (利⽤格⼦id得到格⼦坐标)
- 格⼦的x轴坐标: idx = id % nx (利⽤格⼦id得到x轴坐标编号)
- 格⼦的y轴坐标: idy = id / nx (利⽤格⼦id得到y轴坐标编号)
三、实现AOI格子结构
1 - 实现AOI格子结构分析
2 - 实现AOI格子结构体
- mmo_game_zinx/core/grid.go
- Grid 这个格⼦类型，很好理解，分别有上下左右四个坐标，确定格⼦的领域范围，还是有格⼦ID，其中 playerIDs 是⼀个map，表示当前格⼦中存在的玩家有哪些
- 这⾥提供了⼀个⽅法 GetPlyerIDs() 可以返回当前格⼦中所有玩家的ID切⽚
package core import ( "fmt" "sync" ) /* 一个AOI地图中的格子类型 */ type Grid struct { //格子ID GID int //格子的左边边界坐标 MinX int //格子的右边边界坐标 MaxX int //格子的上边边界坐标 MinY int //格子的下边边界坐标 MaxY int //当前格子内玩家或者物体成员的ID集合 playerIDs map[int]bool //保护当前集合的锁 pIDLock sync.RWMutex } //初始化当前的格子的方法 func NewGrid(gID, minX, maxX, minY, maxY int) *Grid { return &Grid{ GID: gID, MinX: minX, MaxX: maxX, MinY: minY, MaxY: maxY, playerIDs: make(map[int]bool), } } //给格子添加一个玩家 func (g *Grid) Add(playerID int) { g.pIDLock.Lock() defer g.pIDLock.Unlock() g.playerIDs[playerID] = true } //从格子中删除一个玩家 func (g *Grid) Remove(playerID int) { g.pIDLock.Lock() defer g.pIDLock.Unlock() delete(g.playerIDs, playerID) } //得到当前格子中所有的玩家ID func (g *Grid) GetPlayerIDs() (playerIDs []int) { g.pIDLock.RLock() defer g.pIDLock.RUnlock() for k, _ := range g.playerIDs { playerIDs = append(playerIDs, k) } return } //调式使用-打印出格子的基本信息 func (g *Grid) String() string { return fmt.Sprintf("Grid id: %d, minX:%d, maxX:%d, minY:%d, maxY:%d, playerIDs:%v", g.GID,g.MinX,g.MaxX,g.MinY,g.MaxY,g.playerIDs) }- 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
四、实现AOI管理模块
1 - AOIManager属性分析
2 - AOIManager方法分析
3 - 实现AOIManager的初始化
- mmo_game_zinx/core/aoi.go：创建⼀个AOI模块(可以理解为⼀个2D的矩形地图)，⾥⾯有若⼲份grids，NewAOIManager() 会平均划分多分⼩格⼦，并初始化格⼦的坐标，计算⽅式很简单，初步的⼏何计算
package core import ( "fmt" ) //定义一些AOI的边界值 const ( AOI_MIN_X int = 85 AOI_MAX_X int = 410 AOI_CNTS_X int = 10 AOI_MIN_Y int = 75 AOI_MAX_Y int = 400 AOI_CNTS_Y int = 20 ) /* AOI区域管理模块 */ type AOIManager struct { //区域的左边界坐标 MinX int //区域的右边界坐标 MaxX int //X方向格子的数量 CntsX int //区域的上边界坐标 MinY int //区域的下边界坐标 MaxY int //Y方向格子的数量 CntsY int //当前区域中有哪些格子map-key=格子的ID，value=格子对象 grids map[int]*Grid } /* 初始化一个AOI区域管理模块 */ func NewAOIManager(minX, maxX, cntsX, minY, maxY, cntsY int) *AOIManager { aoiMgr := &AOIManager{ MinX: minX, MaxX: maxX, CntsX: cntsX, MinY: minY, MaxY: maxY, CntsY: cntsY, grids: make(map[int]*Grid), } //给AOI初始化区域的格子所有的格子进行编号 和 初始化 for y := 0; y < cntsY; y++ { for x := 0; x < cntsX; x++ { //计算格子ID 根据x,y编号 //格子编号： id = idy *cntX + idx gid := y*cntsX + x //初始化gid格子 aoiMgr.grids[gid] = NewGrid(gid, aoiMgr.MinX+x*aoiMgr.gridWidth(), aoiMgr.MinX+(x+1)*aoiMgr.gridWidth(), aoiMgr.MinY+y*aoiMgr.gridLength(), aoiMgr.MinY+(y+1)*aoiMgr.gridLength()) } } return aoiMgr } //得到每个格子在X轴方向的宽度 func (m *AOIManager) gridWidth() int { return (m.MaxX - m.MinX) / m.CntsX } //得到每个格子在Y轴方向的长度 func (m *AOIManager) gridLength() int { return (m.MaxY - m.MinY) / m.CntsY } //打印格子信息 func (m *AOIManager) String() string { //打印AOIManager信息 s := fmt.Sprintf("AOIManager:\n MinX:%d, MaxX:%d, cntsX:%d, minY:%d, maxY:%d, cntsY:%d\n Grids in AOIManager:\n", m.MinX, m.MaxX, m.CntsX, m.MinY, m.MaxY, m.CntsY) //打印全部格子信息 for _, grid := range m.grids { s += fmt.Sprintln(grid) } return s }- 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
4 - 单元测试AOIManager的初始化
- mmo_game_zinx/core/aoi_test.go
package core import ( "fmt" "testing" ) func TestNewAOIManager(t *testing.T) { //初始化AOIManager aoiMgr := NewAOIManager(0, 250, 5, 0, 250, 5) //打印AOIManager fmt.Println(aoiMgr) }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
五、根据当前格子计算周围的格子
1 - 情况1：格子四周都有格子
2 - 情况2：格⼦在AOI区域的四个顶⻆
3 - 情况3：格子周围缺一列或一行
4 - 根据格⼦的gID得到当前周边的九宫格信息
- 实现分析：
- ①.先算出该gid所处⼀⾏左边和右边是否有格子
- ②.再分别计算这⼀⾏的上边和下边的格⼦是否有格子
- 实际举例：以23的grid来计算
- 先计算23的左边是否有格子 —— 有，22
- 再计算23的右边是否有格子 —— 有，24
- 计算22的上边是否有格子 —— 有，17
- 计算22的下边是否有格子 —— 无
- 计算23的上边是否有格子 —— 有，18
- 计算23的下边是否有格子 —— 无
- 计算24的上边是否有格子 —— 有，19
- 计算24的下边是否有格子 —— 无
- mmo_game_zinx/core/aoi.go：
//根据格子GID得到周边九宫格格子集合 func (m *AOIManager) GetSurroundGridsByGid(gID int) (grids []*Grid) { //判断gID是否在AOIManager中 if _, ok := m.grids[gID]; !ok { return } //将当前gid本身加入九宫格切片中 grids = append(grids, m.grids[gID]) //8 //需要gID的左边是否有格子?右边是否有格子 //需要通过gID得到当前格子x轴的编号 --idx = id %nx idx := gID % m.CntsX //3 //判断idx编号是否左边还有格子 if idx > 0 { grids = append(grids, m.grids[gID-1]) //7 } //判断idx编号是否右边还有格子 if idx < m.CntsX-1 { grids = append(grids, m.grids[gID+1]) //9 } //将x轴当前的格子都取出，进行遍历，再分别得到每个格子上下是否还有格子 //得到当前x轴格子的ID集合 gidsX := make([]int, 0, len(grids)) for _, v := range grids { gidsX = append(gidsX, v.GID) } //遍历gidsX 集合中每个格子的gid for _, v := range gidsX { //得到当前格子id的y轴的编号 idy = id / ny idy := v / m.CntsY //gid 上边是否还有格子 if idy > 0 { grids = append(grids, m.grids[v-m.CntsX]) } //gid 下边是否还有格子 if idy < m.CntsY-1 { grids = append(grids, m.grids[v+m.CntsX]) } } return }- 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
5 - 单元测试根据gID获取九宫格信息
- mmo_game_zinx/core/aoi_test.go
func TestAOIManagerSuroundGridsByGid(t *testing.T) { //初始化AOIManager aoiMgr := NewAOIManager(0, 250, 5, 0, 250, 5) for gid, _ := range aoiMgr.grids { //得到当前gid的周边九宫格信息 grids := aoiMgr.GetSurroundGridsByGid(gid) fmt.Println("gid : ", gid, "grids len = ", len(grids)) gIDs := make([]int, 0, len(grids)) for _, grid := range grids { gIDs = append(gIDs, grid.GID) } fmt.Println("surounding grid IDs are ", gIDs) } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
6 - 根据坐标求出九宫格信息
- mmo_game_zinx/core/aoi.go：⾸先应该根据坐标得到所属的格⼦ID，然后再⾛根据格⼦ID获取九宫格信息就可以了
//通过x、y横纵轴坐标得到当前的GID格子编号 func (m *AOIManager) GetGidByPos(x, y float32) int { idx := (int(x) - m.MinX) / m.gridWidth() idy := (int(y) - m.MinY) / m.gridLength() return idy*m.CntsX + idx } //通过横纵坐标得到周边九宫格内全部的PlayerIDs func (m *AOIManager) GetPidsByPos(x, y float32) (playerIDs []int) { //得到当前玩家的GID格子id gID := m.GetGidByPos(x, y) //通过GID得到周边九宫格信息 grids := m.GetSurroundGridsByGid(gID) //将九宫格的信息里的全部的Player的id 累加到 playerIDs for _, grid := range grids { playerIDs = append(playerIDs, grid.GetPlayerIDs()...) //fmt.Println("===> grid ID : %d, pids :%v ====", grid.GID, grid.GetPlayerIDs()) } return }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
六、AOI格⼦添加删除操作
- mmo_game_zinx/core/aoi.go
//添加一个PlayerID到一个格子中 func (m *AOIManager) AddPidToGrid(pID, gID int) { m.grids[gID].Add(pID) } //移除一个格子中的PlayerID func (m *AOIManager) RemovePidFromGrid(pID, gID int) { m.grids[gID].Remove(pID) } //通过GID获取全部的PlayerID func (m *AOIManager) GetPidsByGid(gID int) (playerIDs []int) { playerIDs = m.grids[gID].GetPlayerIDs() return } //通过坐标将Player添加到一个格子中 func (m *AOIManager) AddToGridByPos(pID int, x, y float32) { gID := m.GetGidByPos(x, y) grid := m.grids[gID] grid.Add(pID) } //通过坐标把一个Player从一个格子中删除 func (m *AOIManager) RemoveFromGridbyPos(pID int, x, y float32) { gID := m.GetGidByPos(x, y) grid := m.grids[gID] grid.Remove(pID) }- 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
七、项目目录结构与源码
-
项目目录结构
-
相关阅读:
linux gitlab 502 也可能是文件权限不足
lMe and My Girlfriend: 1 ~ VulnHub靶机
Oracle和MySQL的基本区别（入门级）
WPF livecharts 折线图遮挡数字问题
day04-1群聊功能
Docker compose插件安装
工薪信用贷款全攻略：条件、流程与选择
【相机坐标系、ORB_SLAM2坐标系】
20_ue4进阶末日生存游戏开发[AI基础框架搭建]
figma都有哪些小技巧，分享3个给你
- 原文地址：https://blog.csdn.net/qq23001186/article/details/125022501