引言

许多 Minecraft 模组都在 2D 和 3D 环境中集成了功能特性[1][2][3]，但暴力方法经常被证明效率低下。为此，我们提出了 Tetrachord Lib，这是一个轻量级的模组库，旨在提供各种优化数据结构。

相关工作

服务器端优化 Mod

jellysquid3_[4] 提出了 Lithium，这是一种突破性的优化模组，可以提升 Minecraft 服务端各个方面的性能。 该模组采用精确的算法来最大限度地减少方块和区块的访问，不仅增强了世界生成，还增强了生物 AI、碰撞检测、兴趣点（poi）发现以及其他关键方面，以提高计算效率并减少服务器的每刻的毫秒数（mspt）。

Spottedstar[5] 提出了 Starlight，这是一项创新修改，重新设计了 Minecraft 的光照引擎，以提高区块生成、方块放置和破坏方面的性能。 与Phosphor相比，Starlight 并不仅仅是在原版的光照系统上进行修改——相反，它通过引入新的算法对其进行了革命性的改变。

Tetrachord Lib 不同于上述两种 mod，通过实现高性能数据结构、并暴露接口给其它模组开发者的方式，来提高程序运行速度，达到计算优化的效果。

数据结构

KD 树[7]是一种在高维空间中用于存储和组织 k 维数据点的数据结构。作为一棵二叉树，KD 树中的每个节点代表一个 k 维数据点，并根据数据点的特征值（维度）进行分区。KD 树特别适合在高维数据集中进行范围查询和最近邻搜索，它们还有助于优化 Minecraft 世界中的数据检索。

KD 树图示

线段树[8]是一种用于处理范围更新和查询的数据结构。它将一个段划分为更小的子部分，并以树结构分层组织它们。线段树对于区间数据更新和查询非常有效。在以 3D 张量表示的 Minecraft 世界中，当涉及频繁的范围更新和查询时，使用线段树可以极大地提高性能。

线段树图示

实验

评价指标

Spark是一个轻量级性能分析器 mod，它可以详细显示每个 mod 的运行时间、内存和 CPU 使用情况、每刻毫秒数（mspt）以及客户端和服务器的其他性能指标。我们利用 Spark 并选择模组运行时间和 mspt 作为衡量 Tetrachord Lib 优化能力的指标。

基准

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

围火无怪

在特定场景下，当玩家点燃篝火时，周围数个方块范围内的区域将不再产生怪物。原始mod[1]提供了一种暴力的方法，涉及多次方块访问，导致服务器上的 mspt 显著增加，并减慢游戏程序的速度。我们选择利用 KD 树来实现这个需求。我们利用 Spark Profiler 记录了不同参数设置下 1 分钟的正常游戏，实验结果如下图所示：

围火无怪

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

考虑到玩家在信标附近开采方块的情况，假设他们可以根据开采方块周围的矿石块数量获得额外的经验奖励。 下表说明了与每种矿石块相关的响应区域和“矿石分数”，最终挖掘的方块将会掉落 [( 当前位置矿石分数 +1) / 2] 点经验值：

我们选择实用 2D 线段树来维护“矿石分数”和处理区间更新和查询，利用 Spark Profiler 记录了不同参数设置下的 32 个矿石块放置和 32 个方块挖掘的性能数据，实验结果如下图所示：

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

结论

实验表明，Tetracord Lib 在不同的情况下都发挥了显著性的优化作用，并提供了一种高效的方法来实现一些 2D 和 3D 空间的更新和查询需求。

Tetrachord Lib mod 目前作为一个库运行，因此开发人员可以将其用作依赖项来提高 mod 性能。模组安装在客户端或服务端并无强制要求——这将取决于下游拓展模组的需要。

参考资料

[1] Serilum. 围火无怪. MC 百科 2019.

[2] Serilum. 治愈营火. MC 百科 2019.

[3] Mikul, chubbymomo, skinnymomo. 冷汗. MC 百科 2021.

[4] jellysquid3_. 锂. MC 百科 2020.

[5] Spottedstar. 星光. MC 百科 2021.

[6] jellysquid3_. 磷. MC 百科 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. 火花. MC 百科 2020.