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

计算机迷宫搜索算法仿真研究-计算机论文计算机迷宫搜索算法仿真研究 邓辉,詹杰,何家伟,李先春(湖南科技大学物理与电子科学学院,湖南湘潭411201)摘要:在电脑鼠的设计过程中,往往需要耗费大量的时间在迷宫搜索算法的调试上。通过研究迷宫地图,采用模块化的设计方法,模拟实现了对迷宫搜索算法的仿真,还设计了迷宫地图的编辑和迷宫搜索算法的导入等功能。仿真试验结果表明,仿真迷宫搜索算法可提高迷宫搜索算法设计和调试的效率。关键词 :电脑鼠;迷宫搜索算法;仿真;多线程中图分类号::A文章编号:1674-5884(2014)08-0179-04电脑鼠[1](Micromouse)是一个由微控制器、探测器、驱动电机组成的一种集感知、判断、行走功能于一体,能够在迷宫中自动寻找到达终点最佳路径的微型机器人。电脑鼠走迷宫比赛集竞赛和趣味性于一体,吸引了大量青年科技人员参加,文献[1]给出了有关迷宫电脑鼠的比赛规则和要求。在迷宫电脑鼠的设计中,迷宫搜索算法的设计和调试最困难[3-7]。主要因为迷宫搜索算法的设计和调试过程容易受到周围环境以及电脑鼠底层软硬件的影响而出现运行错误,从而使得调试经常被打断,完成一次完整的调试非常麻烦[8],需耗费大量时间。本文针对电脑鼠设计者在迷宫搜索算法设计和调试上所面临的问题,设计了迷宫搜索算法仿真程序,提高迷宫搜索算法设计和调试的效率,减轻设计者的负担。该算法仿真程序及其实现思路不仅可以推广到电脑鼠走迷宫竞赛中,而且还可以作为电脑鼠迷宫搜索算法研究者的一个理想研究平台。1仿真模块设计迷宫搜索算法仿真程序的主要功能模块包含动态仿真器、迷宫搜索算法接口、人机交互界面和迷宫地图编辑器。动态仿真器是整个程序的核心,迷宫搜索算法接口用于连接动态仿真器和迷宫搜索算法,人机交互界面和迷宫地图编辑器,分别负责响应用户的鼠标动作和迷宫地图的设置。地图编辑器需要接受用户的动作来完成地图的编辑工作,所以将迷宫地图编辑器作为人机交互界面的一个子功能来实现。图1是迷宫搜索算法仿真程序的系统模块框图。动态仿真器实现了三个功能,为迷宫搜索算法获取迷宫信息,根据迷宫搜索算法的指令控制模拟电脑鼠运动,显示运行中产生的过程数据。迷宫搜索算法接口定义了该算法的函数格式及通信协议。人机交互界面是人机交互平台,内部实现了与用户交互的按钮控件和控制程序工作状态的状态机,按钮控件获取用户的鼠标事件,并将其作为状态机的输入信号,状态机用于控制迷宫搜索算法仿真程序工作状态的转移。迷宫地图编辑器用于编辑二维迷宫地图,完成地图设置后,将该地图以图片形式保存。这里采用多线程设计方法,将动态仿真器和人机交互界面分别设计于两个不同的线程中。。迷宫地图根据IEEE标准迷宫场地的大小进行等比例的缩小。,和实际迷宫相比,边长等效为723个像素,迷宫单元的栅栏长度、厚度分别为45个像素和3个像素。整个显示界面分为三部分,左方正方形部分显示迷宫地图,右方上半部分显示按钮控件,右方下半部分显示运行信息。按钮控件有6个,分别是载入地图按钮、设置地图按钮、保存地图按钮、迷宫算法按钮、设置起点按钮和开始仿真按钮。()进行检测,通过事件检测函数UserEventDetect()获取;用户事件检测函数所返回的数据作为参数传递给状态机,由状态机控制相应的动作和效果。人机交互界面定义了7个工作状态,分别为初始状态、地图编辑状态、地图保存状态、地图载入状态、算法载入状态、起点设置状态,这7种状态反映了状态机在用户事件驱动下的状态跳转。,绝对方向以迷宫地图为参照系,相对方向以电脑鼠自身作为参考的方向,如前后左右。,其原型如下:structMICROMOUSE{unsignedchardir;intx;inty;intstart_x;intstart_y;intstate;};结构体中,dir用于存储电脑鼠的绝对方向,x和y用于电脑鼠的当前坐标、start_x和start_y用于存储电脑鼠的起点坐标,而state用于存储电脑鼠的当前状态。、右转、左转、原地后转和停止,动态仿真器收到动作指令后,,然后根据新的绝对方向调取相应的图像,用于动画绘制。当执行动画动作时,仿真器会根据电脑鼠的绝对方向对电