本文首發(fā)于 B 站《深圳 IO》文集（https://www.bilibili.com/read/readlist/rl569860）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。

此文章已過時(shí)。請?zhí)D(zhuǎn)至?【深圳 IO 攻略】阿瓦隆城第 5 關(guān)《海藻收割機(jī)器人》的全新解決方案（空間換時(shí)間） 繼續(xù)閱讀。

關(guān)卡展示

本關(guān)的 C2S-RF901 會不定期地發(fā)送一些長度為 2 的數(shù)據(jù)包：兩個(gè)數(shù)字分別記為 x 和 y，表示在 (x, y) 位置出現(xiàn)了新的海藻。題目保證不會在 (0, 0) 點(diǎn)出現(xiàn)海藻。

當(dāng)隊(duì)列中有等待收割的海藻時(shí)，命令電機(jī)按照先來后到的順序依次收割所有的海藻。這次的電機(jī)變成了在二維平面上運(yùn)動，控制規(guī)則如下：

• 【電機(jī) x】和【電機(jī) y】信號初值均為 50。

• 給【電機(jī) x】發(fā)送 a 秒的 0 信號，表示令電機(jī)左移 a 格；給【電機(jī) x】發(fā)送 b 秒的 100 信號，表示令電機(jī)右移 b 格。

• 給【電機(jī) y】發(fā)送 c 秒的 0 信號，表示令電機(jī)下移 a 格；給【電機(jī) y】發(fā)送 d 秒的 100 信號，表示令電機(jī)上移 d 格。

• 可以同時(shí)給【電機(jī) x】和【電機(jī) y】兩路輸出發(fā)送信號，此時(shí)電機(jī)將按斜線方向移動：x = 100, y =?100?時(shí)，向右上方移動；x = 100, y =?0?時(shí)，向右下方移動；x = 0, y = 0 時(shí)，向左下方移動；x = 0, y = 100 時(shí)，向左上方移動。

• 移動完畢后，需要將【電機(jī) x】和【電機(jī) y】都還原成?50。

• 當(dāng)電機(jī)移動到有海藻的位置時(shí)，給【收割】端口發(fā)送 1 秒鐘的 100 信號，即可完成一次收割。

為了以最快速度到達(dá)海藻的目標(biāo)位置，我們需要讓電機(jī)優(yōu)先按斜線方向移動。另外，原則上，我們需要按照先來后到的順序收割海藻。但如果前往目標(biāo)點(diǎn)的過程中，遇到了后出現(xiàn)的海藻，也順帶收割掉。

例如，當(dāng)電機(jī)停在 (0, 0)，需要前往 (2, 3) 收割海藻時(shí)，需要依次移動到?(0, 0)→(1, 1)→(2, 2)→(2, 3) 點(diǎn)。如果在走到 (1, 1) 點(diǎn)時(shí)，發(fā)現(xiàn)了后出現(xiàn)的海藻，那么即使它是先來后到里的后者，也順帶收割掉。

本關(guān)的難點(diǎn)在于維護(hù)一個(gè)【任務(wù)隊(duì)列】。和第 1 關(guān)不同，第 1 關(guān)從冷庫中拿食物的規(guī)則是【隨用隨取】，需要用了就拿出來，你需要隨時(shí)告訴系統(tǒng)，我現(xiàn)在要拿編號多少的食物。而本關(guān)收割海藻的要求是按照先來后到的順序收割，系統(tǒng)不會告訴你，現(xiàn)在要往哪跑，收割哪里的海藻。

隊(duì)列是一種動態(tài)存儲大量數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，就跟生活中隨處可見的“排隊(duì)”一樣，排在前面的人最先享受服務(wù)。在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)里，添加操作只能在隊(duì)列的末端進(jìn)行，讀取和刪除操作只能在隊(duì)列的首端進(jìn)行。如下圖所示。

我們收到數(shù)據(jù)包的時(shí)候，將要到達(dá)的目標(biāo)位置放在【隊(duì)尾】。當(dāng)任務(wù)隊(duì)列中還有數(shù)據(jù)時(shí)，我們需要令電機(jī)到達(dá)【隊(duì)頭】所指示的位置，完成收割后，將【隊(duì)頭】元素刪除。如此，便能實(shí)現(xiàn)“按先來后到的順序收割海藻”的要求。

