生产链算法详解

一个开源项目中 Endfield Calc 的核心计算算法，用于处理包含循环依赖的生产链。

整体流程

1
2
3
4
5
6
7
用户选择目标物品和产量
  → ① buildBipartiteGraph（构建二部图）
  → ② detectSCCs（Tarjan 算法识别循环）
  → ③ buildCondensedDAGAndSort（压缩 + 拓扑排序）
  → ④ calculateFlows + solveSCCFlow（流量计算）
  → ⑤ buildProductionGraph（组装结果）
  → 生产表格 / 可视化树

如果计算失败（出现无解的循环），backtrackRecipeChoices 会回溯尝试其他配方组合，最多迭代 100 次。

第一步：构建二部图（buildBipartiteGraph）

原理

将生产链建模为二部图：物品和配方作为两类节点，边表示"消费"和"产出"关系。

1
物品 ──消费──→ 配方 ──产出──→ 物品

从用户选择的目标物品出发，递归向上游遍历所有依赖，直到遇到原材料（如 源矿、清水）停止。

配方选择启发式（selectRecipe）

当一个物品有多个可选配方时，按优先级选择：

  1. 单产出优先 — 没有副产物的配方
  2. 不产生循环 — 配方输入的物品不在当前遍历路径中
  3. 多产出选非循环
  4. 默认第一个

终末地实例

简单线性链：目标选 铁制零件，产量 6/min

1
2
3
4
5
铁制零件 (目标, 6/min)
  └── [配方: 蓝铁块→铁制零件] (组装台, 2s)
        └── 蓝铁块 ×1
              └── [配方: 蓝铁矿→蓝铁块] (熔炉, 2s)
                    └── 蓝铁矿 (原材料)

这条链是线性的，没有循环。

多配方选择：蓝铁块 有两种获取方式

配方 输入 输出 设施
蓝铁矿→蓝铁块 蓝铁矿 ×1 蓝铁块 ×1 熔炉
蓝铁粉末→蓝铁块 蓝铁粉末 ×1 蓝铁块 ×1 熔炉

启发式会优先选 蓝铁矿→蓝铁块，因为 蓝铁矿 是原材料（不会引入新的依赖循环）。

第二步：SCC 检测（detectSCCs）

原理

当多个物品之间存在相互依赖时，形成强连通分量（SCC），即生产闭环。

使用 Tarjan 算法在一次 DFS 遍历中找出所有 SCC。

终末地实例

循环生产：蓝铁粉末 ↔ 蓝铁块

游戏中存在以下两条配方：

配方 输入 输出 设施
蓝铁粉末→蓝铁块 蓝铁粉末 ×1 蓝铁块 ×1 熔炉
蓝铁块→蓝铁粉末 蓝铁块 ×1 蓝铁粉末 ×1 研磨机

如果用户强制选择这两个配方，就会形成循环：

1
2
蓝铁粉末 ──消费──→ 熔炉 ──产出──→ 蓝铁块
蓝铁块 ──消费──→ 研磨机 ──产出──→ 蓝铁粉末

这是一个大小为 4 的 SCC（2 个物品 + 2 个配方）。如果没有任何外部需求，净产出为零，属于无效循环。

第三步：拓扑排序（buildCondensedDAGAndSort）

原理

将每个 SCC 压缩为超级节点，剩余非循环节点保持原样，得到的图是无环的 DAG，可以拓扑排序。

使用 Kahn 算法（入度法）确定计算顺序：从最终产品到原材料。

终末地实例

假设目标为 铁制零件，且选择了包含蓝铁粉末↔蓝铁块循环的配方：

1
2
3
4
5
6
拓扑顺序（逆序遍历）：

1. [SCC: 蓝铁粉末↔蓝铁块]  ← 循环，需要解方程组
2. 蓝铁矿              ← 原材料
3. 蓝铁块→铁制零件       ← 普通配方
4. 铁制零件            ← 目标

第四步：流量计算（calculateFlows + solveSCCFlow）

逆拓扑序遍历每个节点，计算设施数量和物品产量。

情况 A：普通配方（非 SCC）

直接计算：

1
设施数量 = max(各输出物品的需求 / 单设施产出速率)

然后向上游传播输入需求。

终末地实例

目标：铁制零件 6/min

  1. 配方：蓝铁块→铁制零件（组装台，2s）

    • 单设施产出 = 60s / 2s × 1 = 3/min
    • 需要设施 = 6 / 3 = 2 台组装台
    • 向上游传播：蓝铁块需求 = 6/min

  2. 配方：蓝铁矿→蓝铁块（熔炉，2s）

    • 单设施产出 = 3/min
    • 需要设施 = 2 台熔炉
    • 向上游传播：蓝铁矿需求 = 6/min

  3. 蓝铁矿是原材料，计算结束。

情况 B：SCC（循环生产）

循环内的配方相互依赖，需要建立线性方程组同时求解（solveSCCFlow）。

数学模型

对于 SCC 内的 n 个物品和 m 个配方：

1
2
3
4
5
6
7
物品平衡方程：总产出 - 总消耗 = 外部需求

矩阵形式：A × x = d

x[j] = 配方 j 的设施数（待求解）
A[i][j] = 配方 j 对物品 i 的净产出速率
d[i] = 物品 i 的外部需求

求解器：solveLinearSystem（高斯消元法）

终末地实例

蓝铁粉末↔蓝铁块循环，假设外部要求每分钟产出 6 个蓝铁块：

1
2
3
4
5
6
7
8
9
配方：
  R1 (熔炉): 蓝铁粉末 → 蓝铁块 (3/min)
  R2 (研磨机): 蓝铁块 → 蓝铁粉末 (3/min)

方程：
  蓝铁粉末: -3×R1 + 3×R2 = 0
  蓝铁块: +3×R1 - 3×R2 = 6

结果：方程矛盾（行列式为零），无解

算法标记为无效循环，触发 backtrackRecipeChoices：尝试 蓝铁矿→蓝铁块，跳出循环。

第五步：结果组装（buildProductionGraph）

将计算结果组装成 ProductionDependencyGraph：

数据 说明
nodes 所有物品节点（产量、是否原材料）和配方节点（设施数）
edges 消费边、产出边
detectedCycles 有效循环（SCC），用于 UI 高亮
invalidCycles 无效循环警告

特殊情况处理

用户配方覆盖导致无解

用户强制选择配方后可能形成零净产出闭环。

处理方式（tryExtendSCCWithFeeders）：

  • 引入供给配方（如 蓝铁矿→蓝铁块）加入系统
  • 打破循环，让方程有解
  • 如果仍无解，标记为无效循环

配方回溯（backtrackRecipeChoices）

发现无效 SCC 时，遍历有可选配方的物品，尝试下一个配方组合重新计算。

副产物处理

多产出配方的副产物不主动遍历，标记为"已产出"，等被消费时再展开。

数据结构概览

类型 作用
BipartiteGraph 二部图：物品-配方连接关系
SCCInfo 强连通分量（循环）信息
FlowData 物品需求、配方设施数
ProductionDependencyGraph 最终输出（节点、边、循环）

详见 src/types/production.ts。