四、迷宫算法的研究 （一）传统算法
电脑鼠的迷宫算法分为迷宫搜索算法和迷宫最优路径算法。迷宫搜索算法的目的是在没有预知迷宫路径的情况下从起点迷宫格搜索到终点迷宫格，再从终点迷宫格搜索到起点迷宫格，好的搜索算法要求以更短的时间搜索到更多的迷宫格，尽量避免重复搜索已经搜索过的地方。迷宫最短路径算法要求根据已知的迷宫信息找出一条从入口到出口的最优路径，最优路径不仅要短而且要求弯道尽量少。
常见的迷宫搜索算法有：
1.右手法则: 以右边为优先的前进方向,然后是直线方向、左边方向。 2.左手法则: 以左边为优先的前进方向,然后是直线方向、右边方向。 3.中左法则: 以直线为优先的前进方向,然后是左边方向、右边方向 4.中右法则: 以直线为优先的前进方向,然后是右边方向、左边方向 5.乱数法则: 取随机值作为前进方向。
6.向心法则: 遇有交叉时,以指向迷宫中心的方向为优先的前进方向。 实际应用时应采用上述搜索法则混合的搜索策略。因为当电脑鼠在迷宫中遇到“孤岛”时，如果采取的是单一搜索法则，则电脑鼠很容易陷入死循环。 经典的最优路径算法有：
1.深度优先搜索(DFS)：从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回(回溯)，换一个方向再继续探索．直至所有可能的通路都探索到为止。如果恰好某一步探索到出口，则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回，防止死循环，需要使用堆栈来保存大量记录。而要求解迷宫最短路径，则必须用深度优先搜索出所有到达出口的路径，
通过比较得到最短距离的路径．这样也必然要求增加数据空间来保存搜索过程中当前最短路径．增加了空间复杂度。
2.广度优先搜索(BFS)：从入口出发，离开入口后依次访问与当前位置邻接的单元格(上下左右方向)，然后分别从这些相邻单元格出发依次访问它们的邻接格，并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问，直至访问到迷宫出口，则找到了迷宫问题的最优解，即迷宫最短路径。该算法的显著特点是“层层推进”，探索点会随着探索的深入急剧增加，相应地，需要大量的空间用来保存探索过程的记录。空间复杂度大。
但是上述两种算法都比较抽象复杂, 编程时由于牵涉到回溯、递归等较复杂 的算法，实现起来容易出现问题,非常容易出错，尤其牵涉到复杂数据结构栈( 深度优先搜索) 、队列( 广度优先搜索) 的操作, 调试跟踪比较麻烦。 （二）本文的迷宫算法
本文算法思想：想象你站在一个迷宫里，迷宫格之间的隔板由不透水的材料制成。你手中有一个带开关的水管。当你想找出通往迷宫出口的最短路径时，你可以打开水管开关，此时水便从你所在的迷宫格向四周漫出，第一支到达出口的水流所代表的路径便是你想找的最短路径。
算法改进：上述算法成立的前提条件是你已经掌握了迷宫格的墙壁资料。当你站在入口处还没进行迷宫格搜索时迷宫情况是未知的，因而不能直接用上述算法得到最短路径，但是如果将该算法用在已经探索过的迷宫格上，并且每当探索到一个新的迷宫格就用该算法刷新一下地图，同样可以找到最短路径。 以16*16迷宫为例，用数组CellOrder[16][16]存储迷宫格序号，迷宫格序号表示从入口到此迷宫格的距离。用数组Cellshape[16][16]存储迷宫格墙壁信息。函数LowestNeighbouringcelll(x,y)返回与（x,y）相邻的赋过值的且没
有隔板隔开的迷宫格序号最大的迷宫格的序号，若周围迷宫格未被赋值则返回-1。每次刷新地图前除了入口处迷宫格序号赋0外，其余迷宫格均赋-1。每次刷新按照从（0,0）开始从下到上从左到右的顺序遍历每一个迷宫格，若该迷宫格未被赋值且周围有已赋值的迷宫格则将函数LowestNeighbouringcelll(x,y)的返回值加1后赋予它。如果未能给出口迷宫格赋值则再次重复上述顺序遍历一遍直至给出口迷宫格赋值后才结束本次刷新。具体代码如下：
while(1){ for(x=0;x<=15;x++){
for(y=0;y<=15;y++){ //按从下向上从左到右的顺序遍历迷宫格 if(CellOrder[x][y]!=-1) //若该格已被赋值则跳过不予处理
continue;
if(LowestNeighbouringCell(x,y)!=-1) CellOrder[x][y]==LowestNeighbouringCell(x,y)+1;
//若相邻最小序号格存在，则将此序号加1后赋给该格
}
} } if(CellOrder[dist_x][dist_y]!=-1) //若出口迷宫格已被赋值，结束此处刷新，否则再遍历一次 }
break;
当刷新完序号图后，从出口迷宫格为起点沿序号值递减的顺序绘出一条路径，老鼠每按此路径行走一步，刷新序号图一次。
本算法将迷宫搜索算法和迷宫最优路径算法合二为一，且只用到数组这个简单形象的数据结构, 算法简单, 相应的编程代码短小高效, 在迷宫规模较小时, 完全可以进行人工纸上模拟运行，不足之处的是此算法找出的是最短路径但不一定是最优路径，因为本算法没有考虑弯道因素，但是在转弯速度快的情况下（例如采取连续转弯）最短路径近与最优路径效果差距不大。
五、算法的实现与调试
（一）基于 uC/OS-II 多进程的软件设计
电脑鼠的软件设计非常复杂，若采用传统的前后台模式来管理程序会导致很大的开发难度，且程序不易修改。因此考虑在LM3S615上移植μC/OS-Ⅱ，作为一种嵌入式实时操作系统，μC/OS-Ⅱ提供了很多系统服务，例如信号量、互斥型信号量、事件标志、消息邮箱、消息队列、块大小固定的内存申请与释放及时间管理等，基于RTOS编程，不仅使系统的实时性、稳定性和可靠性有很高的保障，而且为设计者与CPU之间建立了桥梁，使设计者考虑的问题会大大的减少，同时也便于修改与维护。在硬件上覆盖一层操作系统，虽然增加了代码的长度，占用了系统更多的时间和空间资源，但是对于基于Cortex-M3内核的LM3S615来说，这点开销是完全可以承受的。
整个系统分为四个进程（>比较的是优先级的大小）：总线进程 >姿态纠正进程>控制进程>决策进程，以及四个中断（>比较的是中断优先级的大小）：无线ISR>传感器ISR>左电机ISR>右电机ISR。系统的总体关联图如图十一所示。
图十一 系统的总体关联图