本關(guān)需要 6 塊芯片分工合作完成。1 號芯片是數(shù)據(jù)庫管理員，和 C2S-RF901 直接連接，用于不斷向任務(wù)隊(duì)列里添加新的收割任務(wù)。2 號芯片是監(jiān)察員，不斷監(jiān)測當(dāng)前的隊(duì)頭任務(wù)是否完成。隊(duì)頭任務(wù)完成后，需要向后尋找新的任務(wù)，并將隊(duì)頭指向新的任務(wù)，同時(shí)給 3 號芯片發(fā)送新的任務(wù)指令。3 號芯片是調(diào)度員，用于給后面的 4~6 號工人芯片發(fā)送新的任務(wù)指令。4~6 號芯片是勤勞的工人，分別控制電機(jī) x、電機(jī) y 和收割信號。其中 6 號芯片也兼顧數(shù)據(jù)庫管理員這一職，每完成一次收割，就將任務(wù)隊(duì)列里的對應(yīng)任務(wù)清除，以便 2 號監(jiān)察員能夠監(jiān)視到。電路圖如下所示：

本關(guān)的接線非常復(fù)雜。我先解釋一下為什么要連這么多線。

左上角的芯片是 1 號數(shù)據(jù)庫管理員芯片，需要完成【從?C2S-RF901 中接收數(shù)據(jù)包】、【將新的數(shù)據(jù)包寫入任務(wù)隊(duì)列】、【喚醒右側(cè)的總監(jiān)芯片】3 件事情。所以它的 x0 口和 C2S-RF901 的 rx 口連接，x1 口和 RAM 的 d0 口連接、x3 口和右側(cè)的總監(jiān)芯片連接。

正中央的芯片是 2 號監(jiān)視員芯片。雖然是每秒鐘都需要監(jiān)視數(shù)據(jù)庫，但由于 1 號芯片向任務(wù)隊(duì)列中寫入新任務(wù)是一個(gè)耗時(shí)操作，如果過快啟動，會導(dǎo)致本秒監(jiān)測不到需要啟動的新任務(wù)。為了同步的需要，這里的監(jiān)視員還是選擇每秒鐘都等 1 號芯片喚醒自己后再工作。這塊芯片需要完成【監(jiān)視數(shù)據(jù)庫】，以及【向上方的 3 號芯片告知當(dāng)前任務(wù)】的這兩項(xiàng)任務(wù)，看似只需要使用 3 個(gè) x 口，分別接 RAM 的 d1、a1，以及上方芯片的一個(gè) x 口即可。為什么這么簡單的任務(wù)卻接了 4X1P 共五個(gè)口，我們后面會詳細(xì)說。

上方居中的芯片是 3 號調(diào)度員芯片，x0 口和 p1 口都是用于和下方芯片通訊的，而 x2 口連接著右邊控制電機(jī)移動的 4、5 號芯片，用于給它們發(fā)送電機(jī)要到達(dá)的目標(biāo)位置。

然后是右邊的 3 塊工人芯片。4、5 號芯片的 x0 口用于接收 3 號芯片發(fā)來的任務(wù)，p1 口連接著【電機(jī) x/y】的輸出端信號。而 x1 口是和 6 號芯片的 x3 口相連的，作用是：每到達(dá)一個(gè)新位置，就喚醒 6 號芯片，讓它檢查現(xiàn)在腳下有沒有待收割的海藻。

6 號收割芯片的 x3 口用于和上方負(fù)責(zé)移動電機(jī)的芯片通訊，p1 口連接著【收割】的輸出端信號。x0、x1 口連接著 RAM 的?d1 和 a1，以便當(dāng)自己成功收割一個(gè)海藻后，能夠抹除數(shù)據(jù)庫里的相應(yīng)任務(wù)記錄。

這一關(guān)里，芯片間的信息傳遞非常頻繁，雖說看起來導(dǎo)線連接得異常錯(cuò)綜復(fù)雜，但真的沒有一根導(dǎo)線是廢線。我們先從 1 號數(shù)據(jù)庫管理員芯片開始寫起。代碼如下：

首先將本秒內(nèi)?C2S-RF901 中的首數(shù)字讀入 acc（mov x0 acc），檢查它是不是 -999（tcp acc -999）。若不是，說明是由兩個(gè)一位數(shù)組成的數(shù)據(jù)包，首數(shù)字代表新海藻所在的 x 坐標(biāo)，第二個(gè)數(shù)字代表新海藻所在的 y 坐標(biāo)。此時(shí) x 坐標(biāo)已經(jīng)放在了個(gè)位，我們只需要讀入第二個(gè) y 坐標(biāo)的數(shù)字，并把它放在十位上，就可以得到一個(gè)由兩位數(shù)組成的【海藻位置】信息（+ dst 1 x0）。處理完成后，我們就可以將這個(gè)新的坐標(biāo)加入任務(wù)隊(duì)列了（+ mov acc x1）。不管本秒內(nèi)是否往任務(wù)隊(duì)列里加入了新的任務(wù)，我們都需要在臨睡前喚醒 2 號監(jiān)視員芯片（mov 0 x3），待喚醒 2 號芯片后，方可睡去（slp 1）。

