1、AOI基本介绍

游戏的AOI(Area of Interest)算法应该算作游戏的基础核心了，许多逻辑都是因为AOI进出事件驱动的，许多网络同步数据也是因为AOI进出事件产生的。因此，良好的AOI算法和基于AOI算法的优化，是提高游戏性能的关键。

为此，需要为每一个玩家设置一个AOI，当一个对象状态发生改变时，需要将信息广播给全部玩家，那些AOI覆盖到的玩家会收到这条广播消息，从而做出对应的响应状态。

功能：

• 服务器的玩家或NPC状态发生变化时，将消息广播到附近的玩家。
• 玩家进入NPC警戒区域时，AOI模块将消息发送给NPC，NPC再作出响应的AI反应。

2、网格法实现AOI算法

首先绘制一个2D的地图

假设在8中的玩家抽中了一把武器，那么周围2、3、4、9、14、13、12、7方格内的玩家都应该收到消息。通过分析，我们至少脑海里要有两个结构体，第一就是AOI格子数据类型，第二就是AOI管理格子(地图)数据类型。

格子的详细情况：

• 格子
  • 属性：格子ID、格子的右边界坐标、格子左边界坐标、格子上边界坐标、格子下边界坐标、当前格子内玩家/物体成员的ID集合、保护锁
  • 方法：初始化格子的方法、格子添加玩家/物品、格子删除玩家/物品、获取所有玩家、打印格子信息(调试)
• 管理格子(地图)

  • 属性：区域的左边界、区域的右边界、X方向格子的数量、区域的上边界、区域的上边界、Y方向格子的数量、当前区域有哪些格子map

  • 方法：初始化一个AOI区域管理模块、打印当前AOI地图的信息(调试)、根据格子ID查询周围的格子信息、添加一个玩家到指定格子中、移除一个格子中某个玩家、通过坐标将玩家添加进一个格子中、通过坐标把一个玩家从指定的格子中移除、通过玩家的坐标获得当前player周边九宫格内全部的玩家、通过坐标获取得到对应的玩家所在的GID

    • 如何通过x、y计算编号：$gid=y\ast cntsX+y$
    • 如何通过x、y计算格子的x、y：

      • 格子的minX：$aoi.MinX+x\ast gh$

      • 格子的maxX：$aoi.MinX+(x+1)\ast gh$

      • 格子的minY：$aoi.MinY+y\ast gl$

      • 格子的maxY：$aoi.MinY+(y+1)\ast gl$

        
        完整代码在文章的最后。

3、实现通知周围

如果是黄色格子里面对象，我们如何实现通知周围的格子呢？其主要情况有以下几种：

当然在这里我们可以分别格子是不是内部点或者顶点或者是边缘点，但是这样算法复杂程度有些复杂了。在这里我们的采用都按照第一种来，如果你的周围是合法的格子就直接返回，而那些不合法的格子就直接不要。算法实现细节如下：

// GetSurroundGridsByGid 根据格子GID得到周边就宫格的ID集合
func (m *AOIManager) GetSurroundGridsByGid(gID int) (grids []*Grid) {// 判断gID是否在AOIManager中if _, ok := m.Grids[gID]; !ok {return nil}// 初始化返回值数组grids = append(grids, m.Grids[gID])// 判断gID左边是否有格子、右边是否有格子indexX := gID % m.CntsX// 需要通过gID得到当前格子X轴的编号 idx:= id % cnx// 判断idx编号坐标右边是否还有格子if indexX > 0 {grids = append(grids, m.Grids[gID-1])}// 判断idx编号坐标左边是否还有格子if indexX < m.CntsX-1 {grids = append(grids, m.Grids[gID+1])}// 遍历一个slicefor _, grid := range grids {if grid.GID/m.CntsY > 0 {grids = append(grids, m.Grids[grid.GID-5])}if grid.GID/m.CntsY < m.CntsY-1 {grids = append(grids, m.Grids[grid.GID+5])}}return
}

4、完整代码

aoi.go

