电脑鼠走迷宫：从DFS探索到BFS寻路的算法与嵌入式实践

1. 项目概述：从玩具到算法的经典实践

“电脑鼠走迷宫”听起来像是一个复古的电子玩具项目，但在算法学习和嵌入式系统开发领域，它却是一个历久弥新的经典课题。我第一次接触这个项目还是在大学实验室，当时觉得就是让一个小车在格子里乱撞，后来自己动手实现，才发现它完美融合了硬件控制、传感器融合、路径规划和算法优化，是一个绝佳的综合性练手项目。简单来说，它的核心任务是：让一个搭载了微控制器和传感器的自主移动机器人（即“电脑鼠”），在一个由纵横墙壁构成的未知迷宫中，从起点出发，自主探索并找到通往终点的最短路径。

这个项目的魅力在于其清晰的阶段性目标。第一阶段是“探索”，电脑鼠需要像盲人摸象一样，利用传感器（通常是红外或超声波）探测周围墙壁，构建迷宫地图。第二阶段是“求解”，在内存中基于已探索的地图，运行路径搜索算法（如标题中的DFS深度优先搜索和BFS广度优先搜索）来计算从当前位置到目标点的可行路线。第三阶段是“冲刺”，让电脑鼠沿着计算出的最短路径，以尽可能快的速度、稳定地跑到终点。整个过程，是对一个嵌入式智能体“感知-决策-执行”闭环的完整模拟。

为什么DFS和BFS会成为这个项目的经典组合？因为它们在算法特性上形成了完美互补。DFS（深度优先搜索）就像一个有冒险精神的探索者，它会选择一条路走到黑，直到碰壁再回溯，这种策略在探索未知迷宫时非常高效，能快速覆盖大面积区域，但找到的路径往往不是最短的。而BFS（广度优先搜索）则像一个稳健的规划者，它从起点开始一层层均匀向外扩散，确保第一次到达终点时所走过的路径，一定是步数最短的（在无权图中）。因此，常见的策略是：在探索阶段用DFS快速摸清迷宫全貌并记录地图；在已知地图后，用BFS来求解起点到终点的最短路径，用于最后的冲刺跑。

这个项目适合所有对机器人、算法和嵌入式开发感兴趣的朋友。无论你是刚学完数据结构想找实战项目的学生，还是想重温经典算法的工程师，都能从中获得扎实的锻炼。接下来，我将拆解整个系统的设计思路、核心算法实现、软硬件联调的坑点，以及如何让你的“老鼠”既聪明又跑得快。

2. 核心思路与系统架构设计

做一个能走的电脑鼠，远不止写个算法那么简单。它是一个软硬件紧密结合的微型系统。在动手写代码前，必须把整体架构想清楚，这能避免后期无数头疼的联调问题。

2.1 硬件平台选型与核心模块

电脑鼠的硬件可以很简单，也可以很复杂。对于入门和大多数竞赛，一个经典配置完全够用：

• 主控芯片（大脑）：STM32系列（如F103C8T6，即“蓝桥杯”）、Arduino（如Mega2560）或ESP32是主流选择。STM32性能强大、外设丰富，适合对实时性要求高的场景；Arduino生态好，上手快；ESP32则自带Wi-Fi/蓝牙，方便调试。我个人更推荐STM32，它的定时器、中断系统能让你更精细地控制电机和传感器时序。
• 运动模块（腿脚）：通常由两个带编码器的直流减速电机配合轮子实现差速转向。编码器至关重要，它能反馈电机的实际转速和行走距离，是实现精准直线行走和转弯的基石。电机驱动芯片常用L298N或TB6612FNG，后者体积小、发热低，是更优的选择。
• 感知模块（眼睛）：迷宫墙壁的探测主要靠红外传感器。常见方案是在车体左、前、右各安装一对红外发射接收管，用于探测对应方向的墙壁。高级一点的会用到多对传感器阵列，或者使用激光测距（如VL53L0X）来获得更精确、更稳定的距离信息。一个关键细节：迷宫墙壁通常是白色底板+黑色墙条，红外传感器的读数受环境光影响巨大。因此，传感器电路最好设计成“调制解调”式，即让红外管以特定频率发射，接收端只解调该频率的信号，能极大抗环境光干扰。
• 电源模块（心脏）：千万别小看电源。电机启动瞬间电流很大，会造成电压骤降，导致单片机复位。方案是：使用大容量（如18650）锂电池，配合独立的电机驱动供电和单片机稳压电路，中间用二极管或MOS管做一定隔离，并在单片机电源入口加一个大电容（如470uF）缓冲。

