Алгоритмы сортировки

RimSort предлагает два алгоритма. С v1.0.10 по умолчанию — топологическая сортировка.

Разные алгоритмы могут дать разные, но «корректные» порядки.

Корректный порядок — без предупреждений о порядке в RimSort. Проблемы в игре часто означают недостающее правило — задайте его в редакторе правил и сообщите автору мода и в community rules DB.

Многоуровневая сортировка

Какой бы алгоритм ни был выбран, RimSort не сортирует весь активный список модов одним проходом. Вместо этого Sorter сначала разделяет активный список на четыре уровня, сортирует подграф каждого уровня независимо выбранным алгоритмом, а затем объединяет результаты в порядке уровней:

  • Уровень 0 — Core, Harmony, Prepatcher, официальные DLC RimWorld и всё, что рекурсивно зависит от них.
  • Уровень 1 — известные каркасные моды (например, Universum, Vanilla Expanded Framework и XMLExtensions), а также моды с меткой loadTop (Force load at top of list), плюс их рекурсивные зависимости.
  • Уровень 2 — всё остальное.
  • Уровень 3 — моды с меткой loadBottom (Force load at bottom of list) и моды, которые рекурсивно зависят от них.

То есть правила loadTop / loadBottom, которые вы задаёте (через редактор правил или community rules database), не переставляют моды напрямую — вместо этого они направляют моды на более высокий или нижний уровень. Моды с loadTop всегда сортируются перед любым модом без этой метки, а моды с loadBottom — после любого мода без неё.

Алфавитная сортировка

Алгоритм Alphabetical — более простой подход к корректной сортировке. В пределах каждого уровня этот метод сортирует моды по алфавиту перед применением правил.

Шаги как в RimPy Autosorting Wiki:

  1. Сортировка по имени мода
  2. Правила из About.xml и внешних метаданных принудительно применяются

Итог: в основном алфавитный список с корректировками по правилам.

Что значит принудительно?

Это можно показать на примере: пусть список модов — [A, B, C, D, E]. Он уже отсортирован по алфавиту, поэтому RimPy вставляет моды в итоговый порядок по одному, начиная с A. У мода A нет зависимостей — на первой итерации он попадает в итоговый порядок, который теперь [A].

На следующей итерации вставляется B. Однако у B есть зависимости loadAfter: [D, E] (возможно, заданные в его About.xml). RimPy принудительно вставляет D и E перед B, но после A. Итерации итогового порядка загрузки выглядят так:

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

Однако бывает, что у зависимостей B есть правила друг относительно друга, например D должен загружаться после E. Чтобы учесть такие случаи, при вставке каждой зависимости нужно пройти по подсписку уже вставленных зависимостей и найти последнее вхождение зависимости, от которой зависит вставляемый нами мод. По сути, принудительно означает, что алгоритм сортировки рекурсивно внедряет зависимости прямо перед модом, который от них зависит.

Что гарантируется?

При отсутствии конфликтов правил — все правила порядка соблюдаются.

Топологическая сортировка

По умолчанию (v1.0.10)

Алгоритм Topological использует топологическую сортировку (Toposort): уровни — моды без зависимостей, затем следующий уровень и т.д.

loadAfter / loadBefore образуют направленный граф. Внутри уровня — алфавитный порядок.

Что гарантируется?

Без конфликтов — математически оптимальный порядок. Результат часто отличается от RimPy — это нормально.