接下來是位于線路板最中央的 2 號監(jiān)視員芯片：

上方的 3 號芯片我預(yù)寫了兩行代碼。因?yàn)樽髠?cè)的芯片向 x3 口發(fā) 0 時(shí)，是會同時(shí)喚醒 2、3 兩塊芯片的（純屬無奈，電路板沒有足夠的空間布置成更細(xì)致的樣子）。3 號芯片需要在 2 號芯片做好準(zhǔn)備工作后才能開始工作，現(xiàn)在被喚醒純屬副作用，唯一能做的事就是把 1 號芯片發(fā)來的 0 給丟棄掉，防止線程阻塞（slx x0, mov x0 null）。1 號芯片之前發(fā)來的 0 是沒有任何含義的，只是為了喚醒而隨意發(fā)送的一個(gè)數(shù)字，這個(gè)數(shù)字換成其他任何數(shù)字都可以。

然后我們看 2 號芯片的代碼。2 號芯片的 acc 寄存器用于存儲隊(duì)頭地址，即【當(dāng)前正在執(zhí)行的任務(wù)編號】。當(dāng)任務(wù)隊(duì)列為空（即沒有新任務(wù)）時(shí)，acc 表示的是【上一個(gè)已完成的任務(wù)編號】。前一個(gè)任務(wù)完成后，這個(gè)芯片不會立刻將這個(gè)已完成任務(wù)從隊(duì)列里清除，而是掃描到新任務(wù)后，再去清除。這樣可以保證隊(duì)列里“至少有一個(gè)任務(wù)”（即使這個(gè)任務(wù)是已完成的任務(wù)），降低邏輯的復(fù)雜度。初始上電狀態(tài)下，我們既沒有【正在執(zhí)行的任務(wù)】，也沒有【上一個(gè)已完成的任務(wù)】。隊(duì)列是真正意義上的空隊(duì)列。 所以此時(shí)，我們需要人為地把隊(duì)頭往前移一格，將 13 號任務(wù)“視為上一個(gè)已完成的任務(wù)”，將隊(duì)頭地址初始化為 13（@ mov 13 acc）。

初始化完畢后，我們進(jìn)入等待喚醒狀態(tài)（slx x0）。喚醒后，發(fā)來的數(shù)字會被上方的 3 號芯片吸收掉，所以我們不需要在本芯片里再吸收一次了，這也就是后續(xù)代碼里不再有任何讀 x0 的操作的原因。喚醒后，首先我們把 RAM 的 a1 指針重置到隊(duì)頭，以便檢查隊(duì)頭的任務(wù)有沒有執(zhí)行完畢（mov acc x3）。如果隊(duì)頭處的數(shù)字仍然大于 0，說明隊(duì)頭任務(wù)還在執(zhí)行中，那么什么改變都不用做，直接跳到最后喚醒 3 號芯片就行了（tgt x2 0, + jmp c）。讀一次 RAM 后，地址指針會自動 +1。我們知道 1 號芯片操作的是 d0 數(shù)據(jù)口，這就導(dǎo)致 a0 地址口始終指向隊(duì)尾。如果隊(duì)頭地址 +1?正好等于隊(duì)尾地址，就說明隊(duì)列中僅有一個(gè)任務(wù)。這個(gè)任務(wù)要么正在進(jìn)行，要么已完成。正在進(jìn)行的話剛才已經(jīng)說過了，直接跳到結(jié)尾。而如果唯一的一個(gè)任務(wù)是已完成狀態(tài)的話，那么任務(wù)隊(duì)列事實(shí)上相當(dāng)于是空的。此時(shí)我們根本沒有新任務(wù)可以安排，也只能什么都不做，直接跳到最后喚醒 3 號芯片（- teq x3 x1, + jmp c）。

隊(duì)頭已經(jīng)變成了 0，且隊(duì)列大小不為 1 時(shí)，就說明隊(duì)頭任務(wù)已經(jīng)執(zhí)行完畢，同時(shí) RAM 里還有其他的等待執(zhí)行的任務(wù)。此時(shí)我們需要向后查找第一個(gè)非 0 的格子，將隊(duì)頭地址更新為該格子的地址（mov x3 acc, tgt x2?0, - jmp 7），后面的時(shí)間里改為監(jiān)測這個(gè)格子是否變成 0。找到新的隊(duì)頭后，我們將新的目標(biāo)位置同步到 p 口上，并喚醒上方的 3 號芯片（mov acc x3, mov x2 p1, mov 0 x0）。

