Minecraft基巖版紅石系統(tǒng)設(shè)計簡述
這期主要是對之前幾篇的總結(jié)和補(bǔ)完，有大量重復(fù)內(nèi)容，應(yīng)該會比較長，不管有沒有屁用的細(xì)節(jié)都提一嘴。
1. 紅石系統(tǒng)是如何產(chǎn)生的
1.1 信號和響應(yīng)分離的設(shè)計模式
獨(dú)立運(yùn)作，基本互不影響。負(fù)責(zé)信號的部分叫電路原件(Circuit Component),所有與紅石相關(guān)的方塊都包含這一原件的子類；負(fù)責(zé)響應(yīng)的部分可能是方塊(Block)，也可能是方塊實(shí)體(Block Actor)，這部分和其他一般功能性方塊沒有區(qū)別。
在游戲主循環(huán)中，同一gt內(nèi)紅石信號計算和響應(yīng)是在不同的階段完成的，這里姑且將其稱之為信號更新階段和響應(yīng)階段（包含方塊實(shí)體響應(yīng)和方塊響應(yīng)），下圖表明了這些階段在主循環(huán)中的相對位置。
(請暫時先無視圖中的“依賴更新”階段，后文再提及)
其中響應(yīng)階段中原件根據(jù)自身的紅石信號值（從電路原件中獲取）判定接下來的行為。能接受響應(yīng)的原件本質(zhì)上是一個接受外部輸入的狀態(tài)機(jī)，這個狀態(tài)機(jī)每隔1gt更新一次，但是外部輸入（也就是紅石信號）2gt才更新一次，因此狀態(tài)機(jī)的響應(yīng)是有延遲的，這也說明了為什么好多所謂的0t、瞬時現(xiàn)象在基巖版永遠(yuǎn)無法產(chǎn)生。
根據(jù)原件的自身屬性可以將響應(yīng)分為兩種：
來自方塊實(shí)體的響應(yīng)，其內(nèi)部調(diào)用函數(shù)為
XXXBlockActor.tick，常見的例子有活塞根據(jù)自身信號更新推出狀態(tài)、漏斗根據(jù)自身信號檢查是否被鎖住、發(fā)射器根據(jù)自身狀態(tài)決定是發(fā)射物品等來自非方塊實(shí)體的響應(yīng)，其內(nèi)部調(diào)用函數(shù)為
xxxBlock.onRedstoneUpdate，常見的例子有紅石線根據(jù)自身信號值更新數(shù)據(jù)值，各種門根據(jù)自身信號值修改開關(guān)狀態(tài)等。
而信號階段表示電路原件內(nèi)部信號值的計算、緩存以及設(shè)置行為，這一階段除了修改電路原件內(nèi)部的信號值外不會產(chǎn)生任何額外行為，因此在不借助任何輔助手段的情況下玩家無法判定電路原件內(nèi)部的信號值是否發(fā)生變化，所有發(fā)生的變化都是由響應(yīng)階段產(chǎn)生，包括但不限于任何碰撞箱，貼圖等的變化。
此外，響應(yīng)階段是在區(qū)塊更新內(nèi)部完成的，而信號更新不依賴區(qū)塊加載(它的限制后文再說)，因此你看到非加載區(qū)塊外部的紅石電路一動不動，不代表其內(nèi)部的信號更新停止，只是單純沒有響應(yīng)階段而已。
接下來的全部篇幅，我們主要關(guān)注信號更新階段。
1.2. 信號的流動路徑 -- 抽象原件的形成
在Mojang的設(shè)計中，每個和紅石相關(guān)的方塊內(nèi)部都有且只有一個紅石原件，紅石原件根據(jù)其內(nèi)部信號流動的特點(diǎn)被分為四個大類:
生產(chǎn)者(Producer)：發(fā)出信號的原件,如紅石塊，拉桿，按鈕等
消費(fèi)者(Consumer)：消費(fèi)信號的原件，即只能接受生產(chǎn)者產(chǎn)生的信號并產(chǎn)生響應(yīng)的原件，如活塞，發(fā)射器等
傳輸者(Transporter)：幫助生產(chǎn)者搜索消費(fèi)者的原件，除此之外沒有實(shí)際價值，主要是紅石線
充能方塊(Powered Block)：靈活且特殊的一類，用于輔助實(shí)現(xiàn)紅石系統(tǒng)內(nèi)的充能機(jī)制
這其中有一類特殊的生產(chǎn)者，它們既能發(fā)出信號，也能消費(fèi)信號，被稱之為電容器(Capacitor)，它是Producer的子類別，全游戲中有且僅有四種電容器：紅石火把、偵測器、紅石中繼器和紅石比較器。
注意，在后面的討論中說到生產(chǎn)者是不包含電容器的。
此外，活塞是唯一一個只能從五個方向激活的消費(fèi)者，因此它屬于消費(fèi)者子類下特殊的一類（并不是因為它的推拉性質(zhì)）。
下圖展示了上述紅石原件之間的繼承和類別關(guān)系(所有的紅石原件都繼承自抽象類Base Circuit Component):
關(guān)于信號的生產(chǎn)、消費(fèi)在這里有直觀的理解和感受即可，下面講電路構(gòu)建的時候會詳述。
1.3. 從紅石原件到紅石電路 -- Mojang的網(wǎng)絡(luò)流設(shè)計
Mojang使用類似網(wǎng)絡(luò)流的模型來表達(dá)一個紅石電路。在Mojang的設(shè)計中，紅石信號是流動的、衰減的、有方向性的。紅石信號永遠(yuǎn)都是從生產(chǎn)者流向電容器，然后從電容器流向消費(fèi)者（或者跳過電容器直接流向消費(fèi)者）。且初始信號的最大值恒定為15，每流過1個邏輯距離，信號值就會衰減1。下面對這句話做簡單的解釋：
在游戲內(nèi)部用另外一個詞"源(Source)"來表示生產(chǎn)者，生產(chǎn)者就是紅石信號的源頭，負(fù)責(zé)為消費(fèi)者提供紅石信號
沒有衰減結(jié)束的紅石信號(即大于0)才會被消費(fèi)者接收，消費(fèi)者在下一個gt的響應(yīng)階段產(chǎn)生外部行為
如果只有生產(chǎn)者和消費(fèi)者，紅石系統(tǒng)的局限性是很大的，因為信號的初始強(qiáng)度、衰減能力和延遲都是恒定的，這嚴(yán)重限制了電路的規(guī)模和復(fù)雜性，而電容器的出現(xiàn)就是為了解決這一問題：電容器可以增強(qiáng)、延遲（如中繼器）紅石信號，甚至可以對紅石信號做算數(shù)和邏輯運(yùn)算（如比較器），這些機(jī)制大大豐富了紅石電路的可玩性，讓這一系統(tǒng)產(chǎn)生了更多的可能。
下面用一張圖來表明電路中信號的流動方向
看到這里，你可能會問傳輸者(transporter)去哪了，答案很簡單，傳輸者的唯一作用是輔助電路的構(gòu)建，在穩(wěn)定的紅石電路中傳輸者不會起到任何作用，這也是有些玩家觀察到連著某些原件（如發(fā)射器）的紅石線根本就沒亮過但是發(fā)射器能工作的原因。
為了后續(xù)描述方便，這里定義如下的專有名詞：如果信號從A流向B,即A是提供信號的原件，B是消費(fèi)信號的原件，那么我們稱A是B的父原件，B是A的子原件。比如，使用紅石塊激活了紅石燈，那么我們稱紅石塊是該紅石燈的父原件，紅石燈是紅石方塊的子原件。且需要明確：
生產(chǎn)者不可能有父原件，只可能有子原件
消費(fèi)者不可能有子原件，只可能有父原件
電容器父子原件都可能有
1.4. 使用有向帶權(quán)圖(森林)來描述網(wǎng)絡(luò)流
在游戲內(nèi)部Mojang采用帶權(quán)有向圖描述上述的網(wǎng)絡(luò)流架構(gòu)。在其設(shè)計中，每個維度內(nèi)部的所有原件及其連接關(guān)系構(gòu)成一張巨大的帶權(quán)有向圖（森林），(為了和源碼統(tǒng)一，下文將該圖成為電路場景圖(Circuit Scene Graph))。由于原版游戲只有三個維度，因此整個游戲?qū)嵗还仓挥腥龔堧娐穲鼍皥D，或者說三個巨大的紅石電路。MJ分兩部分來維護(hù)每張巨大的電路場景圖：
第一部分是全局的，每個電路場景圖有且僅有一個實(shí)例，可以認(rèn)為這部分信息存儲在每個維度實(shí)例內(nèi)部。下面只描述該部分內(nèi)幾個重要的結(jié)構(gòu)，剩余的等提到再補(bǔ)充
全局元件表(All Components)，記錄了整個維度所有紅石相關(guān)方塊的坐標(biāo)及其內(nèi)部的紅石原件，該數(shù)據(jù)由哈希表存儲。
能量連接表(Power Association Map)，記錄了整個維度所有的生產(chǎn)者，以及每個生產(chǎn)者的所有子原件信息，該數(shù)據(jù)也由哈希表存儲。
第二部分是局部的，是屬于每個紅石原件內(nèi)部的信息，存儲在每個紅石組件的內(nèi)部。這些信息主要包括：
該原件的位置（方塊坐標(biāo)）
該原件的所有父原件以及距離每個父原件的阻尼(Damping，表示該信號源搜索到當(dāng)前原件時衰減的信號強(qiáng)度，也就是邏輯距離，下文統(tǒng)稱距離)。
其他一些信號值
通過上述描述不難看出，原件內(nèi)部的局部信息構(gòu)成了一個使用鄰接表表示的帶權(quán)圖結(jié)構(gòu)，距離即為邊的權(quán)。
為了便于理解，這里還是用之前專欄的兩張圖來舉個例子。如圖所示的紅石電路：
在游戲內(nèi)部被描述為如下的一張帶權(quán)有向圖：
現(xiàn)在對該圖做簡單解釋：活塞有兩個父原件：紅石塊和拉桿，而且距離都是2。紅石燈沒有任何父原件，因此它在圖中是孤立的節(jié)點(diǎn)。?這一堆紅石線有相同的父原件，也就是拉桿和紅石塊
。在簡單介紹整個系統(tǒng)的設(shè)計思路后下面對整個系統(tǒng)背后的運(yùn)行機(jī)制做較為詳細(xì)的分析。
2. 電路構(gòu)建機(jī)制--依賴更新階段簡述
2.1 隊列式的構(gòu)建算法
當(dāng)玩家(或其他實(shí)體、方塊，反正是所有會影響世界的行為，下面均以“玩家”簡稱)放置一個紅石相關(guān)方塊時，游戲并不會立即創(chuàng)建屬于這個方塊的紅石原件(component)，而是將相關(guān)信息(稱為Circuit Scene Graph Redstone Pending Entry，下面簡稱更新請求)加入到電路場景圖內(nèi)的特殊隊列中。玩家破壞一個方塊的時候也是如此，游戲并不會立將其從維度電路圖移除，而是暫存到特殊隊列中。
被緩存到特殊隊列的更新請求會在游戲主循環(huán)的一個特定的階段被游戲集中處理掉，這里稱這個集中處理的階段為依賴更新階段。該階段在響應(yīng)階段之后，信號更新階段之前(見1.1的圖中虛線框)。
在依賴更新階段，電路場景圖一共有三個隊列需要處理：
依賴增加隊列(AQ)：用于暫存當(dāng)前gt內(nèi)玩家添加紅石原件的請求
依賴移除隊列(RQ)：用于暫存當(dāng)前gt內(nèi)玩家破壞紅石原件的請求
依賴更新隊列(UQ)：用于暫存前兩個隊列的的處理結(jié)果，下節(jié)詳述。
?下面分兩個階段對依賴更新階段做詳細(xì)介紹（為了方便介紹，對上述三個隊列使用AQ,RQ和UQ做簡稱）。
2.2 依賴更新階段1 -- 請求處理
一開始，AQ和RQ內(nèi)已經(jīng)緩存了有多個更新請求（數(shù)據(jù)來自上1gt的玩家行為）。游戲會優(yōu)先處理RQ再處理AQ。
處理依賴移除隊列
RQ內(nèi)存儲了需要從電路場景圖中移除的元件的位置等信息。在處RQ時，游戲會遍歷隊列內(nèi)的每個移除更新信息，對每個位置執(zhí)行如下操作(做了一定的簡化)：
從全局元件表中移除該原件的信息(移除節(jié)點(diǎn))
如果該原件是信號源/電容器的話(移除邊)
從能量連接圖中移除該原件的連接關(guān)系 (移除有向圖的正向邊(信號源->子原件))
從該原件的所有子原件的父原件表中移除該原件（移除有向圖的反向邊(子原件->信號源)）
將下列紅石原件加入UQ(如果有的話)
該原件的所有父原件
該原件的所有子原件（如果不是消費(fèi)者）
該原件六個面的所有非消費(fèi)者原件以及它們的所有父原件
由于移除了某些元件后會可能導(dǎo)致周圍部分元件的狀態(tài)（如信號，距離等）發(fā)生變化，因此才會有第3步：把可能發(fā)生狀態(tài)變化的元件暫存（即加入UQ）起來集中處理。MJ這里做的很保守，有的沒的都會加入隊列，雖然會稍微增加卡頓，但是起碼不會出現(xiàn)狀態(tài)更新不及時的情況。
處理依賴增加隊列
在處理AQ時游戲也會遍歷該列隊的每個添加更新請求，對每個位置執(zhí)行如下操作(做了一定的簡化)：
把該原件加入全局元件表(添加節(jié)點(diǎn))
將下列方塊加入依賴更新隊列(如果有的話)
如果該元件是信號源，或者電容器，直接將其加入
如果該元件是消費(fèi)者，將它們的父元件加入
如果該元件是信號源/電容器，加入該元件自身
六個面的所有原件
如果該元件是電容器，把同一平面上該元件東南、東北、西南、西北四個方向的電容器加入
對上中下三個方塊的六個面的方塊
上述步驟的邏輯也比較清晰，基本思路就是首先更新電路場景圖的節(jié)點(diǎn)和邊，最后將附近的一些生產(chǎn)者或者電容器加入UQ。
2.2 依賴更新階段2 -- 電路搜索和網(wǎng)絡(luò)構(gòu)造
依賴更新階段2的任務(wù)就是處理以依賴更新階段1中向UQ添加的更新請求。這一步的行為是
首先移除隊列內(nèi)元件和其子元件之間的關(guān)系（移除有向圖中的舊邊）
對于隊列內(nèi)的每個元件，以其為原點(diǎn)開始進(jìn)行搜索，找到它的所有子元件并更新距離等信息(添加新的邊)
依賴更新階段1中處理RQ和AQ時都向UQ中添加了部分元件信息，這些信息要么是生產(chǎn)者，要么都是電容器，因為只有這兩種才能作為“源”產(chǎn)生信號。因此第二步的邏輯才是從自身開始搜索它的子元件的過程。由于第一步比較簡單，這里不再過多介紹。下面對第二步的搜索進(jìn)行較為詳細(xì)的介紹：
基本搜索算法
注意：這一節(jié)的內(nèi)容過于復(fù)雜和零碎，筆者自己也沒完全搞懂，因此只能提供部分信息，且不保證完全正確，僅供參考。
對于UQ內(nèi)的每個信號源，MJ使用廣度優(yōu)先搜索算法(BFS)，從信號源開始，向六個方向進(jìn)行搜索。搜索過程中使用一個稱之為電路追蹤信息（Circuit Tracking Info）的數(shù)據(jù)結(jié)構(gòu)來記錄上下文，它記錄的上下文主要包含如下信息：
當(dāng)前搜索路徑的源頭，也就是信號源的信息(Power)
當(dāng)前搜索到的元件的信息(Current)
當(dāng)前搜索到的元件上一個元件的信息(Nearest)
當(dāng)前搜索到的元件上上一個元件的信息(2ndNearest)
當(dāng)前搜索到的元件是否為“直接激活的”(Directly Powered)，下文簡稱DP
當(dāng)前搜索路徑的阻尼(也就信號源和當(dāng)前元件的距離)
這個信息采用了類似鏈表的形式記錄了搜索路徑的局部信息，用于判定搜索是否結(jié)束，以及設(shè)定元件的其他一些性質(zhì)。有了上述鋪墊后，下面就是較為具體的搜索過程：
搜索分為三個部分，下面三個部分都要在當(dāng)前搜索路徑的阻尼<15的時候才進(jìn)行,當(dāng)阻尼達(dá)到15時搜索結(jié)束。
搜索充能方塊。如果當(dāng)前元件不是充能方塊，則遍歷它的六個面，找到帶有合適性質(zhì)的方塊（如石頭就可以，玻璃就不行）
搜索普通元件。遍歷當(dāng)前方塊6個面的六個方塊，分出六條路徑進(jìn)行搜索。對于搜索到的每個元件，都要檢查它的
allowConnection和addSource兩個函數(shù)，當(dāng)且僅當(dāng)這兩個函數(shù)檢查都通過時，最初的信號源才會成為當(dāng)前元件的父元件（也就是建立新的有向邊并更新邏輯距離），同時更新電路追蹤信息(產(chǎn)生新的current, 舊的current變成nearest，以此類推，邏輯距離+1)。搜索鐵軌。沒看懂。
當(dāng)UQ被請清空，即所有都搜索結(jié)束后，整個電路就建立完成了。
電路的連接檢查和元件的屬性(*僅供參考)
這里稍微介紹下allowConnection和addSource兩個函數(shù)。每個類不同的元件這倆函數(shù)的實(shí)現(xiàn)基本都不一樣，如果沒有自己的實(shí)現(xiàn)就采用其基類的實(shí)現(xiàn)。
AllocationConnection定義了元件的基本連接特性,如
比較器和中繼器只允許一個輸入端
充能方塊不能充能充能方塊
非指向性生產(chǎn)者（如紅石塊）不能充能充能方塊
紅石線復(fù)雜的壓線和引線規(guī)則等等
由于這個函數(shù)內(nèi)部細(xì)節(jié)過多，這里就不再詳細(xì)介紹，有興趣的自行研究源碼細(xì)節(jié)。
addSource在allowConnection的基礎(chǔ)上添加了更多的限制，如消費(fèi)者的充能類別、指向性等等信息，該函數(shù)除了連接外還會更新上下文中的DP(即是否直連)參數(shù)。要介紹這個函數(shù)，首先得知每個元件除了能量強(qiáng)度外其他的一些性質(zhì)，下面對重要的性質(zhì)做下簡單的總結(jié)。
生產(chǎn)者
生產(chǎn)者具有獨(dú)有的性質(zhì)allowAttachments，即是否運(yùn)行“附著”到其他方塊上，其實(shí)就是該信號源是否具有方向性，允許附著的主要有如下類型：比較器，中繼器，偵測器，拉桿，絆線鉤，壓力板，按鈕。這之中是不包含紅石塊的，因為紅石塊沒有所謂的方向性。
消費(fèi)者
消費(fèi)者具有兩個獨(dú)有的性質(zhì)：
Propagate Power,即是否能被強(qiáng)充能,具有該屬性的元件有：鐘，命令方塊，發(fā)射器，投擲器，音符盒，紅石燈
Accept Half Pulse 即是否接受半脈沖(看專欄2)，具有該屬性的元件有：門，發(fā)射器，投擲器，末影龍頭，陷阱門
此外，消費(fèi)者還具有一個依據(jù)電路連接情況而變的屬性Promoted To Producer，直譯過來是"晉升為生產(chǎn)者"，其實(shí)就是在說當(dāng)前消費(fèi)者是否被強(qiáng)充能了。
現(xiàn)在再看addSource在什么條件才進(jìn)行連接。
剩下的過于復(fù)雜，鴿了。
3. 信號算計機(jī)制--信號更新階段簡述
由于上一步中電路的結(jié)構(gòu)發(fā)生了變化，因此電路中每個元件的紅石信號值也會發(fā)生變化，信號更新階段的任務(wù)就是計算并更新游戲中每個元件內(nèi)部的的紅石信號值。
3.1 信號更新的6個步驟
信號更新階段分兩個步驟：cacheValues和evaluate,不同的元件的在這些階段要做的事情并不相同，但是這些行為可以分為兩類：
計算新值：根據(jù)自身特性和連接情況計算下1rt的紅石信號值，并緩存起來
設(shè)置新值：把當(dāng)前元件的紅石信號值設(shè)置為緩存起來的新值
下表列出了常見的元件的在這兩個步驟的行為（空白即為什么都不做）。
在信號更新過程中：1~6步依據(jù)如下的順序進(jìn)行：
[2,5] -> [3,1] -> [4,6]
其中 -> 表示嚴(yán)格的先后順序，[a,b]表示ab之間的順序隨機(jī)可交換。下面對每個部分進(jìn)行介紹：
2. 電容器計算新值： 電容器根據(jù)它的父元件以及自身的特性計算新的紅石信號值，并緩存。注意到這里電容器的父元件都沒有更新自身的信號值，因此它的計算使用的是上1rt的紅石電路的數(shù)據(jù)。
5. 紅石線計算新值：紅石線根據(jù)自身的父元件計算自己的新值，計算算法見下一節(jié)。同樣的，這里紅石線的父元件都沒有更新自身信號值，因此他的計算也是全部使用上1rt的紅石電路的數(shù)據(jù)。
3. 電容器設(shè)置新的值: 電容器將2中計算的新值設(shè)定為當(dāng)前值
1. 生產(chǎn)者設(shè)置新值: ?生產(chǎn)者將自己當(dāng)前信號值設(shè)定為新值。由于生產(chǎn)者的新值是即時產(chǎn)生的(比如你拉下拉桿的一瞬間，拉桿的新值就被設(shè)定為15了)，且它不可能有父元件，因此它并不需要計算新值。
4. 消費(fèi)者計算新值并設(shè)計新值：消費(fèi)者根據(jù)自身的父元件計算自己的新值，計算算法見下一節(jié)（3.2）。同樣的，這里消費(fèi)者的父元件必定全部更新了自身的信號值，因此它的計算全部使用的下1gt的紅石電路的設(shè)計
6. 紅石線設(shè)置新值：紅石線將2中計算的新值設(shè)定為當(dāng)前值
這里把部分元件的信號更新拆成兩部分，以及使用上述的順序，Mojang有自己的考量：這么做主要是為了防止時序混亂。如果不拆分電容器和紅石線的兩個階段，那么可能部分元件使用上1rt的數(shù)據(jù)來更新，而部分元件使用下1rt的數(shù)據(jù)來更新。此外，2，5在最前面就保證了電容器和紅石線的所有新值全部使用上1gt的數(shù)據(jù)來計算，而第六步的消費(fèi)者并未拆分且放到最后即可保證它的信號計算一定全部使用的下1gt的紅石線路的數(shù)據(jù)。（當(dāng)然這個算法也導(dǎo)致了一些特殊的延遲特性：比如特定情況下的無延遲中繼器，見紅石專欄1）。
3.2. 父元件的信號計算算法
紅石線和消費(fèi)者的新值，以及電容器的（某個）信號輸入值，都計算于它的父元件。計算算法如下所示：對于該消費(fèi)者的每一個父元件Fi，設(shè)其與當(dāng)前元件的阻尼（也就是邏輯距離）為Di(該值在搜索過程中計算并設(shè)置)，稱Fi的紅石信號值S(Fi)和距離Di的差值為該父元件為該元件提供的信號值。所有信號值的最大值為該消費(fèi)者的信號值，該值最小為0。根據(jù)上述描述可總結(jié)出如下公式：
舉例來說，設(shè)某個活塞有3個父元件，每個父親元件的信號值分別為15,0,6,距離分別為10,15,0那么該活塞的信號值則為max(0,max(15-10,0-15,6-0)) = 6.
完成上述所有步驟后，游戲的紅石更新就完全結(jié)束了。此時游戲會執(zhí)行其他任務(wù)，并在下1gt的響應(yīng)階段中根據(jù)當(dāng)前設(shè)置的新值更新方塊或者方塊實(shí)體的狀態(tài)。
4. 其他細(xì)節(jié)和補(bǔ)充
4.1 紅石電路和持久化
紅石電路的所有信息都不會被寫入存檔內(nèi)部，而是在區(qū)塊加載的時候動態(tài)構(gòu)建。在一個游戲?qū)嵗?，只要是加載過的區(qū)塊都會被緩存到內(nèi)存中，而不會被手動移除。這一設(shè)計使得游戲的區(qū)塊的二次加載很快，同時也增大了內(nèi)存占用。隨著玩家游玩時間的增加，經(jīng)過的區(qū)塊也會慢慢增多，如果新加載的區(qū)塊中有紅石元件的話，也會被加入該區(qū)塊所屬維度的電路場景圖中的數(shù)據(jù)結(jié)構(gòu)中。因此在一個具有大量紅石元件的地圖中，如果只加載少量的區(qū)塊，則基本不會產(chǎn)生卡頓。
待補(bǔ)充。
