【深圳 IO 攻略】最终 BOSS 关《水下收割机器人》的全新解决方案(空间换时间)

本文首发于 B 站《深圳 IO》文集(https://www.bilibili.com/read/readlist/rl569860)。原创不易,转载请注明出处。
前排提示:你现在看到的解决方案是截至 2022 年 9 月,世界排行榜上最省电的方案。但愿将来有更厉害的大佬能打破我的这个世界纪录。
点击主页上的【控制面板】,在【谜题档案】里输入数字 3113,打开隐藏关第 3 关《水下收割机器人》。这也是整个游戏(截至 2022 年 9 月)的最终 BOSS 关卡。

本关是阿瓦隆城第 5 关《海藻收割机器人》的升级关卡,尚未完成阿瓦隆城第 5 关的同学建议先阅读阿瓦隆城第 5 关的攻略,完成后再来挑战本关:【深圳 IO 攻略】阿瓦隆城第 5 关《海藻收割机器人》的全新解决方案(空间换时间)
和阿瓦隆城第 5 关相比,本关虽然少了【收割】这一路输出,但是难度却陡然增大。因为本关的要求是就近收割,而不是按照先来后到的顺序收割。也就是说,每走一步都需要扫描一遍区域里有哪些海藻,然后往最近的海藻方向奔去。因为是就近收割,所以不存在像第 5 关那样往远处跑的过程中“顺手牵羊”的情形,自然也就不需要【收割】这一路输出信号了。
另外,为了简化问题,计算距离时,对角线方向上 1 格的距离也是 1,不是根号 2。类似于国际象棋里的国王,既可以横/竖走一步,也可以斜着走一步。国王在 a 点,到达棋子 b 处至少需要走多少步,在这道题里 a 点和 b 点的距离就是多少。
那么,相比于阿瓦隆城第 5 关来说,本关的思路要做这么几点改变:
因为是就近收割,不是按先来后到的顺序收割,所以我们向 RAM 里添加新的海藻坐标时,要使用第 1 关的模式:遍历 RAM,找到空位后就放进去。如果仍然使用队列模式的话,存在“早期海藻因为距离过远迟迟未被收割,致使新出现的海藻坐标覆盖掉早期海藻”的可能性。
因为每一步都要搜索距离自己最近的海藻在哪,而电机和海藻间的距离是随着电机的移动而变化的,不是一成不变的。所以控制电机的芯片每秒钟都要对外公布自己所在的 (x, y) 坐标,以方便其余芯片计算此时此刻电机和各海藻间的距离。
我的设计方案里,一共花了 26 块钱(MC6000×3 + MC4000(X)×3 + RAM×1),写了 60 行代码,且走了背线。不过我的方案是目前世界排行榜上的最省电量的方案,只有 4467 电量。


电路图和代码如下:


整块电路板堆得满满的,一股浓浓的窒息感。我来说明一下各个芯片的分工:
左下角的芯片和 C2S-RF901 直接相连,为 1 号芯片。该芯片负责接收 C2S-RF901 发来的海藻坐标,并放入 RAM 的空位中。
RAM 正右侧的芯片为 2 号芯片,位于它右下方的是 3 号芯片,位于它右上方的是 4 号芯片。它每秒钟都遍历 RAM,将找到的所有海藻坐标都扔给 3 号芯片,委托 3 号芯片去计算当前电机和各个海藻间的距离。它自己则是汇总这些距离,找到距离最近的海藻,记下这个海藻的坐标,并将这个坐标值告诉 4 号芯片,由 4 号芯片委托控制电机的芯片来移动电机。
位于 2 号芯片右下方的 3 号芯片只做一件事——等 2 号芯片发海藻坐标,然后计算电机和这个海藻的距离并回传给 2 号芯片。
位于 2 号芯片右上方的 4 号芯片要做两件事——一是等待 2 号芯片把本秒钟要到达的目标位置发来,然后给右边的电机控制芯片下发最新任务;二是寻找 RAM 中的空位,然后将 RAM 地址定位到这个空位上,以便 1 号芯片下一秒能放入新的海藻坐标。
位于最右端的 5、6 号芯片在收到 4 号芯片发来的目标位置后,判定本轮是否应该移动一格,以及向什么方向移动。移动完毕后,向 3 号芯片报告电机的最新 x、y 坐标,方便 3 号芯片去计算电机与各海藻间的距离。
我们依次来分析。首先是 1 号芯片:

这里我要先提一下:上一版被废弃掉的方案里,我使用的是“两位数存储法”,用个位存目标点的 x 坐标,用十位存目标点的 y 坐标。这种压缩存储的方法只适合在存储空间捉襟见肘的时候使用,实际执行时,存储时需要压缩成一个两位数,使用时又要解压,属于【用时间换空间】,有效率上的损失。而且由于题目保证了等待收割的海藻不超过 6 个,2 号芯片全盘扫描 RAM 时,至少有 8 格是空的,这就导致了全盘扫描 RAM 时,至少一半的时间在做无用功,效率进一步降低。
当存储空间并没有捉襟见肘时,正确的做法应当是【用空间换时间】,用两格 RAM 来存储一个目标位置的 x、y 坐标,而不是把一个目标位置压缩成两位数。本次的新攻略正是修正了前一次【用时间换空间】的错误。本方案的三项指标分别为 26 元成本、4.5K 电量、60 行代码,上一版废弃方案的 31 元成本、6.4K 电量、74 行代码被完爆到渣都不剩。
和阿瓦隆城第 5 关类似,这块芯片在第 1 秒钟对 RAM 进行初始化操作,所有偶数格内全部写上 -999;从第 2 秒开始,每秒钟将 C2S-RF901 里的两个数字写入到上一秒钟 4 号芯片指定好的空位里。
第 1 行 @ teq 0 1 用于上电时激活 - 开头的指令。初始化时,该芯片的代码看起来是这样的:
首先从 rx 口读一个数字(一定读到 -999)写入 RAM 的第偶数格(mov x2 x0),地址自增后再读一次 RAM 的第奇数格(一定读到 0)让地址值重新跳至第偶数格。此时判断读到的 0 是否和地址值一致,即地址值是否等于 0(- teq x0 x1)。若地址值不为 0,说明不是所有的第偶数格都写上了 -999,跳回第 2 行继续写,直到地址值归零,所有的第偶数格都写上了 -999 后,初始化完毕,休眠进入下一个周期(+ slp 1)。
从第 2 秒开始,该芯片的 - 号指令就不可能再被激活了,代码看起来就变成了这个样子:
很简单,就是字面意思:每秒钟将 C2S-RF901 里的两个数字写入到(上一秒钟 4 号芯片指定好的)空位里。为了确保其他芯片读取海藻坐标数据时不产生混乱,这里我们规定:第偶数格存的是 x 坐标,第奇数格存的是 y 坐标。
现在我们来看 2 号芯片:

这块芯片的代码里使用了 【深圳 IO 攻略】番外篇:调整代码执行顺序以节省行数 里的技巧,直接解释比较麻烦。所以下面我先贴一个优化前的代码:
第 1 秒钟里,1 号芯片还在执行初始化任务,所以 2 号芯片也跟着睡觉(slp 1)。从第 2 秒开始,就要开始遍历 RAM 中记录的所有海藻,并找出距离最近的那个海藻了。该芯片的 dat 寄存器用于存储和最近的海藻的距离,由于整个版面的最大距离为 9,即 (0, 0) 到 (9, 9) 点的距离,所以我们将 dat 的初值设为 10,表示尚未找到海藻(mov 10 dat)。初值设为 10 可以确保,只要找到一个海草,dat 的值一定会被更新。
第 3~13 行是一个循环,用于遍历整个 RAM,并将找到的海藻坐标依次发给 3 号芯片,委托它去计算电机与海藻的距离。首先我们从 RAM 中读一格数字(mov x0 acc),并判定读到的数字是否为负数(tlt acc 0)。如果读到了负数,说明当前格是一个空格。由于我们使用两个数字记录一个海藻坐标,所以此时我们需要空读一下数据口,跳过同属于该格的存储空间,进入下一格存储空间(+ mov x0 null)。如果读到了非负数,说明当前格记录了一个海藻的 x 坐标。我们把这个 x 坐标和下一个记录 y 坐标的数字一起扔给 3 号芯片(- mov acc x2, - mov x0 x2),等待 3 号芯片计算好距离后,我们将回传的距离值重新放回 acc(- mov x2 acc)。得到距离值后,检查该距离值是否小于已找到的最小距离值(- tcp acc dat)。如果小于历史最小,就将当前的距离值设为新的历史最小(- mov acc dat)。并且,RAM 的地址值指向了【当前海藻的位置 +2】的地址,我们将该地址值写入 p1 口,供 4 号芯片将来使用(- mov x1 p1)。此时我们检查 RAM 是否遍历完毕,地址是否归零(teq x1 0)。尚未归零时,跳回到第 3 行继续读下一个海藻数据,并计算距离,更新最小距离,如此反复,直到整个 RAM 被遍历一遍,地址值归零为止。
RAM 遍历完成后,该芯片的 dat 寄存器记录的是【最近的海藻距离电机多远】,同时 p1 口写入了【最近的海藻所在位置 +2】的值。此时我们将 dat 寄存器的值发送给 4 号芯片(mov dat x3),唤醒它后,2 号芯片本秒里的任务就完成了,可以跳回开头睡觉了。
由于 teq x1 0 这个条件在上电时一定满足,所以我们可以使用“终止条件前置法”将终止条件和收尾工作前置,然后把收尾工作(mov dat x3)和准备工作(slp 1, mov 10 dat)全部带上 + 号,并去掉 jmp 指令,完成优化。只不过这样的话,第 1 秒钟里会给 4 号芯片多传一个 0,这个额外传输的 0 如何消化掉,分析 4 号芯片的时候我们再说。
现在我们来看专门计算电机和海藻的距离的 3 号芯片:

该芯片可以从 p1 口获得电机当前的 x 坐标(由 5 号芯片每秒刷新),从 p0 口获得当前电机的 y 坐标(由 6 号芯片每秒刷新)。首先等待 2 号芯片发来海藻的 x 和 y 坐标(slx x1)。我们首先得到的是海藻的 x 坐标,此时计算和电机 x 坐标的横向距离(mov x1 acc, sub p1, dst 1 0),计算完毕后放入 dat 中暂存(mov acc dat)。
值得注意的是第 4 行的置位指令(dst 1 0),它的作用是【取绝对值】。我在龙腾第 15 关《卡宾枪瞄准照明器》的攻略里提到过:
置位指令:dst I1/R1/P1 I2/R2/P2,将 acc 寄存器中的某一位置为特定的值。位数由第一个操作数决定,0~2 分别表示个位/十位/百位,若在此范围外,则不执行任何操作。具体设置的值由第二个操作数决定,会只看最低位,忽略最高位,同时会将数字的符号设置为和该数一致。 作者:ココアお姉ちゃん https://www.bilibili.com/read/cv16919367 出处:bilibili
注意这句【同时会将数字的符号设置为和该数一致】。在本游戏里,0 是视为正数的。因此当我们执行了 dst 1 0,将十位强行置为 0 这样的操作后,会强行将 acc 置为正数。10×10 的网格里,任意两点间的距离最多为 9,所以计算出距离后,十位、百位是肯定为 0 的。这里的置位指令并不会修改十位数字,唯一的作用就是取绝对值。
接下来的 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)。
现在是 4 号芯片,它有两个任务:①收到 2 号芯片的唤醒信号后,将 p0 口的值 -2,得到真正的海藻位置,然后将目标 x、目标 y 分别发送给右边的 5、6 号芯片;②发送完毕后,扫描 RAM 里的空位,并将指针定位到空位上,方便 1 号芯片下一秒钟在对应的位置写上新的海藻坐标。我们来看它的代码:

