Еще одно дерево исследований (YART)

Еще одно дерево исследований заменяет дерево исследований ванили более чистой, гораздо более читаемой версией.

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

Функции

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

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

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

Под капотом

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

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

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

Почему поиск такой быстрый?

In an environment with hundreds of mods, scanning every research entry on each keystroke would lag on every character you type — there are mod names, research names, items, plants and more to check, which adds up to millions of characters in a large modpack. It's the classic needle-in-a-haystack problem: searching is slow because you have to comb through the entire haystack. Surprisingly, though, there's a way to find the needle without searching the whole haystack — a data structure called a suffix array. YART implements its own suffix array to deliver near-instant search results. On top of that, it adds quality-of-life search features for several languages: jamo decomposition for Korean, phonetic (romaji) search for Japanese, pinyin search for Chinese, umlaut-insensitive search for German, and accent-insensitive search for Vietnamese and French — so you can find exactly what you're after.

GitHub: github.com/csh1668/YetAnotherResearchTree