為什么要將目標(biāo)位置同步到 p 口上，而不使用 x 口來傳輸呢？有兩點(diǎn)原因：①上方的 3 號芯片需要將這個(gè)兩位數(shù)拆解，每個(gè)周期都要讀兩次原數(shù)，將信號傳到 p 口上可以最大化利用 p 口可以【反復(fù)讀取】的優(yōu)點(diǎn)，節(jié)約數(shù)據(jù)傳輸次數(shù)；②同樣因?yàn)?p 口可以反復(fù)讀，所以 2 號芯片只需要在任務(wù)更新時(shí)才刷新 p 口的值，隊(duì)頭的任務(wù)仍然在進(jìn)行中時(shí)就不需要反復(fù)傳同樣的任務(wù)了。使用 p 口可以大大減少發(fā)送方的壓力。

我們最近的 3 關(guān)：喂貓機(jī)、打靶練習(xí)機(jī)，以及本關(guān)的海藻收割機(jī)，都有傳輸【不頻繁變化，且需要被多塊芯片讀?。煌粔K芯片讀取多次】這類數(shù)據(jù)的需求。這類數(shù)據(jù)相比于傳統(tǒng)的 x 口傳輸法，改用?p 口傳輸對于發(fā)送方和接收方來說都能大大簡化邏輯復(fù)雜度和電量消耗。我們在這 3 關(guān)里也都使用了 p 口傳輸這類數(shù)據(jù)。

接下來是 3 號調(diào)度員芯片：

調(diào)度員執(zhí)行到第 3 條指令時(shí)，由于需要讀入 x0，所以其實(shí)是處于【等待喚醒】的狀態(tài)的。但必須要在本秒內(nèi)喚醒，否則會導(dǎo)致線程阻塞。2 號芯片在最后會將一個(gè) 0 傳給 3 號芯片，所以 3 號芯片的第三行指令（dst x0 p1）相當(dāng)于 dst 0 p1，將 acc 的個(gè)位置為 p1。我們知道，3 號芯片被喚醒前，p1 口會被 2 號芯片修改為【當(dāng)前任務(wù)的 x/y 坐標(biāo)】的值，所以 p1 口的值會是個(gè)兩位數(shù)。與此同時(shí)，我在第 15 關(guān)卡賓槍的攻略里說過：

置位指令：dst I1/R1/P1 I2/R2/P2，將 acc 寄存器中的某一位置為特定的值。位數(shù)由第一個(gè)操作數(shù)決定，0~2 分別表示個(gè)位/十位/百位，若在此范圍外，則不執(zhí)行任何操作。具體設(shè)置的值由第二個(gè)操作數(shù)決定，會只看最低位，忽略最高位，同時(shí)會將數(shù)字的符號設(shè)置為和該數(shù)一致。 作者：ココアお姉ちゃん https://www.bilibili.com/read/cv16919367 出處：bilibili

dst 指令的第二個(gè)操作數(shù)是多位數(shù)時(shí)，會只看個(gè)位，忽略最高位。所以 dst 0 p1 這條指令相當(dāng)于下面兩條指令：

相當(dāng)于將 acc 置為 p1 的個(gè)位。1 號芯片收到一個(gè)新的海藻坐標(biāo)時(shí)，會將個(gè)位置成 x 坐標(biāo)，十位置成 y 坐標(biāo)。我們現(xiàn)在先提取出目的地址的個(gè)位數(shù)（即 x 坐標(biāo)），發(fā)送給右邊的芯片后（mov acc x1），再提取出目的地址的十位數(shù)（即 y 坐標(biāo)），發(fā)送給右邊的芯片（mov p1 acc, dgt 1, mov acc x1）。3 號芯片的 x1 口同時(shí)連接著右邊控制 x、y 的兩塊芯片，發(fā)送的時(shí)候沒有具體指定是哪個(gè)芯片接收，所以 4、5 號芯片需要自我調(diào)整時(shí)序，確保控制 x 坐標(biāo)的芯片接收到的是第一個(gè)數(shù)字，而控制 y 坐標(biāo)的芯片接收到的是第二個(gè)數(shù)字。

接下來是 4、5 號控制電機(jī) x/y 位置的芯片：

兩塊芯片僅僅是第 2、3 行代碼換了一下位置，其余的部分一模一樣。下方芯片用于控制 x 坐標(biāo)，需要接收第一個(gè)數(shù)字，所以在第二行就開始讀 x0；而上方芯片用于控制 y 坐標(biāo)，需要接收第二個(gè)數(shù)字，所以等到第三行，下方芯片讀過一次 x0 后，才開始讀自己這里的 x0。

