计算机迷宫搜索算法仿真研究①

邓 辉，詹 杰，何家伟，李先春

(湖南科技大学物理与电子科学学院，湖南湘潭411201)

电脑鼠［1］(Micromouse)是一个由微控制器、探测器、驱动电机组成的一种集感知、判断、行走功能于一体，能够在迷宫中自动寻找到达终点最佳路径的微型机器人。电脑鼠走迷宫比赛集竞赛和趣味性于一体，吸引了大量青年科技人员参加，文献［1］给出了有关迷宫电脑鼠的比赛规则和要求。

在迷宫电脑鼠的设计中，迷宫搜索算法的设计和调试最困难［3－7］。主要因为迷宫搜索算法的设计和调试过程容易受到周围环境以及电脑鼠底层软硬件的影响而出现运行错误，从而使得调试经常被打断，完成一次完整的调试非常麻烦［8］，需耗费大量时间。本文针对电脑鼠设计者在迷宫搜索算法设计和调试上所面临的问题，设计了迷宫搜索算法仿真程序，提高迷宫搜索算法设计和调试的效率，减轻设计者的负担。该算法仿真程序及其实现思路不仅可以推广到电脑鼠走迷宫竞赛中，而且还可以作为电脑鼠迷宫搜索算法研究者的一个理想研究平台。

1 仿真模块设计

迷宫搜索算法仿真程序的主要功能模块包含动态仿真器、迷宫搜索算法接口、人机交互界面和迷宫地图编辑器。动态仿真器是整个程序的核心，迷宫搜索算法接口用于连接动态仿真器和迷宫搜索算法，人机交互界面和迷宫地图编辑器，分别负责响应用户的鼠标动作和迷宫地图的设置。地图编辑器需要接受用户的动作来完成地图的编辑工作，所以将迷宫地图编辑器作为人机交互界面的一个子功能来实现。图1是迷宫搜索算法仿真程序的系统模块框图。

图1 迷宫搜索算法仿真程序的总框图

动态仿真器实现了三个功能，为迷宫搜索算法获取迷宫信息，根据迷宫搜索算法的指令控制模拟电脑鼠运动，显示运行中产生的过程数据。迷宫搜索算法接口定义了该算法的函数格式及通信协议。人机交互界面是人机交互平台，内部实现了与用户交互的按钮控件和控制程序工作状态的状态机，按钮控件获取用户的鼠标事件，并将其作为状态机的输入信号，状态机用于控制迷宫搜索算法仿真程序工作状态的转移。迷宫地图编辑器用于编辑二维迷宫地图，完成地图设置后，将该地图以图片形式保存。这里采用多线程设计方法，将动态仿真器和人机交互界面分别设计于两个不同的线程中。

2 迷宫搜索算法仿真程序的设计

2.1 人机交互界面的设计

图2为迷宫搜索算法仿真程序的界面。迷宫地图根据IEEE标准迷宫场地的大小进行等比例的缩小。迷宫地图中每个像素代表0.4 cm，和实际迷宫相比，边长等效为723个像素，迷宫单元的栅栏长度、厚度分别为45个像素和3个像素。整个显示界面分为三部分，左方正方形部分显示迷宫地图，右方上半部分显示按钮控件，右方下半部分显示运行信息。按钮控件有6个，分别是载入地图按钮、设置地图按钮、保存地图按钮、迷宫算法按钮、设置起点按钮和开始仿真按钮。

2.2 用户事件检测与状态转移

用户在人机交互界面的动作信息通过鼠标事件获取函数GetMouseMsg()进行检测，通过事件检测函数User-EventDetect()获取;用户事件检测函数所返回的数据作为参数传递给状态机，由状态机控制相应的动作和效果。

图2 迷宫搜索算法仿真程序的界面

图3 用户事件检测函数的流程图

人机交互界面定义了7个工作状态，分别为初始状态、地图编辑状态、地图保存状态、地图载入状态、算法载入状态、起点设置状态，这7种状态反映了状态机在用户事件驱动下的状态跳转。

