深度剖析Minecraft #3 计划刻

发表于 更新于 分类于 阅读次数： 本文字数： 6k 阅读时长 ≈ 11 分钟
计划刻的实现原理以及相关性质的应用

3 计划刻

3.1 什么是计划刻

计划刻，英文为 Tile Tick。国内社区曾用 Next Tick Entry (NTE) 进行描述

在 Minecraft 中，许多方块对变化的响应并不是瞬时，而是延迟一定时间后方才开始执行的，如下面几个常见的例子：

  • 中继器响应信号输入
  • 沙子检测下方方块以准备下落
  • 流体进行流动
  • 悬空脚手架的逐个掉落

对于这一类具有共性的延迟执行的事件，Minecraft 使用计划刻这一概念进行统一的管理，每一个纬度的计划刻管理系统都是相互独立的

1.13 前，方块和流体共用一个计划刻管理系统进行储存，1.13 及以后，方块和流体为独立的计划刻管理系统

3.2 计划刻的实现原理

3.2.1 计划刻管理系统

一个计划刻管理系统，是一个包含了一套完善的与计划刻相关的状态、容器的对象，类名如下

net.minecraft.world.ServerTickList (1.13.2 mcp)

net.minecraft.server.world.ServerTickScheduler (1.15.2 yarn)

其中，有三个储存着计划刻事件的容器是我们所关注的：

名称 属性名 类型 用途
计划刻队列 pendingTickListEntriesTreeSet TreeSet 可视作一个优先队列，用于有序地储存计划刻事件
计划刻队列附属哈希表 pendingTickListEntriesHashSet HashSet 用于快速判断计划刻事件是否在计划刻队列中
即将执行事件列表 pendingTickListEntriesThisTick ArrayList 储存着即将在某个游戏刻执行的计划刻事件

3.2.2 计划刻事件

对于一个计划刻事件（net.minecraft.world.NextTickListEntry）来说，它具有以下属性

  • 事件 id，一个递增的不重复整数
  • 目标方块/流体类型
  • 方块/流体的方块坐标
  • 事件计划执行的游戏刻
  • 事件优先级

事件优先级一共有 7 种可能的取值，从 -3 至 +3，如下所示

1
2
3
4
5
6
7
EXTREMELY_HIGH(-3),
VERY_HIGH(-2),
HIGH(-1),
NORMAL(0),
LOW(1),
VERY_LOW(2),
EXTREMELY_LOW(3);

由其中可看出，每个计划刻事件所储存的属性其实并不是十分详细，不少事件的具体细节是没有储存起来的，如：

  • 计划刻事件仅储存了方块的种类，未储存方块状态
  • 计划刻事件未储存该事件将要执行什么动作，也即在该事件真正执行前游戏是不知道这个事件具体会引发什么动作的

3.2.2.1 计划刻事件间的比较

两个计划刻事件是相同的（equals 方法），当且仅当这两个事件的以下属性相同

  • 目标方块/流体类型
  • 方块/流体的方块坐标

这将用在判断事件是否存在于 即将执行的事件列表（一个 ArrayList）中

在判断事件的大小关系时（compareTo 方法），按照以下关键字依次比较：

  1. 执行时刻，较小者优先
  2. 事件优先级
  3. 事件 id，较小者优先

这将用在计划刻队列（一个 TreeSet）的实现中

3.2.3 计划刻阶段

每游戏刻中，计划刻阶段的执行入口是 net.minecraft.world.WorldServer#tickPending。其中，先处理方块的计划刻阶段，再处理流体相关的计划刻阶段

在计划刻阶段里，游戏将按照事件优先级从高到底的顺序执行将在此游戏刻中执行的计划刻事件。若优先级相同，则比较事件的id，id较小的先执行

具体实现是比较朴素的。Minecraft 使用了一个 TreeSet（使用红黑树实现的二叉平衡树）作为该纬度所有计划刻事件的容器

因为在代码中，不存在直接删改该容器某个具体元素的用法，仅存在插入元素及取出最小元素这两个操作，因此即便这个容器不是明面上的一个队列， 它仍可被视为一个队列，或者更准确的，优先队列。这也是计划刻队列这一词的来由

TreeSet 的时间复杂度是 O(nlogn)，这意味着实际上计划刻元件的卡顿并非线性增加的，不过在实际情况下由于 logn 变化极小，仍可以大致认为卡顿是线性增加的

