Go語(yǔ)言實(shí)現(xiàn)AOI區(qū)域視野管理流程詳解

更新時(shí)間：2023年03月06日 11:27:25 作者：zhizhizhi志

在游戲中,場(chǎng)景里存在大量的物體.如果我們把所有物體的變化都廣播給玩家.那客戶(hù)端很難承受這么大的壓力.因此我們肯定會(huì)做優(yōu)化.把不必要的信息過(guò)濾掉.如只關(guān)心玩家視野所看到的.減輕客戶(hù)端的壓力,給玩家更流暢的體驗(yàn)

一.定義管理器接口

1. 進(jìn)入?yún)^(qū)域

2. 離開(kāi)區(qū)域

3. 在區(qū)域移動(dòng)

4. 同步信息

具體實(shí)現(xiàn):

type TowerAOIManager struct {
	minX, maxX, minY, maxY float64 // 單位 m
	towerRange             float64 // 格子大小
	towers                 [][]tower
	xTowerNum, yTowerNum   int
}

劃分格子: 按照實(shí)際情況出發(fā),規(guī)定格子大小 towerRange. (一般九個(gè)格子的范圍需大于屏幕看到的視野范圍) 這樣才能保證客戶(hù)端場(chǎng)景物體的生成和消失在玩家屏幕外.不會(huì)突然出現(xiàn).

// 構(gòu)造結(jié)構(gòu)
func NewTowerAOIManager(minX, maxX, minY, maxY float64, towerRange float64) AOIManager {
	mgr := &TowerAOIManager{minX: minX, maxX: maxX, minY: minY, maxY: maxY, towerRange: towerRange}
	mgr.init()
	return mgr
}
func (m *TowerAOIManager) init() {
	numXSlots := int((m.maxX-m.minX)/m.towerRange) + 1
	m.xTowerNum = numXSlots
	numYSlots := int((m.maxY-m.minY)/m.towerRange) + 1
	m.yTowerNum = numYSlots
	m.towers = make([][]tower, numXSlots)
	for i := 0; i < numXSlots; i++ {
		m.towers[i] = make([]tower, numYSlots)
		for j := 0; j < numYSlots; j++ {
			key := NewKey(int64(i), int64(j))
			m.towers[i][j].init(int64(key))
		}
	}
}

二.定義區(qū)域tower

type tower struct {
	towerId       int64
	context       *TowerSyncContext
	mapId2Obj     map[uint32]scene.GameObject // obj容器
	mapId2Watcher map[uint32]scene.GameObject // 觀察集合
}

func (t *tower) init(key int64) {
	t.towerId = key
	t.context = NewTowerSyncContext() // 同步信息
	t.mapId2Obj = make(map[uint32]scene.GameObject)
	t.mapId2Watcher = make(map[uint32]scene.GameObject)
}

func (t *tower) AddObj(obj scene.GameObject, fromOtherTower scene.AOITower, bExclude bool) {
	obj.SetAOITower(t)
	t.mapId2Obj[obj.GetId()] = obj
	if fromOtherTower == nil {
		for watcherId, watcher := range t.mapId2Watcher {
			if bExclude && watcherId == obj.GetId() {
				continue
			}
			watcher.OnEnterAOI(obj)
		}
	} else {
		// obj moved from other tower to this tower
		for watcherId, watcher := range fromOtherTower.GetWatchers() {
			if watcherId == obj.GetId() {
				continue
			}
			if _, ok := t.mapId2Watcher[watcherId]; ok {
				continue
			}
			watcher.OnLeaveAOI(obj)
		}
		for watcherId, watcher := range t.mapId2Watcher {
			if watcherId == obj.GetId() {
				continue
			}
			if _, ok := fromOtherTower.GetWatchers()[watcherId]; ok {
				continue
			}
			watcher.OnEnterAOI(obj)
		}
	}
}
func (t *tower) RemoveObj(obj scene.GameObject, notifyWatchers bool) {
	obj.SetAOITower(nil)
	delete(t.mapId2Obj, obj.GetId())
	if notifyWatchers {
		for watcherId, watcher := range t.mapId2Watcher {
			if watcherId == obj.GetId() {
				continue
			}
			watcher.OnLeaveAOI(obj)
		}
	}
}
func (t *tower) addWatcher(obj scene.GameObject, bExclude bool) {
	if bExclude {
		if _, ok := t.mapId2Watcher[obj.GetId()]; ok {
			// todo log
			return
		}
	}
	t.mapId2Watcher[obj.GetId()] = obj
	// now obj can see all objs under this tower
	for neighborId, neighbor := range t.mapId2Obj {
		if neighborId == obj.GetId() {
			continue
		}
		obj.OnEnterAOI(neighbor)
	}
}
func (t *tower) removeWatcher(obj scene.GameObject) {
	if _, ok := t.mapId2Watcher[obj.GetId()]; !ok {
		// todo log
		return
	}
	delete(t.mapId2Watcher, obj.GetId())
	for neighborId, neighbor := range t.mapId2Obj {
		if neighborId == obj.GetId() {
			continue
		}
		obj.OnLeaveAOI(neighbor)
	}
}
func (t *tower) GetWatchers() map[uint32]scene.GameObject {
	return t.mapId2Watcher
}
func (t *tower) GetObjs() map[uint32]scene.GameObject {
	return t.mapId2Obj
}
func (t *tower) GetTowerId() int64 {
	return t.towerId
}
func (t *tower) AddSyncData(mod uint16, cmd uint16, msg protoreflect.ProtoMessage) {
	t.context.AddSyncData(mod, cmd, msg)
}
func (t *tower) Broadcast() {
	if len(t.context.fights) == 0 {
		return
	}
	// 廣播協(xié)議
	 ....   
	t.context.ClearContext()
}

