OpenTTD 货运分配链路图（Link Graph）机制与性能调优指南

• 游戏开发

本文以 docs/linkgraph.md 为主线，结合 OpenTTD 源码中src/linkgraph/目录下的调度器、MCF 求解器与设置定义，系统讲解货运分配（Cargo Distribution）背后的链路图重算线程、多商品流（MCF）算法复杂度，以及recalc_interval、recalc_time、accuracy等配置项如何影响游戏性能与卡顿体验，帮助玩家与开发者在大地图、慢速 CPU 环境下合理调参，理解链路图调度内部原理。

一、链路图（Link Graph）是什么

链路图是 OpenTTD 货运分配（Cargo Distribution）功能的核心数据结构。当你在游戏设置中为旅客、邮件、装甲货物或默认货物启用"对称 / 不对称 / 手动"等分布模式时，游戏会把地图上的站点视为节点，把可通行的运输线路视为边，构建出一张描述"货物供需与运力关系"的图，并在后台周期性重算这张图上的货物流向。

src/linkgraph/目录集中了该功能的全部实现，包括：

• src/linkgraph/linkgraph.h 与 src/linkgraph/linkgraph_base.h：链路图节点/边的数据结构与基本操作；
• src/linkgraph/linkgraphschedule.cpp 与 src/linkgraph/linkgraphschedule.h：调度器，负责排队、启动线程与回收线程；
• src/linkgraph/mcf.cpp 与 src/linkgraph/mcf.h：多商品流（Multi-Commodity Flow）求解器；
• src/linkgraph/demands.cpp：货物需求估算；
• src/linkgraph/flowmapper.cpp：把计算结果写回边注释，供车辆路径选择使用。

从源码结构看，每一次"重算"并非全图一次性完成，而是按连通分量拆分成若干LinkGraphJob，由调度器逐个排队执行（Queue/SpawnNext，见 src/linkgraph/linkgraphschedule.h）。

二、重算线程的生命周期：从 Spawn 到 Join

2.1 每 X 天一个周期

链路图的重算按游戏内的"经济日历日"驱动。LinkGraphSchedule定义了一个静态常量：

static const uint SPAWN_JOIN_TICK = 21; ///< Tick when jobs are spawned or joined every day.

见 src/linkgraph/linkgraphschedule.h。调度逻辑在OnTick_LinkGraph()（src/linkgraph/linkgraphschedule.cpp）中实现：每天的固定 tick，调度器会检查

TimerGameEconomy::date.base() % (_settings_game.linkgraph.recalc_interval / EconomyTime::SECONDS_PER_DAY)

• 余数为0：调用SpawnNext()为队首的链路图启动一个新的重算任务（Job）；
• 余数为recalc_interval / SECONDS_PER_DAY / 2：调用JoinNext()回收"已经到期"的任务线程，并把结果并入游戏状态。

2.2 InitializeLinkGraphs：开局即回收线程

原文档首先强调了一个容易被忽视的事实：

InitializeLinkGraphsjoins all threads, so if the game is abandoned with some threads still running, they're joined as soon as the next game (possibly the title game) is started.

即在开始新一局游戏（甚至只是回到标题画面）时，游戏会调用清理逻辑把所有仍在运行的链路图线程强制回收（join）。对应源码是LinkGraphSchedule::Clear()（src/linkgraph/linkgraphschedule.cpp），它对running列表中每个 Job 先调用AbortJob()再清空队列。配合InitializeGame()（src/misc.cpp）在开新局时的整体初始化流程，任何上一局遗留的线程都会在此被汇合，避免线程泄漏或与新游戏的数据相互干扰。

2.3 线程不可用时同步执行

LinkGraphJob::SpawnThread()（src/linkgraph/linkgraphjob.cpp）的逻辑是：先尝试StartNewThread(&this->thread, "ottd:linkgraph", ...)启动一个名为ottd:linkgraph的后台线程；如果平台不支持线程、启动失败，则在当前线程（主线程）里同步执行整个 Job——这正是原文档所说"没有线程的平台上游戏会卡住"的代码级原因。同步执行期间主线程被 MCF 计算占据，无法响应其他游戏逻辑。

