何家伟 电脑鼠迷宫算法仿真程序的设计.doc

湖 南 科 技 大 学毕 业 设 计（ 论 文 ）题目电脑鼠迷宫搜索算法仿真程序的设计作者何家伟学院物理与电子科学学院专业电子信息科学与技术学号0908020102指导教师李志坚二一三 年 五 月 二十五 日毕业设计（论文）任务书 物理学 院 电子 系（教研室）系（教研室）主任: （签名） 年 月 日学生姓名: 何家伟 学号: 0908020102 专业: 电子信息科学与技术 1 设计（论文）题目及专题： 电脑鼠迷宫搜索算法仿真程序的设计 2 学生设计（论文）时间：自 2013 年 1 月 5 日开始至 2013 年 5 月 25 日止3 设计（论文）所用资源和参考资料：资源：计算机及相关软件、因特网、图书馆藏书及期刊、中国知网等。1 林国恩.电脑鼠的设计与实作D.台湾龙华科技大学,2010.2 朱诗生,张惠珍.人机交互软件界面设计J.信息技术,2009(05):36-39.3 孙鑫.VC+深入详解M.北京:电子工业出版社,2006:142-187.4 (美)柯尼汉,里奇著,徐宝文译.c程序设计语言M.机械工业出版社.2001:1-232.等4 设计（论文）应完成的主要内容：（1） 分析电脑鼠的软件系统，讨论将电脑鼠迷宫搜索算法的仿真原理。（2） 使用VC编程环境完成电脑鼠迷宫搜索算法仿真程序的设计。（3）实现两套迷宫搜索算法，然后用这两套算法对迷宫搜索算法仿真程序进行测试。（4）分析总结本设计中存在的问题，并提出可以改进的地方。5 提交设计（论文）形式（设计说明与图纸或论文等）及要求：提交设计形式：设计图纸和论文。（1）要求认真、独立、按时地完成毕业设计的工作。（2）论文结构合理、层次分明、论据充分、逻辑严密、力求创新。（3）按照学校规定的论文（设计）要求和撰写规范进行论文的撰写。6 发题时间： 2013 年 1 月 5 日指导教师： （签名）学 生： （签名）湖 南 科 技 大 学毕业设计（论文）指导人评语主要对学生毕业设计（论文）的工作态度，研究内容与方法，工作量，文献应用，创新性，实用性，科学性，文本（图纸）规范程度，存在的不足等进行综合评价指导人： （签名）年 月 日 指导人评定成绩： 湖 南 科 技 大 学毕业设计（论文）评阅人评语主要对学生毕业设计（论文）的文本格式、图纸规范程度，工作量，研究内容与方法，实用性与科学性，结论和存在的不足等进行综合评价评阅人： （签名）年 月 日 评阅人评定成绩： 湖 南 科 技 大 学毕业设计（论文）答辩记录日期： 学生： 学号： 班级： 题目： 提交毕业设计（论文）答辩委员会下列材料：1 设计（论文）说明书共页2 设计（论文）图 纸共页3 指导人、评阅人评语共页毕业设计（论文）答辩委员会评语：主要对学生毕业设计（论文）的研究思路，设计（论文）质量，文本图纸规范程度和对设计（论文）的介绍，回答问题情况等进行综合评价答辩委员会主任： （签名）委员： （签名）（签名）（签名）（签名） 答辩成绩： 总评成绩： 摘 要 一台优秀的电脑鼠，必须要有一套优秀的迷宫搜索算法，但迷宫搜索算法的设计作为电脑鼠设计中的重要环节，往往需要耗费大量的时间用于算法的调试上。为了提高迷宫搜索算法设计和调试的效率以减少设计时间，采用模块化设计的方法和数学建模的方法，通过模拟迷宫环境和电脑鼠，实现了一个迷宫搜索算法仿真程序。迷宫搜索算法仿真程序除了实现仿真功能外，还实现了迷宫地图的编辑和迷宫搜索算法的导入等功能。为了验证迷宫搜索算法仿真程序的可行性，基于迷宫搜索算法仿真程序的接口实现了两套迷宫搜索算法，并用这些算法做了一系列的仿真试验。试验的结果显示，两套迷宫搜索算法都能顺利地驱使模拟电脑鼠找到迷宫终点，而且在仿真过程中，两套迷宫搜索算法搜索在仿真程序中的用时比在电脑鼠中实际运行的用时少了90%以上。从试验结果得到的结论是：通过使用迷宫搜索算法仿真程序来提高迷宫搜索算法设计的效率是完全可行的。迷宫搜索算法仿真程序可以作为电脑鼠设计的辅助设计软件，也可以作为迷宫搜索算法的研究平台。关键词：电脑鼠；迷宫搜索算法；仿真；多线程ABSTRACT An excellent maze searching algorithm is necessary for a micromouse. However, as an important part in micromouse design the algorithm of maze searching always spend a lot of time on testing. In order to improve the efficiency on algorithm designing and testing, I try to use the modular designing method and the mathematical modeling method to build an algorithm emulation program. This program can simulate a maze environment and a micromouse, so we can base on this program to design the algorithm of maze searching . In addition to the emulation function, it also realized the function of maze editing and algorithm importing inside of the emulation program. In order to prove if the emulation program is feasible, two algorithms of maze searching had been built and a series of emulating experiments had been made based on the interface of the emulation program. Experimental results showed that both two algorithms can successfully finish the micromouse maze searching, whats more, the simulation time was less than the actual running time 10%. So the conclusion is: the emulation program can significantly increase the efficiency when designing algorithm of maze searching. The maze searching algorithm emulation program can be used as an aids tool on micromouse designing, or as research platform for maze searching algorithm.Keywords: micromouse; algorithm for maze searching; simulating; multithreading湖南科技大学本科生毕业设计（论文）目 录第一章 绪 论11.1 选题背景11.2 研究目的11.3 研究意义1第二章 迷宫搜索算法仿真程序的设计方案22.1 迷宫搜索算法仿真的原理22.2 系统框图22.2.1 系统总框图22.2.2 动态仿真器32.2.3 迷宫搜索算法接口32.2.4 人机交互界面42.2.5 迷宫地图编辑器42.3 开发环境42.3.1 VC6.0集成开发环境42.3.2 EasyX图形库4第三章 迷宫搜索算法仿真程序的设计63.1 多线程的实现63.2 人机交互界面的设计73.2.1 人机交互总界面73.2.2 按钮控件73.2.3 用户事件的检测103.2.4 状态机123.3 迷宫地图编辑器的设计143.3.1 迷宫地图的表示143.3.2 迷宫隔墙的绘制143.3.3 迷宫隔墙的设置153.3.4 迷宫地图的保存163.3.5 迷宫地图的载入163.4 动态仿真器的设计173.4.1 电脑鼠的绝对方向和相对方向173.4.2 模拟电脑鼠的显示173.4.3 模拟电脑鼠结构体的定义183.4.4 模拟电脑鼠的运动控制183.4.5 迷宫信息的获取193.5 迷宫搜索算法接口的设计223.5.1 DLL接口223.5.2 接口的数据协议23第四章 迷宫搜索算法仿真程序的测试244.1 测试方案244.1.1 测试方案244.1.2 迷宫搜索算法的选择244.1.3 迷宫地图的选择244.2 测试结果254.2.1 左手法则迷宫搜索算法的测试结果254.2.2 右手法则迷宫搜索算法的测试结果274.3 测试结论30第五章 总结31参考文献32致 谢33i第一章 绪 论1.1 选题背景 迷宫搜索算法的设计和调试在电脑鼠的整体设计中耗费最多时间15。在传统的电脑鼠整体设计方法中，迷宫搜索算法的设计和调试需要基于电脑鼠硬件进行，由于电脑鼠实际的运行速度较低，迷宫的面积较大，所以对迷宫搜索算法进行调试是非常耗费时间的6,7。而且在迷宫搜索算法调试的过程中，电脑鼠往往会因为受到迷宫地面上的灰尘、环境的光线以及电脑鼠底层软硬件的影响而出现运行错误，从而使得调试被打断重来，造成了时间上的浪费。1.2 研究目的 为解决迷宫搜索算法在设计和调试上耗费大量时间的这一问题，本课题着手设计一个可以对迷宫搜索算法进行仿真的程序。该迷宫搜索算法仿真程序通过模拟出迷宫环境和电脑鼠，为迷宫搜索算法提供一个理想化的运行环境。仿真时，迷宫搜索算法驱动着模拟电脑鼠在理想的模拟迷宫环境中运行，有效地避免了在实际电脑鼠上调试的过程中所受到的影响。由于在仿真程序中的模拟电脑鼠可以以实际电脑鼠不可能达到的速度运行，所以可以大大地减少迷宫搜索算法的运行时间。除此之外，在迷宫搜索算法仿真程序中，可以方便地输出迷宫搜索算法的一些过程数据，为迷宫搜索算法的调试提供便利。1.3 研究意义 虽然很多电脑鼠设计者都在积极地解决迷宫搜索算法在设计和调试上耗费大量时间的问题，譬如为电脑鼠增加无线数据传输模块用于在线监控电脑鼠内部的状态。这样的方法的确能够方便错误原因的查找，减少调试的时间，但是这些方法并不能从根本上解决由于外界因素的干扰和电脑鼠自身的局限所造成的迷宫搜索算法设计和调试耗时间的问题。迷宫搜索算法仿真程序的出现，则可以从根本上解决这个问题，极大地提高了迷宫搜索算法设计和调试的效率，减少了设计和调试时间。因此，本迷宫搜索算法仿真程序及其实现思路可以推广到电脑鼠走迷宫竞赛中，这样参赛者便可以有更充裕的时间用于优秀迷宫搜索算法的设计以及电脑鼠的其它设计阶段上。与此同时，本迷宫搜索算法仿真程序还可以作为电脑鼠迷宫搜索算法研究者的一个理想的研究平台。第二章 迷宫搜索算法仿真程序的设计方案2.1 迷宫搜索算法仿真的原理 迷宫搜索算法仿真是迷宫搜索算法仿真程序的核心功能。迷宫搜索算法仿真程序的仿真功能是根据电脑鼠软件系统的结构实现的。电脑鼠的软件系统整体分为三部分5，分别是迷宫信息采集算法、运动控制算法和迷宫搜索算法。在电脑鼠的软件系统中，迷宫信息采集算法负责获取电脑鼠当前所在迷宫单元中环境信息，运动控制算法负责控制电脑鼠的运动部件实现基本的直行和转弯动作，而迷宫搜索算法则负责收集迷宫信息，并根据已知的迷宫信息指示运动控制算法控制电脑鼠在迷宫中运动。图2.1为电脑鼠的软件系统框图。迷宫搜索算法迷宫信息采集算法运动控制算法图2.1 电脑鼠软件系统框图 根据电脑鼠软件系统的运行原理，迷宫搜索算法仿真程序要实现仿真功能，需要实现迷宫信息的获取和模拟电脑鼠的运动控制两个功能。仿真过程中，迷宫搜索算法仿真程序从模拟迷宫环境中获取迷宫搜索算法所需的迷宫信息，然后将迷宫信息传递给迷宫搜索算法，当获取到迷宫搜索算法返回电脑鼠的动作指令后，仿真程序则根据动作指令控制模拟电脑鼠执行对应的动作。2.2 系统框图2.2.1 系统总框图 迷宫搜索算法仿真程序的主要功能模块包括动态仿真器、迷宫搜索算法接口、人机交互界面和迷宫地图编辑器8。动态仿真器在迷宫搜索算法仿真程序中作为整个程序的核心存在。迷宫搜索算法接口的作用是连接动态仿真器和迷宫搜索算法，其位于动态仿真器和迷宫搜索算法之间。为了方便对迷宫搜索算法进行仿真，围绕动态仿真器实现人机交互界面和迷宫地图编辑器，分别负责响应用户的鼠标动作和设置迷宫地图。由于地图编辑器需要接受用户的动作来完成地图的编辑工作，所以将迷宫地图编辑器作为人机交互界面的一个子功能来实现。图2.2是本迷宫搜索算方法仿真程序的总框图。共享变量动态仿真器人机交互界面迷宫搜索算法接口迷宫搜索算法迷宫地图编辑器主线程子线程图2.2 迷宫搜索算法仿真程序的总框图 在仿真过程中，动态仿真器运行的同时还需要运行人机交互界面来实时地监控和响应用户的动作。要实现动态仿真器和人机交互界面同时运行这一功能要求，传统的单线程程序设计方法会使程序内部流程结构变得复杂，这让程序设计变得困难，与此同时，复杂的程序流程结构对今后的程序调试和功能增添诸多不便。为解决单线程设计所带来的问题，使用多线程程序设计的方法9,10，将动态仿真器和人机交互界面分别设计于两个不同的线程中，两线程之间的通信则通过共享变量来实现。2.2.2 动态仿真器 动态仿真器作为迷宫搜索算法仿真程序的核心，负责对迷宫搜索算法进行仿真。动态仿真器需要实现三个功能，除了为迷宫搜索算法获取迷宫信息和根据迷宫搜索算法的指令控制模拟电脑鼠运动这两个功能之外，动态仿真器另外一个功能是将迷宫搜索算法在运行过程中产生的过程数据显示出来。在动态仿真器中，迷宫信息使用相关的图像处理函数获取，模拟电脑鼠的运动通过动画方式显示，而过程数据通过文字输出函数输出。2.2.3 迷宫搜索算法接口 本设计中，迷宫搜索算法仿真程序和迷宫搜索算法是分开实现的。迷宫搜索算法作为外部动态库实现，当被加载到迷宫搜索算法仿真程序内部时，迷宫搜索算法将作为一个函数被动态仿真器调用。为保证迷宫搜索算法能被正确调用，在两者之间规定一套调用接口，该接口规定了迷宫搜索算法的函数格式以及通信协议。动态仿真器与迷宫搜索算法之间的协议分为两部分，一部分是动态仿真器到迷宫搜索算法的数据协议，用于规范迷宫隔墙信息的表示方法，另外一部分是迷宫搜索算法到动态仿真器的指令协议，用于规范动作指令的表示方法。编写迷宫搜索算法的代码时，需要严格按照迷宫搜索算法接口的规范来编写，否则编译生成的迷宫搜索算法将不能成功地被调用。2.2.4 人机交互界面 人机交互界面是迷宫搜索算法仿真程序与使用者之间的桥梁。人机交互界面内部实现的模块有两个，分别是与用户交互的按钮控件和控制程序工作状态的状态机11,12。 按钮控件可以获取用户的鼠标事件，如鼠标的移动和点击等。获取到特定的鼠标事件后，控件能实现动画效果，如按钮被按下或恢复弹起。按钮被按下后，会产生一个与按钮相对应的指令，该指令将作为状态机的输入信号，用于改变迷宫搜索算法仿真程序的工作状态。 状态机用于控制迷宫搜索算法仿真程序的工作状态的转移。人机交互界面的状态机有7个工作状态，分别是初始状态、地图编辑状态、地图保存状态、地图载入状态、迷宫搜索算法载入状态、迷宫起点设置状态以及迷宫搜索算法仿真状态。从某个工作状态转移到另外一个工作状态，需要满足这两个状态间的特定转移条件，而且两状态间的两个转移方向的转移条件，可以根据不同的功能要求有不同的设置。状态转移时，退出状态前有退出动作，进入状态后有进入动作，退出动作和进入动作也要视乎功能而定。人机交互界面的转移关系和转移动作将会在第三章人机交互界面的实现中详尽介绍，所以此处暂时不介绍。2.2.5 迷宫地图编辑器 迷宫搜索算法仿真程序中，模拟迷宫通过二维图形显示，迷宫地图编辑器的功能就是编辑二维的迷宫地图。迷宫地图编辑器的工作原理如同绘图器，通过鼠标点击特定的位置即可在该位置下绘制或擦除迷宫隔墙。完成迷宫地图设置后，可以将该迷宫地图以图片形式保存，被保存的迷宫地图也可以被载入到迷宫搜索算法仿真程序中用于算法的仿真。2.3 开发环境2.3.1 VC6.0集成开发环境 迷宫搜索算法仿真程序以及迷宫搜索算法均使用使用VC6.0集成开发环境进行开发设计。VC6.0，全称Visual C+ 6.0，是由微软公司开发的一款功能强大的可视化软件开发工具，兼容标准的C/C+程序开发13,14。迷宫搜索算法仿真程序使用到VC6.0的控制台(Win32 Console Application)开发框架实现，而迷宫搜索算法使用动态链接库(Win32 Dynamic-Link Library)的框架实现15。迷宫搜索算法仿真程序通过载入动态链接库DLL的方式来载入迷宫搜索算法。2.3.2 EasyX图形库 迷宫搜索算法仿真程序中需要使用图形功能。EasyX图形库提供的基本图形函数满足本设计的功能需求16，因此选择使用EasyX图形库进行程序开发。 EasyX图形库是针对VC开发环境的一套绘图库，提供了基本的绘点、绘线、图像截取、图像载入、像素颜色获取以及鼠标事件获取等基本功能。EasyX图形库相比于VC6.0的MFC图形库，具有接口简单、使用方便的优点。EasyX图像库的开发者为图形库提供了一个详细的使用说明文档，涵括了常量的定义、结构体的定义、函数的定义以及每一个函数的示例程序，初学者根据使用说明文档可以很快地掌握图形编程的方法。第三章 迷宫搜索算法仿真程序的设计3.1 多线程的实现 在VC6.0中，要实现多线程需要创建子线程函数以及在主线程中调用子线程函数。子线程函数需要使用关键字_stdcall修饰，子线程函数的返回数据类型为双字DWORD，输入参数类型为LPVOID lpParameter13,17。子线程函数的示例代码如下：DWORD _stdcall SonProc(LPVOID lpParameter)/*此处输入本线程的功能代码*/return 0; 主线程中，启动子线程需要使用到线程创建函数CreateThread()。CreateThread函数是WindowsAPI中提供的建立新线程的函数13,14，它的原型如下：HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes,SIZE_T dwStackSize, LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParameter, DWORD dwCreationFlags, LPDWORD lpThreadId); lpThreadAttributes用于设置线程安全性，填写NULL参数表示使用默认安全性。 dwStackSize用于设置子函数初始栈的大小，如果该参数为0，则默认将使用与调用该函数的线程相同的栈空间大小。 lpStartAddress是指向线程函数的指针。 lpParameter为向线程函数传递的参数，是一个指向结构的指针，不需传递参数时，为NULL。 dwCreationFlags为线程标志。 lpThreadId用于保存新线程的ID。 本设计中，人机交互界面在子线程中实现。子线程的函数声明为：DWORD _stdcall UserActionProc(LPVOID lpParameter); 由于需要实现的线程功能不多，线程安全性使用默认值即可，对于栈的使用也没有特殊要求，同样使用默认值即可，因此在主线程中添加创建子线程的代码为：CreateThread(NULL,0,UserActionProc,NULL,0,NULL);3.2 人机交互界面的设计3.2.1 人机交互总界面 人机交互界面包括三个部分，分别为迷宫地图部分、按钮控件部分和仿真信息显示部分。图3.1为迷宫搜索算法仿真程序总界面的效果图。整个显示界面分为三部分，左方正方形部分显示迷宫地图，右方上半部分显示按钮控件，右方下半部分显示仿真信息显示。图3.1 迷宫搜索算法仿真程序的界面3.2.2 按钮控件 按钮是人机交互界面中最直观的的部件，是使用者与程序之间交互的重要窗口。由于用到的EasyX图形库不包含直接生成按钮的函数16，所以要基于基本的绘图函数来实现一套按钮。 按钮的主要属性包括有按钮的边界坐标、识别号、说明文字和状态11。为了方便管理各按钮，创建了一个基本的按钮结构体来存储按钮的各个属性17，该结构体的原型如下：struct BUTTONchar text;int ID;int state;int left;int top;int right;int bottom; 按钮结构体中，text为按钮的说明文字，ID为按钮的识别号，state为按钮的状态，left、top、right和bottom分别为按钮实体左部x坐标、上部y坐标、右部x坐标和下部y坐标。 为体现按钮的动画，需要实现按钮凸出和凹下的两种显示效果11。在始状态下，按钮显示的是凸出效果，当用户点击按钮，按钮切换到凹下效果。在按钮凹下的状态下，当用户释放鼠标按键，按钮又重新恢复到凸出效果。按钮凸出和凹下的两种效果通过两种边框阴影来实现。阴影效果使用到颜色设置函数setcolor()和画线函数line()，setcolor()函数的原型为void setcolor(COLORREF color)，line()函数的原型为void line(int x1,int y1,int x2,int y2)16。 凸出效果如图3.2中的子图a所示，上边和左边使用白色来表现反光效果，下边和右边使用深灰色来表现阴影效果。实现代码如下：void button_up(int left, int top, int right, int bottom)setcolor(0xfffeff);line(left , top , right , top);line(left , top , left , bottom);setcolor(0x96a5a8);line(right , top , right , bottom);line(left , bottom , right , bottom); 凹下的效果如图3.2中的子图b所示，上边和右边使用深灰色阴影表现，下边和右边用白色表现反光效果。实现代码如下：void button_down(int left, int top, int right, int bottom)setcolor(0x96a5a8);line(left , top , right , top);line(left , top , left , bottom);setcolor(0xfffeff);line(right , top , right , bottom);line(left , bottom , right , bottom); a) 凸出效果 b) 凹下效果图3.2 按钮效果 创建了按钮的实体边框之后，还需要为按钮添加文字说明。此处的文字说明使用文字绘制函数outtextxy()实现16，因此需要对button_on()函数和button_down()函数做稍微的改进。两函数的入口参数部分添加说明文字的字符串指针char *string，在函数最底部添加文字绘制语句outtextxy(left,top,string)，修改后的函数如下：void button_up(int left, int top, int right, int bottom, char *string)/*此处省略*/outtextxy(left,top,string);void button_down(int left, int top, int right, int bottom, char *string)/*此处省略*/outtextxy(left,top,string); 图3.3为按钮添加文字说明后的效果，子图a和b分别是按钮添加了文字说明后凸出和凹下的效果。 a)凸出效果 b)凹下效果图3.3 添加了文字说明的按钮效果 如图3.1迷宫搜索算法仿真总界面所示，人机交互界面中，共设定了6个按钮。它们分别是载入地图按钮、设置地图按钮、保存地图按钮、迷宫算法按钮、设置起点按钮和开始仿真按钮。六个按钮它们对应的ID号定义如下：#define LoadMaze1#define EditMaze2#define SaveMaze3#define LoadAlgorithm4#define SetStartingPoint5#define StartEmulation6 人机交互界面中的6个按钮分别保存在按钮结构体数组UiButton中，通过使用ID号作为标号进行调用，例如ID号等于EditMaze，通过语句UiButtonEditMaze-1即可调用地图编辑按钮的结构体信息。在处理按钮的效果时，通过ID号来指向需要被处理的按钮，然后根据该按钮当前的状态实现对应的按钮效果。若当前状态为凸出UP，则显示凹下效果；若当前状态为凹下DOWN，则显示凸出效果。按钮效果显示完之后，对该按钮的状态进行切换，UP变为DOWN，DOWN变为UP。其实现代码如下：void ButtonHandle(int ID)switch(UiButtonID-1.state)case UP:button_down(UiButtonID-1.left, UiButtonID-1.top,UiButtonID-1.right, UiButtonID-1.bottom, &UiButtonID-1.text);UiButtonID-1.state=DOWN;break;case DOWN:button_down(UiButtonID-1.left, UiButtonID-1.top,UiButtonID-1.right, UiButtonID-1.bottom, &UiButtonID-1.text);UiButtonID-1.state=UP;break;default:break;3.2.3 用户事件的检测 用户事件检测函数UserEventDetect()使用鼠标事件获取函数GetMouseMsg()进行检测。GetMouseMsg()函数的原型为MOUSEMSG GetMouseMsg()，其中MOUSEMSG为鼠标事件结构体16。MOUSEMSG结构体的原型如下：struct MOUSEMSGUINT uMsg;bool mkCtrl;bool mkShift;bool mkLbutton;bool mkMbutton;bool mkRbutton;int x;int y;int wheel; 用户事件检测函数调用GetMouseMsg()函数获取鼠标的事件，其中鼠标的事件保存于MOUSEMSG结构体的uMsg中。若检测到鼠标左键被按下时，uMsg等于WM_LBUTTONDOWN，此时可分析当前鼠标所在坐标x和y是否位于按钮所在区域内，如果鼠标当前坐标位于按钮所在区域，则返回该按钮的识别号ID，否则函数返回空数据0；若鼠标左键没被按下，则函数返回空数据0。用户事件检测函数所返回的数据作为参数传递给状态机，由状态机控制相应的动作和效果。图3.4是用户事件检测函数的流程图。否否是是进入函数获取鼠标事件鼠标左键被按下鼠标当前坐标位于按钮区域返回数据0返回鼠标所在按钮区域对应的ID号返回数据0函数返回图3.4 用户事件检测函数的流程图 用户事件检测函数的代码实现如下：int UserEventDetect()int i=0;MOUSEMSG m;m = GetMouseMsg();if(m.uMsg=WM_LBUTTONDOWN)while(iUiButtoni.left&m.xUiButtoni.top& m.yUiButtoni.bottom)return UiButtoni.ID;i+;if(i=6) return 0;elsereturn 0;3.2.4 状态机 状态机的全称是有限状态机，是表示有限个状态以及这些状态之间的转换和动作等行为的数学模型18,19。人机交互界面的状态机有7个工作状态：初始状态、地图编辑状态、地图保存状态、地图载入状态、迷宫搜索算法载入状态、迷宫起点设置状态以及迷宫搜索算法仿真状态。由于迷宫搜索算法仿真程序的工作状态较少，且状态跳转较为简单，所以只使用单层的状态机模型进行设计。 图3.5是人机交互界面的状态图，它反映了状态机在用户事件对的驱动下的状态跳转，下面罗列每个状态的进入条件和退出条件。 初始状态：在初始状态下，在初始状态下状态机不停地等待用户事件，当用户事件被触发后跳转到对应的状态。 地图编辑状态：在初始状态中，点击“设置地图”按钮，状态机将会跳转到地图编辑的状态。在地图编辑状态下，用户可以通过点击地图界面的墙壁来设置墙壁的有无，若用户编辑完地图，点击“设置完成”即可退出地图编辑状态，跳转回初始状态。 地图保存状态：在初始状态下，点击“保存地图”按钮，状态机将会跳转到地图保存的状态。在地图保存状态下，用户需要在输入框中输入地图文件名完成地图的保存，地图保存完之后状态机跳转回初始状态。 地图载入状态：在初始状态下，点击“载入地图”按钮，状态机将会跳转到地图载入的状态。在地图载入状态下，用户选择载入的地图。地图载入完成之后，状态机跳转回初始状态。 算法载入状态：在初始状态下，点击“迷宫搜索算法”按钮，状态机将会跳转到算法载入的状态。在算法载入状态下，用户选择载入的算法文件。算法载入完成之后，状态机跳转回初始状态。 起点设置状态：在初始状态下，点击“设置起点”按钮，状态机将会跳转到起点设置的状态。在起点设置状态下，用户需要选择电脑鼠的起点位置，电脑鼠的起点有两个，分别位于迷宫地图的左下角和右下角。起点设置完成后，状态机跳转回初始状态。 算法仿真状态：从初始状态跳转到算法仿真状态需要同时满足四个条件，条件一是地图已经载入，条件二是算法已经载入，条件三是起点已经设置完成，条件四是“开始仿真”按钮被按下，也就是说在开始仿真之前必须要载入地图、载入算法和设置起点。在算法仿真状态下，仿真程序调用迷宫搜索算法进行仿真，用户可以通过点击“停止仿真”按钮来结束仿真，此时状态机跳转回初始状态。 除了初始状态之外，其余的六个状态均只对本状态对应的按钮事件作出反应，其余的按钮事件均忽略。编辑地图ID=1ID=2ID=2ID=3ID=3ID=4ID=4ID=5ID=5运行迷宫搜索算法ID=6ID=6ID=0ID=1初始状态地图编辑状态地图保存状态地图载入状态算法载入状态起点设置状态算法仿真状态图3.5 状态图3.3 迷宫地图编辑器的设计3.3.1 迷宫地图的表示 迷宫地图通过二维的平面图表示，为标准迷宫的正投影。迷宫地图中使用白色表示迷宫地面，使用红色表示迷宫隔墙，迷宫地图的效果图如图3.6所示。图3.6 迷宫地图 迷宫地图根据IEEE标准迷宫场地的大小进行等比例的缩小7。迷宫地图和实际迷宫的换算比例为每个像素代表0.4cm，因此迷宫地图的边长等效为723个像素，换算后的迷宫单元的隔墙长度和宽分别是45个像素和3个像素。 迷宫地图中，将竖直方向设定为y轴方向，水平方向设定为x轴方向，对应的四个顶角单元的坐标分别是：左上角(0,0)、右上角(15,0)、右下角(15,15)和左下角(0,15)。迷宫终点位于迷宫的中央四格，对应的坐标分别是左上角(7,7)、右上角(8,7)、右下角(8,8)和左下角(7,8)。 3.3.2 迷宫隔墙的绘制 迷宫地图中有两种迷宫隔墙，一种为水平放置的，另一种为竖直放置的。迷宫中可以放置水平隔墙和竖直隔墙的区域均有1616个，坐标为(x,y)的迷宫单元，其上隔墙的坐标为(x,y)，其左隔墙的坐标为(x,y)。 定义了隔墙的坐标之后，可以使用隔墙绘制函数block_on()函数进行迷宫隔墙的绘制。block_on(int x, int y, int dir)函数调用了line()函数来绘制线条，x和y为隔墙所在单元的坐标，dir指示需要绘制的隔墙的类型，若dir的值为TOP，则函数绘制水平的隔墙，若dir为LEFT，则函数绘制竖直的隔墙。block_on()函数的实现代码如下：void block_on(int x, int y, int dir)setcolor(RED);switch(dir)case TOP:line(45*x+3,45*y+0,45*(x+1),45*y+0);line(45*x+3,45*y+1,45*(x+1),45*y+1);line(45*x+3,45*y+2,45*(x+1),45*y+2);break;case LEFT:line(45*x+0,45*y+3,45*x+0,45*(y+1);line(45*x+0,45*y+3,45*x+1,45*(y+1);line(45*x+0,45*y+3,45*x+2,45*(y+1);break;default:break; 进行迷宫设置时，除了可以绘制隔墙之外，还可以撤销隔墙，因此还需实现一个隔墙撤销的函数block_off()。block_off()的实现与block_on()函数相类似，只需将block_on()函数的setcolor(RED)语句改为setcolor(WHITE)即可。block_off()函数的实现代码如下：void block_off(int x, int y, int dir)setcolor(WHITE);/*此处省略*/3.3.3 迷宫隔墙的设置 使用鼠标点击设置隔墙时，检测函数获取鼠标当前的坐标，将两坐标值分别除以45得到鼠标当前所在迷宫单元的坐标(x,y)。获取到鼠标当前所在迷宫单元的坐标后，将鼠标的坐标与鼠标所在迷宫单元的隔墙敏感区域作匹配。为方便点击设置隔墙，将隔墙本身的3个像素区域以及隔墙两侧的10个像素的区域作为敏感区域，总宽度为23个像素。若坐标落于上隔墙，则得出隔墙坐标为(x,y-1)，隔墙放置类型为水平；若坐标落于下隔墙，则隔墙得出隔墙坐标为(x,y+1) ，隔墙放置类型为水平；如果落在左隔墙，得出的隔墙坐标为(x-1,y)，隔墙放置类型为竖直；如果落在右隔墙，得出的隔墙坐标为(x+1,y) ，隔墙放置类型为竖直。 得出隔墙坐标和隔墙的类型后，使用像素点颜色获取函数getpixel()来获取该隔墙区域的几何中心像素颜色16，如果获取到的颜色为红色，说明此处已经布置了一块隔墙，此时使用block_off()函数将该隔墙“撤掉” ；如果获取到的颜色为白色，则说明此处已被撤掉了隔墙，此时使用block_off()函数将该隔墙“补上”。3.3.4 迷宫地图的保存 迷宫地图的保存使用到了两个图像处理函数：图像获取函数getimage()和图像保存函数saveimage()16。程序首先使用getimage()函数获取迷宫地图723723像素的正方形区域的图像数据，图像数据保存在结构体MAZE中。得到迷宫数据后，程序弹出如图3.7所示的输入框，要求输入将要保存的迷宫地图的文件名。最后，程序使用saveimage()函数以输入的文件名将迷宫地图保存到当前目录下的MazeLib文件夹中，迷宫地图的默认格式是位图BMP文件格式。图3.7 保存地图的输入框3.3.5 迷宫地图的载入 由于被保存的迷宫地图存放在MazeLib文件夹中，所以载入迷宫地图的时候，需要进入该文件夹获取所需的地图文件。仿真程序在进行初始化时默认载入MazeLib文件夹内命名为“default.bmp”的默认迷宫地图文件，如果该文件不存在，则需要点击载入地图按钮，以载入其它的迷宫地图文件。 选择载入迷宫地图文件时，程序会弹出如图3.8所示的输入框，要求输入将要载入的地图的文件名。获取到文件名后，程序根据文件名用图像加载函数loadimage()将该迷宫地图调入内存，然后使用图像绘制函数putimage()将该迷宫地图绘制在迷宫区域，直接将原有的迷宫地图覆盖16。如果输入的迷宫地图不存在，则loadimage()函数获取到空的图像文件，putimage()也不会绘制迷宫地图，因此之前的迷宫地图不会被覆盖。图3.8 载入地图的输入框3.4 动态仿真器的设计3.4.1 电脑鼠的绝对方向和相对方向 绝对方向：以迷宫地面作为参考系，迷宫地图的上方为北方NORTH，下方为南方SOUTH，左方为西方WEST，右方为EAST，这四个方向作为电脑鼠的绝对方向13。程序中对四个方向的值进行了如下的定义：#define NORTH0#define EAST1#define SOUTH2#defineWEST3 相对方向：以电脑鼠自身作为参考的方向作为电脑鼠的相对方向13，电脑鼠前方为FRONT，后方为BACK，左方为LEFT，右方为RIGHT，四个相对方向的值的定义如下：#define RIGHT1#define FRONT2#define LEFT4#defineBACK83.4.2 模拟电脑鼠的显示 在仿真程序中，使用长为15像素，宽为12像素的电脑鼠图案来表示模拟电脑鼠。模拟电脑鼠的显示图案如图3.9所示，子图abcd分别是电脑鼠方向为向北NORTH、向南SOUTH、向西WEST和向东WEST的图案。 a) 向北NORTH b) 向南SOUTH c) 向西WEST d) 向东EAST图3.9 模拟电脑鼠的显示图案 模拟电脑鼠四个方向的图像以北东南西的顺序存入IMAGE