这块芯片的代码使用了 【深圳 IO 攻略】番外篇:上电时设置符号以提高运行效率 里的技巧,直接解释比较麻烦,所以下面我先贴一个优化前的代码:
首先等待 2 号芯片的唤醒信号(slx x2),并将 2 号芯片发来的距离值存入 dat(mov x2 dat)。这里我们将发来的距离值分 3 种情况讨论:
距离为 1,下一秒钟这个海藻就要被收割掉。发送完目标位置后,我们直接将 RAM 的地址值定位在这个海藻的位置(视为空位),以便下一秒钟 1 号芯片能将这个海藻的信息覆盖掉。
距离为 2~9,下一秒钟这个海藻不会被收割掉。发送完目标位置后,我们需要寻找 RAM 中的空位,以便下一秒钟 1 号芯片能将新的海藻信息写入空位。
距离为 10,RAM 中没有任何海藻。此时电机应该原地待命,这块芯片不应该发任何数字给右边的芯片。空位也不需要刻意去找,因为此时整个 RAM 都是空的。
距离为 1 时,代码看起来是这样的:
距离小于 10 的条件是满足的(tlt dat 10),此时我们将 RAM 的地址置为 p0 - 2,得到真正的海藻位置(+ mov p0 acc, + sub 2, + mov acc x0),然后将目标 x、目标 y 分别发送给右边的 5、6 号芯片(+ mov x1 x3, + mov x1 x2)。接下来,距离小于 2 的条件也是满足的(+ tlt dat 2),此时我们直接将 RAM 地址重置为 p0-2(+ mov acc x0),以便下一秒里 1 号芯片能将这个距离为 1 的海藻信息给抹掉。
距离为 2~9 时,代码看起来是这样的:
就是在以上代码的基础上,加了 3 行包裹了 - 号的循环。距离为 2~9 时,距离小于 2 的条件是不满足的(+ tlt dat 2),于是进入循环,寻找 RAM 中的负数(- mov x0 acc, - tlt x1 0, - jmp a),找到负数后,acc 存的是该负数所在地址,将它重置为 RAM 的地址,以便下一秒里 1 号芯片能在这个空位写上新的海藻信息(+ mov acc x0)。
距离为 10 时,代码看起来是这样的:
距离小于 10 的这个条件是不满足的(tlt dat 10),说明整个 RAM 都是空的,没有任何海藻数据。我这里选择了共用代码,跳到第 10 行的循环里寻找负数,并将 RAM 指向该负数。其实这时候更好的办法是直接 jmp 1,什么都不做。因为整个 RAM 都是空位,所有的第偶数格都是负数,不需要去找。
以上代码,我们使用“上电设置符号法”优化,完成
①准备工作前添加 @ teq 0 0;②准备工作和收尾工作全部带上 + 号;③循环体去掉 jmp 作者:ココアお姉ちゃん https://www.bilibili.com/read/cv18047538
这三步曲后,代码会变成下面的样子:
这段代码和图示的代码只有第一行的区别。为什么第一行要改成 @ teq x2 0 呢?还记得我之前分析 2 号芯片的时候怎么说的吗?
由于 teq x1 0 这个条件在上电时一定满足,所以我们可以使用“终止条件前置法”将终止条件和收尾工作前置,然后把收尾工作(mov dat x3)和准备工作(slp 1, mov 10 dat)全部带上 + 号,并去掉 jmp 指令,完成优化。只不过这样的话,第 1 秒钟里会给 4 号芯片多传一个 0,这个额外传输的 0 如何消化掉,分析 4 号芯片的时候我们再说。
这里,把 @ teq 0 0 中的一个 0 换成 x2,就很自然地解决了“消化掉这个额外传输的 0”这样的问题。妙啊!
最后是控制电机的 5、6 号芯片:

