"工厂"流水线执行模型的设计

前言

最近心血来潮，想试试从零写一个工厂游戏，其中最难的部分莫过于执行模型的设计，也就是怎么让上一Tick的结果在下一Tick中生效，从而让机器之间的资源流动起来。

你感兴趣的话，可以点下方的Tile玩玩，核心玩法就是混合任意两个物品随机得到一个新的物品，同类混合也是支持的，因为这样这个游戏的玩法也是失败的。

UI是由AI编写的，但这不是重点，主要是希望能够编写一下背后的执行逻辑，对我来说有无UI不太重要。

至于我说玩法失败，那么是因为我发现了一种极其简便的通关游戏的方法，也就是一个生成器，再加上一个连接了输出到指向自身的传送带的混合器，这样你就可以利用基础资源和基础 资源的子代，来合成数值膨胀的物品。

你需要知道的概念

在工厂游戏中，我认为如果需要支撑这个玩法，那么就需要最基本的三类机器:

1. 资源生成(Generator) - 例如：仓库出站、矿机…
2. 资源加工(Processor) - 例如：仓库入站、粉碎机、合成器…
3. 资源运输(Belt) - 例如：传送带、溢流门、分配器…

在这篇文章中，我们会把它们简称为 G, P, B，为了更加立体的表示他们的方向，下面会用 Up, Down, Left, Right 的缩写来指示，也就是M(U/D/L/R)。

所有的机器都具有槽位，槽位分为两类: 输入槽位和输出槽位，输入槽位(in)用于接收资源，输出槽(out)位用于输出资源。

这三类机器可能是这样的:

pub struct Item;
pub type Slot = Option<Item>;

pub struct Generator {
    pub out: Slot,
}

pub struct Processor {
    pub in0: Slot,
    // pub in1: Slot,
    // ...
    pub out: Slot,
}

pub struct Belt {
    pub in0: Slot,
    pub out: Slot,
}

一个独立的，由数个机器连接在一起的整体，我称之为”网络”。

为了能够宽泛地表示这类不同的节点，我们可以定义一个枚举，同时使用另一个 struct 来表示它们的方向:

pub enum NodeObject {
    Generator(Generator),
    Processor(Processor),
    Belt(Belt),
}

pub enum Direction {
    Up,
    Down,
    Left,
    Right,
}

pub struct Node {
    pub object: NodeObject,
    pub direction: Direction,
}

pub struct Pos {
    pub x: usize,
    pub y: usize,
}

原型

现在有了三类机器了，下一步就是把网络表示出来。

试想一下原型，也就是最简单的网络: G(R)B(R)P(R) (G->B->P)

很显然，这是一张有向图。对于当前的原型，我们进一步限制网络只有一个没有入边的根节点 G，并且资源只能沿箭头方向流动，因此我们暂时把它视作一个单源有向无环图。

既然能够被认作有向图，我们只需要按顺序从根节点G开始，依次访问它的子节点B和P，就可以把整个网络遍历一遍，同时处理完他们的输入输出。

那么代码会是这样的(我们暂且忽略大多数情况，包括越界检查、不重要的代码细节和潜在的性能问题，并且以一种直观的数据结构来表示):

// 我们可以认为一张图中存放了多个网络，且在此图中，网络之间是没有连接的
pub struct Graph(Map<Pos, Node>);

impl Graph {
    // 因为网络之间没有连接，所以我们可以根据根节点的特性来发现所有网络
    // 在一般情况下：根节点的特征是它没有入边，并且没有输入
    // 不一般的情况指可能存在的非法的连接（例如 B->G->...），当然，我们需要实现剔除这类多余节点
    pub fn networks<'a>(&'a mut self) -> Vec<Network<'a>>;
}


pub struct Network<'a> {
    // nodes[0] 是根节点 G
    pub nodes: Vec<&'a mut Node>,
    // 某个 index 可能会连接多个节点，考虑分配器，溢流器等情况。
    // 在单源网络中，(Direction, usize) 只是为了指示特殊节点的流向方向，
    // 虽然在示例并没有体现出来，实际上只需要告知 push 有何处可推送即可。 
    pub edges: Map<usize, Vec<(Direction, usize)>>,
}

impl NodeObject {
    // set in0 / in1 / ...
    fn push(&mut self, item: Item);
    // consume in0 / in1 / ... and produce out
    fn work(&mut self);
    // in0 / in1 / ... empty?
    fn can_push(&self) -> bool;
    // take out
    fn take(&self) -> Option<Item>;
}

fn try_take_and_push_item(from: &mut NodeObject, to: &mut NodeObject) -> bool {
    if to.can_push() && let Some(item) = from.take() {
        to.push(item);
        true
    } else {
        false
    }
}


impl<'a> Network<'a> {
    pub fn next(&self, index: usize, node_direction: Direction) -> Option<usize>;

    pub fn tick(&mut self) {
        for (index, node) in self.nodes.iter_mut().enumerate() {
            // 如果是溢流器，分配器，这里需要 match node 并且读取内部状态来决定下一步的方向
            // 这里我们暂且忽略这些复杂的情况，假设每个节点只有一个输出方向
            let maybenext = self.next(index, node.direction);
            // 如果成功推送了物品，那么就执行 work
            if let Some(next) = maybenext && try_take_and_push_item(node.object, self.nodes[next].object) {
                // 对于传送带，work 把输入的物品移动到输出槽位，在下一个 tick 中，传送带的输出槽位会被下一个节点读取
                // 这样就不会产生级联现象
                node.object.work();
            }
        }
    }
}

