Tetrachord Lib

Введение

Множество модов для Minecraft реализуют функциональные возможности как в 2D-, так и в 3D-средах[1][2][3], однако методы перебора часто оказываются неэффективными. В связи с этим мы представляем Tetrachord Lib — легковесную библиотечную модификацию, предназначенную для оптимизации различных структур данных.

Связанные работы

Серверные моды оптимизации

jellysquid3_[4] представил Lithium — революционный мод оптимизации, улучшающий различные аспекты работы серверов Minecraft. Используя точные алгоритмы для минимизации обращений к чанкам и блокам, этот мод повышает не только производительность генерации мира, но и работу ИИ мобов, обнаружение коллизий, поиск точек интереса (poi) и другие важные аспекты, увеличивая вычислительную эффективность и снижая количество миллисекунд на тик (mspt) серверов.

Spottedstar[5] представил Starlight — инновационную модификацию, которая переопределяет световой движок Minecraft для повышения производительности при генерации чанков, установке и разрушении блоков. В отличие от Phosphor[6], Starlight не изменяет ванильную систему освещения — вместо этого он полностью её перерабатывает, внедряя новый алгоритм.

Структуры данных

KD-дерево[7] — это структура данных, используемая в многомерных пространствах для хранения и организации k-мерных точек данных. Работая как бинарное дерево, каждый узел KD-дерева представляет k-мерную точку данных и разделяется в соответствии со значениями признаков (измерений) этой точки. KD-деревья особенно хорошо подходят для выполнения диапазонных запросов и поиска ближайших соседей в многомерных наборах данных, а также могут способствовать оптимизации извлечения данных в мире Minecraft.

Дерево отрезков[8] — это структура данных, используемая для обработки диапазонных обновлений и запросов. Оно разбивает отрезок на более мелкие подотрезки и организует их иерархически в виде дерева. Деревья отрезков эффективны для обновления и запроса диапазонов данных. В контексте мира Minecraft, представленного как 3D-тензор, применение дерева отрезков может значительно повысить производительность при частых диапазонных обновлениях и запросах.

Эксперименты

Оценка

Spark[9] — это легковесный мод-профайлер производительности, который показывает детальные затраты времени модов, использование памяти и ЦП, миллисекунды на тик (mspt) и другие метрики производительности клиентов и серверов. Мы использовали Spark и выбрали затраты времени и mspt в качестве метрик для оценки возможностей оптимизации Tetrachord Lib.

Бенчмарки

Мы реализовали вышеупомянутые структуры данных и провели эксперименты с использованием следующих бенчмарков:

No Hostiles around Campfire

В определённом сценарии, когда игроки зажигают костры, окружающие области в радиусе нескольких блоков перестают спавнить монстров. Оригинальный мод[1] предлагает метод перебора, включающий множество обращений к блокам, что приводит к значительному росту mspt на сервере и замедлению работы игры. Мы решили использовать KD-дерево для реализации этой задачи. Мы применили профайлер Spark для записи 1 минуты обычного игрового процесса при различных настройках параметров, и результаты эксперимента показаны на следующем рисунке:

Ore Blocks near Beacon Increase Xp Drop

Рассматривая сценарий, в котором игроки добывают блоки рядом с маяком, они могут получить дополнительную награду в виде опыта в зависимости от количества рудных блоков вокруг добытого блока. Таблица ниже иллюстрирует зону отклика и «рудный счёт», связанные с каждым типом рудного блока:

Мы использовали профилировщик Spark, чтобы записать установку 32 блоков руды и добычу 32 блоков при разных настройках параметров, и результаты эксперимента показаны на следующем рисунке:

Заключение

Эксперименты показывают, что Tetrachord lib играет важную роль в разных ситуациях и предоставляет высокоэффективный способ реализации некоторых требований к обновлениям и запросам в 2D- и 3D-пространстве.

На данный момент мод Tetrachord Lib работает как библиотека, поэтому разработчики могут использовать его как зависимость для повышения производительности своих модов.

Ссылки

[1] Serilum. No Hostiles Around Campfire. Modrinth 2022.

[2] Serilum. Healing Campfire. Modrinth 2022.

[3] Mikul, chubbymomo, skinnymomo. Cold Sweat. Modrinth 2023.

[4] jellysquid3_. Lithium. Modrinth 2021.

[5] Spottedstar. Starlight. Modrinth 2021.

[6] jellysquid3_. Phosphor. Modrinth 2021.

[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. Modrinth 2021.