Введение
Многочисленные моды Minecraft интегрировали функциональные возможности как в 2D, так и в 3D средах[1][2][3], однако методы прямого перебора часто оказываются неэффективными. В этой связи мы представляем Tetrachord Lib, легковесную библиотечную модификацию, разработанную для оптимизации разнообразных структур данных.
Связанные работы
Моды оптимизации на стороне сервера
jellysquid3_[4] представил Lithium, революционный мод оптимизации, улучшающий различные аспекты серверов Minecraft. Используя точные алгоритмы для минимизации доступа к чанкам и блокам, этот мод улучшает не только генерацию мира, но и ИИ мобов, обнаружение столкновений, поиск точек интереса (poi) и другие важные аспекты для повышения вычислительной эффективности и снижения миллисекунд за тик (mspt) на серверах.
Spottedstar[5] представил Starlight, инновационную модификацию, переопределяющую движок освещения Minecraft для повышения производительности при генерации чанков, размещении и разрушении блоков. В отличие от Phosphor[6], Starlight не изменяет ванильную систему движка освещения — вместо этого он революционизирует её, вводя новый алгоритм.
Структуры данных
KD Tree[7] — это структура данных, используемая в многомерных пространствах для хранения и организации k-мерных точек данных. Функционируя как бинарное дерево, каждый узел в KD Tree представляет собой k-мерную точку данных и разделяется в соответствии со значениями признаков (измерений) точки данных. KD деревья особенно хорошо подходят для выполнения запросов по диапазону и поиска ближайших соседей в многомерных наборах данных; они также могут способствовать оптимизации извлечения данных в мире Minecraft.
Segment Tree[8] — это структура данных, используемая для обработки обновлений и запросов диапазонов. Она разделяет сегмент на более мелкие подсекции и организует их иерархически в древовидную структуру. Деревья отрезков эффективны для обновления и запроса диапазонов данных. В контексте мира Minecraft, представленного как 3D тензор, использование дерева отрезков может значительно повысить производительность при частых обновлениях и запросах диапазонов.
Эксперименты
Оценка
Spark[9] — это легковесный мод-профайлер производительности, который показывает детальные затраты времени модов, использование памяти и CPU, миллисекунды за тик (mspt) и другие метрики производительности клиентов и серверов. Мы использовали Spark и выбрали затраты времени и mspt в качестве метрик для оценки способности к оптимизации Tetrachord Lib.
Бенчмарки
Мы реализовали упомянутые структуры данных и провели эксперименты, используя следующие бенчмарки:
Отсутствие враждебных существ у костра
В определенном сценарии, когда игроки разжигают костры, области в радиусе нескольких блоков перестают порождать монстров. Исходный мод[1] предлагает метод прямого перебора, включающий множественные обращения к блокам, что приводит к значительному росту mspt на сервере и замедлению работы игровой программы. Мы выбрали использование KD Tree для реализации этого требования. Мы использовали профайлер Spark для записи 1 минуты обычного игрового процесса при разных настройках параметров; результаты эксперимента показаны на следующем рисунке:
Рудные блоки рядом с маяком увеличивают выпадение опыта
Рассмотрим сценарий, при котором игроки добывают блоки рядом с маяком и получают дополнительную награду XP, основанную на количестве рудных блоков вокруг добываемого блока. В таблице ниже показана область воздействия и "балл руды", связанный с каждым типом рудного блока:
| Тип руды | Медь | Железо | Золото | Алмаз | Незерит |
|---|---|---|---|---|---|
| Область воздействия | 5x5 | 9x9 | 13x13 | 17x17 | 19x19 |
| Балл руды | 1 | 1 | 1 | 2 | 3 |
Мы использовали профайлер Spark для записи размещения 32 рудных блоков и добычи 32 блоков при разных настройках параметров; результаты эксперимента показаны на следующем рисунке:
Заключение
Эксперименты показывают, что Tetrachord Lib играет значительную роль в различных ситуациях и предоставляет высокоэффективный способ реализации некоторых требований по обновлениям и запросам в 2D и 3D пространстве.
Мод Tetrachord Lib в настоящее время функционирует как библиотека, поэтому разработчики могут использовать его как зависимость для повышения производительности своих модов.
Ссылки
[1] Serilum. No Hostiles Around Campfire. CurseForge 2019.
[2] Serilum. Healing Campfire. CurseForge 2019.
[3] Mikul, chubbymomo, skinnymomo. Cold Sweat. CurseForge 2021.
[4] jellysquid3_. Lithium. CurseForge 2020.
[5] Spottedstar. Starlight. CurseForge 2021.
[6] jellysquid3_. Phosphor. CurseForge 2019.
[7] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (Sept. 1975), 509–517.
[8] Jon Louis Bentley. Solutions to Klee's rectangle problems, Unpublished Manuscript, 1977.
[9] Iucko. Spark. CurseForge 2020.