下面以方块的计划刻阶段为例，核心流程如下：

  1. 检索应在该游戏刻执行的事件
    1. 取出计划刻队列中位于最前的事件（比较方法见上方所列的优先级）
    2. 若当前的游戏时间小于该事件的执行时刻，或者本计划刻阶段已取出了 65536 个计划刻事件 [1]，则退出循环，跳出循环。超过上限的事件将会延迟到下一游戏刻尝试执行
    3. 将该事件移出计划刻队列，暂存入一个即将执行的事件列表

第一步执行完后，游戏已经确认下来了这个游戏刻中将执行哪些计划刻事件。注意到这些事件已经被移出了计划刻队列，因此一个新的相同的计划刻事件现在是可以添加成功了（计划刻事件添加的判据见 3.2.4 计划刻事件的添加）

随后，游戏开始执行这些计划刻事件：

  1. 处理即将执行的事件列表

    • 对于列表中每个计划刻事件，若事件的方块的坐标所在区块处于加载状态，则：

      1. 判断世界中此坐标的方块是否仍与该事件的方块类型相同，如果相同，则调用该方块的 tick方法

    • 若坐标所在的区块未加载，则：

      1. 添加一个计划刻事件，属性为：

        • 坐标：该事件的坐标
        • 方块：该事件的方块
        • 延迟：0
        • 优先级：0

        不过此计划刻事件不会添加成功，因为此事件的坐标所在区块未被加载。至于为何要实现此逻辑，仍有待考究

  2. 计划刻阶段结束

为了让表述更流畅，上述描述并非与源代码 100% 对应的分析，但是其效果是等价的。具体代码可见：

net.minecraft.world.ServerTickList#tick (1.13.2 mcp)

net.minecraft.server.world.ServerTickScheduler#tick (1.15.2 yarn)

3.2.4 计划刻事件的添加

若要添加一个计划刻事件，需要传入以下的参数：

  • 方块/流体的坐标
  • 方块/流体的类型
  • 执行延迟
  • 事件优先级。若未指定则为默认值 0

随后，游戏会依次执行下述步骤判断此次添加是否合法：

  1. 若添加的是方块计划刻事件，则该事件方块不可为空气；若添加的是流体计划刻事件，则流体不可为空
  2. 事件所在坐标的区块处于已加载状态
  3. 计划刻队列中不存在相同的事件

最后，一个新的计划刻事件将会创建并加入至计划刻队列中 [2]，其方块/流体的类型与坐标即为所给值，而执行时刻则从给出的执行延迟计算得到，为 执行延迟 + 该纬度当前的游戏时间

3.2.5 计划刻事件的删除

计划刻事件在添加入计划刻队列后，是不会直接被游戏删除的，即便原方块/流体已经被改变。游戏中唯一类似删除计划刻事件的地方，是由于事件所处的区块被卸载，从而导致执行该事件的时候被游戏移除队列且不再加入队列不过放心，在区块卸载保存的时候，计划刻队列是会保存至磁盘的，因此不需要担心计划刻元件的动作被丢失了

计划刻事件的不易被删除特性，在某些情况下是可以利用的

3.3 计划刻事件执行顺序

3.3.1 单个元件

事件间比较大小的关键字依次为：

  1. 执行时刻，较小者优先
  2. 事件优先级
  3. 事件 id，较小者优先

按照这三个关键字，我们可以很轻易地判断两个计划刻事件间的执行先后。前两个关键字很容易获得，但是第三个关键字并为直接给出，因此不能在前两个关键字相同的情况下，并不能直观地判断孰先孰后

观察 事件 id 的定义，这是一个递增的不重复的整数，因此，先创建的计划刻事件一定会有较小的 事件 id ，也就是在执行时刻与事件优先级相同的情况下，先创建的事件会优先于后创建的事件执行

也就是先进先出！

下面是一些例子：

single0

执行时刻，A 先于 B，因此 A 先执行

single1

执行时刻：A 与 B 相同

优先级：A 大于B

因此 A 先执行

single2

执行时刻：相同

优先级：相同

创建顺序（事件 id）：A 先于 B

因此 A 先执行

3.3.2 多元件组合

在总延迟相同的前提下，用不同档位凑出来的中继器/比较器/序列谁先输出信号，是一个老生常谈的问题，比如下图

multi0

由于总延迟是相同的，并且最末端的元件具有相同的优先级，我们不能简单地观察最末端的元件来判断执行顺序，我们需要结合其余元件进行考虑，得出最末端元件创建事件的顺序间的先后关系，从而得到执行顺序

