« November 2017 | Main

December 10, 2017

ECS 的 entity 集合维护

最近在基于 ECS 模型做一些基础工作。实际操作时有一个问题不太明白,那就是涉及对象 (entity) 集合本身的 System 到底应该怎样处理才合适。

仔细阅读了能找到的关于 ECS 的资料,网上能找到的大多是几年前甚至 10 年前的。关于 ECS 的资料都不断地强调一些基本原则:C 里面不可以有方法(纯数据结构),S 里面不可以有状态(纯函数)。从这个角度看,Unity 其实只是一个 EC 系统,而不是 ECS 系统。从 Unity 中寻找关于 System 的设计模式恐怕并不合适。

重看了一遍暴雪在今年 GDC 上的演讲 Overwatch Gameplay Architecture and Netcode —— 这可能是最新公开的采用 ECS 模式的成功(守望先锋)实践了—— 我想我碰到的基础问题应该在里面都有答案。

从绝大多数资料看来,Entity-Component 是对 C++ 中对象模型的一个反思:基于组合,甚至是运行期组合,而不是继承,去合成对象;System 是对 OO 面向对象设计方法的反思:把方法和数据结构分离,不要把一组方法绑定在对象上,即面向对象所主张的,由对象来处理针对它的不同行为;而是由 System 来处理不同的对象聚合。

采用 ECS 模型是因为过去的 OOP 模型耦合度太高,EC/System 的方式可以用来解耦。

把对象 Entity 拆分为更基础的数据结构单元(Component),让 System 直接作用于 Component 集合而不是对象,的确可以对大部分问题解耦。正如 Wikipedia 页面上的举例:假设有一个绘图 System将迭代所有有物理组件和可视组件的 Entity ,它从可视组件中了解 Entity 的怎样绘制,再从物理组件中了解 Entity 该在哪里绘制。而另一个 System 专门处理碰撞检测,它迭代出所有有物理组件的 Entity ,处理他们的碰撞关系,负责产生碰撞事件,但这个 System 不用关心这些 Entity 是怎么绘制的,也不用知道 Entity 具体是什么东西,碰撞本身会有什么后果。再会有另一个 System 负责 Entity 的血量,血量组件记录了 Entity 的 HP 数据,这个 System 处理碰撞事件,知道当子弹击中怪物后,怪物需要扣血。

这样看都很美好,只是,游戏引擎中,往往还有一个性能相关的需求:剔除。一个 System 需要处理的对象往往是全体对象的一个子集。如果子集远小于全体的话,每帧按 Component 类型去迭代整体就有很大的性能开销。

比如,渲染 System 通常会根据摄像机在场景中的位置,剔除掉场景中的大部分物件。如果我们编写了这么一个剔除的 System ,那么在这个 System 运作之后,后续的其它 System 就不应该在整个世界中迭代可视的 Component ,而应该针对的是剔除后的集合了。

如果忽略 EC 这种基于组合的对象模型和传统 C++ 中基于继承的对象模型的实现上的差异,我们可以把 Component 仅看成是 Entity 身上的一种筛选标签 Label ,ECS 模型其实是为 System 提供了按 Label 筛选出 Entity 集合的能力。那么,我们是不是应该提供一种不太影响处理效率的,动态贴标签和撕标签的能力?空间剔除器可以给 Entity 打上需要渲染的标签,后续的渲染器可以迭代“需渲染”的组件集合。

我在 Overwatch Gameplay Architecture and Netcode 中看不到类似的设计,在我自己的实践中,Label 的想法也有不少问题。所以想了另一种方案。

据说,在守望先锋的引擎中,存在着大量的单件(singleton)组件。相关的 System 只会处理这一个组件,从里面读取数据,或把数据放在其中。我认为、用于 System 间交换数据的事件队列、剔除器的结果、这些都应该是存放在某个单件中。像渲染器这种 System 不必从 Entity 全集中迭代需要渲染的集合,而应该转而从剔除器单件里迭代一个子集。

