游戏开发【免费下载链接】OpenTTDOpenTTD is an open source simulation game based upon Transport Tycoon Deluxe项目地址https://gitcode.com/gh_mirrors/op/OpenTTD点击查看免费下载本文以 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 到 Join2.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, theyre 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 算法为什么它可能吃掉大量 CPU3.1 指数级复杂度的来源原文档明确指出The MCF (multi-commodity flow) algorithm can be quite CPU-hungry as its 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。这意味着一张链路图包含的节点站点越多、连通分量越复杂单次重算耗时按指数级增长。原文档据此给出两条实用结论大尺寸地图 复杂链路图 → 建议调高重算时间设置以避免卡顿慢 CPU 系统同理。3.2 调度器的 6 步处理管线每个 Job 在后台线程里由 6 个无状态处理器按序执行LinkGraphSchedule构造函数src/linkgraph/linkgraphschedule.cpp顺序处理器作用0InitHandler初始化节点与边注释见 src/linkgraph/init.h1DemandHandler估算各节点对某类货物的供需见 src/linkgraph/demands.cpp2MCFHandlerMCF1stPass第一趟最短路径饱和与建路3FlowMapper(false)第一趟后写回流量统计4MCFHandlerMCF2ndPass第二趟剩余容量饱和5FlowMapper(true)最终写回边注释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设置表。其中与本主题最直接相关的两个参数配置项默认值范围单位含义linkgraph.recalc_interval84–90秒游戏内时间两次重算启动之间的间隔决定 Job 多久被排队/回收一次linkgraph.recalc_time321–9000秒游戏内时间单个 Job 被允许运行的最长时间到期即 join原文档的解释是重算时间为 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 wont 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–64src/table/settings/linkgraph_settings.ini。它在两个环节影响计算量需求估算DemandHandler以accuracy作为距离缩放的分母——scaled_distance按(accuracy * scaled_distance * 16) / (base_distance * 2)折算 divisoraccuracy 越小 divisor 越小、单次纳入计算的供需越多同时给远处节点分配剩余供给的兜底条件chance accuracy * num_demands * num_supplies也随 accuracy 缩小而更快触发见 src/linkgraph/demands.cpp。可见 accuracy 越低每轮分配的流量越多、需要的迭代轮数越少MCF 两趟求解MCF1stPass与MCF2ndPass都读取job.Settings().accuracy作为每次PushFlow的步长——accuracy 越小单次推流越多收敛越快见 src/linkgraph/mcf.cpp、src/linkgraph/mcf.cpp。因此降低accuracy可以直接减少迭代轮数、缩短单 Job 运行时间代价是流向计算结果更粗糙、分配精度下降。5.2 相关配套参数linkgraph_settings.ini中还定义了与精度/需求相关的其他参数供完整调优参考配置项默认值范围含义linkgraph.demand_distance1000–255% 距离对需求的加权系数100 时按二次方放大源码中over100^2 / 12见 src/linkgraph/demands.cpplinkgraph.demand_size1000–100% 站点规模客流量/吞吐量对需求的加权linkgraph.short_path_saturation800–250% MCF 第一趟的路径饱和上限越低第一趟越早收手、耗时越少见 src/linkgraph/mcf.hlinkgraph.distribution_pax/mail/armoured/defaultManual见 DistributionType 枚举各类货物的分布模式开关对称/不对称/手动决定是否参与链路图计算5.3 配置入口上述配置项以linkgraph.*前缀持久化在openttd.cfg中linkgraph_settings.ini的注释明确说明其同时写入主配置文件、存档 PATS chunk 与每个运行中 Job 的链路图 chunk。运行时可从游戏内设置 → 高级设置Advanced Settings中找到对应条目修改也可在openttd.cfg的[linkgraph]段落直接编辑。由于设置属于GameSettings修改后会写入存档多人游戏需注意联机双方的设置一致性。六、实战调优建议综合原文档结论与源码机制可给出如下调优路线默认配置即可满足大多数场景默认recalc_interval8秒、recalc_time32秒、accuracy16配合后台线程通常不会造成可感知卡顿大地图 / 站点密集的复杂网络优先把linkgraph.recalc_time从 32 逐步提高例如 64、128给每个 Job 更充裕的运行时间减少到期 join 时的主线程阻塞同时接受流量统计更新变慢的事实CPU 较弱的机器在提高recalc_time的同时把linkgraph.accuracy从 16 下调例如 8、4用精度换速度也可适当调低short_path_saturation让 MCF 第一趟更早结束务必理解权衡关系recalc_time越大新建线路的容量变化被纳入统计越慢accuracy越小流向越粗糙。二者不可兼得需按地图规模与机器性能平衡观察信号若游戏频繁出现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。赞分享游戏开发【免费下载链接】OpenTTDOpenTTD is an open source simulation game based upon Transport Tycoon Deluxe项目地址https://gitcode.com/gh_mirrors/op/OpenTTD点击查看免费下载相关推荐Anarlog deeplink2 插件 Tauri 权限机制与 Deep Link 回调链路实现解析Anarlog deeplink2 插件 Tauri 权限机制与 Deep Link 回调链路实现解析 本文以 plugins/deeplink2/permisAI 应用人工智能语音本地部署桌面应用音频SvelteKit 性能优化实战指南从默认机制到资源、导航与托管的全链路调优SvelteKit 性能优化实战指南从默认机制到资源、导航与托管的全链路调优 SvelteKit 开箱即用地实现了代码分割、资源预加载、文件哈希缓存、请求合并Web框架后端前端Gatsby 页面间链接完全指南Link 组件、相对链接与性能机制详解Gatsby 页面间链接完全指南 Link 组件、相对链接与性能机制详解 在 Gatsby 站点中页面之间的跳转是构建多页面应用的基础能力。本文基于 do前端静态站点Web框架上一篇GitHub网络优化终极方案让国内开发者告别龟速访问的实用指南下一篇10分钟掌握OpenCore Configurator黑苹果系统配置终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考