整个系统的信息流是这样的：红外传感器实时采集墙壁信息 -> 主控芯片处理数据，更新内部迷宫地图 -> 路径规划算法（DFS/BFS）根据当前地图和目标点计算下一步动作 -> 主控芯片生成电机控制指令（PWM波） -> 电机驱动驱动电机运动 -> 编码器反馈实际位置，形成闭环控制。

2.2 迷宫表示与地图数据结构

在代码世界里，我们首先要将物理迷宫抽象成计算机能处理的数据。最经典的方法是使用“单元格”法。

• 迷宫离散化：将整个迷宫划分为N×N的网格，每个网格是一个单元格（Cell）。标准竞赛迷宫通常是16x16格，每个格子大小约18cm见方。电脑鼠的物理尺寸通常占据一个格子。
• 单元格数据结构：每个单元格需要记录其四面（东、南、西、北）的墙壁状态。我们可以用一个16位的整数（uint16_t）来表示一个格子，用其中的4个比特位来分别代表四个方向的墙是否存在（1有墙，0无墙）。例如：

  #define WALL_NORTH (1 << 0) #define WALL_EAST (1 << 1) #define WALL_SOUTH (1 << 2) #define WALL_WEST (1 << 3) typedef struct { uint16_t walls; // 墙壁状态 uint8_t x, y; // 坐标 bool visited; // 探索标记 } Cell;

• 地图的存储：用一个二维数组Cell maze[SIZE][SIZE]来存储整个迷宫地图。初始化时，所有格子的墙壁状态设为“未知”或“假设有墙”（安全起见），visited标记为false。随着探索进行，根据传感器读数更新对应坐标格子的墙壁状态，并将visited设为true。

这里有一个极易出错的关键点：坐标系与方向管理。电脑鼠在迷宫中的朝向（北、东、南、西）是相对的，而我们的地图是绝对的。必须时刻维护一个变量current_dir来记录鼠标当前的绝对朝向。当传感器检测到“左边有墙”时，你需要根据current_dir换算成地图上的绝对方向（北/东/南/西），再去更新对应格子的墙壁状态。同理，当算法决定“向前走一格”时，也需要根据当前朝向换算成地图上的坐标增量。混乱的方向管理是初期bug的主要来源，务必封装成函数，如getAbsoluteDir(RelativeDir rel_dir)和moveForward()。

3. 核心算法解析：DFS探索与BFS寻路

这是项目的灵魂所在。我们将深入代码层面，看看DFS和BFS如何在这个具体场景中落地。

3.1 深度优先搜索（DFS）——未知迷宫的探索者

DFS的核心思想是“一路到底，碰壁回头”。在电脑鼠探索中，我们通常实现的是基于栈的DFS。

算法流程如下：

1. 将起点单元格标记为已访问，并将其压入栈中。
2. 当栈不为空时，取出栈顶单元格作为当前单元格。
3. 检查当前单元格的未访问且无墙阻挡的邻居方向。
4. 如果存在这样的邻居，随机选择一个（或按固定优先级，如左前右），将当前单元格压回栈（用于回溯），然后让电脑鼠实际运动到该邻居单元格，标记其为已访问并将其压入栈。
5. 如果不存在未访问的邻居，则从栈中弹出当前单元格（回溯），此时栈顶元素就是上一个位置，控制电脑鼠倒退/转身回到该位置。
6. 重复步骤2-5，直到所有可达单元格都被访问，或者找到目标点（如迷宫中心）。

C语言实现的简化代码骨架：