而剔除器的工作依赖对象本身的状态变化。游戏场景中会有大量的物件,它们的状态几乎不会变化,每帧都迭代一遍是很低效的。最好是只在位置变化时才更新剔除器中的集合。

Wikipedia 页面中也谈到 system 间的通讯问题。某些对象状态改变并不频繁,所以处理需要利用观察者模式来被动触发:

The normal way to send data between systems is to store the data in components. For example, the position of an object can be updated regularly. This position is then used by other systems.

If there are a lot of different infrequent events, a lot of flags will be needed in one or more components. Systems will then have to monitor these flags every iteration, which can become inefficient. A solution could be to use the ovserver pattern. All systems that depend on an event subscribe to it. The action from the event will thus only be executed once, when it happens, and no polling is needed.

我自己在实现的时候给 ECS 框架增加这么一个设施:你可以让一个 System 关注一类 Component 的变化事件。只有这类 Component 变化后,System 才运行 —— 而普通 System 是每帧都运行的。而 Component 的新建和删除都会触发这种变更事件,我还给框架增加了一个方法,可以主动设置一个 Component 变更。同一个 Component 的变更事件在同一帧内只会触发一次。

btw, 如果你有留意 Overwatch Gameplay Architecture and Netcode 演讲,大约在第 4 分钟的时候,他展示了一张系统的结构图,其中 System 有两个方法,一个是 Update ,第二个叫 NotifyComponent ,参数是一个 Component 指针。演讲中并未谈及这个 NotifyComponent 是做什么用的,但我猜想就是做的类似工作。

在我的(基于 Lua 的)实现中,System 每帧都会收到一个变更集合,而不是每个 Component 调用一次 System 的对应函数。这是因为 Lua 中维护集合相对廉价,而函数调用相对昂贵。

这个集合每帧更新。一旦有新建 Component ,或是别的 System 主动触发变更消息,都会添加。一开始,我打算在最后将同帧删除了的 Entity 以及从 entity 中移除了 Component 的部分从集合中去掉,保证 System 遍历集合中的 entity 都是有效的。

后来发现,这种做其实是多余的。因为 System 不仅要关心 component 的变化,更要关心 Component 的消失。比如对于空间管理器来说,一个对象从空间中移除也是重要事件。好在 Entity 我们都用唯一 Id 来引用,即使删除,id 也永不复用。如果只需要在 Entity 删除时也把 id 记在这个集合里,System 自己迭代时,发现一个 Entity id 已经无效了,就说明触发了删除事件。这比单独再设计一个删除事件要简洁的多。

总结:

当 System 需要迭代一组 Entity 对他们中的 Component 做特定操作时,这个集合可以从 EntityAdmin 中用 Component 类别做筛选,也可以从 EntityAdmin 获取一个单件,由单件维护这样的集合。

一个单件中的 Entity 集合由特定的 System 来维护,这个 System 可以订阅指定的 Component 的变更事件。

变更事件包含了 Component 的创建、移除和状态变化,创建和移除事件会随着 Entity 的构建和移除自动产生,状态变化由专有 API 产生;同一帧内,一个 Component 最多只会产生一个变更事件。事件并不区分类别(创建、移除等),由 System 在迭代时自行检查 Entity id 的有效性来判别。

December 03, 2017

Lua 下的 ECS 框架

前段时间,我写了一篇 浅谈《守望先锋》中的 ECS 构架 。最近想试试在 Lua 中实现一个简单的 ECS 框架,又仔细琢磨了一下。

我思考后的结论是:ECS 并不是一个新概念,它的提出其实是和语言相关的。ECS 概念的诞生起于游戏行业,相关框架基本都是基于 C++ 来开发的。它其实是对 C++ 对象模型的一个反思。ECS 针对组件组合对象,而反对 C++ 固有的基于继承的对象模型。对象模型才是 ECS 的设计核心理念。而离开 C++ 的对象模型,ECS 并不是什么新鲜的东西。

我的这个观点也不新鲜,在 ECS 的 Wikipedia 页上也有类似的说法:

