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. 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.