aoi

README

游戏AOI算法大致有4种，在此做一些总结，顺便梳理一下，打算设计出一套统一的接口封装不同的算法实现。 4种算法：全场景同步法（最粗暴简单）、网格法、十字链表法、热点法（云风设计的，暂且叫这个名字）

有一些可行的做法可以简单有效地提高AOI系统的运行效率： (1)对场景中的物体特性作出区分 比如售卖NPC / 玩家 / 有AI自动攻击范围内玩家的怪物 这三种就区别对待，因为售卖NPC显然不需要看到任何物体，但是它需要被玩家看到； 而玩家需要看到所有物体； 而怪物则只需要看到玩家，不需要看到其他怪物，也不需要看到NPC。 而区分特性的做法也很简单，引入一个简单的Interest机制即可。 比如InterestMask，只需要一个 & 操作便可能跳过大量的后续处理； 又比如使用更通用的InterestFilterCallback。 (2)合理利用网络延时 我们的MMORPG运行在一个非即时的网络环境下，公网上120~200ms的延时通常对玩家而言是可接受的， 而我们在接受这个事实的同时也应该利用这个事实。虽然我们实现上可以完全实现移动的同时进行可见集的差异广播， 但是，即使服务器每隔200ms向某个玩家同步一次可见集信息，在很多MMORPG的玩法上，也是可以接受的，而该方案下便可引入其他一些特别的优化了。 (3)基于聚集点做局部优化处理 因为一个在线游戏中，玩家并不是理想地平均分布的，玩家集中的点大部分都受到玩法的影响， 比如功能性NPC的周围、刷怪区域、摆摊区域等，上述等方法在这种密集玩家聚集的区域， 算法时间复杂度都向O(n平方)靠拢。此时可以考虑达到一定的阈值区域特殊处理。 (4)根据可操作距离区分同步频率/区分同步信息层次细节度(LOD) 这个方法是在一个paper上看到的，具体做法是当我们要同步A物体的AOI信息时， 对AOI范围内的物体按距离远近做出信息同步频率的区分； 假设按远近对A的AOI范围物体分为近（可操作）、中（不可操作，但影响游戏感受）、远（不可操作，且不精确移动也无所谓）三级。 近的物体是实时同步的/LOD高，中的物体按照较高频率同步/LOD中，远的物体则低频率同步/LOD低。 物体移动时，原来的中、远距离物体会依次变成近的物体，所以逻辑上是准确无误的。但是可能会有一些跑动后的拉扯行为， 如果觉得不可接受，引入了dead reckoning做行为预测。 (5)策划应该参与优化 列在最后但是并不是最不重要的。其实，无论怎么优化AOI算法，最有效的优化还是策划设置玩法上尽量避免单点（小区域）大量聚合玩家， 单点聚合后接近O(n^2)是少不了的。非常不明智。所以大家也看到为什么很多MMORPG会分门派，每个门派的场景一般不同。 程序的优化相对于策划的优化来说，是下策。

Documentation

Index

• type CallBackFn
• type EntityBase
  • func (e *EntityBase) GetEntityID() EntityID
  • func (e *EntityBase) GetNode() *Node
  • func (e *EntityBase) GetPosition() *r3.Vector
  • func (e *EntityBase) GetRadius() float64
• type EntityID
• type EntityIF
• type EntityType
• type Manager
  • func (m *Manager) Add(entity EntityIF)
  • func (m *Manager) AddRangeOfEntity(entity EntityIF, vector *r3.Vector, entityType EntityType)
  • func (m *Manager) EntitiesInRange(entity EntityIF, radius float64, isIncludeSelf bool) ([]EntityID, error)
  • func (m *Manager) Move(entity EntityIF, point *r3.Vector)
  • func (m *Manager) Remove(entity EntityIF)
• type Node
• type RangeTrigger
• type RangeTriggerNode
  • func (n *RangeTriggerNode) GetEntityID() EntityID
  • func (n *RangeTriggerNode) GetNode() *Node
  • func (n *RangeTriggerNode) GetPosition() *r3.Vector
  • func (n *RangeTriggerNode) GetRadius() float64

Types

type CallBackFn

type CallBackFn func()

type EntityBase

type EntityBase struct {
	Vec    *r3.Vector
	AoiId  EntityID
	Radius float64
	// contains filtered or unexported fields
}

EntityBase aoi entity base

func (*EntityBase) GetEntityID

func (e *EntityBase) GetEntityID() EntityID

func (*EntityBase) GetNode

func (e *EntityBase) GetNode() *Node

func (*EntityBase) GetPosition

func (e *EntityBase) GetPosition() *r3.Vector

func (*EntityBase) GetRadius

func (e *EntityBase) GetRadius() float64

type EntityID

type EntityID uint64

type EntityIF

type EntityIF interface {
	GetEntityID() EntityID
	GetRadius() float64

	GetNode() *Node
	GetPosition() *r3.Vector
	// contains filtered or unexported methods
}

type EntityType

type EntityType uint16

type Manager

type Manager struct {
	// contains filtered or unexported fields
}

Manager aoi manager

func (*Manager) Add

func (m *Manager) Add(entity EntityIF)

Add ...

func (*Manager) AddRangeOfEntity

func (m *Manager) AddRangeOfEntity(entity EntityIF, vector *r3.Vector, entityType EntityType)

AddRangeOfEntity ...

func (*Manager) EntitiesInRange

func (m *Manager) EntitiesInRange(entity EntityIF, radius float64, isIncludeSelf bool) ([]EntityID, error)

EntitiesInRange ...

func (*Manager) Move

func (m *Manager) Move(entity EntityIF, point *r3.Vector)

func (*Manager) Remove

func (m *Manager) Remove(entity EntityIF)

Remove ...

type Node

type Node struct {
	// contains filtered or unexported fields
}

Node aoi node

type RangeTrigger

type RangeTrigger struct {
	// contains filtered or unexported fields
}

type RangeTriggerNode

type RangeTriggerNode struct {
	Cur, Old r3.Vector
	// contains filtered or unexported fields
}

func (*RangeTriggerNode) GetEntityID

func (n *RangeTriggerNode) GetEntityID() EntityID

func (*RangeTriggerNode) GetNode

func (n *RangeTriggerNode) GetNode() *Node

func (*RangeTriggerNode) GetPosition

func (n *RangeTriggerNode) GetPosition() *r3.Vector

func (*RangeTriggerNode) GetRadius

func (n *RangeTriggerNode) GetRadius() float64