下方芯片的 acc 寄存器用于記錄電機(jī)當(dāng)前所在的 x 坐標(biāo)，上方芯片的 acc 寄存器用于記錄電機(jī)當(dāng)前所在的 y 坐標(biāo)。首先都是等待左邊 3 號芯片的喚醒信號（slx x0）。喚醒后，從左邊的芯片接收目標(biāo) x/y 的值，將目標(biāo)的 x/y 和當(dāng)前的 x/y?做三態(tài)判定（tcp x0 acc）。首先假設(shè)是中間狀態(tài)，即目標(biāo) x/y 和當(dāng)前 x/y 是一致的，將電機(jī)信號置為 50（mov 50 p1），如果的確是端點(diǎn)狀態(tài)，再撤銷之前的設(shè)置。如果目標(biāo) x/y 小于當(dāng)前 x/y，需要令電機(jī)向左/下移動一格，同時(shí) acc 里記錄的實(shí)時(shí) x/y 值也要 -1（- sub 1, - mov 0 p1）；如果目標(biāo) x/y 大于當(dāng)前 x/y，需要令電機(jī)向右/上移動一格，同時(shí) acc 里記錄的實(shí)時(shí) x/y 值也要 +1（+ add 1, + mov 100 p1）。做完這些事情后，我們將新的 x/y 值發(fā)給下方的 6 號芯片，由它判斷腳下是否有等待收割的海藻（mov acc x1）。最后，跳回到第 1 行（slx x0），等待下一秒鐘再次被 3 號芯片喚醒。

由于 4、5 號芯片每秒鐘都會被喚醒，所以這里不需要寫成循環(huán)結(jié)構(gòu)，每次喚醒時(shí)都做同樣的事情時(shí)，就相當(dāng)于在循環(huán)了。

最后看 6 號用于控制收割的芯片：

首先等待被 4、5 號芯片喚醒（slx x3）。由于控制 x 的芯片收到第一個(gè)數(shù)字開始干事時(shí)，控制 y 的芯片還在等待接收第二個(gè)數(shù)字，因此控制 x 的芯片總是“快人一步”。觀察 3 號芯片里的指令可以發(fā)現(xiàn)，y 坐標(biāo)比 x 坐標(biāo)至少遲了?3 個(gè)機(jī)器周期才發(fā)出來。因此，即使在此期間 y?坐標(biāo)沒改變但 x 坐標(biāo)改變了（多執(zhí)行了?add/sub 以及 mov 共兩條指令），控制 x 的芯片仍然會快人一步，先將 x 坐標(biāo)發(fā)出來。6 號芯片的收到的第一個(gè)數(shù)字一定是 x 坐標(biāo)，所以先設(shè)置的一定是個(gè)位（dst 0 x3）。y 坐標(biāo)總是會“慢人一步”到來，所以我們后設(shè)置的是十位（dst 1 x3）。如此，便得到了用兩位數(shù)表示的“當(dāng)前電機(jī)所在坐標(biāo)”。如果計(jì)算出來是 0，就說明電機(jī)還停在原點(diǎn) (0, 0)。而題目明確說了不會在 (0, 0) 處出現(xiàn)海藻，所以當(dāng)電機(jī)還停在原點(diǎn)時(shí)，跳回開頭繼續(xù)睡覺，無需檢查這個(gè)位置是否需要收割（teq acc 0, + jmp 1）。當(dāng)我們計(jì)算出來的數(shù)字不是 0 時(shí)，就必須要遍歷整個(gè) RAM 檢查一下是否有海藻停在這個(gè)位置。首先將 RAM 指針歸零（mov 0 x1），每讀一格數(shù)據(jù)，就檢查讀到的數(shù)據(jù)是否和 acc 一致（mov x1 dat, teq x0 acc）。讀到一致的數(shù)據(jù)時(shí)，說明當(dāng)前這一格腳下有等待收割的海藻，我們將 RAM 中這一格的數(shù)據(jù)寫成 0，表示“這個(gè)位置的海藻已被收割”（+ mov dat x1, + mov 0 x0）。改寫完 RAM 后，向【收割】端口發(fā)送 1 秒鐘的 100 信號（+ gen p1 1 0）。如果尚未讀到一致的數(shù)據(jù)，則不停地讀，直到讀遍整個(gè) RAM，地址自然歸零為止（- teq x1 0, - jmp 7）。做完這些后，跳回到第一行（slx x3），等待下一秒鐘再次被 4、5 號芯片喚醒。

點(diǎn)擊左下角的【模擬】，稍等片刻，便會彈出結(jié)算界面：