关于AOI
- 为什么要有AOI
- 如果没有,场景由单线程驱动,场景中有N个人,每个人操作了什么都要广播给自己和其他N-1个人。那么平均每次服务器要给N*N的人发消息。
- 那正常来说这也符合逻辑,我都在一个场景里了,其他人当然要关心我做了什么。
- 但是更多情况下,有些人并不care有些人。就好比
- 北楼起火了,南楼干自己的事情就好了
- 高中生放假了,关我小学生什么事?
- 抽象来说,把场景中的对象分为若干层级,层级之间互不关心。
- 层级可以通过很多方法来区分,最主要的是牵扯到两个(可以有更多,看具体需求)
- 按距离分
- 按玩家所在的层级分,每个玩家可以有多个层级。比如组队层,公会层,场景层,仇人层等等。
进一步抽象
- 每个人拥有自己的一个集合,叫做感兴趣集合,
CollectionOfInterest
- 当某个人需要广播时,只需要往集合中广播就可以,而不必对场景中所有人广播。
- 这个集合可以放在人身上,也可以放在场景的格子上,后面会讲。
感兴趣集合如何创建?
- 即广播即生成型,每次广播的时候生成/更新集合。
- 很费
- 如果是距离集合,每次广播时,场景管理器计算出在这个人周围附近的其他人,加入到集合中。
- 如果是层级集合,每次广播时,场景管理器遍历场景中的所有人,将满足条件(层级相等或者覆盖)的加入到集合中。
- 即变化即生成性,只在集合状态改变的时候生成/更新集合。
- 常用
- 如果是距离集合,每次更新集合
- 如果是层级集合,每次更新集合
深入距离更新集合
- 朴素方法
- 当A的距离发生变化时:
- 遍历其他所有人,更新A的集合:如果其他人在A的距离内,加入到集合中;否则移出集合;
- 遍历其他所有人,针对A,更新其他所有人的集合:如果A在这个人的距离内,加入到集合中;否则,移出集合。
- 超级费,一个人变化需要(N-1) + (N-1)次,一帧有N个人变化就要N*N次
- 经典九宫格/空间切分
- 将场景切分为若干个格子,每个人都会落在某个格子{x,y}中。其实朴素方法相当于一个整个大格子。
- 当A的距离发生变化时,场景管理器要做的事情:
- 计算A变化之后所在的格子,如果和之前的相同,则什么都不做。
- 记录A变化之前所在的格子圈圈集合为
OldGrid,如果是九宫格就是格子周围一圈,也可以是格子周围N圈,根据A的可视范围来定。
- 记录A变化之后的
NewGrid
- 计算
CommonGrid就是二者的交集OldGrid∩NewGrid,计算LeaveGrid就是OldGrid-CommonGrid,计算EnterGrid就是NewGrid-CommonGrid
- 对在
LeaveGrid的所有人,互相更新A和所有人的集合
- 对在
EnterGrid的所有人,互相更新A和所有人的集合
- 经典十字链表
数组VS链表
- 经典内存占用vs存取和查询速度取舍
- 方格全部个小方格,就 退化成经典的朴素方法
- 方格一个大方格,就是全局方法