货物和货车的匹配

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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