三、MCF 算法：为什么它可能吃掉大量 CPU

3.1 指数级复杂度的来源

原文档明确指出：

The MCF (multi-commodity flow) algorithm can be quite CPU-hungry as it's NP-hard and takes exponential time (though with a very small constant factor) in the number of nodes.

多商品流问题本身是 NP-hard 的。OpenTTD 的求解器在 src/linkgraph/mcf.h 中声明了基类MultiCommodityFlow与两趟递进式的实现：

• MCF1stPass：第一趟先饱和最短路径，按需创建新路径并消除环（cycle）。mcf.h的注释明确说明"该计算在节点数量上呈指数复杂度，但常数因子足够小，对大多数真实链路图分量可用"；
• MCF2ndPass：第二趟优先饱和剩余容量最大的路径，且不会沿第一趟未访问过的边新建路径，因此无需再做环检测与消除——环消除是第一趟最耗时的部分，这使得第二趟更廉价（见 src/linkgraph/mcf.h）。

这意味着：一张链路图包含的节点（站点）越多、连通分量越复杂，单次重算耗时按指数级增长。原文档据此给出两条实用结论：

1. 大尺寸地图 + 复杂链路图 → 建议调高重算时间设置以避免卡顿；
2. 慢 CPU 系统同理。

3.2 调度器的 6 步处理管线

每个 Job 在后台线程里由 6 个无状态处理器按序执行（LinkGraphSchedule构造函数，src/linkgraph/linkgraphschedule.cpp）：

ComponentHandler接口的注释（src/linkgraph/linkgraphschedule.h）特别强调：处理器不得读写 Job 之外的任何数据，否则会造成多人游戏 desync。LinkGraphSchedule::Run()会在每个处理器之间检查job->IsJobAborted()，一旦被中止立即返回。

四、重算时间设置：给每个 Job 的"限时"

4.1 配置项定义

链路图相关设置全部集中定义在 src/table/settings/linkgraph_settings.ini，并在 src/settings_table.cpp 注册为_linkgraph_settings设置表。其中与本主题最直接相关的两个参数：

原文档的解释是："重算时间为 X 天"意味着每个链路图 Job 在被 join 之前有 X 天时间运行。换算成源码视角，recalc_interval以秒为单位存储，调度器在OnTick_LinkGraph()中按recalc_interval / EconomyTime::SECONDS_PER_DAY折算成天数取模使用（见 src/linkgraph/linkgraphschedule.cpp）。

4.2 高值的代价：流量统计更新滞后

原文档特别提醒了调高recalc_time的副作用：

The downside is that the flow stats won't be updated before the job is finished and thus a high value means less updates and longer times until changes in capacities are accounted for.

也就是说，在 Job 完成之前，流量统计（flow stats）不会更新。若把重算时间调得很大：

• 新开辟的线路、新增的运力、拆除的设施对货物流向的影响会被推迟反映；
• 玩家在链路图窗口（src/linkgraph/linkgraph_gui.cpp）中看到的统计长期不变，容易误判线路盈亏。

因此在"大图/慢 CPU 需要防卡顿"与"统计及时性"之间存在权衡：recalc_time调得越高，重算越不容易超时，但流向更新越滞后。

4.3 超时与自动暂停保护

当 Job 到期仍未完成时，JoinNext()（src/linkgraph/linkgraphschedule.cpp）会删除 Job 对象并隐式 join 线程——若线程仍在计算，主线程就会在此阻塞，表现为游戏卡顿（原文档称之为 "the game will hang"）。

为防止这种阻塞被玩家感知，OpenTTD 还实现了两处保护：

• StateGameLoop_LinkGraphPauseControl()（src/linkgraph/linkgraphschedule.cpp）：在预计 join 前 2 个 tick（提前量是为多人游戏命令延迟预留的）检测到 Job 尚未完成时，向游戏发布PauseMode::LinkGraph暂停命令，主动暂停游戏等待计算完成，而不是让主循环硬卡；Job 就绪后自动解除暂停。该函数由主循环 src/openttd.cpp 在服务端/单机时每帧调用；
• AfterLoad_LinkGraphPauseControl()（src/linkgraph/linkgraphschedule.cpp）：载入存档时如果某个 Job 已到期仍未完成，立即置暂停位，由存档加载流程 src/saveload/linkgraph_sl.cpp 调用，避免读档后立刻卡死。

