【深圳 IO 攻略】阿瓦隆城第 5 关《海藻收割机器人》的全新解决方案（空间换时间）
本文首发于 B 站《深圳 IO》文集（https://www.bilibili.com/read/readlist/rl569860）。原创不易，转载请注明出处。
关卡展示
本关的 C2S-RF901 会不定期地发送一些长度为 2 的数据包：两个数字分别记为 x 和 y，表示在 (x, y) 位置出现了新的海藻。题目保证不会在 (0, 0) 点出现海藻。
当队列中有等待收割的海藻时，命令电机按照先来后到的顺序依次收割所有的海藻。这次的电机变成了在二维平面上运动，控制规则如下：
【电机 x】和【电机 y】信号初值均为 50。
给【电机 x】发送 a 秒的 0 信号，表示令电机左移 a 格；给【电机 x】发送 b 秒的 100 信号，表示令电机右移 b 格。
给【电机 y】发送 c 秒的 0 信号，表示令电机下移 a 格；给【电机 y】发送 d 秒的 100 信号，表示令电机上移 d 格。
可以同时给【电机 x】和【电机 y】两路输出发送信号，此时电机将按斜线方向移动：x = 100, y = 100 时，向右上方移动；x = 100, y = 0 时，向右下方移动；x = 0, y = 0 时，向左下方移动；x = 0, y = 100 时，向左上方移动。
移动完毕后，需要将【电机 x】和【电机 y】都还原成 50。
当电机移动到有海藻的位置时，给【收割】端口发送 1 秒钟的 100 信号，即可完成一次收割。
为了以最快速度到达海藻的目标位置，我们需要让电机优先按斜线方向移动。另外，原则上，我们需要按照先来后到的顺序收割海藻。但如果前往目标点的过程中，遇到了后出现的海藻，也顺带收割掉。
例如，当电机停在 (0, 0)，需要前往 (2, 3) 收割海藻时，需要依次移动到 (0, 0)→(1, 1)→(2, 2)→(2, 3) 点。如果在走到 (1, 1) 点时，发现了后出现的海藻，那么即使它是先来后到里的后者，也顺带收割掉。
本关的难点在于维护一个【任务队列】。和第 1 关不同，第 1 关从冷库中拿食物的规则是【随用随取】，需要用了就拿出来，你需要随时告诉系统，我现在要拿编号多少的食物。而本关收割海藻的要求是按照先来后到的顺序收割，系统不会告诉你，现在要往哪跑，收割哪里的海藻。
队列是一种动态存储大量数据的数据结构，就跟生活中随处可见的“排队”一样，排在前面的人最先享受服务。在队列这种数据结构里，添加操作只能在队列的末端进行，读取和删除操作只能在队列的首端进行。如下图所示。
我们收到数据包的时候，将要到达的目标位置放在【队尾】。当任务队列中还有数据时，我们需要令电机到达【队头】所指示的位置，完成收割后，将【队头】元素删除。如此，便能实现“按先来后到的顺序收割海藻”的要求。
本关需要 5 块芯片。1 号芯片是数据库管理员，和 C2S-RF901 直接连接，用于不断向任务队列里添加新的收割任务。2 号芯片是监察员，不断监测当前的队头任务是否完成。队头任务完成后，需要向后寻找新的任务，并将队头指向新的任务，同时给后面的 3~5 号工人芯片发送新的任务指令。3~5 号芯片是勤劳的工人，分别控制电机 x、电机 y 和收割信号。其中 5 号芯片也兼顾数据库管理员这一职，每完成一次收割，就将任务队列里的对应任务清除，以便 2 号监察员能够监视到。电路图如下所示：
本关的接线非常复杂。我先解释一下为什么要连这么多线。
左下角的芯片是 1 号数据库管理员芯片，需要完成【从 C2S-RF901 中接收数据包】和【将新的数据包写入任务队列】2 件事情。所以它的 x0 口和 C2S-RF901 的 rx 口连接，x2、x3 口和 RAM 的 d0、a0 口连接。
正中央的芯片是 2 号监视员芯片。这块芯片需要完成【监视数据库】，以及【向右侧的 4、5 号芯片告知实时的目标位置】这两项任务。它的 x2、x3 口和 RAM 的 d1、a1 口相接；它的 x0 口和右侧控制【电机 x】的 3 号芯片相接，用于传输目标 x；它的 p1 口和右侧控制【电机 y】的 4 号芯片相接，用于传输目标 y。至此，还剩下 1X1P 口未被使用。为了充分利用资源，我们不妨顺手将 x1 口和 RAM 的 a0 口相接，以获得队尾指针。
然后是右边的 3 块工人芯片。输入方面，3 号芯片用 x0 接收 2 号芯片发来的 x 坐标，4 号芯片用 p0 口接收 2 号芯片发来的 y 坐标；输出方面，这两块芯片的 p1 口则连接着【电机 x/y】的输出端信号，而 x1 口是和 5 号芯片的 x3 口相连的，作用是：每到达一个新位置，就唤醒 5 号芯片，让它检查现在脚下有没有待收割的海藻。
5 号收割芯片的 x3 口用于和上方负责移动电机的芯片通讯，p1 口连接着【收割】的输出端信号。x0、x1 口连接着 RAM 的 d1 和 a1，以便当自己成功收割一个海藻后，能够抹除数据库里的相应任务记录。
这一关里，芯片间的信息传递非常频繁，虽说看起来导线连接得异常错综复杂，但真的没有一根导线是废线。我们先从 1 号数据库管理员芯片开始写起。代码如下：
这里我要先提一下：上一版被废弃掉的方案里，我使用的是“两位数存储法”，用个位存目标点的 x 坐标，用十位存目标点的 y 坐标。这种压缩存储的方法只适合在存储空间捉襟见肘的时候使用，实际执行时，存储时需要压缩成一个两位数，使用时又要解压，属于【用时间换空间】，有效率上的损失。而且由于题目保证了等待收割的海藻不超过 6 个，右下角的【收割】芯片全盘扫描 RAM 时，至少有 8 格是空的，这就导致了全盘扫描 RAM 时，至少一半的时间在做无用功，效率进一步降低。
当存储空间并没有捉襟见肘时，正确的做法应当是【用空间换时间】，用两格 RAM 来存储一个目标位置的 x、y 坐标，而不是把一个目标位置压缩成两位数。本次的新攻略正是修正了前一次【用时间换空间】的错误。先提前剧透一下，本次【用空间换时间】后，三项指标分别为 21 元成本、2.2K 电量、50 行代码，上一版废弃方案的 24 元成本、3.8K 电量、54 行代码被完爆到渣都不剩。
现在回过头来看代码。1~4 行是第一秒里的初始化操作，我们需要将 RAM 填入一半的 -999。上一版方案里由于目标点的 (x, y) 坐标存在一个两位数里，题目又保证了不会在原点 (0, 0) 出现海藻，所以上一版方案不需要初始化，直接可以把默认的 0 视为空格。但本方案不行，因为本方案是将 (x, y) 坐标分别存储在两格里的，题目可没有保证不在除 (0, 0) 外任意的 (x, 0) 或 (0, y) 点也不出现海藻。如果我们还像上一版方案那样不做初始化处理，那么后续的过程中，我们从 RAM 中读到一格 0 时，其实是并不能确定当前点没有海藻的，非得连续读到两个 0 才能确定，这反而平白无故地增加了复杂度。与其这样，我们还不如用一个负数代表空格呢，这样我们读到一个负数就知道当前格是空格了。
第 1 行 @ teq 0 1 用于上电时激活 - 号开头的指令。初始化部分的代码只有第 2~4 行共 3 行代码，全部用 - 号包裹，后续的代码里都不可能再激活 - 号指令。初始化时，首先往 RAM 中填入一格 -999（- mov -999 x2），然后读一格 RAM（必然读到 0）后判断读到的 0 是否比地址值小，即地址值是否大于 0（- tcp x2 x3），若没有归零则回到第 2 行继续填（- jmp 2），直到地址归零，填满为止。
RAM 地址在上电时位于 0 号位，是第偶数格。写入一格 -999 时，地址会自增一格，这样就跳到了第奇数格。此时再读一格（必然读到 0），地址同样会自增一格，这就又回到了第偶数格。如此反复，当地址在第偶数格时我们就写 -999，当地址在第奇数格时我们就读。如此反复，最终初始化完毕时，RAM 会变成这个样子：
第 5~9 行就是后续的常规任务了。首先休眠 1 秒（slp 1），从第 2 秒起，每秒钟都从 C2S-RF901 里读取数据（mov x0 acc），检查它是不是 -999（tcp acc -999）。若是，关闭一切 +/- 号指令，防止激活以 - 号包裹的初始化部分的代码。若不是，说明是由两个一位数组成的数据包，首数字代表新海藻所在的 x 坐标，第二个数字代表新海藻所在的 y 坐标。此时我们激活 + 号指令的代码，依次将这两个数字存入 RAM（+ mov acc x2, + mov x0 x2）。为了确保其他芯片读取海藻坐标数据时不产生混乱，这里我们规定：第偶数格存的是 x 坐标，第奇数格存的是 y 坐标。
接下来是位于线路板最中央的 2 号监视员芯片：
这块芯片的代码使用了 【深圳 IO 攻略】番外篇：上电时设置符号以提高运行效率 里的技巧，直接解释比较麻烦，所以下面我先贴一个优化前的代码：
2 号芯片的 acc 寄存器用于存储队头地址，即【当前正在执行的任务编号】。当任务队列为空（即没有新任务）时，acc 表示的是【上一个已完成的任务编号】。前一个任务完成后，这个芯片不会立刻将这个已完成任务从队列里清除，而是扫描到新任务后，再去清除。然后，这块芯片的 dat 寄存器用于存储目标 x，目标 y 则是通过 p1 口直接输出给右边的 4 号芯片。
第一秒里一定不会有海藻出现，但是 2 号芯片每秒钟都必须和后面控制电机 x、y 坐标的芯片通讯（后面会说到）。所以第一秒里仍然要将默认的 (0, 0) 坐标发给右边的芯片（mov dat x0, slp 1）（dat 和 p1 的默认值都是 0）。从第二秒开始，我们需要循环检查队头处的海藻有没有被收割掉，首先将 a1 口的地址置为缓存在 acc 里的队头地址（mov acc x2）。接下来的第 4~11 行构成了一个循环，用于寻找从原队头开始的第一个出现的海藻，并将对应的位置设置为新的队头地址。我们每到达一个新的格子，就判断该格是不是 -999（mov x2 acc, tgt x3 -999）。若不为 -999，那么我们就找到了离原队头最近的待收割海藻，我们令 RAM 指向这个新队头（+ mov acc x2），然后依次读取两格数据，并依次写入 dat 寄存器和 p1 口，作为新的目标 x、y（+ mov x3 dat, + mov x3 p1）。执行完毕后，停止搜索，直接跳回第 1 行，将目标 x 通过 x0 口发给右边的 3 号芯片唤醒电机并休眠（mov dat x0, slp 1）。若不幸读到了 -999，则说明尚未找到海藻，此时空读一下数据口，跳过奇数格，直接到达下一个偶数格，确保读取时不奇偶错位（- mov x3 null）。接下来我们判断 RAM 指针是否到达了队尾（- teq x2 x1）。尚未达到队尾时，跳回到第 4 行，继续向后查找，直到到达队尾为止（- jmp 4）。若从队头一直找到队尾都没有找到任何一株等待收割的海草，说明任务队列清空了，电机的目标 x、y 不需要做任何调整，直接原样发出，令电机停留在原地就好了（mov dat x0, slp 1）。此时我们只需要执行第 1、2 行的代码，不需要执行第 6~8 行带 + 号的代码。后者是用于更新目标 x、y 的。简而言之就是：找到了待收割的海藻，则更新目标点并发出信号；没找到时，仅发送信号，不更新目标点。
以上代码，我们使用“上电设置符号法”优化，完成
①准备工作前添加 @ teq 0 0；②准备工作和收尾工作全部带上 + 号；③循环体去掉 jmp 作者：ココアお姉ちゃん https://www.bilibili.com/read/cv18047538
这三步曲后，就变成了如图所示的代码。
接下来是 3、4 号控制电机 x/y 位置的芯片：
3 号芯片的 acc 寄存器用于记录电机的实时 x 坐标，4 号芯片的 acc 寄存器用于记录电机的实时 y 坐标。
由于 2 号芯片每秒钟都会唤醒 3 号芯片，并将目标 x 坐标通过 x0 口传给 3 号芯片，所以 3 号芯片无需使用 slx x0 这样的指令来等待，而是可以直接计算目标 x 和当前 x 的差值（tcp x0 acc）。差值为 0 时，电机保持 50 的电平信号（mov 50 p1），差值为负时，目标 x 在当前 x 的左侧，这一秒里电机在 x 轴方向需要左移一格，令 acc -1 并且给电机赋 0 信号（- sub 1, - mov 0 p1）；差值为正时，目标 x 在当前 x 的右侧，这一秒里电机在 x 轴方向需要右移一格，令 acc +1 并且给电机赋 100 信号（+ add 1, + mov 100 p1）。做完这些后，将新的实时 x 坐标通过 x1 口发给右下角控制收割信号的 5 号芯片并休眠（mov acc x1, slp 1）。
接下来看下方的 4 号芯片。为什么 4 号芯片反而需要 slx 指令唤醒了呢？因为 4 号芯片不像 3 号芯片那样通过 x 口接收坐标数据，而是通过 p 口接收坐标数据。由于 x 口采用的是同步协议，所以 2 号芯片还没有给 3 号芯片的 x0 口传数据时，3 号芯片会一直等着，直到 2 号芯片给它发送了数据以后才继续执行下面的代码。可是 p 口没有同步协议，4 号芯片读 p 口时，2 号芯片如果还在慢悠悠地算的话，那么 4 号芯片就会读到上一秒里的数据。所以读 p 口数据时，必须要手动确保时间差，读取的一方必须要确认写入的一方把数据写入进去后才能读。
这里的 slx x1 指令打的就是这个时间差。当 4 号芯片被 x1 口唤醒时，说明 3 号芯片将实时的 x 坐标往下传给 5 号芯片了。3 号芯片必然是在 2 号芯片动完以后才动的，此时 2 号芯片肯定已经写好目标 y 了，此时再读 p0 便可万无一失。这时候我们只是为了让 3 号芯片顺便唤醒一下自己，咱们可千万不能手贱去读这个 x1，把这个本来要往下传的数字给截断了。接下来的 2~8 行，和 3 号芯片的 1~7 行几乎完全一致，除了把 x0 改成了 p0 以外完全一致。同样也是计算目标 y 和当前 y 的差值（tcp p0 acc）。差值为 0 时，电机保持 50 的电平信号（mov 50 p1），差值为负时，目标 y 在当前 y 的下方，这一秒里电机在 y 轴方向需要下移一格，令 acc -1 并且给电机赋 0 信号（- sub 1, - mov 0 p1）；差值为正时，目标 y 在当前 y 的上方，这一秒里电机在 y 轴方向需要上移一格，令 acc +1 并且给电机赋 100 信号（+ add 1, + mov 100 p1）。做完这些后，将新的实时 y 坐标通过 x1 口发给右下角控制收割信号的 5 号芯片并休眠（mov acc x1, slx x1）。
由于 3、4 号芯片每秒钟都会被唤醒，所以这里不需要写成循环结构，每次唤醒时都做同样的事情时，就相当于在循环了。
最后看 5 号用于控制收割的芯片：
还是同样地，提供一份优化前的代码：
首先等待上方芯片唤醒（slx x3）。唤醒后，将 RAM 的地址归零（mov 0 x1），同时将得到的 x 和 y 分别放入 acc 和 dat 寄存器（mov x3 acc, mov x3 dat）。因为 3 号芯片将 x 坐标送入 x1 口后，4 号芯片才醒，因此接收数据时，一定是先得到 x，后得到 y。第 5~14 行是循环。首先读第偶数格的数据，检查是否和当前电机的 x 一致（teq x0 acc），不一致时，该海藻不在脚下，肯定无法收割，所以直接空读一次第奇数格，跳过这个海藻（- mov x0 null）。一致时，再读一次第奇数格，检查是否和当前电机的 y 一致（+ teq x0 dat）。若当前海藻的 x, y 与当前电机的 x, y 都一致，那么就立刻启动收割仪式。首先将 RAM 地址向前偏移两格，定位到该海藻的 x 处（+ mov x1 acc, + sub 2, + mov acc x1），然后向 RAM 对应位置处写入 -999，将该海藻从 RAM 里抹掉（+ mov -999 x0）。改写完 RAM 后，向【收割】端口发送 1 秒钟的 100 信号（+ gen p1 1 0）。若当前海藻的 x, y 有 1~2 项与当前电机的 x, y 不一致时，就继续向后遍历这个 RAM。检查 RAM 地址有没有回到 0（- teq x1 0），尚未回到 0 时，跳回到第 5 行继续查找有没有海藻就在脚下（- jmp 5）。如果遍历一圈完毕后，仍找不到任何一个在脚下的海藻，那本秒里就不需要收割，就直接回到开头睡眠，等待下一秒电机移动后，再检查是否需要收割。
以上代码，我们使用“上电设置符号法”优化，完成
①准备工作前添加 @ teq 0 0；②准备工作和收尾工作全部带上 + 号；③循环体去掉 jmp 作者：ココアお姉ちゃん https://www.bilibili.com/read/cv18047538
这三步曲后，就变成了如图所示的代码。
点击左下角的【模拟】，稍等片刻，便会弹出结算界面：
21 元成本，2.2K 电量，50 行代码，我们用空间换时间，完爆了上一版 24 元成本，3.8K 电量，54 行代码的方案。