2.3 动态仿真器的设计

2.3.1 电脑鼠属性定义

动态仿真器首先定义了电脑鼠的绝对方向和相对方向，绝对方向以迷宫地图为参照系，相对方向以电脑鼠自身作为参考的方向，如前后左右。为电脑鼠创建了一个结构体MICROMOUSE.mouse用于存储电脑鼠的相关信息，其原型如下:

结构体中，dir用于存储电脑鼠的绝对方向，x和y用于电脑鼠的当前坐标、start_x和start_y用于存储电脑鼠的起点坐标，而state用于存储电脑鼠的当前状态。

2.3.2 电脑鼠的运动控制

电脑鼠的基本动作分为直行、右转、左转、原地后转和停止，动态仿真器收到动作指令后，首先根据动作指令action更新电脑鼠的绝对方向mouse.dir，然后根据新的绝对方向调取相应的图像，用于动画绘制。当执行动画动作时，仿真器会根据电脑鼠的绝对方向对电脑鼠的坐标进行更新。

为了使仿真程序更具一般性，将模拟电脑鼠的移动速度设置为可调，两个控制参数分别是flame和delay_time。flame代表模拟电脑鼠每次移动的像素个数，delay_time为每次移动后需要延时等待的时间(等待指令)。默认为每移动一个基本单元所用的时间为450 ms。delay_time的值为0到2 000 ms之间的任意整数值。

2.3.3 迷宫信息的获取

迷宫栅栏信息的获取根据电脑鼠当前所在迷宫单元的坐标mouse.x和mouse.y完成。绝对方向的信息分别对应变量的 bit3、bit2、bit1和bit0中，对应关系如表1所示。相对方向的对应关系如表2所示。绝对方向的栅栏信息反应迷宫地图信息，相对方向的栅栏信息反映电脑鼠可能运动的方向。

表1 绝对方向下的栅栏信息存储格式

表2 栅栏信息的存储格式

2.3.4 仿真数据统计

动态仿真器的仿真过程产生两种数据，分别是模拟电脑鼠运动的轨迹图和行走步数统计数据。在仿真过程中，动态仿真器会一直记录电脑鼠的坐标，当发现电脑鼠从迷宫起点到达了迷宫终点或者从迷宫终点到达了迷宫起点，则使用图像输出函数putimage()将模拟电脑鼠的行走轨迹绘制出来，如图4所示。绘制模拟电脑鼠的行走轨迹之后，动态仿真器使用图像获取函数getimage()对电脑鼠的行走轨迹进行截取，截取后的轨迹图像保存在程序当前目录下的Result文件夹中。

图4 模拟电脑鼠的轨迹图

图5 步数统计

3 算法测试

为了验证迷宫搜索算法仿真程序的方案是否可行以及该方案是否能够减少迷宫搜索算法设计和调试的时间，本文对迷宫搜索算法仿真程序进行了一系列的测试。本测试基于两套迷宫搜索算法和3个难度各异的迷宫地图开展，最短路径生成采用洪水填充算法，测试的内容包括迷宫搜索算法的仿真情况以及仿真所用时间。测试结束后，通过分析对比迷宫搜索算法的仿真情况以及仿真所用时间，判断是否达到设计目的。

为了便于对比测试结果，对实际电脑鼠的运行速度和模拟电脑鼠的运行速度作统一的假设。假设在实际环境中，电脑鼠每个基本动作用时为0.36 s(由电脑鼠0.5 m/s的运动速度计算而来，0.5米/秒的运动速度参考了比赛中电脑鼠的常用速度)。同时也假设在模拟环境中，模拟电脑鼠的基本动作用时为0.03 s(由模拟电脑鼠在模拟迷宫中1.5像素/ms的速度计算而来)。

3.1 迷宫地图的选择

