下载文档原格式
电脑鼠走迷宫路径规划及控制方法的研究2011年 6 月2 日摘要电脑鼠是使用嵌入式微控制器、传感器和机电运动部件构成的一种微型机器人，可以在迷宫中自动记忆和选择路径，快速地达到所设定的目的地。
电脑鼠走迷宫竞赛是一项具有一定难度、富有挑战性和趣味性的比赛。
本论文首先介绍了电脑鼠的起源与发展，分析了电脑鼠的硬件组成和工作原理，在此基础上重点讨论了电脑鼠软件的设计与实现，具体包括：等高图制作、电脑鼠冲刺、电脑鼠转弯、电脑鼠搜索、相对方向与绝对方向转变、墙壁资料存储和电脑鼠搜索策略。
通过对电脑鼠自动穿越迷宫过程，综合嵌入式专业的电路设计，传感器控制，单片机程序开发和算法研究等多学科知识的研究，使我熟悉掌握嵌入式应用开发的全过程。
最后对电脑鼠研究过程中遇到的问题进行了讨论与总结。
关键词：电脑鼠；迷宫的算法；路径规划；电机；红外感应器ABSTRACTThe micromouse is a typical micro robot, which inclueds embedded microcontroller, sensors and mechanical motion. The micromouse can choose a best and fast way to the destination in the maze, with automatic memory. The contest of micromouse go through a maze is a difficult but challenging and interesting game. This Research-based Curriculum focuses on the hardware design of micromouse and the maze algorithm. The research includes the knowledge of circuit design, the embedded microcontroller program and algorithms such.This paper firstly introduces the origin and development of micromouse. Then it analyzses the micromouse's hardware composition and working principles. After that we discuss the design and implementation of the software. It includes the maze map, absolute orientation, search strategy and optimal path method of the research. At last, the problems during the studying process are discussed and summarized.Keywords: Micromouse,；Flood Algorithm；Path Planning；Motor；Infrared目录第一章绪论 (1)1.1电脑鼠介绍 (1)1.2电脑鼠的国内外现状 (2)1.3电脑鼠比赛简述 (3)第二章迷宫的算法 (4)2.1迷宫坐标和方向 (4)2.2迷宫搜寻法则 (5)2.2.1基础的搜寻法则 (6)2.2.2中心搜寻法则 (7)2.3洪水算法简介 (8)2.4最优路径算法 (8)2.4.1等高图的制作原理 (9)2.4.2转弯加权的等高图 (10)2.5模拟最佳路径 (10)第三章运动控制 (12)3.1电脑鼠原理 (12)3.2底层驱动程序及顶层算法程序 (13)3.2.1两相四线制步进电机驱动时序 (13)3.2.2步进电机的加减速控制 (14)3.3电脑鼠转弯 (15)3.4电脑鼠运动状态的控制 (18)3.4.1电脑鼠姿势修正 (18)第四章软硬件原理 (21)4.1电脑鼠的硬件构造和特点 (21)4.2原理说明 (23)4.2.1电机驱动电路 (23)4.2.2红外线接收传感器 (24)4.2.3按键电路 (26)4.2.4处理器 (27)4.2.5机械结构 (29)4.3软件设计 (30)4.3.1软件开发环境 (30)4.3.2电脑鼠的主要程序 (33)第五章总结与展望 (34)参考文献 (36)附件 (38)附件1程序 (38)附件2英文文献 (43)附件3中文翻译 (54)谢辞 .............................................................................................. 错误!未定义书签。
一、实验目的通过本次实验，了解老鼠在迷宫中的运动轨迹，探究其寻找出口的策略，并尝试运用数据结构中的搜索算法来模拟老鼠的行走过程，分析其路径选择的特点。
二、实验原理迷宫问题是一个经典的算法问题，旨在通过模拟老鼠在迷宫中寻找出口的过程，来验证和优化搜索算法。
本实验采用深度优先搜索（DFS）算法来模拟老鼠的运动轨迹，通过堆栈来存储老鼠走过的路径，并记录其最终找到出口的最短路径。
三、实验材料1. 迷宫地图：一个二维数组，表示迷宫的布局，其中0代表无墙、没走过；1代表墙；2代表无墙、已走过。
2. C语言编程环境：用于编写和运行实验代码。
3. 输入设备：用于输入起始点和迷宫地图。
四、实验步骤1. 设计迷宫地图，初始化二维数组map[10][12]。
2. 输入起始点坐标（行列坐标），判断输入是否合法（越界或起始点在墙中）。
3. 初始化一个空堆栈，用于存储老鼠走过的路径。
4. 使用深度优先搜索算法遍历迷宫，寻找出口：a. 将起始点入栈。
b. 标记当前点为已走过。
c. 判断当前点是否为出口，如果是，则输出路径，结束搜索。
d. 找到当前点的后继点（上下左右），如果后继点合法且未走过，则将其入栈并标记为已走过，继续搜索。
e. 如果当前点没有后继点，则回溯，弹出栈顶元素，尝试下一个方向。
5. 输出最短路径，记录老鼠的运动轨迹。
五、实验结果与分析1. 迷宫地图及起始点：```0 1 1 1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 0 0 0 11 0 1 1 1 1 1 1 1 1 1 11 0 1 0 0 0 0 0 0 0 0 11 0 1 1 1 1 1 1 1 1 1 11 0 1 0 0 0 0 0 0 0 0 11 0 1 1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1```2. 老鼠起始点坐标：(1, 1)3. 运动轨迹及最短路径：```老鼠运动轨迹：[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 11), (3, 11), (4, 11), (5, 11), (6, 11), (7, 11), (8, 11), (9, 11), (10, 11), (11, 11)]最短路径：[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 11), (3, 11), (4, 11), (5, 11), (6, 11), (7, 11), (8, 11), (9, 11), (10, 11), (11, 11)]```4. 分析：通过实验结果可以看出，老鼠在迷宫中寻找出口的过程主要遵循深度优先搜索策略，即优先探索当前路径的深度，直到找到出口。
可编辑修改西安建筑科技大学 课程设计（论文）题 目： 院 （系）： 专业班级： 姓 名： 学 号： 指导教师：可视化走迷宫游戏2011 年 9 月 15 日欢迎下载可编辑修改西安建筑科技大学课程设计（论文）任务书专业班级： 计算机901 学生姓名： 指导教师（签名）：一、课程设计（论文）题目走迷宫游戏：程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的 右下方有一个粮仓。
游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到 粮仓处。
二、本次课程设计（论文）应达到的目的数据结构是实践性很强的课程。
课程设计是加强学生实践能力的一个强有力手 段。
课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。
严格实 施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训 练，将起到显著的促进作用。
本题目要达到目的：熟练掌握最短路径的算法设计。
三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术 参数、设计要求等）1、 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2、 迷宫的墙足够结实，老鼠不能穿墙而过； 3、 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4、 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 找出走出迷宫的所有路径，以及最短路径。
四、应收集的资料及主要参考文献：由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经上 机练习了“线性表”的基本操作。
参考文献：1. 本年级使用的教材：数据结构与算法分析（C++版）（第二版）影印版 2005.72. 数据结构与算法，科学出版社，2005.08；赵文静 祁飞等编著 3. 数据结构-C++语言描述，西安交通大学出版社，1999.01，赵文静编著 4. 《Visual C++编程实例》(任意一本此类书籍)五、审核批准意见教研室主任（签字）欢迎下载可编辑修改摘要本设计是为了实现一个可视化迷宫，以及利用最短路径算法 寻找迷宫的出路以及将最短路径打印在屏幕上，并且限制小老鼠 不能穿越墙，只能在路径上移动。
一种电脑鼠走迷宫的算法电脑鼠走迷宫的算法1探测策略电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。
这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15分钟的时间，因此是不可能的。
另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。
电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。
电脑鼠在任一单元内，可能的行走方向最多只有三个（前、左、右），如果有二个或二个以上的可能行走方向，称为交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选择法则：•右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。
•左手法则：遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。
•中左法则：遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。
与此类似的还有中右法则。
•乱数法则：遇有交叉时，取随机值作为前进方向。
•向心法则：由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前进方向。
2标记为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。
全迷宫共有16×16个单元组成，可采用二维坐标方式标记，即用每个单元的XY坐标表示，如起点可标记为（0，0），终点为（7，7）。
此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或相对方位二种方式。
绝对方位：这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别表示“东”﹑“西”﹑“南”和“北”四个方向。
以1表示允许行进（无墙壁），0表示不允许行进（有墙壁）。
相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实现标记，分别表示“前”“左”“右”，以1表示允许（无墙壁），0表示不允许（有墙壁）。
3阻断在电脑鼠试跑过程中或在最后冲刺时，需要对部分路径进行“阻断”，即在发现某条路径是死路（只有入口而无出口）时，在该路径的入口处（一般是交叉点）设置标记，即将入口的线路标记由1改为0。
西安建筑科技大学课程设计（论文）题目：可视化走迷宫游戏院（系）：专业班级：姓名：学号：指导教师：2011年 9月 15 日西安建筑科技大学课程设计（论文）任务书专业班级：计算机 901学生姓名：指导教师（署名）：一、课程设计（论文）题目走迷宫游戏：程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。
游戏的任务是使用键盘上的方向键操控老鼠在规定的时间内走到粮仓处。
二、本次课程设计（论文）应达到的目的数据结构是实践性很强的课程。
课程设计是增强学生实践能力的一个强有力手段。
课程设计要修业生在达成程序设计的同时能够写出比较规范的设计报告。
严格实行课程设计这一环节，关于学生基本程序设计修养的培育和软件工作者工作作风的训练，将起到明显的促使作用。
此题目要达到目的：娴熟掌握最短路径的算法设计。
三、本次课程设计（论文）任务的主要内容和要求（包含原始数据、技术参数、设计要求等）1、老鼠形象可辨识，可用键盘操控老鼠上下左右挪动；2、迷宫的墙足够结实，老鼠不可以穿墙而过；3、正确检测结果，若老鼠在规准时间内走到粮仓处，提示成功，不然提示失败；4、增添编写迷宫功能，可改正目前迷宫，改正内容：墙变路、路变墙；找出走出迷宫的所有路径，以及最短路径。
四、应采集的资料及主要参照文件：因为本课程没有安排“课内上机”学时，所以，在课程设计从前一定自己已经上机练习了“线性表”的基本操作。
参照文件：1.今年级使用的教材：数据结构与算法剖析（ C++ 版）（第二版）影印版 2005.72.数据结构与算法，科学第一版社， 2005.08 ；赵娴静祁飞等编著3.数据结构 -C++ 语言描绘，西安交通大学第一版社，1999.01，赵娴静编著4.《Visual C++ 编程实例》 (随意一本此类书本 )五、审查同意建议教研室主任（署名）纲要本设计是为了实现一个可视化迷宫，以及利用最短路径算法找寻迷宫的出路以及将最短路径打印在屏幕上，并且限制小老鼠不可以穿越墙，只好在路径上挪动。
南京理工大学毕业设计说明书(论文)作者: 学号：学院(系):自动化学院专业: 电气工程及其自动化题目: 走迷宫电脑鼠软件设计目次1 引言 (1)1.1 电脑鼠的简介 (1)1.2论文主要完成的工作 (1)1.3 器件选择 (2)1.4 相关开发工具 (5)2 走迷宫挡板检测 (5)2.1 红外接收头的工作原理 (5)2.2 原理分析 (6)2.3 用红外进行挡板检测 (7)3 步进电机的驱动控制 (8)3.1步进电机的驱动 (11)3.2车速检测模块 (11)4 电脑鼠姿势修正 (12)4.1姿势修正 (12)4.2挡板检测 (14)4.3 电脑鼠转弯 (15)5 电脑鼠走迷宫的算法 (17)5.1电脑鼠软件主要模块 (17)5.2迷宫地图相对方向与绝对方向的建立 (17)5.3墙壁资料存储 (21)5.4电脑鼠搜索策略 (23)5.5 迷宫搜索程序 (26)结论 (31)致谢 (32)参考文献 (33)1 引言1.1 电脑鼠的简介人类在科技的发展上，一直在尝试着想要创造出一个具有肢体，感觉，脑力，综合一体的机械，而智能老鼠既是一个能够用来诠释肢体，感官及脑力综合工作的智能机械。
所谓的智能老鼠我们用电脑鼠（MicroMouse）来代替,它是使用微控器，光电传感器和机动运动部件构成一种智能行走装置的俗称，它可以在“迷宫”中自动记忆和选择路径，寻找出口，最终达到所设的目的地。
电脑鼠搜索路径应该是没有人工干预的情况下自主完成的，也就是说，需要运用搜索算法使电脑鼠自主行走。
搜索算法的主要目的是，根据电脑鼠当前的位置确定下一步，以迅速达到迷宫的中心并返回，同时利用搜索迷宫时得到的隔墙信息找出从起点到终点并返回的最优路径。
电脑鼠的制作技术的基本要求一定要稳定，在符合规则的不同迷宫中都能运行自如。
快速，高效的探索迷宫则一直是个重点更是个难点。
快速和高效两个要素又彼此联系，相互影响。
实现快速探索可以通过选用合适的电机解决，但是快速不一定实现高效。
一、实验目的1. 了解迷宫实验的基本原理和操作方法。
2. 探讨白鼠在迷宫实验中的学习与记忆能力。
3. 分析白鼠在迷宫实验中的行为规律，为行为学研究提供实验依据。
二、实验材料1. 白鼠：实验用白鼠若干只，年龄、体重、性别一致。
2. 迷宫：实验迷宫为三维迷宫，共有三个出口，出口之间通过走廊相连。
3. 记录工具：摄像机、计时器、纸笔等。
三、实验方法1. 实验前准备：将白鼠随机分为实验组和对照组，实验组进行迷宫实验，对照组不进行任何处理。
2. 迷宫实验：将实验组白鼠放入迷宫中，观察其从起点到终点的行走过程。
实验过程中，记录白鼠的行走时间、错误次数、记忆时间等指标。
3. 数据分析：对实验数据进行统计分析，比较实验组和对照组的差异。
四、实验结果1. 实验组白鼠在迷宫实验中的表现：实验组白鼠在迷宫实验中表现出较强的学习与记忆能力。
大部分白鼠在实验过程中能够迅速找到正确的出口，且错误次数较少。
随着实验次数的增加，白鼠的行走时间逐渐缩短，记忆时间逐渐延长。
2. 对照组白鼠的表现：对照组白鼠在迷宫实验中表现较差，大部分白鼠在实验过程中无法找到正确的出口，错误次数较多。
行走时间和记忆时间均较长。
五、实验分析1. 实验组白鼠在迷宫实验中的表现说明，白鼠具有较好的学习与记忆能力。
这可能与白鼠的神经系统发育和认知能力有关。
2. 实验组白鼠在迷宫实验中的错误次数较少，说明白鼠在实验过程中能够根据环境信息进行有效的学习与调整。
这与白鼠的适应能力有关。
3. 实验组白鼠的行走时间和记忆时间随实验次数增加而缩短和延长，说明白鼠在迷宫实验中能够逐渐适应环境，提高学习与记忆能力。
六、结论1. 白鼠在迷宫实验中表现出较强的学习与记忆能力。
2. 白鼠的适应能力和认知能力在迷宫实验中发挥了重要作用。
3. 迷宫实验为行为学研究提供了实验依据，有助于深入探讨动物的学习与记忆机制。
七、实验展望1. 进一步研究白鼠迷宫实验中的神经机制，为神经科学领域提供实验依据。
目录一、课题需求描述 (2)1.1走迷宫游戏 (2)二、总体功能与数据结构设计 (2)2.1总体功能结构 (2)2.2 数据结构设计 (2)三、算法设计和程序设计 (3)3.1 原理 (3)3.2 流程图 (3)3.3 算法设计 (4)四、调试与测试 (9)五、设计总结 (11)5.1 收获 (11)5.2 存在问题 (11)一、课题需求描述1.1走迷宫游戏程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。
游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。
要求：1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2) 迷宫的墙足够结实，老鼠不能穿墙而过；3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5) 找出走出迷宫的所有路径，以及最短路径。
利用序列化功能实现迷宫地图文件的存盘和读出等功能。
二、总体功能与数据结构设计2.1总体功能结构实现概要设计中定义的所有数据类型及操作的伪代码算法节点类型和针类型；迷宫矩阵类型：int maze[M+2][N+2];为方便操作使其为全局变量；迷宫中节点类型及队列类型：struct point{int row,col,predecessor} que[512] 。
2.2 数据结构设计①屏幕上显示操作菜单②构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵③自动或手动生成迷宫，即为二维数组maze[M+2][N+2]④构建一个队列用于存储迷宫路径⑤建立迷宫节点struct point，用于存储迷宫中每个节点的访问情况⑥实现搜索算法三、算法设计和程序设计3.1 原理①屏幕上显示操作菜单②构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵③自动或手动生成迷宫，即为二维数组maze[M+2][N+2]④构建一个队列用于存储迷宫路径⑤建立迷宫节点struct point，用于存储迷宫中每个节点的访问情况⑥实现搜索算法3.2 流程图3.3 算法设计①主函数main（）②手动生成迷宫函数shoudong_maze（）③自动生成迷宫函数zidong_maze()④将迷宫打印成图形print_maze()⑤打印迷宫路径(若存在路径) result_maze()⑥入队enqueue()⑦出队dequeue()⑧判断队列是否为空is_Empty()⑨访问节点visit()⑩搜索迷宫路径mgpath()数据结构算法设计：①手动生成迷宫void shoudong_maze(int m,int n) { int i,j;cout<<endl;cout<<"请按行输入迷宫,0表示通路，1表示障碍(每输入一个数字请按空格或回车):";cout<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++)cin>>maze[i][j]; //为二维数组maze[M+2][N+2]赋值}②系统自动生成迷宫void zidong_maze(int m,int n){int i,j;cout<<"迷宫生成中......"<<endl;system("pause");for(i=0;i<m;i++)for(j=0;j<n;j++)maze[i][j]=rand()%2; //为二维数组maze[M+2][N+2]赋值//由于rand()产生的随机数是从0到RAND_MAX//RAND_MAX是定义在stdlib.h中的,其值至少为32767)//要产生从X到Y的数,只需要这样写：k=rand()%(Y-X+1)+X;}③搜索迷宫路径int mgpath(int maze[41][41],int m,int n){X=1;struct point p={0,0,-1};if(maze[p.row][p.col]==1){cout<<"========================================"<<endl;cout<<"此迷宫无解"<<endl;X=0;return 0;}maze[p.row][p.col]=2;enqueue(p);while(!is_Empty()){p=dequeue();if((p.row==m-1)&&(p.col==n-1))break;if((p.col+1<n)&&(maze[p.row][p.col+1]==0))visit(p.row,p.col+1,maze);if((p.row+1<m)&&(maze[p.row+1][p.col]==0))visit(p.row+1,p.col,maze);if((p.col-1>=0)&&(maze[p.row][p.col-1]==0))visit(p.row,p.col-1,maze);if((p.row-1>=0)&&(maze[p.row-1][p.col]==0))visit(p.row-1,p.col,maze);}if(p.row==m-1&&p.col==n-1){cout<<"========================================"<<endl;cout<<"迷宫路径为："<<endl;cout<<p.row<<p.col;maze[p.row][p.col]=3;while(p.predecessor!=-1){p=queue[p.predecessor];cout<<p.row<<p.col;maze[p.row][p.col]=3;}}else{ cout<<"========================================"<<endl;cout<<"此迷宫无解！"<<endl;X=0;} return 0;}④将迷宫打印成图形void print_maze(int m,int n){int i,j;cout<<"迷宫生成结果如下:"<<endl;cout<<"迷宫入口"<<endl;cout<<"↓";for(i=0;i<m;i++){cout<<endl;for(j=0;j<n;j++){if(maze[i][j]==0)cout<<"□";//通路if(maze[i][j]==1)cout<<"■";//此路不通}}cout<<"→迷宫出口"<<endl;}⑤通路路径示意图void result_maze(int m,int n){int i,j;cout<<"迷宫通路(用“鼠”表示)如下所示："<<endl;for(i=0;i<m;i++){cout<<endl;for(j=0;j<n;j++){if(maze[i][j]==0||maze[i][j]==2)cout<<"□";if(maze[i][j]==1)cout<<"■";if(maze[i][j]==3)cout<<"鼠";}}}void enqueue(struct point p)//入队{queue[tail]=p;tail++;}struct point dequeue()//出队{head++;return queue[head-1];}bool is_Empty() //判断队列是否为空{return head==tail;}⑥主函数int main(){int i,m,n,cycle=0;system("cls");system("color 0D");while(cycle!=(-1)){ //此处省略主界面设计代码cout<<endl<<endl;cout<<"Please input your selection>>>>>>>>>>"<<endl;cin>>i;switch(i){case 1:cout<<"请输入行数>>>>>>>>>>"<<endl;cin>>m;cout<<endl;cout<<"请输入列数>>>>>>>>>>"<<endl;cin>>n;while((m<=0||m>39)||(n<=0||n>39)){cout<<"您输入的行列数超出范围，请输入0-39的数！"<<endl;cout<<"请输入行数>>>>>>>>>>"<<endl;cin>>m;cout<<endl;cout<<"请输入列数>>>>>>>>>>"<<endl;cin>>n;}shoudong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)result_maze(m,n);cout<<"Press Enter Contiue!"<<endl;getchar();while(getchar()!='\n');break;case 2:cout<<"请输入行数>>>>>>>>>>"<<endl;cin>>m;cout<<endl;cout<<"请输入列数>>>>>>>>>>"<<endl;cin>>n;while((m<=0||m>39)||(n<=0||n>39)){cout<<"您输入的行列数超出范围，请输入0-39的数！"<<endl;cout<<"请输入行数>>>>>>>>>>"<<endl;cin>>m;cout<<endl;cout<<"请输入列数>>>>>>>>>>"<<endl;cin>>n;}zidong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)result_maze(m,n);cout<<"Press Enter Contiue!"<<endl;getchar();while(getchar()!='\n');break;case 3:cycle=(-1);break;default:cout<<"\n";cout<<"您的输入有误!请重新输入！"<<endl;cout<<"Press Enter Contiue!"<<endl;getchar();while(getchar()!='\n');break;}}return 0;}四、调试与测试1.主界面如图所示：2.手动生成迷宫（图为输入过程）：3.执行后如图所示：4.系统自动生成迷宫（图为输入过程）5.执行后如图所示：五、设计总结5.1 收获通过这几个星期的算法设计技能训练，使我对数据结构这门课程有了更进一步的了解，对计算机方面的基础知识等也有了进一步的了解，在算法设计的过程中，往往程序本身不是最主要的，而最重要的则是如何在编写完成能够运行程序之后想出更好解决办法来解决某个问题，算法设计技能训练让我的思维变得更加开阔，考虑问题也更加全面了。
电脑鼠走迷宫 1 项目编号：31SZDYKC-090601
全国大学生电子设计竞赛 项目名称：电脑鼠走迷宫 学生班级：1104班 学生姓名：王忆文 所在系（部）：通信工程系 指导教师： 电脑鼠走迷宫
2 摘 要 “电脑鼠”是使用嵌入式微控制器、传感器和机电运动部件构成的一种微型机器人，可以在 “迷宫”中自动记忆和选择路径，快速地达到所设定的目的地。电脑鼠走迷宫竞赛是一项具有一定难度、富有挑战性和趣味性的比赛。
能力。通过系统分析、硬件设计、软件设计、整合电路设计、汇编语言、C语言专业知识解决问题的综合应用能力,激发我们对电脑鼠的研究兴趣。 创新点是提出了对电脑鼠电源电路、传感器电路的改进方案。给出了电机控制算法、用于纠正姿态的算法、传感器驱动算法、连续转弯算法、迷宫信息采集算法以及迷宫搜索与迷宫最短路径算法等算法模块。 关键词：嵌入式系统，电脑鼠，智能算法电脑鼠走迷宫
3 ABSTRACT "Computer mouse" is the use of embedded microcontrollers, sensors and electromechanical moving parts consisting of a micro-robot maze memory and automatically select the path to reach the set destination. Computer Mouse Maze Competition is a certain degree of difficulty, challenging and fun game. completion of the research program circuit board testing, knowledge and technical skills in the school curriculum learning algorithm, data query and retrieval, project management, integration cultivate awareness of scientific and technological innovation and hands-on design capabilities. System analysis, hardware design, software design, integrated circuit design, assembly language, C language application of knowledge in the development of SCM culture integrated application skills, stimulate our interest in the study of computer mouse use our expertise to solve the problem. The innovation of the computer mouse power circuit, sensor circuit improvement program. Motor control algorithm, the algorithm used to correct posture, the sensor-driven algorithm, continuous turning algorithm, the maze information collection algorithms, and maze search maze shortest path algorithm, algorithm module. Keywords：Embedded System，Micromouse，Intellegent Algorithm电脑鼠走迷宫
1 目录 摘要 ………………………..2 第一章 前言 ………………………..2 1.1项目背景 ………………………..2 1.2项目介绍第三章 电脑鼠硬件与软件 ..………………………2 第二章 电脑鼠硬件及软件 ...………………………4 2.1电脑鼠的硬件 …………………………4 2.1.1 电脑鼠硬件组成 …………………………4 2.1.2电脑鼠基本动作 ………………………….6 2.2电脑鼠软件 …………………………7 2.2.1等高图制作模块 .……………………….9 2.2.2冲刺模块 ……………………….10 2.2.3转弯模块 ……………………….10 2.2.4搜索模块 ………………………11 2.2.5迷宫地图相对方向与绝对方向的建立 ………………………11 2.2.6 墙壁资料存储 .……………………….13 2.2.7电脑鼠搜索策略第四章 问题总结及改进 ……………………….14 第三章 问题总结及改进 ………………………15 总结 ………………………..19 参考文献 ……………………….20 电脑鼠走迷宫
2 第一章 前言
所谓“电脑鼠”，英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称。它可以在“迷宫”中自动记忆和选择路径，寻找出口，最终达到所设定的目的地。
1.1项目背景 电脑鼠可看作是一种具有人工智能的小型机器人，依照比赛规则，当电脑鼠放入“迷宫”起点，按下启动键之后，它就必须自行决定搜寻法则并且在迷宫中前进、转弯、记忆迷宫墙壁资料、计算最短路径、搜寻终点等功能。电脑鼠更结合了机械、电机、电子、控制、光学、程序设计和人工智能等多方面的科技知识。 国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛。首场电脑鼠迷宫竞赛1979年于纽约举行，1991年以来，每年都有世界级的比赛。2007年，国内开始举行IEEE标准电脑鼠走迷宫邀请赛,自举办以来各高校参赛踊跃。 电脑鼠走迷宫竞赛具有一定难度，是一项富有挑战性和趣味性的比赛。电脑鼠可看作是一个集多项工程学科知识于一体的小型系统，成功的设计者通常都是合作团体，他们必须考虑电子、电气、机械以及计算机各方面的问题，重量、速度、功耗、传感技术、重心以及程序各方面都是设计中需要决定和综合考虑的因素。 电脑鼠结合了多学科知识，对于提升我们的动手能力、团队协作能力和创新能力，促进课堂知识的消化和扩展自身的知识面都非常有帮助；
1.2项目介绍 本课程将重点研究电脑鼠硬件与改进、迷宫算法分析与改进。通过对由微处理器控制的、集传感与控制于一体的电脑鼠自动穿越迷宫过程的的研究，综合嵌入式专业的电路设计、传感器控制、单片机程序开发和算法研究等多学科知识，学电脑鼠走迷宫 3 生可熟悉掌握嵌入式应用开发的全过程，从而具备一定的嵌入式应用开发基础与能力。另外，该课程可以提高学生专业学习兴趣，锻炼学生独立学习、综合运用专业知识的能力。 通过该研究性课程，我们将要完成电路板测试、算法研究、资料查询与检索、项目管理等学校课程外的知识与技术技能的学习、整合，培养科技创新意识和动手设计能力。通过系统分析、硬件设计、软件设计、整合电路设计、汇编语言、C语言在单片机开发中的应用知识，培养运用专业知识解决问题的综合应用能力,具体包括: (1) 制定学习计划、项目计划，学会合理安排时间与事先准备的能力； (2) 检索信息，查阅资料，自主学习的能力； (3) 团体合作，与项目组成员以及老师的沟通协调能力； (4) 分析、设计、编程、调试、测试等软件设计的综合能力； (5) 规范编程，整理文档，综合演示，锻炼文字表达、语言表达能力。 （6）通过竞赛，培养责任感、荣誉感、集体观念，锻炼学生在遇到难题与压力的情况下不放弃、迎难而上，树立坚强的自信心。电脑鼠走迷宫
4 第二章 电脑鼠硬件与软件 2.1电脑鼠硬件 2.1.1 电脑鼠硬件组成 电脑鼠的硬件大致分为以下几部分：传感器、执行部件、微处理器、机械结构，如图3-1所示
1.传感器 传感器是电脑鼠准确获取外部环境信息以做出正确判断的依据，是电脑鼠灵敏快捷的保证。红外测距方式在电脑鼠上应用最广。 Micromouse615使用5组红外传感器，每组红外传感器由红外发线射器和红外线接收器组成用于检测迷宫墙壁信息，分别用于检测左、左前、前、右前和右五个方向的墙壁信息。我们用U1-U5表示红外线接收头传感器，RF1-RF5为发送红外线装置，使用5组可调电阻W1-W5控制红外信号发射强度，调整可见距离。信号采用载波调制，增强抗干扰性。
电脑鼠 传感器 执行部件 微处理器 机械结构 红外传感器
车身设计
步进电机
LM3S615
图3-1电脑鼠硬件结构图 电脑鼠走迷宫
5 2.执行部件 电机是电脑鼠的动力源，是电脑鼠的四肢。只有具备健壮且灵活的四肢的电脑鼠才有可能在比赛中高效的解开迷宫。电机不但要能输出足够的马力还要便于控制，在此基础上再配以合适的控制算法就能使电脑鼠快速而精确的行走。电脑鼠中常用的是步进电机和直流电机，步进电机控制容易，但直流电机使电脑鼠控制更加灵敏。 Micromouse615上有两个两相四线制的步进电机，左电机和右电机用来控制电脑鼠前进，左转和右转，停止。步进电机是一种将电脉冲转化为角位移的执行机构。当步进驱动器接收到一个脉冲信号，它就驱动步进电机按设定的方向转动一个固定的角度(称为“步距角”)，它的旋转是以固定的角度一步一步运行的。可以通过控制脉冲个数来控制角位移量，从而达到准确定位的目的；同时可以通过控制脉冲频率来控制电机转动的速度和加速度，从而达到调速的目的。四相步进电机如图3-3所示
3.微处理器 微处理器是电脑鼠的核心部分，是电脑鼠的大脑。几乎所有的信息，包括墙壁信息，位置信息，角度信息和电机状态信息等都需要经过微处理器处理并做出相应的判断。所有的数据分析，算法实现和执行指令的发出等都需要由微处理器来完成。 Micromouse615的微控制器是由Luminary 公司生产的Cotex-M3内核的ARM处理器——LM3S615，该芯片具有32位RISC性能，带有8KB单周期Flash，2KB单周期SARM，2个定时器(每一个都可配置为一个32位定时器或两个16位定时器，以及高达18个GPIO口。 4.机械结构 电脑鼠要能够在迷宫里面灵活穿梭，必须有一副好身板，有适合在迷宫中快速运行的身体结构。首先他必须结实，拥有两只东倒西歪的轮子的电脑鼠是很难不在迷宫中碰壁的，其次身材娇小的电脑鼠在迷宫里是会更灵活的，它有更大的空间用于完成转弯，有更大的空间用于纠正姿，最后体重太大和没有平衡感的老鼠也是不适宜迷宫竞赛的。基于如此多的考虑，一只学富五车而又娇小玲珑的电脑鼠要求我们从机械上面有更多创新。电脑鼠的机械结构如图3-4所示，左边是
