Tetrachord Lib

简介

许多 Minecraft 模组已在 2D 和 3D 环境中集成了各种功能[1][2][3]，但暴力方法往往效率低下。为此，我们推出了 Tetrachord Lib，这是一款轻量级前置库，旨在优化多种数据结构。

相关作品

服务端优化模组

jellysquid3_[4] 推出了钠（Lithium），这是一款开创性的优化模组，可提升 Minecraft 服务器的多个方面。该模组采用精确的算法来减少对区块和方块的访问，不仅能优化世界生成，还能优化生物 AI、碰撞检测、兴趣点（poi）的发现等关键方面，从而提高计算效率并降低服务器每刻耗时（mspt）。

Spottedstar[5] 推出了 Starlight，这是一款创新模组，通过重新设计 Minecraft 的光照引擎，提升区块生成、方块放置和破坏时的性能。与 Phosphor[6] 不同，Starlight 并未修改原版光照引擎系统，而是通过引入新算法对其进行了革新。

数据结构

KD 树[7]是一种用于高维空间的数据结构，可存储和组织 k 维数据点。KD 树采用二叉树结构，其中每个节点代表一个 k 维数据点，并根据该数据点的特征值（维度）进行划分。KD 树尤其适用于在高维数据集中执行范围查询和最近邻搜索，也有助于优化 Minecraft 世界中的数据检索。

线段树[8]是一种用于处理范围更新和查询的数据结构。它将一个区间划分为更小的子区间，并以树形结构进行分层组织。线段树能够高效地更新和查询数据区间。在将 Minecraft 世界表示为 3D 张量的情况下，使用线段树可以显著提升频繁执行范围更新和查询时的性能。

实验

评估

Spark[9] 是一款轻量级性能分析模组，可显示模组的详细耗时、内存和 CPU 使用情况、每刻耗时（mspt），以及客户端和服务器的其他性能指标。我们使用 Spark，并选取耗时和 mspt 作为指标，评估 Tetrachord Lib 的优化能力。

基准测试

我们实现了上述数据结构，并使用以下基准测试进行了实验：

篝火周围没有敌对生物

在一种特定场景中，玩家点燃篝火后，周围数个方块半径内将不再生成怪物。原模组[1]采用暴力方法，需要多次访问方块，导致服务器 mspt 大幅上升，使游戏运行变慢。我们选择使用 KD 树来实现这一需求。我们使用 Spark 性能分析器，在不同参数设置下记录了 1 分钟的正常游戏过程，实验结果如下图所示：

信标附近的矿石方块增加经验掉落

在玩家挖掘信标附近方块的场景中，玩家可以根据被挖掘方块周围的矿石方块数量，获得额外的经验奖励。下表展示了每种矿石方块对应的作用范围和“矿石分数”：

我们使用 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. 用于关联搜索的多维二叉搜索树。Commun. ACM 18, 9 (1975年9月)，509–517。

[8] Jon Louis Bentley. Klee 矩形问题的解法，未发表手稿，1977。

[9] Iucko. Spark. CurseForge 2020.