三.AOI的具體方法實(shí)現(xiàn)

我們?cè)诨剡^(guò)頭來(lái)繼續(xù)說(shuō) mgr 的方法.

1.進(jìn)入實(shí)現(xiàn)

前提:

GameObject : 一切場(chǎng)景物體的基礎(chǔ)接口

type GameObject interface {}

Vector2d : X,Y 坐標(biāo)

type Vector2d struct {
	x, y, w float64
}

具體實(shí)現(xiàn):

如果是從上一個(gè)區(qū)域內(nèi)離開(kāi),則先走離開(kāi)上一個(gè)區(qū)域,然后計(jì)算當(dāng)前進(jìn)入位置坐標(biāo)對(duì)應(yīng)的九宮區(qū)域,

然后把obj 加入到各個(gè)區(qū)域內(nèi)

func (m *TowerAOIManager) OnEnter(obj scene.GameObject, enterPos *geom.Vector2d) bool {
	if obj.GetAOITower() != nil {
		m.OnLeave(obj) // 離開(kāi)上一個(gè)區(qū)域
	}
	obj.SetPosition(enterPos) // 設(shè)置當(dāng)前位置
    // obj 視野范圍內(nèi)的所有區(qū)域
	m.visitWatchedTowers(enterPos, obj.GetViewRange(), func(tower *tower) {
		tower.addWatcher(obj, false)
	})
	t := m.getTowerXY(enterPos)
    // 當(dāng)前位置所在的區(qū)域
	t.AddObj(obj, nil, false)
	return true
}
func (m *TowerAOIManager) getTowerXY(xyPos *geom.Vector2d) *tower {
	xi, yi := m.transXY(xyPos.GetX(), xyPos.GetY())
	return &m.towers[xi][yi]
}

關(guān)鍵的方法:

計(jì)算obj當(dāng)前位置中,視野內(nèi)能被觀察到的所有區(qū)域.

func (m *TowerAOIManager) visitWatchedTowers(xyPos *geom.Vector2d, aoiDistance float64, f func(*tower)) {
	ximin, ximax, yimin, yimax := m.getWatchedTowers(xyPos.GetX(), xyPos.GetY(), aoiDistance)
	for xi := ximin; xi <= ximax; xi++ {
		for yi := yimin; yi <= yimax; yi++ {
			tower := &m.towers[xi][yi]
			f(tower)
		}
	}
}
func (aoiman *TowerAOIManager) getWatchedTowers(x, y float64, aoiDistance float64) (int, int, int, int) {
	ximin, yimin := aoiman.transXY(x-aoiDistance, y-aoiDistance)
	ximax, yimax := aoiman.transXY(x+aoiDistance, y+aoiDistance)
	return ximin, ximax, yimin, yimax
}
func (m *TowerAOIManager) transXY(x, y float64) (int, int) {
	xi := int((x - m.minX) / m.towerRange)
	yi := int((y - m.minY) / m.towerRange)
	return m.normalizeXi(xi), m.normalizeYi(yi)
}
func (m *TowerAOIManager) normalizeXi(xi int) int {
	if xi < 0 {
		xi = 0
	} else if xi >= m.xTowerNum {
		xi = m.xTowerNum - 1
	}
	return xi
}
func (m *TowerAOIManager) normalizeYi(yi int) int {
	if yi < 0 {
		yi = 0
	} else if yi >= m.yTowerNum {
		yi = m.yTowerNum - 1
	}
	return yi
}

