【深圳 IO 攻略】最終 BOSS 關(guān)《水下收割機器人》的全新解決方案（空間換時間）
本文首發(fā)于 B 站《深圳 IO》文集（https://www.bilibili.com/read/readlist/rl569860）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。
前排提示：你現(xiàn)在看到的解決方案是截至?2022 年 9 月，世界排行榜上最省電的方案。但愿將來有更厲害的大佬能打破我的這個世界紀錄。
點擊主頁上的【控制面板】，在【謎題檔案】里輸入數(shù)字 3113，打開隱藏關(guān)第 3 關(guān)《水下收割機器人》。這也是整個游戲（截至 2022 年 9?月）的最終 BOSS 關(guān)卡。
本關(guān)是阿瓦隆城第 5 關(guān)《海藻收割機器人》的升級關(guān)卡，尚未完成阿瓦隆城第 5 關(guān)的同學建議先閱讀阿瓦隆城第 5 關(guān)的攻略，完成后再來挑戰(zhàn)本關(guān)：【深圳 IO 攻略】阿瓦隆城第 5 關(guān)《海藻收割機器人》的全新解決方案（空間換時間）
和阿瓦隆城第 5 關(guān)相比，本關(guān)雖然少了【收割】這一路輸出，但是難度卻陡然增大。因為本關(guān)的要求是就近收割，而不是按照先來后到的順序收割。也就是說，每走一步都需要掃描一遍區(qū)域里有哪些海藻，然后往最近的海藻方向奔去。因為是就近收割，所以不存在像第 5 關(guān)那樣往遠處跑的過程中“順手牽羊”的情形，自然也就不需要【收割】這一路輸出信號了。
另外，為了簡化問題，計算距離時，對角線方向上 1 格的距離也是 1，不是根號 2。類似于國際象棋里的國王，既可以橫／豎走一步，也可以斜著走一步。國王在 a 點，到達棋子 b 處至少需要走多少步，在這道題里 a 點和 b 點的距離就是多少。
那么，相比于阿瓦隆城第 5 關(guān)來說，本關(guān)的思路要做這么幾點改變：
因為是就近收割，不是按先來后到的順序收割，所以我們向 RAM 里添加新的海藻坐標時，要使用第 1 關(guān)的模式：遍歷 RAM，找到空位后就放進去。如果仍然使用隊列模式的話，存在“早期海藻因為距離過遠遲遲未被收割，致使新出現(xiàn)的海藻坐標覆蓋掉早期海藻”的可能性。
因為每一步都要搜索距離自己最近的海藻在哪，而電機和海藻間的距離是隨著電機的移動而變化的，不是一成不變的。所以控制電機的芯片每秒鐘都要對外公布自己所在的 (x, y) 坐標，以方便其余芯片計算此時此刻電機和各海藻間的距離。
我的設(shè)計方案里，一共花了 26 塊錢（MC6000×3?+ MC4000(X)×3 +?RAM×1），寫了 60?行代碼，且走了背線。不過我的方案是目前世界排行榜上的最省電量的方案，只有 4467 電量。
電路圖和代碼如下：
整塊電路板堆得滿滿的，一股濃濃的窒息感。我來說明一下各個芯片的分工：
左下角的芯片和 C2S-RF901 直接相連，為 1 號芯片。該芯片負責接收 C2S-RF901 發(fā)來的海藻坐標，并放入 RAM 的空位中。
RAM 正右側(cè)的芯片為 2 號芯片，位于它右下方的是 3 號芯片，位于它右上方的是 4 號芯片。它每秒鐘都遍歷 RAM，將找到的所有海藻坐標都扔給 3 號芯片，委托 3 號芯片去計算當前電機和各個海藻間的距離。它自己則是匯總這些距離，找到距離最近的海藻，記下這個海藻的坐標，并將這個坐標值告訴 4 號芯片，由 4 號芯片委托控制電機的芯片來移動電機。
位于 2 號芯片右下方的 3 號芯片只做一件事——等 2 號芯片發(fā)海藻坐標，然后計算電機和這個海藻的距離并回傳給 2 號芯片。
位于 2 號芯片右上方的 4 號芯片要做兩件事——一是等待 2 號芯片把本秒鐘要到達的目標位置發(fā)來，然后給右邊的電機控制芯片下發(fā)最新任務；二是尋找 RAM 中的空位，然后將 RAM 地址定位到這個空位上，以便 1 號芯片下一秒能放入新的海藻坐標。
位于最右端的 5、6?號芯片在收到 4?號芯片發(fā)來的目標位置后，判定本輪是否應該移動一格，以及向什么方向移動。移動完畢后，向 3 號芯片報告電機的最新 x、y 坐標，方便 3 號芯片去計算電機與各海藻間的距離。
我們依次來分析。首先是 1 號芯片：
這里我要先提一下：上一版被廢棄掉的方案里，我使用的是“兩位數(shù)存儲法”，用個位存目標點的 x 坐標，用十位存目標點的 y 坐標。這種壓縮存儲的方法只適合在存儲空間捉襟見肘的時候使用，實際執(zhí)行時，存儲時需要壓縮成一個兩位數(shù)，使用時又要解壓，屬于【用時間換空間】，有效率上的損失。而且由于題目保證了等待收割的海藻不超過 6 個，2 號芯片全盤掃描 RAM 時，至少有 8 格是空的，這就導致了全盤掃描 RAM 時，至少一半的時間在做無用功，效率進一步降低。
當存儲空間并沒有捉襟見肘時，正確的做法應當是【用空間換時間】，用兩格 RAM 來存儲一個目標位置的 x、y 坐標，而不是把一個目標位置壓縮成兩位數(shù)。本次的新攻略正是修正了前一次【用時間換空間】的錯誤。本方案的三項指標分別為 26?元成本、4.5K?電量、60 行代碼，上一版廢棄方案的 31?元成本、6.4K 電量、74?行代碼被完爆到渣都不剩。
和阿瓦隆城第 5 關(guān)類似，這塊芯片在第 1 秒鐘對 RAM 進行初始化操作，所有偶數(shù)格內(nèi)全部寫上 -999；從第 2 秒開始，每秒鐘將 C2S-RF901 里的兩個數(shù)字寫入到上一秒鐘 4 號芯片指定好的空位里。
第 1 行 @ teq 0 1 用于上電時激活 - 開頭的指令。初始化時，該芯片的代碼看起來是這樣的：
首先從 rx 口讀一個數(shù)字（一定讀到 -999）寫入 RAM 的第偶數(shù)格（mov x2 x0），地址自增后再讀一次 RAM 的第奇數(shù)格（一定讀到 0）讓地址值重新跳至第偶數(shù)格。此時判斷讀到的 0 是否和地址值一致，即地址值是否等于 0（- teq x0 x1）。若地址值不為 0，說明不是所有的第偶數(shù)格都寫上了 -999，跳回第 2 行繼續(xù)寫，直到地址值歸零，所有的第偶數(shù)格都寫上了 -999 后，初始化完畢，休眠進入下一個周期（+ slp 1）。
從第 2 秒開始，該芯片的 - 號指令就不可能再被激活了，代碼看起來就變成了這個樣子：
很簡單，就是字面意思：每秒鐘將 C2S-RF901 里的兩個數(shù)字寫入到（上一秒鐘?4 號芯片指定好的）空位里。為了確保其他芯片讀取海藻坐標數(shù)據(jù)時不產(chǎn)生混亂，這里我們規(guī)定：第偶數(shù)格存的是 x 坐標，第奇數(shù)格存的是?y 坐標。
現(xiàn)在我們來看 2 號芯片：
這塊芯片的代碼里使用了?【深圳 IO 攻略】番外篇：調(diào)整代碼執(zhí)行順序以節(jié)省行數(shù) 里的技巧，直接解釋比較麻煩。所以下面我先貼一個優(yōu)化前的代碼：
第 1 秒鐘里，1 號芯片還在執(zhí)行初始化任務，所以 2 號芯片也跟著睡覺（slp 1）。從第 2 秒開始，就要開始遍歷 RAM 中記錄的所有海藻，并找出距離最近的那個海藻了。該芯片的 dat 寄存器用于存儲和最近的海藻的距離，由于整個版面的最大距離為 9，即 (0, 0) 到 (9, 9) 點的距離，所以我們將 dat 的初值設(shè)為 10，表示尚未找到海藻（mov 10 dat）。初值設(shè)為 10 可以確保，只要找到一個海草，dat 的值一定會被更新。
第 3~13 行是一個循環(huán)，用于遍歷整個 RAM，并將找到的海藻坐標依次發(fā)給 3 號芯片，委托它去計算電機與海藻的距離。首先我們從 RAM 中讀一格數(shù)字（mov x0 acc），并判定讀到的數(shù)字是否為負數(shù)（tlt acc 0）。如果讀到了負數(shù)，說明當前格是一個空格。由于我們使用兩個數(shù)字記錄一個海藻坐標，所以此時我們需要空讀一下數(shù)據(jù)口，跳過同屬于該格的存儲空間，進入下一格存儲空間（+ mov x0 null）。如果讀到了非負數(shù)，說明當前格記錄了一個海藻的 x 坐標。我們把這個 x 坐標和下一個記錄 y 坐標的數(shù)字一起扔給 3 號芯片（- mov acc x2, - mov x0 x2），等待 3 號芯片計算好距離后，我們將回傳的距離值重新放回 acc（- mov x2 acc）。得到距離值后，檢查該距離值是否小于已找到的最小距離值（- tcp acc dat）。如果小于歷史最小，就將當前的距離值設(shè)為新的歷史最小（- mov acc dat）。并且，RAM 的地址值指向了【當前海藻的位置 +2】的地址，我們將該地址值寫入 p1 口，供 4 號芯片將來使用（- mov x1 p1）。此時我們檢查 RAM 是否遍歷完畢，地址是否歸零（teq x1 0）。尚未歸零時，跳回到第 3 行繼續(xù)讀下一個海藻數(shù)據(jù)，并計算距離，更新最小距離，如此反復，直到整個 RAM 被遍歷一遍，地址值歸零為止。
RAM 遍歷完成后，該芯片的 dat 寄存器記錄的是【最近的海藻距離電機多遠】，同時?p1 口寫入了【最近的海藻所在位置 +2】的值。此時我們將 dat 寄存器的值發(fā)送給 4 號芯片（mov dat x3），喚醒它后，2 號芯片本秒里的任務就完成了，可以跳回開頭睡覺了。
由于 teq x1 0 這個條件在上電時一定滿足，所以我們可以使用“終止條件前置法”將終止條件和收尾工作前置，然后把收尾工作（mov dat x3）和準備工作（slp 1, mov 10 dat）全部帶上 + 號，并去掉 jmp 指令，完成優(yōu)化。只不過這樣的話，第 1 秒鐘里會給 4 號芯片多傳一個 0，這個額外傳輸?shù)?0 如何消化掉，分析 4 號芯片的時候我們再說。
現(xiàn)在我們來看專門計算電機和海藻的距離的 3 號芯片：
該芯片可以從 p1 口獲得電機當前的 x 坐標（由 5?號芯片每秒刷新），從 p0 口獲得當前電機的 y 坐標（由 6?號芯片每秒刷新）。首先等待 2 號芯片發(fā)來海藻的 x 和 y 坐標（slx x1）。我們首先得到的是海藻的 x 坐標，此時計算和電機 x 坐標的橫向距離（mov x1 acc, sub p1, dst 1 0），計算完畢后放入 dat 中暫存（mov acc dat）。
值得注意的是第 4 行的置位指令（dst 1 0），它的作用是【取絕對值】。我在龍騰第 15 關(guān)《卡賓槍瞄準照明器》的攻略里提到過：
置位指令：dst I1/R1/P1 I2/R2/P2，將 acc 寄存器中的某一位置為特定的值。位數(shù)由第一個操作數(shù)決定，0~2 分別表示個位/十位/百位，若在此范圍外，則不執(zhí)行任何操作。具體設(shè)置的值由第二個操作數(shù)決定，會只看最低位，忽略最高位，同時會將數(shù)字的符號設(shè)置為和該數(shù)一致。 作者：ココアお姉ちゃん https://www.bilibili.com/read/cv16919367?出處：bilibili
注意這句【同時會將數(shù)字的符號設(shè)置為和該數(shù)一致】。在本游戲里，0 是視為正數(shù)的。因此當我們執(zhí)行了 dst 1 0，將十位強行置為 0 這樣的操作后，會強行將 acc 置為正數(shù)。10×10 的網(wǎng)格里，任意兩點間的距離最多為 9，所以計算出距離后，十位、百位是肯定為 0 的。這里的置位指令并不會修改十位數(shù)字，唯一的作用就是取絕對值。
接下來的 6~9 行代碼，我們再從 2 號芯片處獲得海藻的 y 坐標，然后計算和電機 y 坐標的縱向距離（mov x1 acc, sub p0, dst 1 0）。至此，dat 中記錄的是橫向距離，acc 中記錄的是縱向距離，兩者中的較大值即為電機和當前海藻的距離。我們將兩者中的較大值反饋給 2 號芯片（tlt?acc dat, -?mov acc x1, +?mov dat x1）。
現(xiàn)在是 4 號芯片，它有兩個任務：①收到 2 號芯片的喚醒信號后，將 p0 口的值 -2，得到真正的海藻位置，然后將目標 x、目標 y 分別發(fā)送給右邊的 5、6 號芯片；②發(fā)送完畢后，掃描 RAM 里的空位，并將指針定位到空位上，方便 1 號芯片下一秒鐘在對應的位置寫上新的海藻坐標。我們來看它的代碼：
這塊芯片的代碼使用了?【深圳 IO 攻略】番外篇：上電時設(shè)置符號以提高運行效率?里的技巧，直接解釋比較麻煩，所以下面我先貼一個優(yōu)化前的代碼：
首先等待 2 號芯片的喚醒信號（slx x2），并將 2 號芯片發(fā)來的距離值存入 dat（mov x2 dat）。這里我們將發(fā)來的距離值分 3 種情況討論：
距離為 1，下一秒鐘這個海藻就要被收割掉。發(fā)送完目標位置后，我們直接將 RAM 的地址值定位在這個海藻的位置（視為空位），以便下一秒鐘 1 號芯片能將這個海藻的信息覆蓋掉。
距離為 2~9，下一秒鐘這個海藻不會被收割掉。發(fā)送完目標位置后，我們需要尋找 RAM 中的空位，以便下一秒鐘 1 號芯片能將新的海藻信息寫入空位。
距離為 10，RAM 中沒有任何海藻。此時電機應該原地待命，這塊芯片不應該發(fā)任何數(shù)字給右邊的芯片?？瘴灰膊恍枰桃馊フ遥驗榇藭r整個 RAM 都是空的。
距離為 1 時，代碼看起來是這樣的：
距離小于 10 的條件是滿足的（tlt dat 10），此時我們將 RAM 的地址置為 p0 - 2，得到真正的海藻位置（+ mov p0 acc, + sub 2, + mov acc x0），然后將目標 x、目標 y 分別發(fā)送給右邊的 5、6 號芯片（+ mov x1 x3, + mov x1 x2）。接下來，距離小于 2 的條件也是滿足的（+ tlt dat 2），此時我們直接將 RAM 地址重置為?p0-2（+ mov acc x0），以便下一秒里 1 號芯片能將這個距離為 1 的海藻信息給抹掉。
距離為 2~9 時，代碼看起來是這樣的：
就是在以上代碼的基礎(chǔ)上，加了 3 行包裹了 - 號的循環(huán)。距離為 2~9 時，距離小于 2 的條件是不滿足的（+ tlt dat 2），于是進入循環(huán)，尋找 RAM 中的負數(shù)（- mov x0 acc, - tlt x1 0, - jmp a），找到負數(shù)后，acc 存的是該負數(shù)所在地址，將它重置為 RAM 的地址，以便下一秒里 1 號芯片能在這個空位寫上新的海藻信息（+ mov acc x0）。
距離為 10 時，代碼看起來是這樣的：
距離小于 10 的這個條件是不滿足的（tlt dat 10），說明整個 RAM 都是空的，沒有任何海藻數(shù)據(jù)。我這里選擇了共用代碼，跳到第 10 行的循環(huán)里尋找負數(shù)，并將 RAM 指向該負數(shù)。其實這時候更好的辦法是直接 jmp 1，什么都不做。因為整個 RAM 都是空位，所有的第偶數(shù)格都是負數(shù)，不需要去找。
以上代碼，我們使用“上電設(shè)置符號法”優(yōu)化，完成
①準備工作前添加 @ teq 0 0；②準備工作和收尾工作全部帶上 + 號；③循環(huán)體去掉 jmp 作者：ココアお姉ちゃん https://www.bilibili.com/read/cv18047538
這三步曲后，代碼會變成下面的樣子：
這段代碼和圖示的代碼只有第一行的區(qū)別。為什么第一行要改成 @ teq x2 0 呢？還記得我之前分析 2 號芯片的時候怎么說的嗎？
由于 teq x1 0 這個條件在上電時一定滿足，所以我們可以使用“終止條件前置法”將終止條件和收尾工作前置，然后把收尾工作（mov dat x3）和準備工作（slp 1, mov 10 dat）全部帶上 + 號，并去掉 jmp 指令，完成優(yōu)化。只不過這樣的話，第 1 秒鐘里會給 4 號芯片多傳一個 0，這個額外傳輸?shù)?0 如何消化掉，分析 4 號芯片的時候我們再說。
這里，把 @ teq 0 0 中的一個 0 換成?x2，就很自然地解決了“消化掉這個額外傳輸?shù)?0”這樣的問題。妙?。?/p>
最后是控制電機的 5、6 號芯片：
5、6 號芯片的 acc 寄存器用來記錄電機的實時?(x, y) 坐標。初始狀態(tài)下，兩塊芯片都給各自的輸出端口賦上 50 的電平值（mov 50 p1），然后等待 4?號芯片發(fā)來的目標 x/y 信號（slx x1）。
這里我們回看一下接線圖：
5 號芯片只有 x1 口和 4 號芯片連接，4 號芯片則是 x0 和 x1 口都和 4 號芯片連接。由于 6 號芯片的 x0 口同時和 2 號芯片的 x3 口及 3 號芯片的 x3 口相連接，本方案里，為了防止誤喚醒，兩塊芯片都采用監(jiān)聽 x1 口的方法來喚醒。與此同時，接收數(shù)據(jù)時，為了防止時序上的沖突，x、y 坐標不通過同一條線路傳輸。5 號芯片使用了 x1 口來接收數(shù)據(jù)，6 號芯片則是使用 x0 口來接收數(shù)據(jù)。
收到發(fā)來的數(shù)據(jù)后，將目標位置和當前位置做差值運算，檢查差值的正負號（tcp x1/x0 acc）。差值為 0 時，讓電平信號保持為 50 即可，同樣也不需要修改 acc 的值。差值為負時，說明目標點在當前點的左／下方，需要令 acc -1，并給輸出口賦上 0 的電平值（- mov 0 p1, slp 1, - sub 1）；差值為正時，說明目標點在當前點的右／上方，需要令 acc +1，并給輸出口賦上 100 的電平值（+ mov 100 p1, slp 1, + add 1）。一秒過后，立刻將新的電機?(x, y) 坐標發(fā)往 p0 口，供 3 號芯片使用（mov acc p0）。
點擊左下角的【模擬】，稍等片刻，便會彈出結(jié)算界面：
恭喜你，學會了如何創(chuàng)造一個世界紀錄。
至此，深圳 IO 的所有主線攻略就全部寫完了。如果這份攻略里出現(xiàn)了筆誤，亦或讀者在某些關(guān)卡里有比我更好的設(shè)計方案的話，歡迎和我探討。也希望各位讀者能喜歡這個游戲作品。