由于在这些判断顺序的实例中，第 n 个元件的计划刻事件创建事件往往是与第 n - 1 个元件的点亮时刻是相同的，因此可以用低 n -1 个元件的点亮时刻来替代第 n 个元件的创建事件时刻

令拉杆拉下的时刻为 gt0。由于序列 A 的第一个中继器是在 gt2 点亮，而序列 B 的第一个中继器是在 gt 8 点亮，晚于序列 A 的第一个中继器，因此序列 A 的第二个也就是末端的中继器先于序列 B 的末端中继器激活

如果还有更多的元件呢，那我们继续比较下去！

  • 若次末端的元件点亮时刻与优先级均相同，则判断倒数第三个元件的点亮先后顺序
  • 若倒数第三个元件的元件点亮时刻与优先级均相同，则判断倒数第四个元件的点亮先后顺序
  • ……

也就是，从尾到头依次比较元件的点亮顺序，直到比较出结果

若比较的两个序列的元件是同一个元件，这时比较更新顺序即可。如一个拉杆向两侧引出 1 挡中继器，这是就需要根据方块更新的顺序来判断哪一侧的中继器先被更新

下面是一些例子：

multi0

末端的中继器的优先级及点亮时间均相同，比较前端的中继器点亮时间：A 先，因此 A 序列比 B 序列先输出

multi1

A, B 与 C, D, E 的比较与上图相同，对于 A, B，第一个元件点亮的优先级是 A 的中继器更高，因此 A 比 B 先输出。总输出顺序为 A, B, C, D, E

multi2

根据最末端元件的优先级可立即得到 A, B, C 比 D, E 先输出。A 的中继器最先得到输入信号，因此 A 最先输出。剩余序列比较方法同上，比较第一个元件的优先级即可得出总输出顺序为 A, B, C, D, E

3.4 计划刻元件

见《深度剖析Minecraft #3.4 计划刻元件》

3.5 时序描述

在分析计划刻相关的时序的时候，计划刻事件的优先级以及计划刻事件的目标常常是我们关心的因素

对于一个优先级为 x ，目标为 y 的计划刻事件，下面使用记号 TileTick.priority=x,target=y，或者简称 TT.x.y 来表示该事件执行时所处在的游戏阶段。在不关心优先级或者目标的场合中，.x .y 是可以视情况选择省略的。在大多数情况下，时序精度划分至计划刻阶段或者计划刻优先级，就已经足够了。

例如，对于单个红石中继器的点亮事件，其发生的游戏阶段为 TT.-1

当然，也可使用计划刻的旧称 NTE 来替换上述的 TT 以得到在特定情境下得到与已有理论体系更好的衔接

3.6 计划刻性质的应用

3.6.1 计划刻滞后/EMP

More like a redstone EMP

—— Casper2002 @ https://youtu.be/1GWaZ5vEd3A

在分析计划刻阶段的流程时，细心的读者可能已经注意到了，每游戏刻可执行的计划刻事件数量有个 65536 的上限，超过上限的事件将会延迟到下一游戏刻尝试执行，这一点似乎是可以加以利用的

如果我们认为的在某一游戏刻中添加了巨量的延迟相同的计划刻事件，使其数量超过了 65536，则可在游戏中制造一些正常情况下不可能发生的事情：某些计划刻事件被延后执行了。这可以用于无线红石信号传输、无限遥控飞行器，也可以用恶意破坏红石电路。该机制的作用范围是整个维度

下面以该机制发现者 Xcom6000 的《原版生存无线红石》为例，分析下其时序

emp-tower

emp-detector

游戏刻 游戏阶段 事件
0 TT.-2 中继器熄灭，大量充能铁轨熄灭，更新 n, n > 65536 个沙子方块。巨量的沙子方块添加了位于 gt 2 的计划刻事件
0 TT.0 某一侧两个侦测器分别检测到对脸的侦测器的变化，添加位于 gt 2 的计划刻事件。这个事件可能是用于熄灭侦测器，也有可能是用于点亮侦测器，不过这并不影响
2 TT.0 计划刻队列由 n 个沙子的事件以及 2 个侦测器的事件组成，其长度 > 65536。游戏仅执行了前 65536 个计划刻事件吗，其余的 n - 65536 个计划刻事件，及侦测器的计划刻事件被推迟到下一个游戏刻执行
3 TT.0 其余的 n - 65536 个计划刻事件及侦测器的计划刻事件依次执行。我们获得了延迟了 3gt 才执行的侦测器。装置两侧的 4gt 对脸侦测器时钟从异步 1gt 变为同步或是异步 2gt
无线红石检测装置检测到执行到了时序，输出信号

