1. 项目缘起：从“玩具”到“算法竞赛”的经典载体

第一次听说“电脑鼠”这个名字，很多人可能会联想到实验室里的小白鼠，或者某种电子宠物。但实际上，在嵌入式系统、机器人以及算法竞赛的圈子里，“电脑鼠”（Micromouse）是一个有着近五十年历史的经典项目。它的核心任务非常简单：让一个巴掌大小、自带传感器的自主机器小车，在一个由16x16方格组成的迷宫中，从起点出发，以最快的速度找到通往中心区域的路径，并最终冲刺到终点。

听起来像是个高级玩具？恰恰相反，它是对一个嵌入式系统综合能力的终极考验。这个小车需要自己感知环境（通过红外或超声波传感器探测墙壁），自己决策（运行寻路算法规划路径），自己控制电机完成精准的移动和转向。而这一切，都发生在一块通常只有单片机级别的微控制器上，对代码的效率、算法的优雅以及硬件控制的精准度提出了极高的要求。其中，最核心、最引人入胜的部分，就是迷宫搜索算法。而深度优先搜索（DFS）和广度优先搜索（BFS），正是解决这个问题的两把经典钥匙，也是几乎所有电脑鼠爱好者入门时必经的“算法初体验”。

我最初接触电脑鼠，是在大学的一个创新实验室里。看着前辈们调试的小车在迷宫里磕磕绊绊，时而撞墙，时而原地打转，最终却总能找到出路，那种软硬件结合带来的成就感是纯软件仿真无法比拟的。今天，我就以“DFS+BFS”这个经典组合为线索，为你彻底拆解电脑鼠走迷宫的核心原理、实现细节，以及那些只有真正动手做过才会知道的“坑”和技巧。无论你是正在准备相关竞赛的学生，还是对嵌入式算法感兴趣的开发者，这篇文章都能给你一份可以直接“抄作业”的实战指南。

2. 迷宫世界的数字化：环境建模与地图表示

在让算法思考之前，我们必须先教会电脑鼠“看”懂迷宫。迷宫对于小车来说，不是一幅视觉图像，而是一系列离散的、逻辑化的信息。因此，环境建模是第一步，也是最基础的一步。

2.1 迷宫的标准与抽象

国际上标准的电脑鼠迷宫由16x16个方格单元（Cell）组成，每个单元是一个边长约18厘米的正方形，四周可能有墙壁。小车从迷宫的一个角落（通常是东南角或西南角）出发，目标是到达中心的4个单元（7,7), (7,8), (8,7), (8,8)中的任何一个。迷宫的整体尺寸、墙壁高度、方格大小都有严格规定，这保证了竞赛的公平性，也为我们设计算法提供了统一的抽象模型。

我们需要将物理迷宫转化为计算机内存中一个可操作的数据结构。最经典和实用的方法是使用两个二维数组来分别表示迷宫墙壁信息和单元访问信息。

// 假设迷宫为16x16，每个单元有东、西、南、北四面墙 #define MAZE_SIZE 16 // 墙壁地图：记录迷宫中永久存在的墙壁 // wall_map[x][y] 的每一位代表一个方向的墙（如用4位二进制：北、东、南、西） uint8_t wall_map[MAZE_SIZE][MAZE_SIZE]; // 访问与代价地图：记录搜索过程中的动态信息 uint16_t cost_map[MAZE_SIZE][MAZE_SIZE]; // 从起点到该点的代价（步数或时间） bool visited[MAZE_SIZE][MAZE_SIZE]; // 该单元是否已被访问

wall_map是核心。初始化时，我们只知道迷宫边界有墙（最外一圈），内部墙壁全是未知。当小车用传感器探测时，它会更新当前位置周围（东、西、南、北）的墙壁状态。例如，如果前方传感器返回的距离小于一个阈值，我们就在wall_map[current_x][current_y]的相应方向位上标记“有墙”。

