【Minecraft】強模ADC簡析（上）

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

本文大致分析一下這兩期視頻的背后思路與部分結(jié)論。

分為上下兩期，分別介紹思路選擇與具體實現(xiàn)。

第一期可能涉及的背景知識：紅石基礎(chǔ)（1.13+）、比較器使用方法。

本文可能涉及到的游戲代碼為MCP-Reborn生成，游戲版本為Java 1.16.5。

背景：

關(guān)于比較器：MC中比較器可以對后方輸入信號與側(cè)方輸入信號進行比較運算或減法運算，并向前方輸出運算結(jié)果，每次運算有固定的2gametick延遲。

關(guān)于無延遲比較器：簡單來說，通過控制計劃刻事件，可以讓一系列比較器瞬間亮起，而不用等待每個比較器固有的2 gt延遲?？梢栽贔allen_Breath的《深度剖析Minecraft》系列了解技術(shù)細(xì)節(jié)。

關(guān)于強模：MC中的紅石信號強度并不局限于紅石粉可以看到的0-15共16個。實際上，一個方塊的充能強度可以從0到2147483647 (Java 32位int最大有效值) 不等，這些信號在生存中的大多數(shù)情況下難以出現(xiàn)，有效利用也相對困難。

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

由于比較器與容器交互時，輸出的強度基本由【容器填滿的程度】決定，具體計算公式可查閱Minecraft Wiki。比如理論上一個潛影盒27個儲物格最多放27把剪刀，這時比較器就檢測并輸出理論上的最高強度15。因此，如果能將本來不可堆疊的物品進行堆疊，就在容器“本該塞滿”的時候再塞一些物品，這時比較器可以輸出超過15的信號。只有比較器能正確運算、傳輸強模信號。

我看到的最早在原版生存實現(xiàn)堆疊不可堆疊物品是Rays Works在1.12實現(xiàn)的；在1.14+版本中，由于MC-157133的存在，砂輪可以很方便地堆疊詛咒附魔書，這個bug截止2023年3月大概還是沒修。

生存模式的簡單強模是令人振奮的，這為有效運用奠定了基礎(chǔ)。

正文：

MC中常見的一種模數(shù)轉(zhuǎn)換思路是【并行比較】。

利用比較器每經(jīng)過1級將信號強度減1，實現(xiàn)信號區(qū)分。配合無延遲比較器可以實現(xiàn)瞬時的模數(shù)轉(zhuǎn)換，運算效率很高。

但一方面，雖然它可以滿足生存模式的需要，但它還沒有配備優(yōu)先編碼器，不算徹底的模數(shù)轉(zhuǎn)換；另一方面，在信號強度很大的強模環(huán)境下，這種與信號強度呈線性關(guān)系的空間占用難以接受，強度為200的強模信號需要長達(dá)400格的處理空間，甚至有可能超出游戲的加載范圍。

?

我們希望得到一種體積更小的結(jié)構(gòu)，來實現(xiàn)一種適用強模的模數(shù)轉(zhuǎn)換。在Minecraft中除法器體積龐大而效率低下，我對此也了解不深，最終沒有采用；轉(zhuǎn)而，類似【逐次比較】的思路可以做到對數(shù)級的空間復(fù)雜度。

但強模信號只能水平方向傳輸，且在比較器環(huán)中儲存也使得輾轉(zhuǎn)比較寄存器的方法不太現(xiàn)實，不過這種逐次比較的思路倒是沿用到了最后。

?

修改后的思路大體上是這樣的：提前規(guī)定模擬信號可以取到的最大值（通常取2^n-1，n為一個較小的正整數(shù)）和最低值（取0），然后將最大值與最低值的差值區(qū)間逐級進行二等分，直到達(dá)到最高精度，記錄過程中二分的順序即可得到二進制表示。

?

讓我們看一個簡單的例子：

假設(shè)最大信號為15 (準(zhǔn)確地說，2^4-1)，二進制為1111；最小信號為0，二進制為0000.

假設(shè)我們想要處理的信號為11，二進制表示為xxxx.

第一步：先將含有16個離散強度的[0,15]區(qū)間進行二分，分為兩個各自含8個離散強度的區(qū)間[0,7]與[8,15]，考察11落在第二個區(qū)間里，11的二進制第一位為1，二進制表示為1xxx.

第二步：將剛才11落在的區(qū)間[8,15]二分為[8,11]與[12,15]，考察11落在前一個區(qū)間里，11的二進制第二位為0，二進制表示為10xx.

…

不難看出這就是二分法。四次比較后，我們便可以得到11的二進制表示為1011。

這種方法大大降低了空間復(fù)雜度，與輸入信號強度呈對數(shù)O(logN)或者與輸出位數(shù)呈線性O(shè)(n)。

不難察覺幾個問題：一方面，如此多的條件判斷、區(qū)間修改與分支轉(zhuǎn)移體積龐大；另一方面，后一步的輸入需要等待前一步的輸出，這種單步的模數(shù)轉(zhuǎn)換速度慢的出奇。還有另外的一些問題，它們有的依托游戲設(shè)計得到了解決，比如我們最終將條件判斷的不同分支合并為層級的條件減法；有的歸結(jié)為游戲設(shè)計的遺憾，比如運算過程的限制。