基于Golang实现多人在线游戏的AOI算法

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计算编号： $g i d = y * c n t s X + y$
  - 如何通过x、y计算格子的x、y：
    - 格子的minX： $a o i . M in X + x * g h$
    - 格子的maxX： $a o i . M in X + (x + 1) * g h$
    - 格子的minY： $a o i . M inY + y * g l$
    - 格子的maxY： $a o i . M inY + (y + 1) * g l$
      
      完整代码在文章的最后。

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])
	}
	// 遍历一个slice
	for _, 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 core

import "fmt"

// AOIManager AOI区域管理模块
type AOIManager struct {
	// 左
	MinX int
	// 右
	MaxX int
	// X方向格子的数量
	CntsX int
	// 上
	MinY int
	// 下
	MaxY int
	// Y方向格子的数量
	CntsY int
	// 当前区域中有哪些格子Id
	Grids 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+x
			gid := y*cntsX + x
			// 初始化gid
			aoi.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])
	}
	// 遍历一个slice
	for _, 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格子id
	gID := m.GetGidByPos(x, y)
	// 通过GID得到周边九宫格信息
	grids := m.GetSurroundGridsByGid(gID)
	// 将九宫格的信息里的全部的Player的id累加到playerIDs
	for _, 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 core

import (
	"fmt"
	"sync"
)

// Grid 一个AOI地图中的格子类型
type Grid struct {
	// 格子ID
	GID 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)

}