package coreimport "fmt"// AOIManager AOI区域管理模块
type AOIManager struct {// 左MinX int// 右MaxX int// X方向格子的数量CntsX int// 上MinY int// 下MaxY int// Y方向格子的数量CntsY int// 当前区域中有哪些格子IdGrids map[int]*Grid
}// NewAOIManager 初始化一个AOI区域管理模块
func NewAOIManager(minX, maxX, cntsX, minY, maxY, cntsY int) *AOIManager {aoi := &AOIManager{MinX:  minX,MaxX:  maxX,CntsX: cntsX,MinY:  minY,MaxY:  maxY,CntsY: cntsY,Grids: make(map[int]*Grid),}// 给aoi初始化区域中所有的格子进行编号和初始化gh := aoi.gridHeight()gl := aoi.gridLength()for y := 0; y < cntsY; y++ {for x := 0; x < cntsX; x++ {/*这里是关键*/// 根据x，y编号，计算格子ID：idy*cntsX+xgid := y*cntsX + x// 初始化gidaoi.Grids[gid] = NewGrid(gid, aoi.MinX+x*gh,aoi.MinX+(x+1)*gh,aoi.MinY+y*gl,aoi.MinY+(y+1)*gl)}}return aoi
}// 得到每个格子在X轴方向的宽度
func (m *AOIManager) gridHeight() 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 {// 打印aoi信息s := fmt.Sprintf("AOIManager:\n"+"MinX:%d,MaxX:%d,CntsX:%d\n"+"MinY:%d,MaxX:%d,CntsX:%d\n", m.MinX, m.MaxX, m.CntsX, m.MinY, m.MaxY, m.CntsY)// 打印格子的信息for _, grid := range m.Grids {s += fmt.Sprintln(grid)}return s
}// GetSurroundGridsByGid 根据格子GID得到周边就宫格的ID集合
func (m *AOIManager) GetSurroundGridsByGid(gID int) (grids []*Grid) {// 判断gID是否在AOIManager中if _, ok := m.Grids[gID]; !ok {return nil}// 初始化返回值数组grids = append(grids, m.Grids[gID])// 判断gID左边是否有格子、右边是否有格子indexX := gID % m.CntsX// 需要通过gID得到当前格子X轴的编号 idx:= id % cnx// 判断idx编号坐标右边是否还有格子if indexX > 0 {grids = append(grids, m.Grids[gID-1])}// 判断idx编号坐标左边是否还有格子if indexX < m.CntsX-1 {grids = append(grids, m.Grids[gID+1])}// 遍历一个slicefor _, grid := range grids {if grid.GID/m.CntsY > 0 {grids = append(grids, m.Grids[grid.GID-5])}if grid.GID/m.CntsY < m.CntsY-1 {grids = append(grids, m.Grids[grid.GID+5])}}return
}// GetPidsByPos 通过横纵坐标得到周边9宫格内全部的PlayersIDs
func (m *AOIManager) GetPidsByPos(x, y float32) (playerIDs []int) {// 得到当前玩家的GID格子idgID := m.GetGidByPos(x, y)// 通过GID得到周边九宫格信息grids := m.GetSurroundGridsByGid(gID)// 将九宫格的信息里的全部的Player的id累加到playerIDsfor _, grid := range grids {playerIDs = append(playerIDs, grid.GetPlayerIDs()...)fmt.Printf("========> grid ID:%d ,pid:%v <===========", grid.GID, grid.GetPlayerIDs())}return
}// GetGidByPos 通过x、y横纵轴坐标得到当前的GID格子编号
func (m *AOIManager) GetGidByPos(x, y float32) int {idx := (int(x) - m.MinX) / m.gridLength()idy := (int(y) - m.MinY) / m.gridLength()return idy*m.CntsX + idx
}// AddPidToGrid 添加一个PlayerID到一个格子中
func (m *AOIManager) AddPidToGrid(pID, gID int) {m.Grids[gID].Add(pID)
}// RemovePidFromGrid 移除一个格子中的PlayerID
func (m *AOIManager) RemovePidFromGrid(pID, gID int) {m.Grids[gID].Delete(pID)
}// GetPidsByGid 通过GID获得全部的PlayerID
func (m *AOIManager) GetPidsByGid(gID int) (playerIDs []int) {playerIDs = m.Grids[gID].GetPlayerIDs()return
}// AddToGridByPos 通过坐标将Player添加到一个格子中
func (m *AOIManager) AddToGridByPos(pID int, x, y float32) {gID := m.GetGidByPos(x, y)grid := m.Grids[gID]grid.Add(pID)
}// RemoveFromGridByPos 通过坐标把一个Player从一个格子中删除
func (m *AOIManager) RemoveFromGridByPos(pID int, x, y float32) {gID := m.GetGidByPos(x, y)grid := m.Grids[gID]grid.Delete(pID)
}

grid.go

package coreimport ("fmt""sync"
)// Grid 一个AOI地图中的格子类型
type Grid struct {// 格子IDGID int// 左界MinX int// 右界MaxX int// 上界MinY int// 下界MaxY int// 当前玩家集合playerIDs map[int]bool// 保护锁pIDLock sync.RWMutex
}// NewGrid 初始化格子的方法
func NewGrid(id, minX, maxX, minY, maxY int) *Grid {return &Grid{GID:  id,MinX: minX,MaxX: maxX,MinY: minY,MaxY: maxY,}
}// Add 格子添加玩家/物品
func (g *Grid) Add(playerID int) {g.pIDLock.Lock()defer g.pIDLock.Unlock()g.playerIDs[playerID] = true}// Delete 格子删除玩家/物品
func (g *Grid) Delete(playerID int) {g.pIDLock.Lock()defer g.pIDLock.Unlock()delete(g.playerIDs, playerID)
}// GetPlayerIDs 获取所有玩家ID
func (g *Grid) GetPlayerIDs() (ids []int) {g.pIDLock.Lock()defer g.pIDLock.Unlock()for k, _ := range g.playerIDs {ids = append(ids, k)}return
}// 打印格子信息(调试)
func (g *Grid) String() string {return fmt.Sprintf("Grid id:%d，minX:%d，"+"maxX:%d，minY:%d，"+"maxY:%d，playerIDs:%v\n", g.GID, g.MinX, g.MaxX, g.MinY, g.MaxY, g.playerIDs)}