Go语言如何实现AOI区域视野管理
更新时间：2023-11-10什么是AOI区域视野管理？
AOI（Area of Interest）指的是玩家的视野范围，将玩家当前所处的场景、区域内的其他玩家或敌人等生物实体纳入到视野范围内，可以实现更加逼真的游戏体验。在多人游戏中，需要进行AOI区域视野管理，以避免每个客户端都向服务器请求全部实体数据，导致网络资源消耗过多和服务器压力过大问题。Go语言可以通过多种方式实现AOI区域视野管理，本文将详细介绍如何使用传统的树状结构和切片数据结构两种方式实现AOI区域视野管理。
使用树状结构实现AOI区域视野管理
树状结构是一种描绘对象间层次关系的数据结构，具有根、节点和叶子节点等特性，在AOI区域视野管理中也可以使用树状结构，对实体进行层次划分，以便快速查找和更新实体位置。以下是使用树状结构实现AOI区域视野管理的示例代码：
package main
import (
"fmt"
"math"
)
const (
// 格子的宽度
gridWidth float64 = 1
// 格子的高度
gridHeight float64 = 1
)
// Entity 实体代表一个生物或玩家
type Entity struct {
id int // 实体ID
x float64 // 实体坐标x
y float64 // 实体坐标y
gridX int // 实体所在的格子x
gridY int // 实体所在的格子y
isInSight bool // 实体是否在玩家视野中
isInUpdate bool // 实体是否在更新列表中
}
// Grid 格子代表AOI区域的一个小方格
type Grid struct {
x int // 格子所处的行
y int // 格子所处的列
players []*Entity // 实体列表
}
// World 世界代表整个AOI区域
type World struct {
width int // 世界的宽度
height int // 世界的高度
entities []*Entity // 所有实体
gridWidth float64 // 格子的宽度
gridHeight float64 // 格子的高度
grids map[int]*Grid // 格子映射表
gridCount int // 格子的数量
gridQueue []*Grid // 等待更新的格子列表
radius float64 // 玩家视野半径
playerSight map[*Entity]int // 玩家视野
}
func newEntity(id int, x, y float64) *Entity {
entity := &Entity{
id: id,
x: x,
y: y,
}
entity.updateGridPos()
return entity
}
func (e *Entity) updateGridPos() {
e.gridX = int(math.Floor(e.x / gridWidth))
e.gridY = int(math.Floor(e.y / gridHeight))
}
// NewWorld 创建一个世界
func NewWorld(width, height int, radius float64) *World {
return &World{
width: width,
height: height,
entities: make([]*Entity, 0),
gridWidth: 100,
gridHeight: 100,
grids: make(map[int]*Grid),
gridQueue: make([]*Grid, 0),
radius: radius,
playerSight: make(map[*Entity]int),
}
}
// UpdatePlayer 更新玩家位置
func (w *World) UpdatePlayer(id int, x, y float64) {
entity := w.getEntity(id)
if entity == nil {
entity = newEntity(id, x, y)
w.entities = append(w.entities, entity)
} else {
entity.x = x
entity.y = y
entity.updateGridPos()
}
w.calcEntitySight(entity)
}
// calcEntitySight 计算实体的视野范围
func (w *World) calcEntitySight(entity *Entity) {
entity.isInSight = false
if _, ok := w.playerSight[entity]; !ok {
w.playerSight[entity] = entity.id
} else {
return
}
gridX, gridY := entity.gridX, entity.gridY
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
newGridX, newGridY := gridX+i, gridY+j
if newGridX >= 0 && newGridX*w.gridWidth <= float64(w.width) && newGridY >= 0 && newGridY*w.gridHeight <= float64(w.height) {
index := newGridX*w.width + newGridY
if grid, ok := w.grids[index]; ok {
for _, other := range grid.players {
if other.id != entity.id && distance(entity.x, entity.y, other.x, other.y) <= w.radius {
entity.isInSight = true
if _, ok := w.playerSight[other]; !ok {
w.playerSight[other] = other.id
other.isInSight = true
}
break
}
}
}
}
}
}
}
// GetNearbyPlayers 获取附近的玩家
func (w *World) GetNearbyPlayers(id int) []*Entity {
entity := w.getEntity(id)
if entity == nil {
return nil
}
players := make([]*Entity, 0)
gridX, gridY := entity.gridX, entity.gridY
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
newGridX, newGridY := gridX+i, gridY+j
if newGridX >= 0 && newGridX*w.gridWidth <= float64(w.width) && newGridY >= 0 && newGridY*w.gridHeight <= float64(w.height) {
index := newGridX*w.width + newGridY
if grid, ok := w.grids[index]; ok {
for _, player := range grid.players {
if player.id != entity.id && player.isInSight {
players = append(players, player)
}
}
}
}
}
}
return players
}
func distance(x1, y1, x2, y2 float64) float64 {
return math.Sqrt(math.Pow(x1-x2, 2) + math.Pow(y1-y2, 2))
}
func (w *World) updatePlayerList(id int, isInUpdate bool) {
entity := w.getEntity(id)
if entity != nil {
entity.isInUpdate = isInUpdate
gridX, gridY := entity.gridX, entity.gridY
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
newGridX, newGridY := gridX+i, gridY+j
if newGridX >= 0 && newGridX*w.gridWidth <= float64(w.width) && newGridY >= 0 && newGridY*w.gridHeight <= float64(w.height) {
index := newGridX*w.width + newGridY
if grid, ok := w.grids[index]; ok {
grid.updatePlayer(entity, isInUpdate)
if !isInUpdate && !grid.isInUpdateQueue() {
w.gridQueue = append(w.gridQueue, grid)
grid.isInUpdate = true
}
}
}
}
}
}
}
func (g *Grid) updatePlayer(entity *Entity, isInUpdate bool) {
for i, player := range g.players {
if player.id == entity.id {
g.players[i].isInUpdate = isInUpdate
return
}
}
if isInUpdate {
g.players = append(g.players, entity)
entity.isInUpdate = true
} else {
entity.isInUpdate = false
}
}
func (g *Grid) isInUpdateQueue() bool {
for _, grid := range world.gridQueue {
if grid.x == g.x && grid.y == g.y {
return true
}
}
return false
}
func (w *World) getEntity(id int) *Entity {
for _, entity := range w.entities {
if entity.id == id {
return entity
}
}
return nil
}
// Refresh 可以在游戏循环中调用
func (w *World) Refresh() {
// 排序
for _, entity := range w.entities {
w.updatePlayerList(entity.id, false)
}
// 移除已不可见的玩家
for _, entity := range w.entities {
if !entity.isInSight && entity.isInUpdate {
w.updatePlayerList(entity.id, false)
}
}
// 添加新可见的玩家
for _, entity := range w.entities {
if entity.isInSight && !entity.isInUpdate {
w.updatePlayerList(entity.id, true)
}
}
// 更新等待更新的格子
for _, grid := range w.gridQueue {
grid.isInUpdate = false
}
w.gridQueue = make([]*Grid, 0)
}
使用切片数据结构实现AOI区域视野管理
除了树状结构之外，还可以使用切片数据结构实现AOI区域视野管理。切片使用更加简单，但是在实现时需要对实体进行位置排序和查找。以下是使用切片数据结构实现AOI区域视野管理的示例代码：
package main
import (
"math"
"sort"
)
const (
// 格子的宽度
cellWidth float64 = 1
// 格子的高度
cellHeight float64 = 1
)
// Player 玩家实体
type Player struct {
ID int // 玩家ID
X float64 // 玩家位置X
Y float64 // 玩家位置Y
CellX int // 玩家所在的格子X
CellY int // 玩家所在的格子Y
Neighbors []*Player
IsInSight bool // 是否在视野内
IsInUpdate bool // 是否需要更新
IsInRefresh bool // 是否需要刷新
}
// World AOI世界
type World struct {
GridWidth float64 // 格子的宽度
GridHeight float64 // 格子的高度
Players []*Player // 所有玩家
Grids map[int][]*Player // 网格
}
func (w *World) newPlayer(id int, x, y float64) *Player {
w.Players = append(w.Players, &Player{
ID: id,
X: x,
Y: y,
IsInUpdate: true,
})
return w.Players[len(w.Players)-1]
}
// UpdatePosition 更新玩家的位置
func (w *World) UpdatePosition(id int, x, y float64) {
player := w.GetPlayerByID(id)
if player == nil {
player = w.newPlayer(id, x, y)
}
player.X = x
player.Y = y
oldCellX := player.CellX
oldCellY := player.CellY
player.CellX = int(math.Floor(player.X / w.GridWidth))
player.CellY = int(math.Floor(player.Y / w.GridHeight))
if oldCellX != player.CellX || oldCellY != player.CellY {
player.IsInRefresh = true
}
player.IsInSight = false
w.CalcPlayerAOI(player)
}
// CalcPlayerAOI 计算玩家的视野范围
func (w *World) CalcPlayerAOI(p *Player) {
p.IsInSight = false
p.Neighbors = nil
var centerX, centerY int
for i, player := range w.Players {
if player.ID != p.ID && player.IsInSight == false {
if player.CellX >= p.CellX-1 && player.CellX <= p.CellX+1 &&
player.CellY >= p.CellY-1 && player.CellY <= p.CellY+1 {
if distance(p.X, p.Y, player.X, player.Y) <= w.GridWidth {
player.IsInSight = true
w.Players[i].IsInSight = true
p.Neighbors = append(p.Neighbors, player)
player.Neighbors = append(player.Neighbors, p)
if _, ok := w.Grids[player.CellX*1000+player.CellY]; !ok {
w.Grids[player.CellX*1000+player.CellY] = []*Player{}
}
w.Grids[player.CellX*1000+player.CellY] = append(w.Grids[player.CellX*1000+player.CellY], p)
}
}
}
}
for _, neighbors := range p.Neighbors {
centerX += neighbors.CellX
centerY += neighbors.CellY
}
if len(p.Neighbors) > 0 {
centerX /= len(p.Neighbors)
centerY /= len(p.Neighbors)
}
if len(w.Grids[p.CellX*1000+p.CellY]) == 0 && len(p.Neighbors) == 1 {
neighbors := p.Neighbors[0]
w.Grids[neighbors.CellX*1000+neighbors.CellY] = nil
neighbors.Neighbors = []*Player{}
neighbors.IsInSight = false
neighbors.IsInUpdate = true
for i := range w.Players {
if w.Players[i] != p && w.Players[i] != neighbors {
w.Players[i].IsInSight = false
w.Players[i].IsInUpdate = true
}
}
}
if len(w.Grids[p.CellX*1000+p.CellY]) == 0 {
return
}
sort.Slice(w.Grids[p.CellX*1000+p.CellY], func(i, j int) bool {
distance1 := distance(p.X, p.Y, w.Grids[p.CellX*1000+p.CellY][i].X, w.Grids[p.CellX*1000+p.CellY][i].Y)
distance2 := distance(p.X, p.Y, w.Grids[p.CellX*1000+p.CellY][j].X, w.Grids[p.CellX*1000+p.CellY][j].Y)
return distance1 < distance2
})
for i, player := range w.Grids[p.CellX*1000+p.CellY] {
if distance(p.X, p.Y, player.X, player.Y) <= w.GridWidth {
player.IsInSight = true
player.IsInUpdate = true
if _, ok := w.Grids[player.CellX*1000+player.CellY]; !ok {
w.Grids[player.CellX*1000+player.CellY] = []*Player{}
}
w.Grids[player.CellX*1000+player.CellY] = append(w.Grids[player.CellX*1000+player.CellY], p)
w.Grids[p.CellX*1000+p.CellY][i] = w.Grids[p.CellX*1000+p.CellY][len(w.Grids[p.CellX*1000+p.CellY])-1]
w.Grids[p.CellX*1000+p.CellY][len(w.Grids[p.CellX*1000+p.CellY])-1] = p
w.Grids[p.CellX*1000+p.CellY] = w.Grids[p.CellX*1000+p.CellY][:len(w.Grids[p.CellX*1000+p.CellY])-1]
}
}
}
// Refresh 更新所有的分块信息
func (w *World) Refresh() {
for _, p := range w.Players {
if p.IsInRefresh || p.IsInUpdate {
w.CalcPlayerAOI(p)
p.IsInRefresh = false
p.IsInUpdate = false
}
}
}
// GetPlayerByID 根据ID查询玩家
func (w *World) GetPlayerByID(id int) *Player {
for _, player := range w.Players {
if player.ID == id {
return player
}
}
return nil
}
func distance(x1, y1, x2, y2 float64) float64 {
return math.Sqrt(math.Pow(x1-x2, 2) + math.Pow(y1 