一个代码执行的时序表，帮助你来理解：

以上就是一个最简单的单源网络。在当前模型中，我们从唯一的根节点开始遍历网络，并通过 take → push → work 推动资源沿着网络逐 Tick 向下游传播。

多源网络

与单源网络相对，多源网络是指有多个没有入边的根节点 G，资源可以从多个源头流入网络，因此，你需要考虑更多的问题。

问题是怎么产生的？

第一个问题是，这种网络的执行模型会变得非常复杂，图中会出现大量的汇合点(或者说”交叉”)，导致资源出现竞争。 想象一下，三叉路口向同一个槽位输入，这个槽位应该接受谁的资源呢？如果你不加限制，那么就会出现资源丢失或是饥饿的问题。

第二个问题是，从谁开始执行？如果像是单源网络那样，我们可能会有大量的节点会被执行无数次，因此会产生大量的操作回滚，最终导致性能问题。

贪心预约

MAtlas 采用了贪心预约的方法，感兴趣可以前往 repo 查阅。

*此部分由Agent代笔，已审阅

要解决”从谁开始执行”，我想到的第一种办法是把一个 tick 拆成两步: 先算，后送。

第一步，让所有节点各自 work() 一次，产物停在各自的输出槽位。因为这一步只生产、不传递，物品不可能在一 tick 内被连续传递两次，级联和回滚也自然消失了。

第二步，才沿着 edges 送。我们按一个固定顺序(按位置从上到下、从左到右)遍历节点，每个节点把自己的产物交给候选方向里第一个还能接收的下游:

impl<'a> Network<'a> {
    pub fn tick(&mut self) {
        // 1. 先算: 所有节点独立生产，产物停在输出槽位
        for node in self.nodes.iter_mut() {
            node.object.work();
        }

        // 2. 后送: 按固定顺序，逐个把输出交给第一个还能接收的下游
        for from in 0..self.nodes.len() {
            let Some((_, to)) = self.route(from) else {
                continue;
            };
            if let Some(item) = self.nodes[from].object.take() {
                self.nodes[to].object.push(item);
            }
        }
    }

    // 在候选边里挑第一个还能接收物品的下游
    fn route(&self, from: usize) -> Option<(Direction, usize)> {
        self.edges
            .get(&from)?
            .iter()
            .copied()
            .find(|(_, to)| self.nodes[*to].object.can_push())
    }
}

这里的”预约”其实不需要额外的表: 下游自己的输入槽位就是那张表。谁先被送到，谁就把槽位占住；等后面的产物再来问 can_push，得到的只会是 false。又因为每一步都是先问 can_push、再 take 和 push，送不出去时产物还留在发起者手里，连退回都省了。

开销上也很划算: 遍历两遍节点，每条边最多被访问一次，整体是 O(V+E)。

不过，贪心预约有一个绕不开的软肋: 公平性完全由遍历顺序决定。

试想这样一张图:

G0(R)B1(R)G1(L)
     G2(U)

B1 只有一个空槽位，而 G0、G1、G2 都想往里送。因为顺序是位置顺序，排在最前面的 G0 会先占住槽位，G1 和 G2 只能干看着:

如果 G0 在之后每一 tick 都持续产出，它就会一直排在前面、一直抢得到槽位，G1 和 G2 则永远挨饿。更麻烦的是，这个顺序只是纯粹的位置顺序，它和玩法里谁更”应该”被服务毫无关系。想让它公平一点，就只能反过来在各节点内部加状态，比如让分配器轮转输出方向、让溢流门交替溢出左右两侧——可这不又把本来要解决的局部冲突，原封不动地塞回节点里了吗？

意图驱动

为何需要处理麻烦的局部节点关系，而不把局部的冲突汇聚起来处理呢？

在我实现了贪心预约后，我想到了一种更加优雅的方法 - 意图驱动。

试想，A 把物品输出给 B 的输入时，可以产生一个 A → B 的迁移意图。意图的发起者是 A，而 B 则是这个意图的目标。 因为得知了这个意图，我们可以代为操作，决定是否要把 A 的物品推送给 B。

那么在 1tick 下，大部分的节点都会产生意图，我们把这些意图收集成按位置查询的表，接下来，执行器再对根据同一位置的节点规则对多个意图进行处理。

直观地表述那么请想象：

G0(R)B1(R)G1(L)
     G2(U)

此时，B1 的意图是 [取走 G0 的物品, 取走 G1 的物品, 取走 G2 的物品]，且B1有且仅有一个空槽位可以接收物品，因此只能选择其中一个。

*取走：在目标获得物品的同时，清理发起者的输出

这时候，我们可以根据方向给这三个节点排个序，假设是 G0 > G1 > G2，那么我们就可以选择 G0 的物品推送给 B1，并且抛弃 G1 和 G2 的意图， 最终，G0的物品被取走，而G1、G2则表现为了阻塞状态，如果需要公平轮转，那么我们只需给 B1 维护一个状态进而改变”取走”的对象，这样一来，竞争不再由“谁先执行”决定，而是交给发生竞争的节点自己决定。

意图驱动的代价也很低，只需要额外维护一张按位置查询的表和当前 Tick 的意图列表，整体复杂度仍然是 O(V+E)，同时你换来了更清晰，心智负担更小的解决方案。