为使测试结果具有普遍的参考意义，本次测试使用的迷宫地图为国内外比赛中出现过的3个迷宫地图。如图6所示，其中图6(a)为2009年中国电脑鼠走迷宫竞赛的迷宫地图。图6(b)为2012年湖南省电脑鼠走迷宫竞赛的迷宫地图。图6(c)为2011年日本电脑鼠走迷宫竞赛的迷宫地图。

图6 测试所选用的迷宫地图

3.2 测试结果

3.2.1 左手法则迷宫搜索算法的测试结果

图7、图8和图9分别是模拟电脑鼠在左手法则迷宫搜索算法的控制下，分别在三个迷宫地图中生成的轨迹图。

图7 左手法则在迷宫地图一中的运行轨迹图

图8 左手法则在迷宫地图二中的运行轨迹图

图9 左手法则在迷宫地图三中的运行轨迹图

除了轨迹图之外，左手法则迷宫搜索算法的仿真结果还包括模拟电脑鼠在三个迷宫地图中仿真时的步数统计数据。如图10所示，图10a)、b)、c)是左手法则迷宫搜索算法分别在迷宫地图一、二、三中的仿真步数统计数据。

图10 左手法则分别在三个迷宫地图中运行的统计数据

3.2.2 右手法则迷宫搜索算法的测试结果

图11、图12和图13分别为模拟电脑鼠在右手法则迷宫搜索算法的控制下，在三个迷宫地图中运行生成的轨迹图。图11，图12、图13中，图a)为模拟电脑鼠第一次搜索时的轨迹图，图b)为模拟电脑鼠第二次搜索时的轨迹图，图c)为模拟电脑鼠冲刺时的轨迹图。

图11 右手法则在迷宫地图一中的运行轨迹图

图12 右手法则在迷宫地图二中的运行轨迹图

图13 右手法则在迷宫地图三中的运行轨迹图

同样，右手法则迷宫搜索算法的仿真结果也包含了步数统计数据。左手法则迷宫搜索算法的仿真统计数据，如图14所示，图a)、b)、c)是右手法则迷宫搜索算法分别在迷宫地图一、二、三中的仿真统数据。

图14 右手法则分别在三个迷宫地图中运行的统计数据

4 结论

从两套迷宫搜索算法生成的轨迹图中可以看出，轨迹图和电脑鼠真实的运动情况没有区别，虽然两套迷宫搜索算法的搜索轨迹都不一样，但最终都能成功搜索到三个迷宫的最短路径。经过多次的测试检验，发现仿真程序均可稳定工作，这说明两套迷宫搜索算法在仿真程序中均能正常运行，设计的迷宫搜索算法仿真程序正确。

采用仿真的形式来研究迷宫搜索算法，可以直观地看到整个仿真过程，还可以显示电脑鼠的行走数据，对算法的性能分析可以起到很大的帮助。因此，本仿真程序可以广泛推广到电脑鼠走迷宫竞赛中使用，帮助参赛队伍有效地提高迷宫搜索算法和电脑鼠的整体设计进度。

［1］周立功.IEEE电脑鼠开发指南［M］.广州:广州致远电子有限公司，2008.

［3］林国恩.电脑鼠的设计与实作［D］.台湾:龙华科技大学，2010.

［4］陈 锋.环境搜索与路径规划算法的研究［D］.长春:吉林大学，2012.

［5］张新谊.一种电脑鼠走迷宫的算法［J］.单片机与嵌入式系统应用，2007(5):84－85.

［6］万玉琼，梁俊有.基于嵌入式微处理器的走迷宫机器人的设计［J］.洛阳理工学院学报(自然科学版)，2010(4):36－39.

［7］李亚洲，严 石.电脑鼠软件系统关键技术研究［J］.单片机与嵌入式系统应用，2011(5):72－73.

［8］付秀伟，张 骅.基于ARM－M3的电脑鼠硬件设计［J］.吉林化工学院学报，2012(1):47 －49.