5、6 号芯片的 acc 寄存器用来记录电机的实时 (x, y) 坐标。初始状态下,两块芯片都给各自的输出端口赋上 50 的电平值(mov 50 p1),然后等待 4 号芯片发来的目标 x/y 信号(slx x1)。
这里我们回看一下接线图:


5 号芯片只有 x1 口和 4 号芯片连接,4 号芯片则是 x0 和 x1 口都和 4 号芯片连接。由于 6 号芯片的 x0 口同时和 2 号芯片的 x3 口及 3 号芯片的 x3 口相连接,本方案里,为了防止误唤醒,两块芯片都采用监听 x1 口的方法来唤醒。与此同时,接收数据时,为了防止时序上的冲突,x、y 坐标不通过同一条线路传输。5 号芯片使用了 x1 口来接收数据,6 号芯片则是使用 x0 口来接收数据。
收到发来的数据后,将目标位置和当前位置做差值运算,检查差值的正负号(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) 坐标发往 p0 口,供 3 号芯片使用(mov acc p0)。
点击左下角的【模拟】,稍等片刻,便会弹出结算界面:

恭喜你,学会了如何创造一个世界纪录。
至此,深圳 IO 的所有主线攻略就全部写完了。如果这份攻略里出现了笔误,亦或读者在某些关卡里有比我更好的设计方案的话,欢迎和我探讨。也希望各位读者能喜欢这个游戏作品。