« 程序员修炼之道第二版译者跋 | 返回首页 | ECS 中的概念缺失 »

ECS 中的消息发布订阅机制

我们在实践 ECS 框架时发现,之所以 ECS 的概念诞生于游戏领域,是因为游戏程序往往都在周期性的处理一批对象,进行运算,根据上个周期的状态得到下个周期的状态。而传统人机交互的应用则是响应型的:即一个外部请求触发一系列的业务运作。

如果你把游戏业务塞到响应型框架中,就会发现,不得不用时间去触发,业务响应的是 timer 。但这种情况下,timer 几乎没有携带任何状态,对单个 timer 的响应,是不可能做成无状态的:它本身就是整个游戏世界对上个状态的迭代。

这种情况下,响应式框架就很低效。

但是,如果框架完全做周期性自迭代,对外部输入事件的处理又远不如响应式框架灵活。

如果只是简单的操作输入还好,比如手柄,我们可以每帧把手柄各个按键的状态置入世界,那么 System 在不断迭代时,直接把这些状态当作世界中某个单例的状态就好了。但更复杂的输入就没那么好做了。

我们在一开始实践 ECS 框架时,很想保持整个模式的纯粹性,刻意回避了传统响应式框架里的东西,仅仅只添加了一个外部事件输入的消息队列。对于框架内部产生的事件,如组件的出生、销毁;内部对象的状态机状态切换引发的次生效应;物理系统抛出的事件,等等,都转换为状态的变化。由对应的 System 每帧去重复处理这些状态。

最近我觉得,刻意的在 ECS 框架中去回避一个事件系统是不对的。游戏业务本身也是一个混合体:混合了周期性的世界状态迭代模式和响应式业务处理模式。

所以我下决心给 ECS 框架增加一个完备的消息发布订阅模块。

由于我们的框架是用 Lua 编写的,所以这样一个模块可以做的远比 C/C++ 的类似框架更灵活。我们的每条消息都是一个 key/value 元组,用 lua table 承载,例如:{ type = "new" , eid = 42 } 就是一条消息,表示一个 id 为 42 的 entity 创建出来了。而鼠标消息则可能是 { type = "mouse", action = "move", x = 100, y = 200 } 。

所有的消息都通过 world:pub(message) 来发布出去。

而任何 System 都可以通过 mailbox = world:sub(pattern) 来订阅满足一类 pattern 的消息。这个 pattern 也是一个 key/value 元组,比如 { type = "new" } 表示关注所有的 new 类型的消息;{ type = "mouse" } 可以跟住所有鼠标消息,{ type = "mouse", action = "move" } 则可以精确到鼠标的移动,{ eid = 42 } 可以关注到 42 号 entity 上发生的所有事情(通常用于 log)。

任何 system 都可以通过 for msg in mailbox:each() do 来枚举信箱里所有的消息,并清空信箱。


看看背后的实现:

时间复杂度最高的部分在于 pub 消息的时候,目前的实现中,pub 的那一刻就已经把消息分发到了所有之前 sub 过的 mailbox 中了,通常会有 n 个 mailbox 关心这条消息。每个 mailbox 就是一个队列,所以迭代反而很简单。

我们的消息匹配(message matching)很灵活,规则却很简单:pattern 中的每一个 key/value 就是一个过滤条件,只有消息满足所有的条件,才会被投递到对应的 mailbox 中。如果不加优化,pub 的时间复杂度是 O(n*m) 的,n 是消息的长度,m 是系统中的 mailbox 数量。

但优化也比较容易,在 sub 时,建立索引 cache ,用空间换时间即可。

例如:在一次 sub 的 pattern 中,出现了一条 type = "new" 的条件,那么就建立一个 type:new 的索引表,把所有满足这个条件的 mailbox 都放在一个集合(候选集)中;同时不满足这个条件的 mailbox 也放入一个集合(排除集)。

其中,满足条件指明确写了 type = "new" 这个条件的 pattern 或是 pattern 中没有 type 这个 key 。不满足条件指,pattern 中有 type 这个 key 但 value 不是 "new" 。

这样,pub 一条消息时,根据消息中的一项,就能 O(1) 快速判断,这个条件能排除哪些 mailbox ,以及哪些 mailbox 是潜在的候选者。遍历完消息后,依然留在候选者名单中的 mailbox 就是筛选出来的。因为每次处理一个条件,最终候选集都会减小。为了减少比较次数,还可以对消息中所有条件对应的候选集的大小排序,先过滤候选集较小的那个条件,

这样,这个过程虽然还是 O(n * m) ,但 m 是最短候选集的长度而不是所有 mailbox 的个数,大多数条件对应的 m 为 0 (没有人关心)。

如果实际使用的时候,筛选条件五花八门,可能导致 cache 索引集占内存过多,我认为可以用元表机制做一些合并,或是标注一些条件不生成 cache ,而是退化成遍历的方式检查。

另外,对于常用的条件组合,还可以生成联合索引 cache 。当然,这些都是以后可以优化的地方。

Comments

事件处理不是自动的,是需要处理的 system 自己去拉的。所以何时被处理,取决于你什么时候去拉。这里的消息系统仅仅负责把消息投递到队列中而已。

所以是否有 off-by-one-frame ,也看你是否能以正确的次序拉取消息并处理它们。

btw, 我们做这些,一个主要动机就是之前的设计出现了 off-by-one-frame 。

云风大大您好,读到您的文章我获益匪浅,对于事件系统还想请教几个问题:
1. ecs 里 pub 一个事件后是在什么时间点执行订阅者的逻辑呢?
1.1 如果立即执行是否会出现一帧内不同 System 面对的状态不一样,会需要维护 update 先后顺序?
1.2 如果不立即执行是否会造成 off-by-one-frame-bugs 或其他影响?这方面的处理有什么经验可以指导的吗?

如果依据ECS的定义和使用场景,订阅发布肯定要这么做,点赞

这个用法不是太能懂,事件订阅系统和消息队列这种用法的区别是啥啊?事件是立即执行的么?

高论,赞一个

Post a comment

非这个主题相关的留言请到:留言本