本文还未完成！

本文还未完成！

本文还未完成！

本文谈谈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改变，进而引发的视野变化

打赏微海报分享