« August 2022 | Main | October 2022 »

September 30, 2022

货物和货车的匹配

我们在制作一款类似 Factorio 以自动化为主题的游戏。在游戏开发中遇到了不少算法上的问题,解决过程都非常有趣。比如之前就写过一篇 流体系统

和 Factorio 体验的最大不同在于,我们不使用传送带做主要物流手段,而是依靠公路网和货车。这种形式并不新,我在 20 多年前的凯撒3 (以及同系列的法老王、宙斯、龙之崛起等)中就玩到过。采用这种物流方式的游戏一直不曾间断,这几年我玩过放逐之城、缺氧、环世界、海狸浮生记也是这种。

这类游戏的共性是需要靠城市资源供养一批工人,然后这些工人干活来供养城市,其中一个重要的工作就是物流。一般受资源产能影响,不会养太多工人,不然很难产生正循环。所以物流所占工作比例并不大。大部分工人的工作(在生产建筑中)从事生产。

我们的游戏可能更贴近 Factorio 一些,不需要工人运作机器,物流更纯粹。供养货车的成本也不高,鼓励玩家尽可能多的增加货车,提高物流效率。和前面提到的系列游戏不同,我们的道路资源是有限的。车辆在道路上必须遵守交通规则,如果车辆太多会发生拥堵。所以限制物流效率的是道路而不是资源。

我想给玩家的体验是:物流的运作会遵循一定的规则,玩家可以大概感知到规则的存在,并通过不同的布局和调整提高整体的效率。玩起来不如传送带规则那么明确,也不会像一个黑箱那样,无法精细控制。

一开始我想设计成偏向铁路运输的逻辑,玩家自己规划路线,货车都严格跑在路线上,只接收路线沿途的上下货。后来觉得游玩体验和交互交互都不太好。最近便改成更智能的规则,不再限定路线,由 AI 自己决定车辆去哪里上货哪里下货。

这个物流系统调度的 AI 比较难做,我不希望它太愚蠢,以至于玩家边玩边骂;也不要太聪明,让游戏的物流部分不需要玩家的任何选择,变成一个无脑的放置游戏。

它的复杂度在于系统要协调三样东西:供给、需求、运力。

当供给大于需求时,车辆不应该跑去装载没有目的地的货物;当运力充沛时,空车也能被提前调配到最希望运力的区域;而运力不足时,最好不要让车总是集中在某一小块区域工作。

由于路网和供给需求方都是动态的(玩家可以边玩边拓展或删除路网),也会拆除新建和物流有关的建筑。所以车辆在运输途中,目的地也可能动态变化,甚至失去原本的目的地(或变得不可达)。这也增加了算法的复杂度。

前面提到了系列游戏的一种做法是把物流的工人绑定在特定建筑上,比如面包房的工人除了做面包也负责去采集原料;仓库的工人只负责本仓库的货物进出。这等于把供给需求运力这三要素中的运力部分绑定在特定建筑上了,不参与整体协调。算法会简单一些。

另一种做法是基于工人少而事情多为前提。由玩家为每个工人设定工作偏好和优先级,当有物流任务产生时,就按优先级去匹配工人。这样,运力这个要素也是被忽略的。

而我们游戏中,运力可以非常充足,也不希望让玩家具体关注到特定一辆车,做精细化控制。

所以一开始在设计调度算法时,同时考虑了三要素的相互匹配。从需求方去匹配供给方,然后锁定双方的货物以及接收栏位,然后再匹配车辆。当车辆发车后,锁定所有相关的资源,直到运单完成或是中途影响运输的状态被改变(例如路网被破坏,目的地不可达,或是供给接收方被拆除等),再回退状态。

整个流程比较复杂,写了几天都没写清楚。

后来想到,这里的复杂度是因为有三个维度的因素要考虑造成的。为了简化算法,我们需要首先简化这个系统。我们可以把物流系统拆分成两个独立的子系统:

其一,比较像京东那样的仓储系统。当有客户订货(需求方),这个系统用来合理的匹配仓库,决定哪个仓库向它供货。这个系统只负责下单:将货物 X 从 A 运输到 B 。而不应该考虑运输将怎样完成。

其二,比较像顺丰这样的快递系统。从前一个系统接单,合理调用手头的运力去完成运输单。

一旦状态变更,我们可以根据运输单在系统一的提交过程中,或是在系统二的运输中,以不同的方式撤销运单。这样每个单独系统实现起来都会简单很多。

另外,我们有另外一种运输单,就是让空车跑到停车场待命。这个是由玩家主动参与的。玩家可以在供给方比较密集的区域(例如矿区,就是只生产不需求的)设定空车车场。当系统二发现运力有盈余时,可以调配多余的空车提前去车厂待命。而这些车厂本身可以设定车位的过滤器,比如矿区的车场停靠的空车只能接收矿石运单,不受其它需求的运单调配。

September 07, 2022

多线程串行运行 Lua 虚拟机

ltask 是一个功能类似 skynet 的库。我主要将它用于客户端环境。由于比 skynet 后设计,所以我在它上面实验了许多新想法。

最近碰到一个需求:我们的游戏引擎中嵌入的第三方 C/C++ 模块以 callback 形式提供了若干接口。在把这些模块嵌入 ltask 的服务中运行时,这些 callback 函数是难以使用全部 ltask 的特性。比如,我们的 IO 操作全部在一个独立服务中,引擎读取文件时,很可能是通过网络异步远程加载数据的。这些第三方模块通常没有考虑异步 IO 操作,都是以同步 IO 方式给出一个读文件的 callback 函数让使用者填写。

那么,怎样才能在这个 C callback 中挂起当前任务,等待 IO 的异步完成呢?

