下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第第页“电脑鼠”斜向45度冲刺算法实现摘要天津中德职业技术学院在2015年天津市高职院校技能大赛的“电脑鼠”走迷宫大赛中成功实现斜向45度冲刺,实现电脑鼠可以斜向冲刺的算法突破,本文介绍这一算法的设计思想和算法实现过程,采用有限状态自动机的设计思想,算法实现通过自动机转换成状态转换矩阵来实现。
关键词有限状态自动机;状态转化矩阵;电脑鼠;斜向45度
中图分类号:TP311文献标识码:A文章编号:1009-3044(2016)14-0186-02
“电脑鼠”,英文名叫做MicroMouse,是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置,电脑鼠可以在不同“迷宫”中自动记忆和选择路径,采用相应的算法,快速地达到所设定目的地。
这项竞技赛事风靡全球,从1979年国际电工和电子工程学会(IEEE)每年都举办一次国际性的电脑鼠走迷宫竞赛,至今已有30年的历史,在欧洲东南亚日本、韩国等地区颇为盛行。
1问题提出的背景
嵌入式微型机器人(电脑鼠)走迷宫竞赛具有一定难度,是一项富有挑战性和趣味性的比赛。此外,它还是一个很好的教学工具。电脑鼠可看作是一个集多项工程学科知识于一体的小型系统。成功的设计者通常都是合作团体,他们必须考虑电子、电气、机械以及计算机软件设计,算法各方面的问题。重量、速度、功耗、传感技术、重心以及程序各方面都是设计中需要决定和综合考虑的因素。
本论文从软件算法角度提出了斜向45度冲刺的算法创新,并在2015年天津电脑鼠相关赛项中成功应用。
电脑鼠在运行中可以划分为四个状态,等待状态、启动状态、搜索迷宫状态和冲刺状态。
1)等待状态
在该状态中,电脑鼠静止在起点,等待开始命令。同时实时显示传感器检测结果和电池的电压,这样方便调试传感器的灵敏度和更换电池。当控制启动的按键按下后,电脑鼠进入启动状态。
2)启动状态
迷宫是由18cm*18cm大小的方格组成的,其行列各有16个方格。以左下角的点为(0,0)点,右上角的点为(15,15)点。在该状态中,电脑鼠根据第一次转弯的方向判断起点是在坐标的(0,0)点还是(15,0)点。
3)搜索迷宫状态
在该状态中,电脑鼠的任务就是探索并记忆迷宫地图。这里采用右手搜索法则,并搜索全迷宫。其程序流程图见图1所示:
4)冲刺状态
迷宫搜索完毕后,根据算法找出一条最优路径冲刺到终点。冲刺结束后返回到起点。
本论文研究的是,在冲刺状态下以最优路径为基础,通过类似自动机原理的算法找到最优路径下可以45度斜向跑的起始位置和终止位置。
5)方向的定义
为了让电脑鼠记住所走过的各个迷宫格的信息,我们就要对这256个迷宫格进行编号。很明显,用坐标是非常方便的。
在本文中,将向上的方向定义为0,向右为1、向下的方向定义为2、向左为3,如图所示。
2冲刺路径绝对方向数组的获取
绝对方向数组的获取,通过读取GucMapBlock(根据当前格修改过周边4格的地图),获取冲刺地图,并变换成冲刺路径绝对方向的数组,在此基础上分析斜向45度路线的起始坐标和终止坐标。
算法分析:斜向包括4个方向,8种情况,每种情况至少连续两组以上即可选择。4个方向,8种情况,以绝对方向1010的情况为例如图3所示:
这种情况可以选择斜向跑,101010以及更多的重复循环情况也可以选择斜向跑,除此之外还有0101,1212,2121,2323,3232,0303,3030以及更多循环的情况。本论文就是通过有限状态自动机原理,把符合条件的所有情况筛选出来。
3算法的实现
首先,搭建有限状态自动机,初始状态为“0”状态,输入值只有0,1,2,3四种情况,每一个输入之后,有限状态自动机会有状态跳转,如:在“0”状态下输入0时调整到“1”状态,输入1时调整到“2”状态,输入2时调整到“3”状态,输入3时调整到“4”状态;在“1”状态下输入0时调整到“1”状态,输入1时调整到“5”状态,输入2时调整到“3”状态,输入3时调整到“6”状态。有的输入会跳转到新状态,有的输入会跳转到已经存在的状态。其中,14,16,18,20,22,24,26,28为终止状态,分别是8种情况,首次达到终止状态,即满足两组斜向45度最低条件,再通过连续一组循环可以连续达到同一个终止状态,再次基础上可以计算出所有满足条件的斜向45度的起始坐标和终止坐标等信息。
有限状态自动机会转换成一个所有状态跳转关系都包含在28*4的状态转换矩阵中。
状态转换矩阵如下:
4编程实现
在VC++6.0环境模拟斜向45度算法,根据缓冲区读取的实际数据在VC环境下,测试算法,通过算法运算出所有符合条件的序列段,并运算出起始步数,起始点绝对方向,起点坐标,终止坐标,步数等信息。
测试用例:test[N]={0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,2,2,1,2,1,2,1,2,1,2,2};
运行结果:
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 有关幼儿园学期计划范文六篇
- 2024年幼儿园安全工作心得体会(3篇)
- 有关教师承诺书汇编10篇
- 企业财务实训总结报告三篇
- 电力员工述职报告
- 调查问卷分析报告4篇
- 观看榜样8的心得体会(最佳15篇)
- 冀教版九年级全册Unit 4 Stories and poems Lesson 19 A Story or a Poem 教案
- 软件系统的销售合同
- 炼钢厂办公室副主任职位说明书
- 水生产企业(自来水公司)安全生产风险分级管控和隐患排查治理双体系方案全套资料(2021-2022版)
- 2024年安徽省九年级省级联考中考二模数学试题(含答案)
- 2024年江苏省徐州市睢宁县小升初总复习语文测试卷含答案
- 小学数学“图形与几何”复习策略与教学建议
- MOOC 麻醉学-西南医科大学 中国大学慕课答案
- 国开电大2023年春季期末考试《人力资源管理》试题(试卷代号2195)
- (正式版)JBT 14449-2024 起重机械焊接工艺评定
- DL-T 5605-2021太阳能热发电厂蒸汽发生系统设计规范-PDF解密
- 《文创产品包装设计》课件-4.2 任务二:非遗文创产品包装设计
- 国防信息动员方案
- 2024重庆环卫集团有限公司所属子企业招聘笔试参考题库附带答案详解
评论
0/150
提交评论