不过，这一类装置仅可滞后计划刻事件的执行，不能让计划刻事件消失

3.6.2 随机刻伪造

也不知道是历史遗留问题还是代码的复用问题，在游戏中，每个方块被随机刻选中时所调用的默认方法是其执行计划刻事件时所调用的方法 net.minecraft.block.Block#tick

1
2
3
4
5
6
7
8
9
10
@Deprecated
public void randomTick(IBlockState state, World worldIn, BlockPos pos, Random random)
{
    this.tick(state, worldIn, pos, random);
}

@Deprecated
public void tick(IBlockState state, World worldIn, BlockPos pos, Random random)
{
}

那些既可以响应随机刻，又可以响应计划刻的方块，在执行 tick 方法的时候，是怎么确认它该执行哪一部分的逻辑呢？Mojang 给出的答案是，在 tick 方法内即时判断

以仙人掌为例。作为一种作物，仙人掌会在被随机刻选中时执行一次生长；作为一种对环境有依赖的植物，在发现其状态不适合生长时（沙子消失/水平毗邻 4 格方块存在可阻挡仙人掌生长的方块），会添加一个延迟为 1 的计划刻事件，用于变为空气并掉落物品，也用于使高耸入云的仙人掌柱能自底向上逐个破坏而减轻服务器的瞬时压力

仙人掌柱被破坏

仙人掌 tick 方法内的逻辑如下所示（net.minecraft.block.BlockCactus#tick）

1
2
3
4
5
6
7
8
9
10
11
public void tick(IBlockState state, World worldIn, BlockPos pos, Random random)
{
    if (!state.isValidPosition(worldIn, pos))  // 判断仙人掌所处位置是否合法
    {
        worldIn.destroyBlock(pos, true);  // 破坏该仙人掌方块
    }
    else
    {
        /* 执行仙人掌生长逻辑 */
    }
}

粗略一看，这个实现好像并没有问题，因为状态不合法而添加的计划刻事件在执行 tick 方法时就会在第一行的 if 判断中进入到破坏仙人掌方块分支

不过仔细一想，并非如此。仙人掌在添加计划刻事件时所处位置不合法，并不意味着仙人掌在执行计划刻事件的时候所处位置仍不合法！如果我们通过某种手段，在仙人掌添加了用于破坏自身的计划刻事件后，在计划刻事件执行前，恢复仙人掌的生长环境，让仙人掌所处位置恢复到合法的适宜仙人掌生长的状态，则这个计划刻执行的时候将会执行随机刻的逻辑。这，就是随机刻伪造，也就算作物的强制催熟

下面是一个仙人掌强制催熟装置的示意图。指向仙人掌的活塞每 0t 伸出一次，即可让仙人掌使用计划刻事件伪造一次随机刻事件，使其生长阶段 +1

强制催熟

时序分析如下：

游戏刻 游戏阶段 事件
0 BE.0 [3] 指向仙人掌的活塞开始伸出，活塞前方发出方块更新，更新到仙人掌方块。仙人掌检查自身状态，发现水平毗邻的方块存在一个活塞头，会阻挡生长，于是添加一个延迟为 1 的计划刻事件用于破坏自身
0 BE.2 [3:1] 指向仙人掌的活塞开始收回，活塞前方方块变为空气。此时仙人掌所处位置状态变为合法
1 TT 仙人掌执行其 tick 方法，判断所处位置是否合法，结果是合法，则执行随机刻相关的逻辑，生长阶段 +1

这就是强制催熟仙人掌的时序分析。由于仙人掌的计划刻延迟为 1gt，我们最快每秒可进行 $20 / 1 = 20$ 次强制催熟，也就是在忽略随机刻作用的前提下，需要 16 次生长才可增高的仙人掌一小时即可长高 $3600 * 20 / 16 = 4500$ 次，效率远超传统的自然生长仙人掌农田

随机刻伪造在1.16中被修复，各种对随机刻有响应的方块执行随机刻相关逻辑的代码被移至了 randomTick 方法中

  1. 在实际的代码实现中，65536 这个限制是在循环开始前就应用了 ↩︎

  2. 在具体代码实现中，计划刻事件在检查的第三步已经创建，以便于判断计划刻队列中是否存在相同的事件 ↩︎

  3. BE.x 表示方块事件阶段中，深度 = x 的方块事件执行时的阶段，将在第四章方块事件中作进一步的解释 ↩︎ ↩︎