#define MAZE_SIZE 16 Cell maze[MAZE_SIZE][MAZE_SIZE]; int current_x = 0, current_y = 0; // 起点(0,0) Direction current_dir = NORTH; // 初始朝北 // 方向偏移量 int dx[4] = {0, 1, 0, -1}; // 北，东，南，西 int dy[4] = {1, 0, -1, 0}; void dfsExplore() { Stack stack; initStack(&stack); push(&stack, current_x, current_y); maze[current_x][current_y].visited = true; while (!isStackEmpty(&stack)) { Point top; peek(&stack, &top); // 查看栈顶但不弹出 // 1. 获取当前可去的、未访问的邻居方向 Direction neighbors[4]; int count = getUnvisitedOpenNeighbors(top.x, top.y, neighbors); if (count > 0) { // 2. 选择一个方向（例如优先级：直行 > 左转 > 右转 > 掉头） Direction next_dir = chooseDirection(neighbors, count); // 3. 控制鼠标转向并前进一格到新格子 rotateTo(next_dir); moveOneCell(); // 4. 更新坐标和朝向 updatePosition(&current_x, ¤t_y, ¤t_dir, next_dir); // 5. 标记新格子并压栈 maze[current_x][current_y].visited = true; push(&stack, current_x, current_y); } else { // 6. 没有未访问邻居，回溯 pop(&stack, &top); // 弹出栈顶（当前位置） if (!isStackEmpty(&stack)) { Point prev; peek(&stack, &prev); // 查看新的栈顶（上一个位置） // 控制鼠标回溯到上一个位置 backtrackTo(prev.x, prev.y); current_x = prev.x; current_y = prev.y; // 注意：回溯后需要重新计算当前朝向，这需要额外记录 } } // 此处可添加检测是否到达目标点的逻辑 } }

DFS探索的实操心得：

• “随机选择” vs “固定优先级”：完全随机选择可能导致探索效率低下。实践中，给“直行”赋予最高优先级，能减少不必要的转弯，提升探索速度。这模拟了生物倾向于沿直线前进的习性。
• 回溯的实现：让电脑鼠物理上倒退回上一个格子通常耗时且容易出错。更高效的做法是：在栈中不仅存储坐标，还存储从上一个格子是如何到达这个格子的（即“父方向”）。这样，当需要回溯时，算法层面直接“跳回”上一个格子，而电脑鼠无需实际倒退，只需在下一个探索步骤中，从新的“当前格子”开始计算即可。鼠标的物理位置只在前进时更新。
• 栈溢出风险：迷宫最大可能路径很长，栈空间要足够。对于16x16迷宫，栈大小设为256是安全的。

3.2 广度优先搜索（BFS）——最短路径的规划师

当探索完成，地图已知后，我们需要计算从起点（或任意点）到终点（如中心区域）的最短路径。BFS是解决无权图最短路径问题的利器。

算法流程如下：

1. 创建一个队列，将起点单元格入队，并标记其距离为0，前驱节点为空。
2. 当队列不为空时，取出队首单元格。
3. 遍历该单元格的所有可达邻居（即没有墙阻挡的方向）。
4. 如果邻居单元格未被访问过（在BFS上下文中），则将其距离设为当前单元格距离+1，记录前驱节点为当前单元格，然后将其入队。
5. 重复步骤2-4，直到队列为空或遇到目标单元格。
6. 从目标单元格开始，沿着记录的前驱节点一路回溯到起点，这条路径就是最短路径。

C语言实现的简化代码骨架：