注意：传感器融合与滤波。在实际中，红外传感器容易受到地面颜色、环境光线影响，产生误判。一个实用的技巧是“多次采样中值滤波”和“运动验证”。比如，在前进到下一个格子前，连续采样5次前方距离，取中值作为判断依据；或者在怀疑某面墙是否存在时，可以尝试让小车轻微左右摆动，从不同角度探测，综合判断。直接相信单次传感器读数，是新手翻车的最常见原因。

2.2 方向与坐标系统定义

为了编程方便，必须定义一套统一的方向和坐标系。通常，我们让迷宫的行索引（y轴）向北增加，列索引（x轴）向东增加。起点设为(0,0)。方向可以用枚举表示：

typedef enum { NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3 } Direction;

当前小车的状态，就可以用一个结构体来完整描述：

typedef struct { int16_t x; // 当前列坐标 int16_t y; // 当前行坐标 Direction heading; // 当前车头朝向 } MouseState;

这个MouseState是算法运行的“上下文”。所有决策（下一步去哪、如何转向）都基于当前状态和wall_map提供的信息。清晰、无歧义的数据模型，是后续复杂算法稳定运行的基础。很多调试时的灵异事件，追根溯源都是坐标转换或方向计算出了差一错误（Off-by-one error）。

3. 深度优先搜索（DFS）：勇往直前的探路者

DFS的策略非常符合人类直觉：一条路走到黑，碰壁了就回头，换个方向继续走。在电脑鼠的语境下，它体现为一种递归回溯的搜索方式，目标是探索并记忆整个迷宫的地图，而不是第一时间找到最短路径。

3.1 DFS的核心算法流程

DFS算法维护一个“栈”（可以是函数调用栈，也可以是显式栈数据结构），用来记录访问路径。其核心伪代码如下：

函数 DFS(当前节点): 标记当前节点为已访问 如果当前节点是目标中心点: 记录路径，返回成功 获取当前节点所有未访问且可通行的邻居节点（顺序很重要：直行优先？右转优先？） 对于每一个邻居节点: 让小车实际移动到邻居节点（调用移动控制函数） 递归调用 DFS(邻居节点) 如果递归返回成功，则逐层返回成功 否则，让小车回溯到当前节点（调用回溯移动函数） 如果所有邻居都尝试失败，返回失败

这里的关键在于“移动”和“回溯”。移动不是简单的坐标加一，而是需要控制小车完成前进、转向（左转90度、右转90度、掉头180度）等一系列物理动作。回溯更是难点，它要求小车能精确地沿原路返回，这依赖于对移动历史的完整记录。

3.2 DFS的代码实现与优化技巧

一个典型的非递归（显式栈）DFS实现可能如下所示，这更适合资源有限的嵌入式环境：

#define MAX_STACK_SIZE 256 MouseState stack[MAX_STACK_SIZE]; int stack_top = -1; bool dfs_explore() { MouseState current = {0, 0, NORTH}; // 起点状态 push_to_stack(current); visited[0][0] = true; while (stack_top >= 0) { current = stack[stack_top]; // 检查是否到达中心 if (is_goal(current.x, current.y)) { return true; // 找到一条通路 } // 获取可行的下一个方向（按特定优先级） Direction next_dir = get_next_unvisited_direction(current, wall_map, visited); if (next_dir != INVALID) { // 计算下一个位置 MouseState next_state = calculate_next_state(current, next_dir); // 执行物理移动：先转向，再前进一格 execute_move(current.heading, next_dir); // 更新状态，压栈 push_to_stack(next_state); visited[next_state.x][next_state.y] = true; // 探测新位置的墙壁信息，更新wall_map update_wall_map(next_state); } else { // 无路可走，回溯 pop_from_stack(); // 弹出当前节点 if (stack_top >= 0) { MouseState prev_state = stack[stack_top]; // 执行回溯移动：需要掉头并返回上一格 execute_backtrack(current, prev_state); current = prev_state; } } } return false; // 栈空，迷宫无解（理论上标准迷宫必有解） }

几个至关重要的优化点：

1. 方向探索优先级：get_next_unvisited_direction函数的优先级策略直接影响探索效率。一个经验策略是“直行优先，然后右转，最后左转”。因为保持直行能耗最低、耗时最短。这能在探索阶段就为后续的速度赛积累时间优势。
2. 移动执行单元：execute_move函数是硬件相关的核心。它需要根据当前朝向(current.heading)和目标朝向(next_dir)计算转向动作（左转90、右转90、掉头180），然后发出精确的脉冲控制电机走过一格的距离。这里的电机PID控制参数需要精心调试，确保小车能走直线、转直角。
3. 回溯的实现：execute_backtrack不能简单地让小车掉头然后前进一格。因为迷宫格子可能有多种尺寸，且电机存在误差累积。更可靠的方法是：让小车在栈中保存的不是状态，而是动作序列。回溯时，逆序执行动作的逆动作（前进的逆动作是后退，左转的逆动作是右转）。这要求底层驱动同时实现前进、后退、左转、右转的精确控制。

踩坑实录：栈溢出与内存管理。在单片机上，递归DFS很容易导致调用栈溢出。因此，强烈建议使用显式栈，并严格控制栈大小。MAX_STACK_SIZE设置为256对于16x16迷宫是足够的（最坏情况遍历所有256格）。另外，visited数组可以用位域（bit-field）来节省内存，这对于只有几KB RAM的单片机意义重大。

DFS的优势在于实现相对简单，能完整探索迷宫并记录地图。但它找到的第一条路径往往不是最短的，弯弯绕绕很多。因此，DFS通常只用于初次探索建图。当完整的wall_map被构建出来后，我们就需要更聪明的算法来规划最短路径了。

4. 广度优先搜索（BFS）：稳扎稳打的最短路径规划师

如果说DFS是激进的探险家，BFS就是严谨的测绘员。BFS的核心思想是“层层推进”，从起点开始，先访问所有距离为1步的邻居，再访问距离为2步的邻居，以此类推。当它第一次访问到目标点时，所走过的路径必然是最短路径（在每一步代价相同的情况下）。在电脑鼠中，BFS不用于实时探索（因为要等一层全部访问完），而是用于在已知地图（wall_map）后，计算起点到终点的最短路径。

4.1 BFS的算法原理与队列实现

BFS使用队列（FIFO）数据结构。其经典流程如下：

函数 BFS(起点， 终点， 墙壁地图): 初始化一个队列Q 初始化代价地图cost_map，全部设为无穷大 初始化前驱地图prev，记录每个节点的“父节点” 将起点加入队列，cost_map[起点] = 0 当队列不为空时: 当前节点 = 出队队列 如果当前节点 == 终点: 跳出循环，反向根据prev构造最短路径 对于当前节点的每一个邻居节点（东、西、南、北）: 如果该方向没有墙，且邻居节点未被访问过（cost_map为无穷大）: cost_map[邻居] = cost_map[当前] + 1 prev[邻居] = 当前节点 将邻居节点入队 如果循环结束仍未找到终点，说明地图有误或终点不可达

这里的“代价”通常就是步数。cost_map不仅用于判断是否访问过，其最终值就是该点到起点的最短距离。prev数组或矩阵则像一串面包屑，让我们能从终点一步步倒退回起点，从而还原出整条路径。

4.2 路径还原与平滑优化

BFS结束后，我们得到的是一个从终点指向起点的反向链路。需要将其反转，并转换成一系列具体的移动指令（前进、左转、右转）。

// 假设prev是一个二维数组，每个元素存储父节点的坐标信息 PathNode* reconstruct_path(Point start, Point goal, PrevMap prev) { // 反向追踪 PathNode* path = NULL; Point current = goal; while (!points_equal(current, start)) { path = prepend_node(path, current); // 在链表头部插入 current = prev[current.x][current.y]; } path = prepend_node(path, start); return path; // 现在path是从起点到终点的一个坐标链表 }

得到坐标路径后，还需要将其转化为小车的动作序列。例如，路径是(0,0)->(0,1)->(1,1)。从(0,0)到(0,1)是向北直行。从(0,1)到(1,1)是向东，但小车当前头朝北，所以需要先右转90度，再直行。这个转换函数需要根据当前朝向和下一个目标点的相对位置，计算出最少的转向动作（直行、左转90、右转90、掉头）。

BFS的致命弱点与优化：标准的BFS找到的是“步数最短”路径，即转弯最少的路径。但对于追求极限速度的电脑鼠竞赛，这还不够。因为转弯，尤其是90度转弯，会耗费大量时间（减速、转向、再加速）。一个更优的路径可能是多走一两个直行格子，但减少一次转弯，总用时反而更短。

因此，高级的电脑鼠算法会对BFS进行加权改造。将cost_map中的代价从“步数”改为“预估时间”。直行动作的代价小（如权重1），转弯动作的代价大（如权重5，掉头权重10）。然后使用Dijkstra算法（本质是加权BFS）或A*搜索算法来规划一条“时间最短”路径。A*算法需要设计一个启发式函数（Heuristic），例如当前点到终点的曼哈顿距离，来引导搜索方向，效率更高。

实操心得：BFS的队列实现选择。在单片机上，用循环数组实现一个固定大小的队列是最稳妥高效的方式。务必在初始化时分配足够空间（如256个元素）。避免使用动态内存分配（malloc），在实时嵌入式系统中容易导致内存碎片和不可预知的行为。同时，prev地图的存储可以优化，不必存储完整的坐标，可以只存储来自哪个方向（4个值），用2个比特位即可表示，能极大节省内存。

5. 融合策略：DFS探索与BFS冲刺的经典组合

单独使用DFS或BFS都有明显缺陷。DFS探索的路径又长又绕；BFS需要已知地图。因此，在实际的电脑鼠竞赛中，最经典、最有效的策略就是“DFS探索建图 + BFS路径规划”的两阶段策略，有时甚至是多阶段循环。

5.1 标准两阶段流程详解

第一阶段：探索与建图 (DFS主导)

1. 小车从起点出发，使用DFS算法（或类似洪水填充算法）进行迷宫探索。
2. 探索的唯一目的是尽可能高效、完整地更新wall_map。不追求直接跑到终点。
3. 探索过程中，可以设定一些启发式规则来优化探索顺序，比如优先探索未知区域多的方向。
4. 当探索到迷宫中心（四个目标格之一）时，第一阶段并不立即结束。一个更优的策略是继续探索，直到确信地图的绝大部分（比如95%以上）已被探明，或者探索时间达到预设上限。因为更完整的地图能为第二阶段的路径规划提供更多优化可能。

第二阶段：最短路径冲刺 (BFS/A*主导)

1. 探索阶段结束后，小车内存中已有一张近乎完整的迷宫地图(wall_map)。
2. 小车利用这张地图，从当前所在位置到迷宫中心，运行加权BFS或A*算法，计算出一条时间代价最小的最优路径。
3. 小车沿着这条计算出的最优路径，以尽可能快的速度（通常是全速）运行到终点。这个阶段不再进行传感器探测（或只进行简单的防撞校验），专注于高速稳定的执行。

5.2 进阶：多阶段循环与动态重规划

对于更复杂的迷宫或追求更高性能，两阶段可以扩展为循环：

1. 探索-规划-执行-再探索循环：小车先探索一部分区域，规划一段路径并执行；到达新区域后，根据新的传感器信息更新地图，并立即重新规划从当前位置到终点的剩余路径。这类似于机器人领域的D* Lite算法思想，能应对一些探索初期因传感器误差导致的错误地图信息。
2. 中心冲刺后的再优化：当小车第一次到达中心后，它已经拥有了全迷宫地图。此时可以让小车回到起点，用完整地图规划出一条全局最优路径，进行最终的“速度赛”冲刺。这也是很多竞赛的标准流程：先有一个“探索赛”，然后有一个独立的“速度赛”。

实现上的关键接口：两个阶段切换的关键，在于状态机设计和数据共享。

typedef enum { STATE_EXPLORATION, STATE_PLANNING, STATE_SPRINT, STATE_FINISHED } MouseMode; MouseMode current_mode = STATE_EXPLORATION; MazeMap global_wall_map; // 被DFS和BFS共享 void main_loop() { switch (current_mode) { case STATE_EXPLORATION: if (dfs_exploration_step(&global_wall_map) == EXPLORE_DONE) { current_mode = STATE_PLANNING; } break; case STATE_PLANNING: optimal_path = a_star_plan(current_position, goal_center, &global_wall_map); current_mode = STATE_SPRINT; break; case STATE_SPRINT: if (execute_fast_path(optimal_path) == SPRINT_DONE) { current_mode = STATE_FINISHED; } break; // ... 其他状态处理 } }

这个状态机在每次主循环中执行一步，保证了系统的响应性。dfs_exploration_step是分步执行的DFS，避免长时间阻塞。

6. 超越算法：那些决定成败的工程细节

算法决定了策略的上限，而工程实现决定了项目的下限。一个设计精妙的算法，可能毁于糟糕的硬件调试。以下是几个比算法本身更让人头疼，也更能体现项目水准的工程环节。

6.1 传感器数据处理与地图纠错

传感器（尤其是红外对管）读数是不可靠的。除了前面提到的滤波方法，还必须有一套地图纠错机制。

• 冗余探测与投票机制：对于同一面墙，在不同位置、不同时间进行多次探测。只有超过一定次数（比如3次中有2次）确认为有墙，才最终更新wall_map。这能有效过滤偶然的噪声。
• 逻辑一致性检查：墙壁具有对称性。如果A单元的东侧有墙，那么其东边邻居B单元的西侧也必然有墙。在更新地图时，可以同时更新这两个对称位置的信息。如果发现矛盾（比如A记了有墙，B却记了无墙），说明之前某次探测有误，需要触发一次重新探测或采用更保守的策略（按有墙处理）。
• “幽灵墙”处理：有时因为传感器误判或迷宫反光，会记录下一堵不存在的“幽灵墙”。这会导致规划出的路径绕远路。一个应对策略是，在冲刺阶段，如果规划路径要求穿过一堵“墙”，而该墙只有单侧被探测到（另一侧未知或标记为无墙），可以尝试让小车以低速、谨慎的方式去“验证”这堵墙。如果确实没有，则更新地图并重新规划。这需要胆大心细的代码设计。

6.2 运动控制：从“能动”到“精准”

让轮子转起来很容易，让小车按预设的轨迹精准移动是另一回事。

• 开环与闭环控制：最基础的是开环控制，给电机发送固定数量、固定占空比的PWM脉冲，期望它走固定距离。但由于电池电压变化、地面摩擦系数不同、电机个体差异，开环控制误差会累积，导致越走越偏。闭环控制是必须的。使用编码器测量轮子实际转过的角度或脉冲数，与目标值比较，通过PID控制器动态调整PWM输出，实现精准的里程计（Odometry）。
• 转向控制：差速转向是主流。通过控制左右轮的速度差来实现原地转向或弧线转向。要实现精准的90度转向，不能简单地让左右轮一正一反转固定时间。同样需要编码器反馈，让两个轮子累计的行程差达到一个预定值（对应90度转向的理论轮程差）。这里PID参数（特别是比例系数P）的调试至关重要，调小了转不到位，调大了会振荡。
• 直线行走校正：即使两个轮子的PID参数调得一模一样，由于装配误差、轮胎磨损，小车也很难走绝对直线。需要在直线行走时，加入一个小的偏航角校正。可以通过陀螺仪（MPU6050等）读取Z轴的角速度积分得到偏航角，如果发现偏离了预定航向，就给一个微小的差速来纠正。这就是典型的航位推算（Dead Reckoning）+ 传感器融合。

6.3 系统调度与实时性

电脑鼠是一个典型的实时嵌入式系统。传感器读取、算法决策、电机控制、日志记录（如果有）需要在一个主循环中有序进行。

• 定时中断驱动：将最严格的任务放在定时器中断服务程序（ISR）中。例如，电机PID控制环和编码器计数读取，可以放在一个1kHz（1毫秒一次）的中断里，确保控制的及时性。
• 主循环分工：主循环负责执行周期稍长的任务，如：
  • 每20ms读取一次红外传感器ADC值并进行滤波。
  • 每50ms运行一次算法状态机的一步（dfs_exploration_step或执行一步路径）。
  • 每100ms通过串口发送一次调试信息（坐标、地图片段等）。
• 避免阻塞：所有函数都应该是非阻塞的。dfs_exploration_step执行一步就返回，而不是运行整个DFS循环。execute_move函数启动一个移动动作后立即返回，由后台的定时中断和状态机去完成移动过程，并通过一个标志位（如move_complete）来通知主循环动作已完成。这种基于状态机的异步编程模型，是保证系统响应流畅的关键。

调试这样的系统，一个逻辑分析仪或者一个能实时绘制小车轨迹和迷宫地图的上位机软件，其价值远超一个更快的单片机。

7. 从仿真到实车：我的踩坑与进阶之路

纸上得来终觉浅，绝知此事要躬行。最后，分享几个我从仿真到实车调试过程中，印象最深刻的教训和心得。

第一个大坑：仿真与现实的“鸿沟”。最初我在PC上用纯软件完美模拟了DFS和BFS算法，小车在虚拟迷宫里运行得行云流水。但一旦把代码烧录进实车，小车就开始“鬼畜”——时而对着空气猛冲（传感器误判无墙），时而在路口犹豫不决（算法循环超时）。教训是：仿真必须包含物理模型。后来的仿真器，我加入了传感器噪声模型（给探测结果加随机误判）、电机误差模型（左右轮速度有5%差异）、甚至地面摩擦系数变化。这样仿真出的问题，80%在实车上都会遇到。

第二个大坑：“最优路径”不等于“最快路径”。我们团队曾精心调教了A*算法，考虑了转弯代价，规划出的路径看起来非常高效。但在速度赛上成绩却不理想。后来用高速摄像机分析发现，小车在连续两个同方向转弯时（如“右转-直行-右转”），第二个转弯前速度还没提起来就要减速了。优化策略是：路径平滑（Path Smoothing）。在规划出的路径基础上，检查连续的几个节点，如果它们大致在一条直线上，就尝试“剪掉”中间点，让小车走一条更平滑的曲线（或长直线），即使总路程略长，但平均速度更高。这需要底层运动控制器支持弧线路径跟踪，难度更大，但效果显著。

第三个心得：调试信息是“第二双眼睛”。给小车加上蓝牙或NRF24L01无线模块，实时将它的坐标、朝向、传感器原始数据、地图数组发送到电脑上位机。用一个自己写的Python程序实时绘制迷宫地图和小车位置。当小车行为异常时，你看一眼上位机画面，立刻就能知道是地图出错了、坐标算错了、还是传感器发疯了。这比盯着串口看数字，或者靠猜，效率高出几个数量级。这项投入的时间，会在调试阶段十倍地回报给你。

电脑鼠项目就像一场微缩的机器人技术马拉松，它涵盖了感知、决策、控制、嵌入式开发等几乎所有核心环节。把DFS和BFS吃透，实现一个能稳定走完迷宫的小车，你已经超越了90%的纸上谈兵者。而当你开始纠结于一个转弯如何能再快0.1秒，一段代码如何能再节省100字节内存时，你就真正踏入了嵌入式系统与机器人技术的奇妙世界。这个过程痛苦且漫长，但当你看到那个自己亲手打造的小家伙，在迷宫里流畅地穿梭、精准地转向，最后冲向终点的那一刻，所有的熬夜和调试都值了。