五、降低精度：另一种降低 CPU 消耗的手段

5.1 accuracy 的作用

原文档指出：

Another option to avoid excessive lags is to reduce the accuracy of link graph calculations. Generally the accuracy is inversely correlated to the CPU requirements of the MCF algorithm.

linkgraph.accuracy的默认值为 16，范围 2–64（src/table/settings/linkgraph_settings.ini）。它在两个环节影响计算量：

1. 需求估算：DemandHandler以accuracy作为距离缩放的分母——scaled_distance按(accuracy * scaled_distance * 16) / (base_distance * 2)折算 divisor，accuracy 越小 divisor 越小、单次纳入计算的供需越多；同时"给远处节点分配剩余供给"的兜底条件++chance > accuracy * num_demands * num_supplies也随 accuracy 缩小而更快触发（见 src/linkgraph/demands.cpp）。可见 accuracy 越低，每轮分配的流量越多、需要的迭代轮数越少；
2. MCF 两趟求解：MCF1stPass与MCF2ndPass都读取job.Settings().accuracy作为每次PushFlow的步长——accuracy 越小，单次推流越多，收敛越快（见 src/linkgraph/mcf.cpp、src/linkgraph/mcf.cpp）。

因此降低accuracy可以直接减少迭代轮数、缩短单 Job 运行时间，代价是流向计算结果更粗糙、分配精度下降。

5.2 相关配套参数

linkgraph_settings.ini中还定义了与精度/需求相关的其他参数，供完整调优参考：

5.3 配置入口

上述配置项以linkgraph.*前缀持久化在openttd.cfg中（linkgraph_settings.ini的注释明确说明其同时写入主配置文件、存档 PATS chunk 与每个运行中 Job 的链路图 chunk）。运行时可从游戏内"设置 → 高级设置（Advanced Settings）"中找到对应条目修改，也可在openttd.cfg的[linkgraph]段落直接编辑。由于设置属于GameSettings，修改后会写入存档，多人游戏需注意联机双方的设置一致性。

六、实战调优建议

综合原文档结论与源码机制，可给出如下调优路线：

1. 默认配置即可满足大多数场景：默认recalc_interval=8秒、recalc_time=32秒、accuracy=16，配合后台线程通常不会造成可感知卡顿；
2. 大地图 / 站点密集的复杂网络：优先把linkgraph.recalc_time从 32 逐步提高（例如 64、128），给每个 Job 更充裕的运行时间，减少到期 join 时的主线程阻塞；同时接受流量统计更新变慢的事实；
3. CPU 较弱的机器：在提高recalc_time的同时，把linkgraph.accuracy从 16 下调（例如 8、4），用精度换速度；也可适当调低short_path_saturation，让 MCF 第一趟更早结束；
4. 务必理解权衡关系：recalc_time越大，新建线路的容量变化被纳入统计越慢；accuracy越小，流向越粗糙。二者不可兼得，需按地图规模与机器性能平衡；
5. 观察信号：若游戏频繁出现PauseMode::LinkGraph自动暂停（表现为主机"未操作却自行暂停"），说明 Job 频繁超时，应进一步加大recalc_time或降低accuracy；若链路图窗口（src/linkgraph/linkgraph_gui.cpp）中流量统计长时间不动，则应考虑缩小recalc_time。

七、结语

链路图重算是 OpenTTD 货运分配功能中最具计算压力的子系统：它把 NP-hard 的多商品流问题放入后台线程，用"限时 + 到期 join"的调度策略在实时性与性能之间寻找平衡。理解InitializeLinkGraphs的线程回收、recalc_interval/recalc_time的调度节奏、以及accuracy与 MCF 迭代次数的反比关系，就能在超大存档或低配机器上有的放矢地调参。相关实现细节可进一步阅读 src/linkgraph/ 目录源码，以及设置定义 src/table/settings/linkgraph_settings.ini。

• 游戏开发