時(shí)隔半年又一次更新

概述

這次主要說說紅石系統(tǒng)是怎么構(gòu)建出來的，這對(duì)紅石玩家應(yīng)該沒啥幫助，唯一的作用也就是解釋一下為什么有些無方塊實(shí)體的紅石電路為何產(chǎn)生卡頓。

在上一篇中給了游戲1gt更新的順序表，這個(gè)表中的第18項(xiàng)也就是更新紅石系統(tǒng)依賴是我沒怎么提的，因?yàn)楫?dāng)時(shí)不懂相關(guān)的細(xì)節(jié)，這次把這個(gè)部分補(bǔ)充一下，講述一下玩家放下紅石和打掉紅石游戲會(huì)進(jìn)行哪些計(jì)算。

紅石系統(tǒng)

首先必須清楚的是，在代碼層面電路原件(CircuitComponent)和紅石相關(guān)的方塊不是一個(gè)東西，這兩個(gè)是分別維護(hù)的，紅石相關(guān)的狀態(tài)都存在電路原件里面，和方塊無關(guān)。每個(gè)維度有且僅有一個(gè)紅石系統(tǒng)，這個(gè)系統(tǒng)存儲(chǔ)了所有的電路原件以及它們之間的相互關(guān)系(相關(guān)關(guān)系上一篇中的無向圖)，具體主要有下面這幾項(xiàng):

• 所有的原件以及它們的位置

• 所有的非充能方塊

• 每個(gè)信號(hào)源以及它們的下級(jí)原件(使用該信號(hào)源的原件)對(duì)應(yīng)表

• 等待移除列表

• 等待添加列表

• 等待更新列表

緩存

當(dāng)玩家放下紅石相關(guān)方塊的時(shí)候，游戲不會(huì)立即將其變成紅石原件，而是把目標(biāo)位置放入等待添加列表中。同上，當(dāng)玩家移除紅石相關(guān)方塊的時(shí)候，游戲也不會(huì)立即將紅石原件移除，而是把目標(biāo)位置放入等待移除列表中

處理

游戲在運(yùn)行到第18項(xiàng)也就是更新紅石系統(tǒng)依賴這一項(xiàng)的時(shí)候，會(huì)集中處理這三個(gè)列表(還有個(gè)暫時(shí)沒說的等待更新列表)：

• 遍歷等待添加列表并生成實(shí)際的紅石原件

  注意到紅石系統(tǒng)中有各種各樣的表,為了保證這些表的數(shù)據(jù)的同步,在增加的時(shí)候,這些表全部都要更新一遍,

  如果更新的原件附近有生產(chǎn)者和電容器,會(huì)把這些原件的坐標(biāo)放入到第三個(gè)列表,也就是等待更新列表中.

• 遍歷等待移除列表并移除紅石原件

  同上,為了保證這些表的數(shù)據(jù)同步,在移除的時(shí)候這些表也全部都要更新一遍,同樣地會(huì)把附近的某些原件坐標(biāo)加入等待更新列表中.

• 遍歷等待更新列表并進(jìn)行實(shí)際操作

  等待更新列表是在添加和移除的過程中產(chǎn)生的,而且這個(gè)表里全部都是生產(chǎn)者和電容器.注意到生產(chǎn)者和電容器都是能提供能量的,因此我們也不難猜出這一步是要做什么,沒錯(cuò),就是進(jìn)行電路連接的構(gòu)建(也就是有向圖的構(gòu)建).對(duì)于表中的每個(gè)原件S,游戲都會(huì)以這個(gè)原件坐標(biāo)為起點(diǎn),以15為最深的搜索深度進(jìn)行廣度優(yōu)先搜索,每搜到一個(gè)原件C,都會(huì)把S加入到C的信號(hào)源列表中,當(dāng)前的深度也就成為了S和c之間的電阻，作為更新紅石信號(hào)時(shí)候的重要數(shù)據(jù)。不同紅石原件的連接特性也就決定了自己能不能被當(dāng)前信號(hào)源搜到。除此之外，充能方塊也是在這個(gè)過程中被發(fā)現(xiàn)和加入紅石原件的。

問題

初看這些東西都沒啥問題，很合理的算法。但是怪就怪在上面的原件信號(hào)源列表以及其它一些會(huì)頻繁隨機(jī)增刪查改的列表的內(nèi)部數(shù)據(jù)結(jié)構(gòu)是vector.在vector上進(jìn)行隨機(jī)增刪會(huì)產(chǎn)生不小的開銷。這也直接導(dǎo)致了某些表面上平平無奇的紅石電路實(shí)際上奇卡無比。