【Minecraft】强模ADC简析（上）

2023-03-03 20:15 作者:卵夫子version2 0人读过 | 我要投稿

本文大致分析一下这两期视频的背后思路与部分结论。

分为上下两期，分别介绍思路选择与具体实现。

第一期可能涉及的背景知识：红石基础（1.13+）、比较器使用方法。

本文可能涉及到的游戏代码为MCP-Reborn生成，游戏版本为Java 1.16.5。

背景：

关于比较器：MC中比较器可以对后方输入信号与侧方输入信号进行比较运算或减法运算，并向前方输出运算结果，每次运算有固定的2gametick延迟。

关于无延迟比较器：简单来说，通过控制计划刻事件，可以让一系列比较器瞬间亮起，而不用等待每个比较器固有的2 gt延迟。可以在Fallen_Breath的《深度剖析Minecraft》系列了解技术细节。

关于强模：MC中的红石信号强度并不局限于红石粉可以看到的0-15共16个。实际上，一个方块的充能强度可以从0到2147483647 (Java 32位int最大有效值) 不等，这些信号在生存中的大多数情况下难以出现，有效利用也相对困难。

（IDEA截图插件真的不好用）

由于比较器与容器交互时，输出的强度基本由【容器填满的程度】决定，具体计算公式可查阅Minecraft Wiki。比如理论上一个潜影盒27个储物格最多放27把剪刀，这时比较器就检测并输出理论上的最高强度15。因此，如果能将本来不可堆叠的物品进行堆叠，就在容器“本该塞满”的时候再塞一些物品，这时比较器可以输出超过15的信号。只有比较器能正确运算、传输强模信号。

我看到的最早在原版生存实现堆叠不可堆叠物品是Rays Works在1.12实现的；在1.14+版本中，由于MC-157133的存在，砂轮可以很方便地堆叠诅咒附魔书，这个bug截止2023年3月大概还是没修。

生存模式的简单强模是令人振奋的，这为有效运用奠定了基础。

正文：

MC中常见的一种模数转换思路是【并行比较】。

利用比较器每经过1级将信号强度减1，实现信号区分。配合无延迟比较器可以实现瞬时的模数转换，运算效率很高。

但一方面，虽然它可以满足生存模式的需要，但它还没有配备优先编码器，不算彻底的模数转换；另一方面，在信号强度很大的强模环境下，这种与信号强度呈线性关系的空间占用难以接受，强度为200的强模信号需要长达400格的处理空间，甚至有可能超出游戏的加载范围。

我们希望得到一种体积更小的结构，来实现一种适用强模的模数转换。在Minecraft中除法器体积庞大而效率低下，我对此也了解不深，最终没有采用；转而，类似【逐次比较】的思路可以做到对数级的空间复杂度。

但强模信号只能水平方向传输，且在比较器环中储存也使得辗转比较寄存器的方法不太现实，不过这种逐次比较的思路倒是沿用到了最后。

修改后的思路大体上是这样的：提前规定模拟信号可以取到的最大值（通常取2^n-1，n为一个较小的正整数）和最低值（取0），然后将最大值与最低值的差值区间逐级进行二等分，直到达到最高精度，记录过程中二分的顺序即可得到二进制表示。

让我们看一个简单的例子：

假设最大信号为15 (准确地说，2^4-1)，二进制为1111；最小信号为0，二进制为0000.

假设我们想要处理的信号为11，二进制表示为xxxx.

第一步：先将含有16个离散强度的[0,15]区间进行二分，分为两个各自含8个离散强度的区间[0,7]与[8,15]，考察11落在第二个区间里，11的二进制第一位为1，二进制表示为1xxx.

第二步：将刚才11落在的区间[8,15]二分为[8,11]与[12,15]，考察11落在前一个区间里，11的二进制第二位为0，二进制表示为10xx.

…

不难看出这就是二分法。四次比较后，我们便可以得到11的二进制表示为1011。

这种方法大大降低了空间复杂度，与输入信号强度呈对数O(logN)或者与输出位数呈线性O(n)。

不难察觉几个问题：一方面，如此多的条件判断、区间修改与分支转移体积庞大；另一方面，后一步的输入需要等待前一步的输出，这种单步的模数转换速度慢的出奇。还有另外的一些问题，它们有的依托游戏设计得到了解决，比如我们最终将条件判断的不同分支合并为层级的条件减法；有的归结为游戏设计的遗憾，比如运算过程的限制。