深度剖析Minecraft #3 計(jì)劃刻
前往我的博客獲得更好的markdown瀏覽體驗(yàn)以及更為長(zhǎng)期的更新支持：
https://fallenbreath.me/2020/09/16/deeply-dissecting-minecraft_3/
3 計(jì)劃刻
3.1 什么是計(jì)劃刻
計(jì)劃刻，英文為 Tile Tick。國(guó)內(nèi)社區(qū)曾用 Next Tick Entry (NTE) 進(jìn)行描述
在 Minecraft 中，許多方塊對(duì)變化的響應(yīng)并不是瞬時(shí)，而是延遲一定時(shí)間后方才開始執(zhí)行的，如下面幾個(gè)常見的例子：
中繼器響應(yīng)信號(hào)輸入
沙子檢測(cè)下方方塊以準(zhǔn)備下落
流體進(jìn)行流動(dòng)
懸空腳手架的逐個(gè)掉落
對(duì)于這一類具有共性的延遲執(zhí)行的事件，Minecraft 使用計(jì)劃刻這一概念進(jìn)行統(tǒng)一的管理，每一個(gè)緯度的計(jì)劃刻管理系統(tǒng)都是相互獨(dú)立的
1.13 前，方塊和流體共用一個(gè)計(jì)劃刻管理系統(tǒng)進(jìn)行儲(chǔ)存，1.13 及以后，方塊和流體為獨(dú)立的計(jì)劃刻管理系統(tǒng)
3.2 計(jì)劃刻的實(shí)現(xiàn)原理
3.2.1 計(jì)劃刻管理系統(tǒng)
一個(gè)計(jì)劃刻管理系統(tǒng)，是一個(gè)包含了一套完善的與計(jì)劃刻相關(guān)的狀態(tài)、容器的對(duì)象，類名如下
net.minecraft.world.ServerTickList (1.13.2 mcp)
net.minecraft.server.world.ServerTickScheduler (1.15.2 yarn)
其中，有三個(gè)儲(chǔ)存著計(jì)劃刻事件的容器是我們所關(guān)注的：
名稱屬性名類型用途計(jì)劃刻隊(duì)列pendingTickListEntriesTreeSetTreeSet可視作一個(gè)優(yōu)先隊(duì)列，用于有序地儲(chǔ)存計(jì)劃刻事件計(jì)劃刻隊(duì)列附屬哈希表pendingTickListEntriesHashSetHashSet用于快速判斷計(jì)劃刻事件是否在計(jì)劃刻隊(duì)列中即將執(zhí)行事件列表pendingTickListEntriesThisTickArrayList儲(chǔ)存著即將在某個(gè)游戲刻執(zhí)行的計(jì)劃刻事件
3.2.2 計(jì)劃刻事件
對(duì)于一個(gè)計(jì)劃刻事件（net.minecraft.world.NextTickListEntry）來(lái)說(shuō)，它具有以下屬性
事件 id，一個(gè)遞增的不重復(fù)整數(shù)
目標(biāo)方塊/流體類型
方塊/流體的方塊坐標(biāo)
事件計(jì)劃執(zhí)行的游戲刻
事件優(yōu)先級(jí)
事件優(yōu)先級(jí)一共有 7 種可能的取值，從 -3 至 +3，如下所示
由其中可看出，每個(gè)計(jì)劃刻事件所儲(chǔ)存的屬性其實(shí)并不是十分詳細(xì)，不少事件的具體細(xì)節(jié)是沒有儲(chǔ)存起來(lái)的，如：
計(jì)劃刻事件僅儲(chǔ)存了方塊的種類，未儲(chǔ)存方塊狀態(tài)
計(jì)劃刻事件未儲(chǔ)存該事件將要執(zhí)行什么動(dòng)作，也即在該事件真正執(zhí)行前游戲是不知道這個(gè)事件具體會(huì)引發(fā)什么動(dòng)作的
3.2.2.1 計(jì)劃刻事件間的比較
兩個(gè)計(jì)劃刻事件是相同的（equals?方法），當(dāng)且僅當(dāng)這兩個(gè)事件的以下屬性相同
目標(biāo)方塊/流體類型
方塊/流體的方塊坐標(biāo)
這將用在判斷事件是否存在于?即將執(zhí)行的事件列表（一個(gè)?ArrayList）中
在判斷事件的大小關(guān)系時(shí)（compareTo?方法），按照以下關(guān)鍵字依次比較：
執(zhí)行時(shí)刻，較小者優(yōu)先
事件優(yōu)先級(jí)
事件 id，較小者優(yōu)先
這將用在計(jì)劃刻隊(duì)列（一個(gè)?TreeSet）的實(shí)現(xiàn)中
3.2.3 計(jì)劃刻階段
每游戲刻中，計(jì)劃刻階段的執(zhí)行入口是?net.minecraft.world.WorldServer#tickPending。其中，先處理方塊的計(jì)劃刻階段，再處理流體相關(guān)的計(jì)劃刻階段
在計(jì)劃刻階段里，游戲?qū)凑帐录?yōu)先級(jí)從高到底的順序執(zhí)行將在此游戲刻中執(zhí)行的計(jì)劃刻事件。若優(yōu)先級(jí)相同，則比較事件的id，id較小的先執(zhí)行
具體實(shí)現(xiàn)是比較樸素的。Minecraft 使用了一個(gè) TreeSet（使用紅黑樹實(shí)現(xiàn)的二叉平衡樹）作為該緯度所有計(jì)劃刻事件的容器
因?yàn)樵诖a中，不存在直接刪改該容器某個(gè)具體元素的用法，僅存在插入元素及取出最小元素這兩個(gè)操作，因此即便這個(gè)容器不是明面上的一個(gè)隊(duì)列， 它仍可被視為一個(gè)隊(duì)列，或者更準(zhǔn)確的，優(yōu)先隊(duì)列。這也是計(jì)劃刻隊(duì)列這一詞的來(lái)由
TreeSet 的時(shí)間復(fù)雜度是 O(nlogn)，這意味著實(shí)際上計(jì)劃刻元件的卡頓并非線性增加的，不過(guò)在實(shí)際情況下由于 logn 變化極小，仍可以大致認(rèn)為卡頓是線性增加的
下面以方塊的計(jì)劃刻階段為例，核心流程如下：
1. 檢索應(yīng)在該游戲刻執(zhí)行的事件
????1. 取出計(jì)劃刻隊(duì)列中位于最前的事件（比較方法見上方所列的優(yōu)先級(jí)）
????2. 若當(dāng)前的游戲時(shí)間小于該事件的執(zhí)行時(shí)刻，或者本計(jì)劃刻階段已取出了 65536 個(gè)計(jì)劃刻事件[^1]，則退出循環(huán)，跳出循環(huán)。超過(guò)上限的事件將會(huì)延遲到下一游戲刻嘗試執(zhí)行
???? 3. 將該事件，暫存入一個(gè)即將執(zhí)行的事件列表
第一步執(zhí)行完后，游戲已經(jīng)確認(rèn)下來(lái)了這個(gè)游戲刻中將執(zhí)行哪些計(jì)劃刻事件。注意到這些事件已經(jīng)被移出了計(jì)劃刻隊(duì)列，因此一個(gè)新的相同的計(jì)劃刻事件現(xiàn)在是可以添加成功了（計(jì)劃刻事件添加的判據(jù)見?3.2.4 計(jì)劃刻事件的添加）
2. 處理即將執(zhí)行的事件列表
????- 對(duì)于列表中每個(gè)計(jì)劃刻事件，若事件的方塊的坐標(biāo)所在區(qū)塊處于加載狀態(tài)，則：
????????1. 判斷世界中此坐標(biāo)的方塊是否仍與該事件的方塊類型相同，如果相同，則調(diào)用該方塊的 tick 方法
????- 若坐標(biāo)所在的區(qū)塊未加載，則：
????????1. 添加一個(gè)計(jì)劃刻事件，屬性為：
????????????- 坐標(biāo)：該事件的坐標(biāo)
????????????- 方塊：該事件的方塊
????????????- 延遲：0
????????????- 優(yōu)先級(jí)：0
????????????不過(guò)此計(jì)劃刻事件不會(huì)添加成功，因?yàn)榇耸录淖鴺?biāo)所在區(qū)塊未被加載。至于為何要實(shí)現(xiàn)此邏輯，仍有待考究
3.?計(jì)劃刻階段結(jié)束
[^1]: 在實(shí)際的代碼實(shí)現(xiàn)中，65536 這個(gè)限制是在循環(huán)開始前就應(yīng)用了
為了讓表述更流暢，上述描述并非與源代碼 100% 對(duì)應(yīng)的分析，但是其效果是等價(jià)的。具體代碼可見：
net.minecraft.world.ServerTickList#tick (1.13.2 mcp)
net.minecraft.server.world.ServerTickScheduler#tick (1.15.2 yarn)
3.2.4 計(jì)劃刻事件的添加
若要添加一個(gè)計(jì)劃刻事件，需要傳入以下的參數(shù)：
方塊/流體的坐標(biāo)
方塊/流體的類型
執(zhí)行延遲
事件優(yōu)先級(jí)。若未指定則為默認(rèn)值 0
隨后，游戲會(huì)依次執(zhí)行下述步驟判斷此次添加是否合法：
若添加的是方塊計(jì)劃刻事件，則該事件方塊不可為空氣；若添加的是流體計(jì)劃刻事件，則流體不可為空
事件所在坐標(biāo)的區(qū)塊處于已加載狀態(tài)
計(jì)劃刻隊(duì)列中不存在相同的事件
最后，一個(gè)新的計(jì)劃刻事件將會(huì)創(chuàng)建并加入至計(jì)劃刻隊(duì)列中 [^2]，其方塊/流體的類型與坐標(biāo)即為所給值，而執(zhí)行時(shí)刻則從給出的執(zhí)行延遲計(jì)算得到，為?執(zhí)行延遲 + 該緯度當(dāng)前的游戲時(shí)間
[^2]: 在具體代碼實(shí)現(xiàn)中，計(jì)劃刻事件在檢查的第三步已經(jīng)創(chuàng)建，以便于判斷計(jì)劃刻隊(duì)列中是否存在相同的事件
3.2.5 計(jì)劃刻事件的刪除
計(jì)劃刻事件在添加入計(jì)劃刻隊(duì)列后，是不會(huì)直接被游戲刪除的，即便原方塊/流體已經(jīng)被改變。游戲中唯一類似刪除計(jì)劃刻事件的地方，是由于事件所處的區(qū)塊被卸載，從而導(dǎo)致執(zhí)行該事件的時(shí)候被游戲移除隊(duì)列且不再加入隊(duì)列不過(guò)放心，在區(qū)塊卸載保存的時(shí)候，計(jì)劃刻隊(duì)列是會(huì)保存至磁盤的，因此不需要擔(dān)心計(jì)劃刻元件的動(dòng)作被丟失了
計(jì)劃刻事件的不易被刪除特性，在某些情況下是可以利用的
3.3 計(jì)劃刻事件執(zhí)行順序
3.3.1 單個(gè)元件
事件間比較大小的關(guān)鍵字依次為：
執(zhí)行時(shí)刻，較小者優(yōu)先
事件優(yōu)先級(jí)
事件 id，較小者優(yōu)先
按照這三個(gè)關(guān)鍵字，我們可以很輕易地判斷兩個(gè)計(jì)劃刻事件間的執(zhí)行先后。前兩個(gè)關(guān)鍵字很容易獲得，但是第三個(gè)關(guān)鍵字并為直接給出，因此不能在前兩個(gè)關(guān)鍵字相同的情況下，并不能直觀地判斷孰先孰后
觀察?事件 id?的定義，這是一個(gè)遞增的不重復(fù)的整數(shù)，因此，先創(chuàng)建的計(jì)劃刻事件一定會(huì)有較小的?事件 id?，也就是在執(zhí)行時(shí)刻與事件優(yōu)先級(jí)相同的情況下，先創(chuàng)建的事件會(huì)優(yōu)先于后創(chuàng)建的事件執(zhí)行
也就是先進(jìn)先出！
下面是一些例子：
執(zhí)行時(shí)刻，A 先于 B，因此 A 先執(zhí)行
執(zhí)行時(shí)刻：A 與 B 相同
優(yōu)先級(jí)：A 大于B
因此 A 先執(zhí)行
執(zhí)行時(shí)刻：相同
優(yōu)先級(jí)：相同
創(chuàng)建順序（事件 id）：A 先于 B
因此 A 先執(zhí)行
3.3.2 多元件組合
在總延遲相同的前提下，用不同檔位湊出來(lái)的中繼器/比較器/序列誰(shuí)先輸出信號(hào)，是一個(gè)老生常談的問題，比如下圖
由于總延遲是相同的，并且最末端的元件具有相同的優(yōu)先級(jí)，我們不能簡(jiǎn)單地觀察最末端的元件來(lái)判斷執(zhí)行順序，我們需要結(jié)合其余元件進(jìn)行考慮，得出最末端元件創(chuàng)建事件的順序間的先后關(guān)系，從而得到執(zhí)行順序
由于在這些判斷順序的實(shí)例中，第 n 個(gè)元件的計(jì)劃刻事件創(chuàng)建事件往往是與第 n - 1 個(gè)元件的點(diǎn)亮?xí)r刻是相同的，因此可以用低 n -1 個(gè)元件的點(diǎn)亮?xí)r刻來(lái)替代第 n 個(gè)元件的創(chuàng)建事件時(shí)刻
令拉桿拉下的時(shí)刻為 gt0。由于序列 A 的第一個(gè)中繼器是在 gt2 點(diǎn)亮，而序列 B 的第一個(gè)中繼器是在 gt 8 點(diǎn)亮，晚于序列 A 的第一個(gè)中繼器，因此序列 A 的第二個(gè)也就是末端的中繼器先于序列 B 的末端中繼器激活
如果還有更多的元件呢，那我們繼續(xù)比較下去！
若次末端的元件點(diǎn)亮?xí)r刻與優(yōu)先級(jí)均相同，則判斷倒數(shù)第三個(gè)元件的點(diǎn)亮先后順序
若倒數(shù)第三個(gè)元件的元件點(diǎn)亮?xí)r刻與優(yōu)先級(jí)均相同，則判斷倒數(shù)第四個(gè)元件的點(diǎn)亮先后順序
……
也就是，從尾到頭依次比較元件的點(diǎn)亮順序，直到比較出結(jié)果
若比較的兩個(gè)序列的元件是同一個(gè)元件，這時(shí)比較更新順序即可。如一個(gè)拉桿向兩側(cè)引出 1 擋中繼器，這是就需要根據(jù)方塊更新的順序來(lái)判斷哪一側(cè)的中繼器先被更新
下面是一些例子：
末端的中繼器的優(yōu)先級(jí)及點(diǎn)亮?xí)r間均相同，比較前端的中繼器點(diǎn)亮?xí)r間：A 先，因此 A 序列比 B 序列先輸出
A, B 與 C, D, E 的比較與上圖相同，對(duì)于 A, B，第一個(gè)元件點(diǎn)亮的優(yōu)先級(jí)是 A 的中繼器更高，因此 A 比 B 先輸出?？傒敵鲰樞?yàn)?A, B, C, D, E
根據(jù)最末端元件的優(yōu)先級(jí)可立即得到 A, B, C 比 D, E 先輸出。A 的中繼器最先得到輸入信號(hào)，因此 A 最先輸出。剩余序列比較方法同上，比較第一個(gè)元件的優(yōu)先級(jí)即可得出總輸出順序?yàn)?A, B, C, D, E
3.4 計(jì)劃刻元件
見《深度剖析Minecraft #3.4 計(jì)劃刻元件》
【施工中】
【TODO】
【Coming s∞n】
【Happy Lazy】
3.5 時(shí)序描述
在分析計(jì)劃刻相關(guān)的時(shí)序的時(shí)候，計(jì)劃刻事件的優(yōu)先級(jí)以及計(jì)劃刻事件的目標(biāo)常常是我們關(guān)心的因素
對(duì)于一個(gè)優(yōu)先級(jí)為 x ，目標(biāo)為 y 的計(jì)劃刻事件，下面使用記號(hào) TileTick.priority=x,target=y，或者簡(jiǎn)稱 TT.x.y 來(lái)表示該事件執(zhí)行時(shí)所處在的游戲階段。在不關(guān)心優(yōu)先級(jí)或者目標(biāo)的場(chǎng)合中，.x .y 是可以視情況選擇省略的。在大多數(shù)情況下，時(shí)序精度劃分至計(jì)劃刻階段或者計(jì)劃刻優(yōu)先級(jí)，就已經(jīng)足夠了。
例如，對(duì)于單個(gè)紅石中繼器的點(diǎn)亮事件，其發(fā)生的游戲階段為 TT.-1
當(dāng)然，也可使用計(jì)劃刻的舊稱 NTE 來(lái)替換上述的 TT
3.6 計(jì)劃刻性質(zhì)的應(yīng)用
3.6.1 計(jì)劃刻滯后/EMP
More like a redstone EMP
—— Casper2002 @?https://youtu.be/1GWaZ5vEd3A
在分析計(jì)劃刻階段的流程時(shí)，細(xì)心的讀者可能已經(jīng)注意到了，每游戲刻可執(zhí)行的計(jì)劃刻事件數(shù)量有個(gè) 65536 的上限，超過(guò)上限的事件將會(huì)延遲到下一游戲刻嘗試執(zhí)行，這一點(diǎn)似乎是可以加以利用的
如果我們認(rèn)為的在某一游戲刻中添加了巨量的延遲相同的計(jì)劃刻事件，使其數(shù)量超過(guò)了 65536，則可在游戲中制造一些正常情況下不可能發(fā)生的事情：某些計(jì)劃刻事件被延后執(zhí)行了。這可以用于無(wú)線紅石信號(hào)傳輸、無(wú)限遙控飛行器，也可以用惡意破壞紅石電路。該機(jī)制的作用范圍是整個(gè)維度
下面以該機(jī)制發(fā)現(xiàn)者 Xcom6000 的《原版生存無(wú)線紅石》為例，分析下其時(shí)序
不過(guò)，這一類裝置僅可滯后計(jì)劃刻事件的執(zhí)行，不能讓計(jì)劃刻事件消失
3.6.2 隨機(jī)刻偽造
也不知道是歷史遺留問題還是代碼的復(fù)用問題，在游戲中，每個(gè)方塊被隨機(jī)刻選中時(shí)所調(diào)用的默認(rèn)方法是其執(zhí)行計(jì)劃刻事件時(shí)所調(diào)用的方法?net.minecraft.block.Block#tick
那些既可以響應(yīng)隨機(jī)刻，又可以響應(yīng)計(jì)劃刻的方塊，在執(zhí)行?tick?方法的時(shí)候，是怎么確認(rèn)它該執(zhí)行哪一部分的邏輯呢？Mojang 給出的答案是，在?tick?方法內(nèi)即時(shí)判斷
以仙人掌為例。作為一種作物，仙人掌會(huì)在被隨機(jī)刻選中時(shí)執(zhí)行一次生長(zhǎng)；作為一種對(duì)環(huán)境有依賴的植物，在發(fā)現(xiàn)其狀態(tài)不適合生長(zhǎng)時(shí)（沙子消失/水平毗鄰 4 格方塊存在可阻擋仙人掌生長(zhǎng)的方塊），會(huì)添加一個(gè)延遲為 1 的計(jì)劃刻事件，用于變?yōu)榭諝獠⒌袈湮锲?，也用于使高聳入云的仙人掌柱能自底向上逐個(gè)破壞而減輕服務(wù)器的瞬時(shí)壓力
仙人掌?tick?方法內(nèi)的邏輯如下所示（net.minecraft.block.BlockCactus#tick）
粗略一看，這個(gè)實(shí)現(xiàn)好像并沒有問題，因?yàn)闋顟B(tài)不合法而添加的計(jì)劃刻事件在執(zhí)行?tick?方法時(shí)就會(huì)在第一行的 if 判斷中進(jìn)入到破壞仙人掌方塊分支
不過(guò)仔細(xì)一想，并非如此。仙人掌在添加計(jì)劃刻事件時(shí)所處位置不合法，并不意味著仙人掌在執(zhí)行計(jì)劃刻事件的時(shí)候所處位置仍不合法！如果我們通過(guò)某種手段，在仙人掌添加了用于破壞自身的計(jì)劃刻事件后，在計(jì)劃刻事件執(zhí)行前，恢復(fù)仙人掌的生長(zhǎng)環(huán)境，讓仙人掌所處位置恢復(fù)到合法的適宜仙人掌生長(zhǎng)的狀態(tài)，則這個(gè)計(jì)劃刻執(zhí)行的時(shí)候?qū)?huì)執(zhí)行隨機(jī)刻的邏輯。這，就是隨機(jī)刻偽造，也就算作物的強(qiáng)制催熟
下面是一個(gè)仙人掌強(qiáng)制催熟裝置的示意圖。指向仙人掌的活塞每 0t 伸出一次，即可讓仙人掌使用計(jì)劃刻事件偽造一次隨機(jī)刻事件，使其生長(zhǎng)階段 +1
時(shí)序分析如下：
這就是強(qiáng)制催熟仙人掌的時(shí)序分析。由于仙人掌的計(jì)劃刻延遲為 1gt，我們最快每秒可進(jìn)行?20/1=20?次強(qiáng)制催熟，也就是在忽略隨機(jī)刻作用的前提下，需要 16 次生長(zhǎng)才可增高的仙人掌一小時(shí)即可長(zhǎng)高?3600?20/16=4500?次，效率遠(yuǎn)超傳統(tǒng)的自然生長(zhǎng)仙人掌農(nóng)田
隨機(jī)刻偽造在1.16中被修復(fù)，各種對(duì)隨機(jī)刻有響應(yīng)的方塊執(zhí)行隨機(jī)刻相關(guān)邏輯的代碼被移至了?randomTick?方法中
[^3]: BE.x 表示方塊事件階段中，深度 = x 的方塊事件執(zhí)行時(shí)的階段，將在第四章方塊事件中作進(jìn)一步的解釋