2.離開(kāi)區(qū)域

func (m *TowerAOIManager) OnLeave(obj scene.GameObject) bool {
	obj.GetAOITower().RemoveObj(obj, true) // 離開(kāi)當(dāng)前區(qū)域
    // 查找視野內(nèi)所有區(qū)域,然后從關(guān)注列表中移除
	m.visitWatchedTowers(obj.GetPosition(), obj.GetViewRange(), func(tower *tower) {
		tower.removeWatcher(obj)
	})
	return true
}

3.移動(dòng)

每幀移動(dòng)坐標(biāo)點(diǎn) movePos

func (m *TowerAOIManager) OnMove(obj scene.GameObject, movePos *geom.Vector2d) bool {
	oldX, oldY := obj.GetPosition().GetX(), obj.GetPosition().GetY()
	obj.SetPosition(movePos) //設(shè)置當(dāng)前坐標(biāo)
	t0 := obj.GetAOITower()
	t1 := m.getTowerXY(movePos)
    // 判斷移動(dòng)是否跨區(qū)域了
	if t0.GetTowerId() != t1.GetTowerId() {
		t0.RemoveObj(obj, false)
		t1.AddObj(obj, t0, true)
	}
    // 計(jì)算前后變化的區(qū)域,進(jìn)行移除和添加關(guān)注列表
	oximin, oximax, oyimin, oyimax := m.getWatchedTowers(oldX, oldY, obj.GetViewRange())
	ximin, ximax, yimin, yimax := m.getWatchedTowers(movePos.GetX(), movePos.GetY(), obj.GetViewRange())
	for xi := oximin; xi <= oximax; xi++ {
		for yi := oyimin; yi <= oyimax; yi++ {
			if xi >= ximin && xi <= ximax && yi >= yimin && yi <= yimax {
				continue
			}
			tower := &m.towers[xi][yi]
			tower.removeWatcher(obj)
		}
	}
	for xi := ximin; xi <= ximax; xi++ {
		for yi := yimin; yi <= yimax; yi++ {
			if xi >= oximin && xi <= oximax && yi >= oyimin && yi <= oyimax {
				continue
			}
			tower := &m.towers[xi][yi]
			tower.addWatcher(obj, true)
		}
	}
	return true
}

4.同步

每幀同步所有區(qū)域變化的物體對(duì)象

func (m *TowerAOIManager) OnSync() {
	for i := 0; i < m.xTowerNum; i++ {
		for j := 0; j < m.yTowerNum; j++ {
			m.towers[i][j].Broadcast()
		}
	}
}

簡(jiǎn)單的實(shí)現(xiàn)了 AOI 區(qū)域變化管理,當(dāng)然后面還需要優(yōu)化,我們知道"九宮格" 算法的缺點(diǎn):

1 . 當(dāng)玩家跨越格子的時(shí)候,比如說(shuō)從A點(diǎn)到B點(diǎn).瞬間會(huì)有新增格子,那其中的對(duì)象就會(huì)進(jìn)入視野,與此同時(shí),就會(huì)有消失的格子,那其中的對(duì)象就要消失視野.這個(gè)瞬間就會(huì)出現(xiàn)一個(gè)流量激增點(diǎn),它可能會(huì)導(dǎo)致客戶(hù)端卡頓等問(wèn)題.

2. 流量浪費(fèi).有客戶(hù)端不需要的對(duì)象被同步過(guò)來(lái)了.我們知道它是基于格子來(lái)管理地圖對(duì)象的.那么就會(huì)無(wú)法保證九宮區(qū)域一定剛好是視野范圍.肯定是大于視野區(qū)域這樣才保證同步對(duì)象正確.(如果是俯視角那種 ,視野就會(huì)是一個(gè) 梯形范圍.)