开发者用Rust重写Splatoon 3邮箱像素画自动绘制工具

2026.11.04 :: Víctor :: {algorithms, gaming, embedded} :: #splatoon #nintendo #rust #rp2040 :: 15 min 在联网状态下玩 Splatoon 3 时，除了离线 NPC，你还能看到真实的玩家。 这一功能让玩家可以与其他玩家互动，获取对方服装或物品的复制品。 此外，玩家还可以展示消息供他人查看。 很多玩家会在消息里加入精美的像素画，我很好奇他们大多数人是怎么做到的，因为创建一条消息的过程既缓慢又繁琐。 要展示一条消息，你必须走到邮箱前，用 Joy-Con 一个像素一个像素地输入，这项任务可能要花上几个小时。 后来我发现了 splork，这个工具能把想要的像素画转换成手柄输入。它运行在 Raspberry Pi Pico（任意 RP2040 板子）上，伪装成 USB 游戏手柄，于是 Switch 以为有人在按键。 我试了试，确实能用，但速度很慢，因为它遍历和绘制像素的方式非常简陋——平心而论，作者在项目的 TODO 里也列出了一个更快的算法。 于是我决定改进它，并用 Rust 从头写一遍，这也是学习嵌入式 Rust 中 USB 协议栈、把玩复杂算法的绝佳借口。成果就是 splatt3rs。 splatt3rs 包含三个部分：一个优化器，把图像转换成指令列表（按键操作）；一个模拟器，把该列表回放成 GIF，好让我预测它会画出什么；以及用于执行该列表的 RP2040 固件。 留言板尺寸为 320×120 像素。光标从左上角开始，按一次方向键移动一个像素，按 A 键绘制光标所在的像素。固件能理解九种指令： pub enum Op { Xp, Xm, Yp, Ym, // 右、左、下、上移动 D, // 绘制当前格子 XpD, XmD, YpD, YmD, // 移动后绘制（单次按键报告） 最后四种是关键。移动加绘制可以融合成一条指令，因为手柄可以在同一份 USB 报告中同时按住方向和 A 键，因此它能执行整套指令集。 为了比较算法，我们评估生成的指令数与要绘制的像素数之间的比值。1.0 到 1.2 之间是非常好的解，其中一些是最优解；超过 1.5 则有相当大的开销（浪费的光标移动）。 splork 逐行扫描图像（水平或垂直，取较短的那个方向）。根据其生成器的说法，非空行的每个像素花费两条指令（一条绘制或空操作指令加一次移动）。此外，每一行还会额外得到 10 条指令，用于补偿光标漂移。空行会被跳过，但被跳过的行仍然要花费一条移动指令加上光标补偿。 指令数不取决于图像有多少像素，只取决于有多少空行。它每 25 ms 发送一条指令，因此一次绘制后接一次移动，会给 A 键一个 25 ms 的按下和 25 ms 的释放，然后方向键也是如此。也就是每个像素 50 ms，无论是否绘制。 它的指令速率很快，但偶尔会出现漂移，而且在稀疏图像上很慢。 给定网格上的一组点、一个从固定角落开始的光标，我们需要找到访问所有这些点的最短路径。路径不需要回到起点，可以重复经过任何地方。这正是我们这里要解决的问题：带曼哈顿距离的旅行商问题（TSP）（固定起点的开放路径）。 这是组合优化中的一个 NP 难问题，在理论计算机科学和运筹学中很重要。判断是否存在完美方案，等价于网格图上的哈密顿路径问题，而它是 NP 完全的。 面对多达 38,400 个像素，在合理时间内找到最优解是不现实的，所以计划是构建好的启发式算法，而不是最优求解器，并衡量它们离下界有多远。 优化器运行四种算法，保留最短的结果。它们按所需开销从小到大排列： line 按顺序扫描列或行，每一行选择离光标更近的方向开始（蛇形），并在两种朝向中保留更好的那个。它很快，但在稀疏图像上表现不佳。 grid 把图像的包围盒切成方形块（大小为 2、3、4、5、6、8、10、16、20、40 和 120，全部并行尝试），按蛇形顺序访问这些块，并以当前光标位置下 8 种朝向中最好的那一种扫描每个块。分块让光标保持在局部范围内，所以它胜过 line，但它对像素的形状一无所知。 tsp_stable 用 Warnsdorff 游走构建路径（总是走向未访问邻居最少的相邻未访问像素，这样可以避免把像素困在角落里），卡住时就跳到最近的未访问像素。然后通过局部搜索改进路径：2-opt（如果反转路径的一段能缩短它，就反转）和 Or-opt（把最多 3 个像素的短片段移到更好的位置）。它是确定性的，而且很快。 tsp_optimal 使用迭代局部搜索（ILS）改进前一个算法。该算法对路径进行踢动以寻找更好的局部最优（交换两个最多 30 像素的相邻小窗口），用局部搜索修复，如果路径更短就保留结果。它在连续多次踢动都没有改进结果，或 10 秒没有改进后停止。多个工作进程并行运行，每个核心一个，各自有自己的随机种子，最短路径获胜。这个搜索之所以可行，是因为只评估曼哈顿距离为二的像素。距离一有 4 个，距离二有 8 个，合起来就是 12 个最近邻。 优化器针对参考输入集进行了测试，共七张 320×120 的图像。数字就是上面定义的比值，所以 1.000 是完美，越低越好。最后一列是获胜的算法。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）