Yet Another Research Tree (YART)

Yet Another Research Tree заменяет стандартное дерево исследований на более чистую и гораздо более читаемую версию.

Я — заядлый пользователь модпаков, использующий 450+ модов. Проблема была в том, что ни стандартное дерево исследований, ни существующие моды для него не позволяли легко найти нужное исследование среди сотен пунктов. Поэтому я решил создать этот мод самостоятельно. Он долгое время дорабатывался, чтобы вы могли быстро находить нужные исследования, даже в сотнях проектов.

Возможности

• Более компактное и читаемое дерево исследований — расположение узлов переработано, чтобы вы могли сразу уловить логику связей.
• Разделённый по вкладкам или единый вид — просматривайте исследования, разделённые по вкладкам как в оригинале, или расположите все проекты на одном экране.
• Очередь исследований — планируйте следующие проекты заранее и продолжайте исследования сразу после завершения предыдущего, без простоев.
• Параллельные каналы исследований — исследования из модов, таких как Anomaly DLC и Vanilla Gravship Expanded, можно вести одновременно с вашими обычными исследованиями.
• Оптимизированная отрисовка — отдалите изображение и просматривайте сотни узлов исследований без какого-либо лага.
• Оптимизированная система поиска — ищите по названию мода, предмета, растения, названия исследования и многому другому, с мгновенным откликом даже в большом модпаке.
• Настраиваемые цвета и поддержка для дальтоников
• Создан для тяжёлых модпаков — разработан и протестирован в сильно модифицированной среде, точно такой же, как та, в которой я играю.

Совместимость

• Anomaly DLC / Vanilla Gravship Expanded — Поддерживается (предоставляет параллельные каналы исследований)
• World Tech Level — Поддерживается (исследования, превышающие уровень технологий мира, автоматически скрываются из дерева)
• Semi Random Research — Поддерживается
• Мультиплеер - Поддерживается (предоставляет MP-адаптер)
• Другие моды для дерева исследований — Не поддерживаются (используйте только один мод для дерева исследований)
• Совместим с существующими сохранениями.

Технические детали

Как устроено дерево исследований?

Дерево исследований по своей сути является ациклическим ориентированным графом (DAG). Проблема чистого отображения ориентированного графа изучается десятилетиями, и она действительно сложна (NP-полная). YART реализует хорошо зарекомендовавший себя Sugiyama-фреймворк, специально адаптированный для дерева исследований RimWorld. Суть подхода такова:

• Разделение на столбцы по эпохам. Сначала каждое исследование группируется в "эпохальную полосу" в порядке Неолит → Средневековье → Промышленная → Космическая…, а внутри каждой полосы столбцы назначаются слева направо в соответствии с отношениями предшествования.
• Предотвращение чрезмерной высоты. YART адаптивно вычисляет "высотный бюджет" для каждого столбца на основе общего размера графа, перенося исследования из переполненных столбцов в соседние, чтобы всё выглядело с приятным соотношением сторон.
• Минимизация пересечений линий. Количество пересечений стрелок сильно зависит от того, как узлы упорядочены сверху вниз в столбце. YART генерирует несколько вариантов расположения из разных начальных точек и выбирает тот, в котором меньше всего пересечений, затем уточняет его путём перестановки соседних узлов (wmedian, transpose) — а для маленьких кластеров даже перебирает все перестановки (subset DP) — чтобы максимально уменьшить количество запутанных линий.
• Объединение линий в единые каналы. Стрелки, расходящиеся от одного исследования, объединяются, чтобы они проходили через один общий канал, с финальным пост-процессингом, который сглаживает и выпрямляет эти пучки.

Какой поиск настолько быстрый?

В среде с сотнями модов сканирование каждого пункта исследований при каждом нажатии клавиши приводило бы к лагам на каждый введённый символ — нужно проверять названия модов, исследований, предметы, растения и многое другое, что в большом модпаке составляет миллионы символов. Это классическая задача поиска иголки в стоге сена: поиск медленный, потому что приходится перебирать весь стог. Однако, удивительно, но есть способ найти иголку без перебора всего стога — с помощью структуры данных, называемой суффиксным массивом. YART реализует собственный суффиксный массив, чтобы обеспечивать почти мгновенные результаты поиска. Кроме того, он добавляет удобные функции поиска для нескольких языков: декомпозицию на jamo для корейского, фонетический (ромадзи) поиск для японского, поиск по пиньинь для китайского, нечувствительный к умлаутам поиск для немецкого и нечувствительный к акцентам поиск для вьетнамского и французского — так что вы сможете найти именно то, что ищете.

GitHub: github.com/csh1668/YetAnotherResearchTree