Micromouse 机器人的洪水填充迷宫求解

洪水填充是赢得大多数 Micromouse 比赛的算法，也是理解“在不确定之下做规划”很好的入门教材。和教科书式的寻路不同，迷宫机器人不是一开始就拿到完整地图的——它必须一边开一边发现墙。洪水填充正是为这一点而设计的。在迷宫求解模拟器里看它跑起来。

距离场，而不是路径

洪水填充给每格赋一个数：它到目标的距离。目标格为零。从那里开始，每一个没被挡住的相邻格取比自己最低邻居多一的值，向外扩散，直到每个可达格都有了数值。

机器人从不存储路线。它只是站在一格里，看看邻居，然后踏进任何数值恰好低一的那一格。距离场就是规划，这也正是它在地图变化时能优雅恢复的原因。

对未知的墙保持乐观

机器人看不到整个迷宫，所以洪水填充把它尚未感知到的每一面墙都当作开放的。这种乐观给出了可能的最短估计，也让机器人持续朝目标移动，而不是漫无目的地探索。

当某个传感器揭示出一面原本被假定开放的墙时，机器人会记录它——在共享边的两侧都记——然后重算距离场。规划自我修正，机器人从它所在的位置继续。

为什么第一趟不是最短路

一个常见的意外：洪水填充并不保证第一趟走出最短路线。因为它是在乐观假设下行动的，它找到的是一条通往目标的路，不一定是最好的那一条。真实的 Micromouse 机器人用两个阶段：

1. 一趟搜索，探索足够多的迷宫以建立准确的地图。
2. 一趟速度跑，沿着完整地图揭示出来的最短路径跑。

在早期阶段，高效的探索比第一趟的最优性重要得多。

洪水填充与 BFS 和 A* 的对比

广度优先搜索和 A* 是在一张你已经知道的图上做规划。洪水填充是为一个你还在发现中的迷宫设计的：每出现一面新墙它就重新填充一次。数学上这次填充就是一次广度优先的距离计算——区别在于洪水填充预期地图会持续变化，而且重算很便宜。

它也胜过简单的沿墙走（始终让一只手扶着墙），后者到不了迷宫中心的目标，也很少找到短路。

感知—规划—运动这个环

void planOneCell(Maze& map, Robot& robot) {
  map.observe(robot.cell(), robot.senseLeftFrontRight());
  map.floodFill(centerGoals);
  Cell next = map.bestDescendingNeighbor(robot.cell());
  robot.turnAndMoveTo(next);
}

把感知、建图、规划和运动保持为彼此独立的步骤。正是这条边界，让同一个规划器既能在浏览器模拟器里跑，也能在你的桌面上跑，还能在装了真实距离传感器和编码器的 ESP32 上跑。

完整的填充

距离场就是从目标出发的一次广度优先展开，短到可以完整写出来：

const uint8_t N = 16;                       // 16 x 16 maze
uint8_t dist[N][N];                         // distance to goal, per cell
uint8_t walls[N][N];                        // bitmask: 1=N, 2=E, 4=S, 8=W

// A simple ring buffer beats a std::queue on a microcontroller.
uint8_t queueR[N * N], queueC[N * N];

void floodFill(const uint8_t goals[][2], uint8_t goalCount) {
  memset(dist, 255, sizeof(dist));          // 255 = unreachable

  uint16_t head = 0, tail = 0;
  for (uint8_t g = 0; g < goalCount; g++) {
    const uint8_t r = goals[g][0], c = goals[g][1];
    dist[r][c] = 0;
    queueR[tail] = r; queueC[tail] = c; tail++;
  }

  const int8_t dr[4] = {-1, 0, 1, 0};       // N, E, S, W
  const int8_t dc[4] = { 0, 1, 0, -1};

  while (head < tail) {
    const uint8_t r = queueR[head], c = queueC[head];
    head++;

    for (uint8_t d = 0; d < 4; d++) {
      if (walls[r][c] & (1 << d)) continue;             // wall in the way

      const int8_t nr = r + dr[d], nc = c + dc[d];
      if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

      if (dist[nr][nc] > dist[r][c] + 1) {              // 255 means unvisited
        dist[nr][nc] = dist[r][c] + 1;
        queueR[tail] = nr; queueC[tail] = nc; tail++;
      }
    }
  }
}

这就是整个算法。在 16×16 的迷宫上它最多访问 256 格，在 Arduino 上远不到一毫秒就跑完——这正是每发现一面新墙就整个重新填充完全负担得起的原因，也是没人费劲去做增量更新的原因。

墙要记在两侧

洪水填充最常见的缺陷根本不在填充本身。一面墙被两格共享，只在一侧记录它，会产出一张机器人能从一个方向穿过去、却不能从另一个方向穿过去的地图：

void setWall(uint8_t r, uint8_t c, uint8_t dir) {
  walls[r][c] |= (1 << dir);

  const int8_t dr[4] = {-1, 0, 1, 0};
  const int8_t dc[4] = { 0, 1, 0, -1};
  const int8_t nr = r + dr[dir], nc = c + dc[dir];
  if (nr < 0 || nr >= N || nc < 0 || nc >= N) return;

  walls[nr][nc] |= (1 << ((dir + 2) % 4));   // the same wall, from the other side
}

(dir + 2) % 4 就是反方向——北变南，东变西。这一点写错的症状是，机器人规划出一条径直穿过它亲手记录下来的墙的路线，看着确实让人一头雾水。

在 Arduino 上的内存

16×16 的迷宫放在 Uno 的 2 KB SRAM 上很紧，但可行，而且这份账值得在以困难方式发现之前就算清：

队列是最贵的部分，也最容易缩小：改成一个装 r<<4|c 打包字节的数组就能减半到 256 B。如果还是紧，把墙图按每格 2 位打包又能省下 192 B。大多数人到这里会直接转去买 ESP32 或 Mega，这也是个合理的决定——不过把东西塞进内存这个练习本身就有教益。

目标格怎么选

标准 Micromouse 的目标是中心的 2×2 块，而不是单独一格，而且这不是细节。把四格都用距离 0 作为种子，意味着机器人会朝那个方块它能以最低代价抵达的那一面冲——这既更快，也比死盯着某一个它可能只能从一个别扭方向靠近的格子更稳健。

上面代码已经处理了这一点：把四格都传进 goals，填充会同时从它们每一格开始。这是距离场方法一个实实在在的优势——多目标不花任何代价，而 A* 需要改启发式。

把探索做对

洪水填充告诉机器人在它已知的信息下该往哪走。它对机器人该学什么一个字也说不出来，而一台只沿梯度下降的机器人会到达目标，却根本没看见迷宫的大部分——于是速度跑所谓的“最短路”，只是在它碰巧走过的那几条走廊里最短。

竞赛中常见的折中是第二行或第三行：先到达目标，然后朝起点方向反向填充并按那条路开，这自然会揭示出另一批走廊。两次遍历通常能产出一张足够好的地图，让速度跑落在最优的几个百分点之内。

故障排查

第五行是重要那一行，值得明说：**算法不是 Micromouse 的难点。**洪水填充只有四十行，你可以在模拟器里完全不用硬件就把它验证掉。难点在于走出十格之后，机器人已经不在它以为自己所在的位置了，而一份从一个虚构位置出发执行的完美规划，会径直开进墙里。

自己试试

在迷宫求解模拟器里一格一格地走，看着机器每发现一面墙距离场就重算一次。看着那些数字变化，是理解“为什么机器人永远有一份可用规划”最快的方式。