初看是不可能做到的。框架没有设计成支持异步机制,我们难以从 C 函数中 yield ,挂起当前任务。这样,同一个服务就不可能在 callback 结束前相应外部消息,也就无法利用 ltask 的调度器完成异步 IO 工作。

Lua 虚拟机也并没有(也无必要)设计成多线程安全的,我们不能把这个 C 模块及其 Lua binding 的运行环境放在一个独立线程环境中。所以,callback 中阻塞调用 IO 请求,就意味着整个服务的阻塞。

一个比较简单的解决方法是给 IO 服务额外开通一个 channel ,不走 ltask 内部的消息。在 C callback 中,通过这个额外的 channel 和 IO 服务通讯。


但我仔细思考了这个问题,发现当 C callback 不返回时,未必整个服务必须跟着一起阻塞住。其实,只要 ltask 框架稍做一些支持,我们还是可以让服务继续工作的。

现在的任务调度模型是:由调度器分配一个工作线程运行一个服务的一小段任务(通常是用 lua resume 运行 lua vm 中的一个 coroutine 一个片段),在此期间,服务处于忙状态,别的工作线程无法拿到该服务。这就保证了单个服务不会重入。

当这一段任务执行完毕,而服务的消息队列为空时,调度器将服务设为闲置状态。等有新的消息投递到服务的消息队列后,闲置状态的服务会重新回到调度器中。

如果我们给服务一个新的状态:在 C 函数中挂起。那么,其实我们还是可以让服务重新进入调度器。从 ltask 的调度器视角来看,它冻结了一整个工作线程,但服务内的 Lua 虚拟机其实也处于停滞状态(因为停在了 C Side ),只要它不回到 Lua side ,这个 Lua 虚拟机依旧可以工作。调度器所作的工作只是把服务的忙状态取消即可。这样,其它工作线程就可以正常的调度它了。

但框架还需要多做一些工作。因为 Lua VM 的工作 coroutine 也处于忙状态,我们不能继续在这个 coroutine 在运行新的代码。所以在此时,应该在该 Lua VM 中创建出一个新的 coroutine 并取代服务的工作 coroutine 。然后让 C callback 等待到一个操作系统的条件变量上;直到业务层认为事情已经完成,需要回到一开始挂起的 C Callback 时,再将环境恢复,唤醒操作系统的条件变量,交还执行流。

在这个流程中,服务中的 Lua VM 从未处于并行状态,所以是安全的。但稍显怪异的是,Lua VM 的确工作在多线程环境下,由两个不同的操作系统线程在独立运行不同的 Lua coroutine 。这样,才保证了其中一个 Lua coroutine 可以一直保有自己的 C 调用栈。

这种运行 Lua VM 的方式,我称之为多线程串行运行。需要注意一些原本在 Lua 中成立的约束不成立了。比如,在单线程环境下,如果你运行一个 Lua 函数,该函数没有修改一个全局状态,函数也没有让出,那么可以认为这个全局状态是不会改变的;但现在,这个函数可能在 C side 挂起,而另一个操作系统线程可能从另外一个 lua coroutine 修改这个状态。

在我们的初步实践中发现,对应的 C/C++ 模块最好也能设计成多线程安全的。虽然在这个模型下,C 代码也没有并行的问题,但会多出很多重入问题。即,一个 C 函数运行了一半,有可能挂起,由另外一个系统线程再进入一次。一般非线程安全的 C 模块很可能在这方面考虑不周。(接口中有 callback 的框架更容易出现重入 bug )

我在 ltask 的 taskrun 分支实现了这个特性

September 02, 2022

路网中路径的储存

我们正在制作的游戏中,交通和物流是基于公路网的。公路网其实是以路口为顶点,路为边构成的(无向)图。因为我们有大量的车辆行驶在这个路网中,所以,我需要一个空间高效的方法储存这些车辆的路径。

在大部分情况下,我们的车辆都选择唯一的最短路径,也就是说如果从 A 路口到 B 路口存在一条制定好的路径的话,所有的车都会走这条路。基于这一点,我们可以对多条路径合并储存。

我选择用当前路口 id 和目的地路口 id 做 key ,把下一站路口 id 作为 value ,保存在一张 hash 表中。这样,先用 dijkstra 算法求出起点到终点的最短路线后,再把每一段路线用该结构保存下来即可。

当车辆到达某个路口,只需要用当前路口和它自己的目的地就可以索引到应该往哪个方向开。这个结构很适合保存在 Lua table 中,用元表触发尚未计算过的路径。而且这样一个路径表只是一个 cache ,随时可以清理重建。

如果路网已经稳定,那么还可以选择一个内存更紧凑的结构保存它们。

对于每个路口,连接的路是有限的。在我们的游戏中,其实只有十字路口( 4 叉)和 T 字路口( 3 叉)两种。我们可以对路口连接的路编号为 1-4 。我们用 4 个数组就能储存下所有的路径信息。

驶向同一编号出口的路径可以储存在一起。比如,如果从 42 号路口去向 100 号路口的车需要在 42 号路口的第 2 出口驶出,我们就把 (42,100) 记录在 2 号数组里。

每个数组都是有序的,这样可以用二分查找确定一段路径是否在该数组中。因为最复杂的路口只有四个出口,而车在我们的规则中,不准在路口调头,原路折返。所以在一个路口查询下一阶段的去向,最多只需要做两次二分查找就可以确定(在起点处做四次查询可以知道是否可达)。

当路网固定,不会动态增删时,这四个数组可以储存在一片连续内存中。它储存了在这个路网中,任意两个路口间的最短路径。

以上,我作了一个简单的实现