四弦琴

引言

众多 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 分钟的正常游戏进程，实验结果如下图所示：

信标附近矿石方块提升经验掉落

设想玩家在信标附近开采方块的场景，玩家可以根据开采方块周围矿石方块的数量获得额外经验奖励。下表展示了每种矿石方块对应的响应区域和“矿石分数”：

矿石类型	铜	铁	金	钻石	下界合金
响应区域	5x5	9x9	13x13	17x17	19x19
矿石分数	1	1	1	2	3

我们使用 Spark 分析器记录了不同参数设置下 32 次矿石放置和 32 次方块开采的过程，实验结果如下图所示：

结论

实验表明，Tetrachord Lib 在不同情境下均发挥着重要作用，并为在 2D 和 3D 空间内实现更新和查询相关需求提供了一种高效的方式。

Tetrachord Lib 模组目前作为库运行，因此开发者可以将其作为依赖项使用，以提升模组性能。

参考

[1] Serilum. 篝火附近无敌对生物. Modrinth 2022.

[2] Serilum. 治疗篝火. 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. 用于关联搜索的多维二叉搜索树. Commun. ACM 18, 9 (Sept. 1975), 509–517.

[8] Jon Louis Bentley. Solutions to Klee's rectangle problems, 未出版手稿, 1977.

[9] Iucko. Spark. Modrinth 2021.