IncServer的场景管理及AOI实现

本文还未完成!

本文还未完成!

本文还未完成!

本文谈谈IncServer如何管理游戏场景中的对象(玩家、怪物、机关等)及其AOI实现。

为了简化讨论,本文略去了游戏对象类型和patch粒度两个维度,在文章末尾会做一个简单的补充说明。

基本概念

Scene

Scene即为游戏场景,可以认为每张游戏地图都是一个scene。比如主城场景、公会战场景、每个单人副本或多人副本的场景。

Scene用于记录跟游戏场景相关的静态信息:

  • 游戏地图的尺寸(height、width)
  • 静态的寻路信息(navmesh)
  • 高度图(heightmap)

IncServer中的scene也有对象管理的功能,但我所接触的用IncServer开发的几款游戏中并未使用这个功能。猜测是在多world的scene中,用于管理在每个world中都相同的静态对象。本文对此不做讨论。

World

World也是游戏场景,与scene记录游戏场景的静态信息不同,world记录场景中的动态信息,尤其是各种游戏对象(以下简称对象),比如玩家、怪物、NPC、机关、掉落物,等等。

一个scene可以对应一个world,也可以对应多个world。对于一个scene对应多个world的情况,每个world就可以看做是一个副本了,这确实也是副本概念的一种实现方式。

不过,IncServer虽然支持scene world一对多,但在实际开发中,scene和world都是一对一的。

Plane

Plane,位面,其本质就是一个整数,可用于实现副本的概念,也可以用于实现主城分线的功能(主城分线可以看做是主城的副本)。

每个游戏对象都有一个plane属性,记录其所属的位面。在同一个world中,只有同一plane的游戏对象才可以互相看到、互相影响,不同plane的对象完全感觉不到其他plane的对象的存在。

小结

每个游戏场景对应一个scene,每个scene对应一个world,每个world可以有任意多个plane。

每个scene、world、plane都有其专属的ID,因此一个游戏对象由scene ID、world ID、plane ID三者共同确定其所属的游戏场景及其所属位面。在实际开发中,只用到了一对一的scene和world,因此scene ID和plane ID两个就够了。

场景划分

由于在实际的开发过程中scene和world是一对一的,因此后文不再区分这两个概念,统一称之为场景

Land

IncServer将每个场景看做是由n个land(块)组成,每个land就是一个大小固定的正方形,默认512 * 512。比如一个scene的尺寸为1200 * 700:

则需要6个land来表示:

Patch

Land进一步被划分为若干个Patch(格子)。以patch为单位,land的边长是2的整数次幂。

目的

为什么要将场景划分成这么多格子?

试想一个场景中有1000个玩家,如果任意一个玩家的状态发生变化,都需要广播给其他玩家,将会是$O(n^2)$的复杂度。而对某个玩家来说,通常情况下只对其附近某个范围之内的其他玩家的状态感兴趣。因此有必要采取一种方式,界定这个感兴趣的范围,即AOI(Area of Interest)的概念。

对象管理

全局管理器

World中的所有对象被放在一个数组中统一管理。

众所周知,数组的随机删除操作是低效的,而有些游戏场景经常会出现游戏对象的新增和删除。比如主城场景,玩家进进出出是再自然不过的事情。貌似链表更适合这种增删频繁的场景,那为什么还要用数组来管理所有对象呢?

设计初衷我不了解,我个人的理解是:使用数组可以方便的将各个对象的处理逻辑均分到多个线程去执行。只要知道对象数组当前所存储的对象数量即可,而用链表就不怎么方便了。

但低效的随机删除问题如何解决呢?IncServer的做法如下:

  • 从world中删除对象时,将其索引存储于一个已删除索引的链表中,对象数组相应的位置置为NULL。
  • 在world中新增对象时,优先取用已删除索引链表中的索引。
  • World中记录对象数组的历史最大索引,即world中对象数量的历史最高值-1。
  • 已删除索引链表中无索引可用时,使用历史最大索引+1作为新索引。
  • 历史最大索引可用于均分对象到各处理线程。

比如,world中原本一共有5个对象,此时最大有效索引为4:

Player 1,Player 4依次离开,索引链表中新增两个已删除索引,最大索引依然为4:

Player 5进入world,从索引链表中取用索引4:

Player 6进入world,从索引链表中取用索引1:

Player 7进入world,索引链表无索引可用,历史最大索引递增1,作为Player 7的索引:

可以看出,对象数组中记录的对象并非都是有效的对象,这不是什么大问题,在使用之前判断一下是否为NULL就行了。

分块管理

World对游戏对象的管理以patch为单位,每个patch都对应有一个对象链表

整个world中所有的对象链表的链表头可依次存储于一个一维数组中,这样根据对象的世界坐标,即可方便的计算出其所属的patch以及对应的对象链表。

假设对象的坐标为(x, z),patch的边长为patch_size,land的边长为land_size,整个场景在x方向上有land_x个land,则对象所属的对象链表的索引计算方式为:

index = (z / patch_size) * (land_x * (land_size / patch_size)) + (x / patch_size);

AOI

与常见的九宫格不同,IncServer支持NEAR、MIDDLE、FAR、FULL四种视野范围:

  • NEAR:当前对象所位于的patch
  • MIDDLE:与NEAR相邻的patch
  • FAR:与MID相邻的patch(NEAR除外)
  • FULL:NEAR + MIDDILE + FAR

不过在实际开发中,所有对象的视野都是FULL,即每个对象都能看到以自己所在patch为中心前后左右各两个patch(总计25个patch)内的其他对象。之后的讨论均假设所有游戏对象的视野范围均为FULL

如果对象B进入对象A的视野范围,则根据A对象类型,可能会触发不同的逻辑,比如:

  • 对象A是玩家:将B对象序列化到对象A的客户端。
  • 对象B是怪物:执行对象进入怪物视野的逻辑,比如激活AI等。

后文将以上情况称之为在对象A的视野中加载对象B,简称为视野加载

主要操作

讨论完IncServer如何划分场景、如何管理场景中的对象,以及AOI,接下来看看场景中的主要操作。

新增对象

在world中新增一个游戏对象需要执行以下步骤:

  • 将对象指针加入到全局对象数组中。
  • 找到对象所属的patch,将对象指针加到patch的对象链表中。
  • 遍历对象视野范围内的所有patch,与各个patch对象链表中的对象互相加载视野。

修改对象

移动

跳转

删除对象

删除对象时新增对象的逆操作,因此反向执行新增对象的步骤即可:

  • 遍历对象视野范围内的所有patch,与各个patch对象链表中的对象互相加载视野。

查找对象

增加管理维度

向world中新增一个对象

  • 先加到等待添加的对象数组add_ary_中()add_obj,等到下一帧统一添加add_ary_中的所有对象
  • 真正添加
  • 添加到链表obj_link_
  • 添加到obj_ary_
  • 改变在obj_link_中的位置
  • 处理视野加载

_modifylink

处理对象的位置改变导致其所在的patch改变,进而引发的视野变化

说点什么

avatar
  订阅  
提醒