“电脑鼠”斜向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}；

运行结果：

5 总结

这是利用编译原理课程中，词法分析的有限状态自动机原理的一次实际应用，解决了有限状态并且有限输入的情况下一类问题的分析和解决方法。在实际测试中达到预期效果，为“电脑鼠走迷宫”赛项的技术发展起到了推动作用。