In the original talk at GDC Scott Bilas compares C++ object system and his new Custom component system. This is consistent with a traditional use of this term in general Systems engineering with Common Lisp Object System and Type system as examples. Therefore, the ideas of "Systems" as a first-class element is a personal opinion essay. Overall, ECS is a mixed personal reflection of orthogonal well-established ideas in general Computer science and Programming language theory. For example, components can be seen as a mixin idiom in various programming languages. Alternatively, components are just a small case under the general Delegation (object-oriented programming) approach and Meta-object protocol. I.e. any complete component object system can be expressed with templates and empathy model within The Orlando Treaty vision of Object-oriented programming,

抛开理论不谈,如果要在 Lua 中实践,我们到底可以做点什么呢?

我认为需要有这几个方面:

首先应该对 Lua 加强类型系统。Lua 的动态性天然支持把不同的组件聚合在一起,我们把不同的 Component 放在一张表里组合成 Entity 就足够了。但如果 Component 分的很细的话,用很多的表组合成一个 Entity 对象的额外开销不小。不像 C++ ,结构体聚合的额外开销几乎为零。我们完全可以把不同 Component 的数据直接平坦放在一个 table 中,只要键值不冲突即可。但是我们需要额外的类型信息方便运行时从 Entity 中萃取出 Component 来。另外,如果是 C / Lua 混合设计的话,某些 Component 还应该可以是 userdata 。

从节省空间及方便遍历的角度讲,我们甚至可以把同类的 C Component 聚合在一大块内存中,然后在 Entity 的 table 中只保留一个 lightuserdata 即可。ECS 的 System 最重要的操作就是遍历处理同类 Component ,这样天然就可以分为 C System 和 Lua System 。数据的内聚性很高,可以直接区分开 C data 和 Lua Data 。

然后、就是方便的遍历。ECS 的 System 需要做的就是筛选出它关心的 Entity ,针对其中的 Component 做操作。如果需要筛选结果大大少于全体 Entity 数量,遍历逐个判断就会效率很低。好在在 Lua 中,我们可以非常容易地做出 cache ,只需要遍历筛选一次,在监控新的 Component 的诞生就可以方便的维护遍历用的集合了。


我写了一个初步的版本。打算等到实际使用起来再慢慢完善。

它可以实现成一个纯 Lua 版,但我特地尝试把里面的两个函数编写了 C 的等价版,看起来可以提高不少性能。

这里的 API 中, Entity 全部使用唯一数字 id 标识,而不主张直接引用 entity 的 table 。这也是一般 ECS 框架的通用做法。数字 id 可以提高健壮性,还可以避免对已经销毁的 Entity 错误的引用。如果需要 C / Lua 混合编程的话,在 C 中引用 id 也方便的多。

类型系统是这样设计的:

每个 Component 有一个 16bit 的唯一类型 id ,每个 Entity 是由若干 Component 组合而成,我将它们的类型 id 升序排列成一个字符串,作为整个 Entity 的动态类型。然后 Lua 中实现了一个 cache ,可以从这个类型字符串转换成易用的类型对象。类型对象用来对 Entity 做筛选,从里面分离出 Component 。这个类型字符串的拼接我实现的是一个 C 版本,虽然 Lua 也能实现的出来,但是效率会低很多。

大部分 Component 我主张直接平坦的放在 Entity 对象表中,但若需要用 C 结构来承载,或单独用一个子表,也提供了 Component 类型注册方法,可以在 new component 时定义一个专门的构造函数(以及 delete 时的析构函数)。

这里还提供了遍历包含特定 Component 的 Entity 集合 的迭代器。它由一个弱表实现的 cache 来管理。在第一次遍历时,会创建一个集合,收集 Entity 全体集合中符合要求的部分,把筛选出来的 id 记录下来。一旦遍历集合创建好,它还会跟踪新的 Component 的创建,自动加进来。

这里的迭代器,我同时实现了 Lua 版本和 C 版本。C 版本的性能会高一些,我认为这个 C 版本在遍历相关集合时,性能表现不会差于用 C/C++ 实现的原生容器。


以上是对 Entity 和 Component 的支持。System 相关的方法,我还没有想好可以做点什么。等用到了再完善。