typedef struct { int x, y; int dist; // 从起点到该点的距离 Point parent; // 前驱节点，用于回溯路径 } BFSNode; bool bfsFindPath(Point start, Point goal, Direction path[], int *path_len) { bool visited[MAZE_SIZE][MAZE_SIZE] = {false}; BFSNode queue[MAZE_SIZE * MAZE_SIZE]; int front = 0, rear = 0; // 起点入队 queue[rear++] = (BFSNode){start.x, start.y, 0, {-1, -1}}; visited[start.x][start.y] = true; while (front < rear) { BFSNode current = queue[front++]; // 找到目标 if (current.x == goal.x && current.y == goal.y) { // 回溯构建路径 *path_len = 0; Point p = {current.x, current.y}; while (p.x != -1 && p.y != -1) { // 根据p和它的parent，判断移动方向，存入path[] // ... 回溯逻辑 ... p = parent_of_p; // 获取p的前驱节点 } reversePath(path, *path_len); // 路径是反的，需要反转 return true; } // 遍历四个方向 for (Direction dir = 0; dir < 4; dir++) { if (!hasWall(current.x, current.y, dir)) { // 该方向无墙 int nx = current.x + dx[dir]; int ny = current.y + dy[dir]; if (isInMaze(nx, ny) && !visited[nx][ny]) { visited[nx][ny] = true; queue[rear++] = (BFSNode){nx, ny, current.dist + 1, {current.x, current.y}}; } } } } return false; // 未找到路径 }

BFS寻路的注意事项：

• 路径存储：BFS找到的是最短步数路径，但存储的是一系列“方向”指令。回溯生成路径时，需要将连续的坐标差转换为具体的转向指令（直行、左转90度、右转90度、掉头180度）。
• 多终点处理：迷宫竞赛的目标常是中心4个格子。BFS可以稍作修改，将这四个格子都视为目标，谁先被搜到，路径就是到该格子的最短路径。
• 与DFS地图的衔接：BFS运行在DFS探索后生成的maze地图上。务必确保地图信息准确，特别是墙壁信息。一个错误的墙壁标记会导致BFS计算出错误甚至撞墙的路径。

4. 运动控制与系统集成：让算法落地跑起来

算法算出路径只是纸上谈兵，让电脑鼠精准、快速地执行这些动作，才是真正的挑战。这部分是软硬件结合的深水区。

4.1 精准的电机闭环控制

让两个轮子精确地走直线、转固定的角度，需要闭环控制。核心是PID控制器。

• P（比例）：当前误差乘以一个系数。误差大，输出就大，快速响应。
• I（积分）：累积历史误差，消除静态误差（比如始终差一点）。
• D（微分）：预测误差变化趋势，抑制超调，让系统更稳定。

对于电脑鼠的差速驱动，我们需要两个PID环：

1. 速度环：每个电机独立一个PID。输入是目标转速（由“走一格”或“转90度”换算而来）和编码器反馈的实际转速，输出是PWM占空比。保证每个轮子自己能稳定达到目标转速。
2. 位置环/航向环（可选但推荐）：在直线行走时，比较左右轮编码器的累计脉冲数。如果左轮慢了，就微增左轮速度目标，微减右轮速度目标，形成差速来纠正航向偏航。这能有效对抗地面摩擦不均、电池电压变化等干扰。

PID参数整定是个经验活：

• 先P后I再D：先把I和D设为0，逐渐增大P，直到电机出现轻微、稳定的振荡。然后取这个P值的50%-60%作为基础。
• 加I消静差：加入较小的I值，观察是否能消除到达目标速度后的小幅稳态误差。I值太大会引起积分饱和，导致系统反应迟钝甚至失控。
• 加D抑超调：最后加入D，观察快速加速或减速时，是否能让曲线更平滑，超调更小。D值对噪声敏感，编码器信号最好做滤波处理。
• 实测技巧：在电脑鼠静止时，用手轻轻阻碍一个轮子，观察它能否“较劲”地试图回到目标速度（这考验P和I）。快速推动它然后松开，看它能否平稳停下而不来回晃（这考验D）。

4.2 动作序列的执行与状态机

电脑鼠的执行过程不是一个死循环，而是一个清晰的状态机。这能让代码结构清晰，易于调试。

typedef enum { STATE_IDLE, // 空闲 STATE_EXPLORING, // DFS探索中 STATE_CALCULATING, // 计算最短路径（BFS） STATE_RUNNING_PATH, // 执行路径冲刺 STATE_TURNING, // 正在转弯（子状态） STATE_MOVING, // 正在直行一格（子状态） STATE_FINISHED // 任务完成 } MouseState; MouseState current_state = STATE_IDLE; Direction planned_path[MAX_PATH_LEN]; int path_index = 0; void mainLoop() { switch (current_state) { case STATE_IDLE: if (startButtonPressed()) { initMaze(); current_state = STATE_EXPLORING; } break; case STATE_EXPLORING: runDFSOneStep(); // 每次循环只执行DFS的一步（前进一格或回溯） if (isExplorationDone()) { current_state = STATE_CALCULATING; } break; case STATE_CALCULATING: if (bfsFindPath(current_pos, goal, planned_path, &path_length)) { path_index = 0; current_state = STATE_RUNNING_PATH; } else { // 路径计算失败处理 } break; case STATE_RUNNING_PATH: if (path_index >= path_length) { current_state = STATE_FINISHED; break; } Direction next_action = planned_path[path_index]; if (next_action == MOVE_FORWARD) { current_state = STATE_MOVING; startMovingOneCell(); } else { current_state = STATE_TURNING; startTurning(next_action); // 传入转向方向 } break; case STATE_TURNING: if (isTurningFinished()) { path_index++; current_state = STATE_RUNNING_PATH; } break; case STATE_MOVING: if (isMovingOneCellFinished()) { path_index++; current_state = STATE_RUNNING_PATH; } break; case STATE_FINISHED: stopAllMotors(); blinkLED(); break; } }

这种状态机设计，使得上层逻辑非常清晰，并且将耗时的动作（转弯、直行）转化为非阻塞的、由子状态管理的过程，系统可以实时响应传感器数据。

4.3 传感器数据处理与地图更新

传感器的读数不是非0即1的。它可能是模拟量（ADC值），且存在噪声。

• 阈值校准：在迷宫现场，让电脑鼠分别面对“有墙”和“无墙”的情况，读取传感器原始值，取一个中间值作为阈值。最好能有“不确定”区间，避免在边界附近抖动。
• 滤波算法：简单的移动平均滤波或中值滤波能有效去除毛刺。例如，连续采样5次，去掉最大最小值后取平均。
• 地图更新策略：当传感器判定“有墙”时，直接设置该方向墙状态为true。当判定“无墙”时，需要谨慎：如果该格子从未被访问过，可以设置为false；如果已经被访问过且之前记录为true（有墙），则可能意味着上次探测有误，或者是可穿过的虚墙？这需要根据比赛规则来定。通常采取保守策略：只增不减，即一旦标记为有墙，就不再清除，除非有特别可靠的多次反证。这能保证安全性，避免撞墙。

5. 调试技巧、常见问题与性能优化

做到这里，你的电脑鼠应该能磕磕绊绊走完全程了。但要让它跑得又快又稳，还需要下面这些“踩坑”换来的经验。

5.1 调试：没有显示屏怎么办？

嵌入式开发，调试是一大难关。除了LED灯和蜂鸣器这种原始手段，强烈推荐使用串口打印。

• 将迷宫地图实时打印到电脑串口助手，用字符图形显示（比如#表示墙，.表示空地，M表示鼠标位置）。这是最直观的调试方式。
• 打印传感器原始值、PID输出、当前状态、坐标等关键变量。
• 注意：在最终冲刺跑时，要关闭或尽量减少串口打印，因为打印函数非常耗时，会影响实时控制。

5.2 常见问题排查清单

5.3 性能优化与进阶思路

当基础功能实现后，你可以尝试以下优化，让成绩大幅提升：

• “洪水填充”算法：这是比BFS更受竞赛欢迎的最短路径算法。它给每个单元格一个“距离值”（洪水的水位），从目标点开始“淹没”，所有单元格的值等于其邻居最小值+1。鼠标只需一直走向数值更小的邻居，就能走最短路径回家。它计算一次就能得到所有点到目标的最短路径，非常适合需要多次往返搜索的比赛。
• 对角线冲刺：如果比赛规则允许，且你的鼠标运动控制足够精准，可以规划斜向路径（穿过格子中心交点），距离比曼哈顿距离更短，但对控制和传感器定位要求极高。
• 滑动转弯与全速冲刺：高级鼠标不是“停稳-转弯-启动”，而是通过两轮差速实现平滑的弧线转弯，在出弯时就已经加速，全程不损失动能。这需要非常高阶的运动控制算法。
• 多目标点优化：终点是中心4个格子的任意一个。可以在探索时实时计算到每个可能目标点的距离，一旦发现某个目标可达，立即评估是否值得前往，实现探索与冲刺的智能结合。

从让电脑鼠动起来，到能探索，再到找到路，最后跑出速度，每一个阶段都会遇到不同的问题。这个项目的价值不仅在于结果，更在于解决问题的整个过程。它强迫你去思考硬件如何与软件对话，算法如何适应物理世界的噪声和不完美，是一个从理想代码走向现实工程的绝佳桥梁。我最深的体会是，调试的时间远多于写代码的时间，而一个清晰的系统状态机和可靠的调试接口，是节省时间最重要的法宝。当你第一次看到它靠自己跑完全程时，那种成就感是无可替代的。不妨就从最基础的DFS探索和BFS寻路开始，一步步让你的“老鼠”聪明起来吧。