Sorting Algorithms

RimSort 默认提供两种排序算法来对激活的 Mod 列表排序。自 v1.0.10 起，默认使用 拓扑排序。

不同排序算法可能产生不同的「正确」排序结果。

这种意义上的正确排序，仅指遵循所有定义规则的排序（即在 RimSort 中不会出现顺序警告）。如果你在使用某些算法时，遇到游戏内问题，很可能是存在未检测到的「缺失」排序规则，此时你需要通过规则编辑器手动定义该规则。我们强烈建议你将新发现的规则报告给 Mod 作者和社区规则数据库！

分层排序

无论选择哪种算法，RimSort 都不会对整个激活 Mod 列表做单次遍历排序。相反，Sorter 会先将激活列表划分为四个层级，用所选算法独立对每个层级的子图排序，然后按层级顺序拼接结果：

  • 层级 0 — Core、Harmony、Prepatcher、官方 RimWorld DLC，以及所有递归依赖于它们的 Mod。
  • 层级 1 — 已知框架 Mod（如 Universum、Vanilla Expanded Framework、XMLExtensions），以及带有 loadTop（强制排序至列表顶部）标记的 Mod，加上它们的递归依赖项。
  • 层级 2 — 其他所有 Mod。
  • 层级 3 — 带有 loadBottom（强制排序至列表底部）标记的 Mod，以及递归依赖于它们的 Mod。

这意味着你通过规则编辑器或社区规则数据库定义的 loadTop / loadBottom 规则并不会直接重排 Mod，而是将 Mod 路由到更高或更低的层级。带有 loadTop 标记的 Mod 总是排在任何未标记 Mod 的_之前_，带有 loadBottom 标记的 Mod 总是排在任何未标记 Mod 的_之后_。

字母顺序排序算法

第一种算法，字母顺序排序（Alphabetical），采用更简单的方法进行合理排序。在每个层级内，该方法在应用规则之前先按字母顺序排列你的 Mod。

该算法大致遵循 RimPy 自动排序 Wiki 中描述的步骤：

  1. Mod 列表根据 Mod 名称按字母顺序排序
  2. 从 Mod 的 About.xml 文件中提取的规则与外部提供的元数据将被 强制应用（下文详述具体含义）

最终结果是一个大体按字母顺序排列的 Mod 列表，其中已定义的加载顺序规则会对部分 Mod 位置进行调整。需要优先加载的 Mod 会已处于合适位置（因字母排序），或被强制插入到依赖项之前。

强制应用 是什么意思？

通过示例说明：假设初始 Mod 列表为 [A, B, C, D, E]，已按字母排序。RimPy 开始逐个将它们插入到最终加载顺序，首先插入 A。Mod A 无依赖，因此在第一次迭代后顺序为 [A]。

接下来插入 B，但 B 有依赖项 loadAfter: [D, E]（可能是在它的 About.xml 中指定的）。此时 RimPy 会强制将 D 和 E 插入到 B 之前，但位于 A 之后。如果 D 和 E 自身无其他依赖，插入 B 后的顺序变为 [A, D, E, B]。

但当依赖项之间存在相互规则时（例如 D 需在 E 之后加载），直接插入会导致规则冲突。因此算法在插入每个依赖项时，会遍历已插入的依赖项子列表，寻找当前依赖项所依赖的最新出现项。最终加载顺序的迭代过程如下：

[A]
[A, B]
[A, E, B]
[A, E, D, B]
...

强制应用 本质上指算法以递归方式将依赖项直接插入到依赖它们的 Mod 之前。

该算法保证什么？

在无冲突的加载规则的前提下，该算法保证遵守所有加载顺序规则。因为当算法遍历按字母排序的 Mod 列表，并逐个插入时，当前 Mod 的依赖项会被强制前置，或依赖项已存在于列表更靠前位置。

拓扑排序

默认算法（v1.0.10）

第二种算法，拓扑排序算法（Topological）采用 拓扑排序 思想来整理 Mod。

拓扑排序算法使用 Toposort 包将 Mod 列表排序为「拓扑层级」：第一拓扑层的 Mod 不依赖任何其他 Mod；当第一层 Mod 被处理后，第二层 Mod 将不再依赖其他 Mod；依此类推。这是对有向图线性排序的数学解法（Mod 的 loadAfter 和 loadBefore 关系本质上构成有向图）。

同一拓扑层级内的 Mod 顺序无关紧要。但 RimSort 实现上会在将拓扑层级加入最终加载顺序前，对其中的 Mod 进行字母顺序排序。

该算法保证什么？

在无冲突规则的情况下，该算法保证数学意义上的最优排序。注意，最终加载顺序通常与 RimPy 算法结果显著不同，这是符合预期的，因为两种算法的排序逻辑完全不同。