当前位置：文档之家 › 一种电脑鼠走迷宫算法的设计与实现

一种电脑鼠走迷宫算法的设计与实现

  • 格式：pdf
  • 大小：483.80 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

一种电脑鼠走迷宫算法

一种电脑鼠走迷宫算法

一种电脑鼠走迷宫算法作者：周杰来源：《电脑知识与技术》2018年第03期摘要：该文通过对电脑鼠走迷宫算法的研究，提出了一种电脑鼠走迷宫算法，该算法引用了斜线K和Z用以更新期望坐标，并将迷宫分割为多个部分，以斜线K上的点为起点坐标，下一条斜线K上的点为期望终点坐标，找到起点坐标和终点坐标的最优解，以局部最优，引出全局最优找到最佳路径，并与传统走迷宫算法进行比较，提高了迷宫搜索效率。

关键词：迷宫；斜线；局部最优；最佳路径中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）03-0053-031 概述电脑鼠是一种机电一体化装置，是由单片机、传感器、机电运动部件组成的一种能在迷宫行走的小型机器人可以通过预先设定的算法，探索迷宫，可以找到一条从预设的起点到终点的最佳路径，运行环境是由一个16X16正方形单元格所组成的迷宫，其中单元格的大小为18cmX18cm，文献[1][2]给出了电脑鼠走迷宫的相关规则，每一个单元格有相应的挡板组成，电脑鼠的目的是在最短的时间内找到出口，在整个电脑鼠中最重要的是硬件的可靠性和算法的优劣，在当今单片机迅速发展的时代，硬件稳定性上已经趋于稳定，本文主要研究和设计搜索迷宫算法，并提出了一种电脑鼠搜索迷宫的算法。

2 迷宫环境建模电脑鼠不具有思维能力，它只能按照我们设定的算法运行，因此需要模拟现场运行环境[6][7].构建一个16X16的迷宫，迷宫的水平方向为Y轴，垂直方向为X轴，第一个坐标为（1，1），那么依次下去最上角的坐标为（16，16）。

迷宫构建图，如图1 所示，迷宫内的挡板信息未知。

假设起点为（1，1）终点为（16，16），现在规定，X方向为地理北，Y方向为地理南，如图2所示。

对于当前坐标，和下一步目标，两个坐标的差值比如（X1，Y1）-（X2，Y2）。

（1，0）表示电脑鼠向北前进一步。

其中差值（0，1）表示向东前进一步，（-1，0）表示向南前进一步，（0，-1）表示向西前进一步。

智能老鼠走迷宫算法的设计

智能老鼠走迷宫算法的设计
１ 引言 ・ 人类 在科技的发展 上， 一直在尝试着 想要创造 出一个具
有 肢 体 、 官 、 力 ， 合 一 体 的 机 械 ， 智 能 老 鼠 即 是 一 个 感 脑 综 而
走 出迷 宫
。
３ 分 析 方 法 ．
能够用 来诠 释肢体 、 感官及脑 力综合工作 的智能机械 。希望 能够藉 由智 能老 鼠的创 作进而研 究 与发 明更 加复 杂的智 能
脱 与 高 效 行 进 都 可 以 依 靠 等 高 图 。将 迷 宫 认 为 划 分 为 若 干
图 ３加减 速 示意 图
的迷 宫格 ， 并将 每个迷 宫格 的等高值 赋予最大 值 ０ ｆ， 图 ｘ 如
盟 拥 ，
加 减 速 实 时 算 法 的 核 心 是 使 用 定 时器 中 断 ， 当定 时器 发
能老 鼠的驱动 ，采用 红外线 发射 管和一 体化接 收头组 成传
感 器 单 元 ，使 用 基 于 Ｃ ｒ ｘＭ３ 内核 的 ３ ｏｔ ． ｅ ２位 Ａ Ｍ 微 控 制 Ｒ 器 Ｌ Ｓ １ 为 运 算 控 制 中 心 。方 案 通 过 建 立 自动 适 应 迷 Ｍ３ ６５作
宫 的搜 索算法 ， 依靠 强大运 算 能力 的处理 器 ， 最后 实现 了智 能老 鼠快速 高效的迷宫搜 索 。
・－— —
４ －— ３ － —
黝 基 金 项 目
速， 之后匀速 运行 。当快要到 达指定 的停 Ｊ位 置时 ， 以恒 卜 再 定 的减速度减速 ， 在停止位 置处停住。如图 ３所示 。其 中加 速度和减 速度要根 据不 同的电机设 定， 如果它们 的值较 大， 则可 以较快地 到达 目的位置 ， 有可能产生振荡 。如果它们 但
２ 原 理 ．
２ １ 器件选择 ． 传感器单元 ：Ｒ ８ ０ Ｓ红外线一体 化接 收头；普通 红 Ｉ Ｍ．６ １ 外线发射管 。 驱 动单 元 ：反 应式 步进 电机 ； Ａ ８ ５ Ｓ步进 电机专 用 Ｂ ６４Ｆ 驱 动芯片 。

迷宫电脑鼠的设计报告

迷宫电脑鼠的设计报告
1、L9110器件的管脚图如图所示。
2、管脚定义如下：
3、通过L9110驱动芯片IA、IB输入的逻辑值的组合，不同高低电平的输入输出，控制电机正转、反转、停转。L9110的逻辑关系表如下表所示：
L9110逻辑关系
IA
IB
OA
OB
H
L
H
L
正转
L
H
L
H
反转
L
L
L
L
停止
H
H
L
L
停止
3.3
3.3.1
电脑鼠正常行走包括直走、左转弯、右转弯和向后转弯四个功能函数。这四个功能函数中要用到T0、T1定时/计数器；所以函数中首先初始化T0、T1。T0初始化：打开总开关EA=1；开T0中断ET0=1;设定T0模式2，8位自动重装值定时计数器TMOD&=0xf6; TMOD|=0x06;设定T0计数初值,定义中断脉冲数TH0=256-ICP;TL0=256-ICP;//启动T0计数TR0=1;T1初始化也是一样的。
传感器组是由38KHz的红外一体化接收头和红外发射管构成的障碍感测器。为了能够让传感器组正常工作，红外发射管需要一个38KHz的方波来驱动，使红外发射管发射出调制频率与接收头接收频率匹配的红外光。如图所示，是产生38KHz方波的载波发生器电路。
（4）传感器的调试
（主要写每组传感器如何进行调试。）
1、左右两边的传感器检测是否有墙壁。
sbit LED3=P0^2;
sbit LED4=P0^3;
sbit LED5=P0^4;
sbit LED6=P0^5;
sbit LED7=P0^6;
sbit LED8=P0^7;
//红外地址接口定义(74HC138译码器

课程设计_老鼠走迷宫[1]

课程设计_老鼠走迷宫[1]

HUNAN CITY UNIVERSITY 数据结构课程设计报告设计题目：老鼠走迷宫专业：计算机科学与技术学生姓名：邓宇班级学号： 0906401-23指导教师：杨格兰、胡奇光2011 年 6 月 18 日一、设计时间2011年6月20日——24日二、设计地点湖南城市学院第一实验楼计算机系机房509三、设计目的1.培养实际工作所需要的动手能力，进一步熟悉基本概念；2.熟练掌握对实际问题的抽象技能，了解程序基本的流程；3.培养查阅资料，独立思考问题的能力。

四、设计人邓宇五、指导老师杨格兰、胡奇光六、设计课题老鼠走迷宫开发环境：Visual Studio 2010 Ultimate UML Activity DiagramVisual C # 2008 Express EditionsAdobe Photoshop CS4七、基本思路及关键问题的解决方法技术要求：程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。

游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。

要求：1、老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；解决方案：老鼠图片形象可以用Photoshop来制作，通过键盘按键事件发送消息到对象（老鼠），实现老鼠的移动。

2、迷宫的墙足够结实，老鼠不能穿墙而过；解决方案：在老鼠每一步的移动中检测是否撞墙，若是则停止走动。

由于地图是图片，要检测就需要取出墙壁那点的颜色（显然不是白色），然后作比较来作碰撞检测。

3、若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；解决方案：加载定时器，设定60秒钟，若在规定的时间，及时间变成0时，弹出对话框提示用户游戏失败。

4、添加编辑迷宫功能，可修改当前迷宫。

解决方案：备用一张地图图片资源，可以用于更换地图。

八、算法及流程图Visio流程图：因为这是面向对象而非面向工程的程序设计，事件和判断都具有同时性和并发性。

UML建模图如下：九、调试过程中出现的问题及解决方法本次课程设计出现最严重的问题是通过键盘来如何控制对象（老鼠）的移动，刚开始做时试用了多种方法但是没有效果。

电子老鼠闯迷宫

电子老鼠闯迷宫

一、实习问题：电子老鼠闯迷宫二、问题描述：有一只电子老鼠被困在如下图所示的迷宫中。

这是一个7*7单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。

电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。

现给定一个起点start和一个终点finish，求出电子老鼠最少要几步从起点走到终点。

三、问题分析：该问题可用分支限界法来解决。

迷宫问题的解空间是一个图。

解此问题的队列式分支限界法从start开始将它作为第一个扩展结点。

与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格start到这些方格的距离为1。

接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。

这个过程一直继续到算发搜索到目标方格finish或活结点队列为空时为止。

在实现算法时，首先定义一个表示迷宫上方格位置的类Position，它的两个私用成员row 和col分别表示方格所在的行和列。

在迷宫的任何一个方格处，电子老鼠可沿右、下、左、上4个方向进行。

沿这4个方向的移动分别记为移动哦0,1,2,3。

在表中，offset[i].row和在实现上述算法时，用二维数组grid表示所给的方格阵列。

初始时，grid[i][j]=0,表示该方格允许走；而grid[i][j]=1表示该方格被封锁，不允许走。

为了便于处理方格边界的情况，算法在所给方格阵列四周设置一道“围墙”，即增设标记为“1”的附加方格。

算法开始时测试初始方格与目标方格是否相同。

如果这两个方格相同，则不必计算，直接放回起始位置标记为2。

由于数字0和1用于表示方格的开放或封锁状态，所以在表示距离时不用这两个数字，因而将距离的值都加2。

实际距离应为标记距离减2。

算法从起始位置start开始，标记所有标记距离为3的方格并存入活结点队列，然后依次标记所有标记距离为4,5…..的方格，直至到达目标方格finish或活结点队列为空时为止。

电脑鼠走迷宫实验报告附程序

电脑鼠走迷宫实验报告附程序

东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台第二届IEEE标准电脑鼠走迷宫竞赛论文东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台目录一．软件程序框图 (3)二．参赛软件研发过程 (4)三．软硬件调试过程 (4)四．各组员分工 (4)五．体会心得 (5)附录 (6)参考书目 (9)软件程序框图东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台参赛软件研发过程在void main()函数中，采用压栈的方式进行电脑鼠搜索，数组uint8 GmcCrossway[MAZETYPE*MAZETYPE]用于暂存未走过支路坐标。

数组uint8 GucMapBlock[MAZETYPE][MAZETYPE]记录每个点的地图信息，初始化为0x00。

函数void mouseGoahead(int8 cNBlock)、void mazeSearch(void)、void mouseTurnleft(void)、东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台void mouseTurnright(void)、void mouseTurnback(void)和void objectGoTo(int8 cXdst, int8 cYdst)控制电脑鼠的运动状态。

void mapStepEdit(int8 cX, int8 cY)为制作等高图函数，它把记录等高值的数组uint8 GucMapStep[MAZETYPE][MAZETYPE]（初始化为0xff）赋值。

当电脑鼠搜索时无方向可走时就按照这个等高图的信息退回上个点，冲刺时也是一样的道理。

另外，为了缩短转弯时间，并且保证电脑鼠的稳定性，采取转弯时整步，直走时半步。

我们在Mouse_Drive.c文件中，加入全局变量int8 maincheck，初始化为0（其中0为不转弯，1为转弯）。

基于ARM的走迷宫电脑鼠的设计与实现

１ ３ ６
基于 Ａ Ｒ Ｍ 的走 迷 宫 电脑 鼠的设 计 与实 现
基于 Ａ Ｒ Ｍ的走迷宫电脑鼠的设计与实现
Ｄｅ ｓ ｉ ｇｎ ａ ｎ ｄ Ｉ ｍｐｌ ｅ ｍｅ ｎ ｔ ｉ ｎ ｇ ｏ ｆ Ｍａ ｚ ｅ －ｒ ｕ ｎ ｎ ｉ ｎ ｇ Ｍｉ ｃ ｒ ｏ ｍｏ ｕ ｓ ｅ Ｂａ ｓ ｅ ｄ ｏ ｎ ＡＲＭ
ｂｌ ｏｃ ｋ， ｉ ｎ ｆ ｒ ａｒ ｅ ｄ ｄ ｅｔ ｅ ｃ ｔ ｉ ｏｎ ｍｏ ｄｕｌ ｅ ａ ｎｄ ｍｏ ｔ ｏ ｒ ｃ ｏｎ ｔ ｒ ｏｌ ｍｏ ｄｕｌ ｅ， ｅ ｔ ｃ． Ｔ ｈｅ ｓ ｏ ｆ ｔ ｗａ ｒ ｅ ｍｏ ｄｕｌ ｅ ｗａ ｓ ｃ ｏｎ ｓ ｉ ｓ ｔ ｅ ｄ ｏｆ ｕ ｎ ｄｅ ｒ ｌ ｙ ｉ ｎｇ ｄｒ ｉ ｖ ｅ ｒ ｐ ｒ ｏ — ｇｒ ａｍ ｒ ｅａ ｌ ｉ ｚ ｉ ｎ ｇ ｓ ｏｍｅ ｂａ ｓ ｉ ｃ ｆ ｕ ｎ ｃ ｔ ｉ ｏｎ ｓ ｏ ｆ ｔ ｈｅ ｍ ｉ ｃｒ ｏｍｏｕ ｓ ｅ ａ ｎ ｄ ｔ ｏ ｐ ｉ ｎ ｔ ｅｌ ｌ ｉ ｇ ｅｎ ｃ ｅ ａｌ ｇｏ ｒ ｉ ｔ ｈ ｍ． Ｏｎ ｅ ｓ ｉ ｍｐｌ ｅ ａｌ ｇｏ ｒ ｉ ｔ ｈ ｍ ｏ ｆ ｍ ａ ｚ ｅ—ｒ ｕ ｎ — ｎ ｉ ｎ ｇ ｍｉ ｃ ｒ ｏ ｍｏｕ ｓ ｅ ｗａｓ ｐｒ ｏｐ ｏｓ ｅ ｄ ａｃ ｃ ｏｒ ｄｉ ｎ ｇ ｔ ｏ ａ ｄｖ ａｎ ｃ ｅｄ ｎ ｏｍｏ ｇｒ ａ ｐｈ ｙ ａｎ ｄ ｃｅ ｎ ｔ ｒ ａｌ ｄｏｇ ｍａ Ｔｈ ｅ ａ ｌ ｇｏ ｒ ｉ ｔ ｈ ｍ ｗｉ ｔ ｈ ｔ ｏ ｗ ｃ ｏｍ ｐ ｌ ｅ ｘ ｉ ｔ ｙ ｗａ ｓ ｓ ｉ ｍｐｌ ｅ ａ ｎｄ ｅａ ｓ ｙ ｔ ｏ ａｃ ｈ ｉ ｅ ｖ ｅ ｐ ｒ ｏ ｇｒ ａ ｍ ｍｉ ｎ ｇ
弯、 加 减 速 和 制 动 等基 本 功 能 。

基于向心法则的电脑鼠走迷宫算法设计与优化


ｌ 引 言
迷 宫电脑 鼠的概念最早 由 ＩＥ ｐ ｃ ｕ 杂志在 Ｅ Ｅ Ｓ ｅｔ ｍ ｒ
传统 算法最 基本 的是深度搜 索和广度 搜索【， 统算 ７传 】 法存在搜 索效率 不高的 问题， 很多情况下 都有可能 在 会遍历 整个迷 宫才 能找到解， 以许多人在传 统算法 所 的基础 上，进 一步改善 这些算法，经过 改进后 的算法 有 Ｆｏ ｄ ｉ 算法【、 ｉ ｓ ａ 【等， ｌ ｌ ｏ Ｆｌ ８ Ｄ ｉ ｔ ’’ 这些算法在搜索效 １ ｋ ｒ ｓ】
２１ ０ ２年 第 ２ 卷 第 ９期 １
ｈｔ：ｗ ． ｓ ．ｒ． ｔ ／ ｗｗｃ － ｏｇｃ ｖ／ －ａ ｎ
计 算 机 系 统 应 用
基于 向心法则的 电脑 鼠走迷宫算法设计与优化①
贺 少波，孙克
（ 南 大 学 物 理 与 电 子学 院，长 沙 ４ ０ ８ ） 中 １０ ３ Nhomakorabea摘
要：电脑 鼠是一个集 自主迷宫搜索 、搜索完后最短路冲刺 、传感与控制于一体 的 自主移动机器 人系统． 具体
７ Ｏ年 代提 出，就是使用嵌入式微控制器 、传 感器 和机 电运 动部件 构成 的一种 智能行走 装置，可 以在” 宫” 迷
中 自动记 忆和选 择路径 ， 找 出 口，最终达 到所 设的 寻
目的地川．目前 电脑 鼠走迷 宫 比赛在许 多 国家都很 受
关注，迷宫 电脑 鼠在我国起 步较晚， 到 ２ ０ 直 ０ ７年才在
ｗｅｆ ｕ ｄｔ ａ ｅ ｔａ ｅｈ ｄ ｉ ｅ ｙｅ ｃ ｅ ｔｍ ａ ｅｓ ａ ｃ ｌ ｏ ｉｈ ｏ ｎ ｈ ｔｔ ｃ ｎ ｒ ｌ ｔ ｏ ｓａｖ ｒ ｆ ｉｎ ｚ ｅ ｒ ｈ ａｇ ｒｔ ｍ ｈｅ ｍ ｉ
Ｋｅ ｙ ｗｏｒ ｓ ｍｉｒ － ｕ ｅ ｍａ ｅｓ ａ ｃ ａ ｔ ｎ ｍｏ ｓｍｏ ｉｅｒ ｂ ｔ ｃ ｎ ｌ ｔ ｏ ｄ ： ｃ ｏ ｍｏ ｓ ； ｚ ｅ ｒｈ； ｕ ｏ ｏ ｕ ｂ ｌ ｏ ｏ ； ｅ ￣ａ ｈ ｄ ｍｅ

一种走迷宫电脑鼠的设计与实现

１ ． 电源 部 分 ２
Ｉ
●… ．ห้องสมุดไป่ตู้
电 机 控 制 于系 统
… … …
— ●
Ｉ
图 １系统 硬件 结 构图
电源包括 电池组和 电压调节 电路 。电池组采用 ４节 ＡＡ
电池 ， 使 用 ２５ ．Ｔ 型 插 座 ， 电压 调 节 电 路 采 用 Ｓｐ ｘ公 司 ． ２ ４ ￣ｅ 生 产 的 Ｓ ６ ４Ａ 芯 片¨， 该 芯 片 是 一 个 极 低 静 态 电流 、 高 Ｐ６ １ Ｊ
技 术交 流
微 型 电脑 应 用
２０ ０ ８年 第 ２ ４卷 第 ９期
种 走 迷 宫 电脑 鼠 的设 计 与 实 现
朱姗 傅 或哲 吴 忠 丽 王伟 仇 润鹤
摘
要 ：该 文介绍 了一种基 于ＡＲ 嵌入 式的电脑 鼠，主要 由 电源、传感子 系统、 电机控制 子系统、微控制 器单元等功能模 Ｍ
Ｃ ｒ ｘ ３ 理 器 Ｌ ３ １２ 主 控 制 器 ， 控 制 和 检 测 红 外 传 ｏｔ Ｍ 处 ｅ Ｍ Ｓ ０为 感 器 ； 控 制 器 根 据 检 测 到 的传 感信 号 ， 制 电机 驱 动 电路 ， 微 控 调 整 行 走 ，按 照 载 入 算 法 进 行 迷 宫 的 探 测 ，寻 找 最 短 路 径 ， 最 终 实 现 从 起 点 到终 点 的冲 剌 。
块 组 成 ， 中对 各 个 模 块 的工 作 原 理 ， 别 从 硬 件 结构 、 件 流 程 二 个 主 要 环 节 对走 迷 宫 的 电脑 鼠 实现 过程 进行 深 入 的说 明 ， 文 分 软 并在 算 法 方 面 对 传 统 的 中左 法 则进 行 了改 进 ， 于 泛 洪 算 法 的 思 想 ， 合 向心 法则 ， 出 了一 种 简单 的 电脑 鼠走 迷 宫 的 算 法 ， 基 结 提 仅 用 一 个 一 维 数 组 就 可 以记 录迷 宫 的 全部 信 息 ， 具 有 较 低 的 复杂 度 ， 易 于 实 现 编程 ，本 设 计 有 较 广 泛 的 发展 应 用 前 景 。 关 键 词 ：嵌 入 式 ； 电脑 鼠 ； 中左 法则 ； 泛 洪 算 法 中图分 类号 ：Ｔ ３ ９ Ｐ ９ 文件标识码 ：Ａ

电老鼠走迷宫算法

摘要 摘 要 一种电脑鼠走迷宫的算法■ 上海商学院 张新谊─────────────────────────────────────────────────────────────────电脑鼠（Micromouse ）实际上是一个由微处理器控制的，集感知、判断、行走功能于一体，能够自动寻找最佳路径到达目的地的小型机器人。

国际电工和电子工程学会（IEEE ）每年都要举办一次国际性的电脑鼠走迷宫竞赛。

本文介绍一种能满足IEEE 学会颁布规则的电脑鼠走迷宫算法。

───────────────────────────────────────────────────────────────── 关键词 运行时间 迷宫时间 碰触 排障时间─────────────────────────────────────────────────────────────────电脑鼠的英文名称为Micromouse ，实际上是一个由微处理器控制的，集感知、判断、行走功能于一体，能够自动寻找最佳路径到达目的地的小型机器人。

它可以在“迷宫”中自动感知并记忆迷宫地图，通过一定的算法，寻找一条最佳路径，以最快的速度到达目的地。

1997年，在美国举办了第一届电脑鼠竞赛，随后，电脑鼠竞赛传入欧洲，首届欧洲电脑鼠竞赛于1980年在伦敦举办，之后英国的电脑鼠比赛便由电子工程协会（IEE ）主办。

1980年11月日本电脑鼠协会（JMA ）在东京举办了第一届竞赛，此后，日本每年都要举办一届电脑鼠竞赛。

我国台湾也于1986年10月举办了首届电脑鼠比赛。

现在国际电工和电子工程学会（IEEE ）每年都要举办一次国际性的电脑鼠走迷宫竞赛，各国选手报名踊跃，主要是大学生，为此部分大学还开设了“电脑鼠原理和制作”选修课程。

由于电脑鼠要由参赛选手自己设计制作，不仅要求选手具有嵌入式系统应用﹑传感器﹑控制技术等多方面的知识、经验和实践能力，还要求具有编写寻找最佳路径算法的能力。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2． 2
迷宫搜索算法的设计
为了讨论方便， 这 里 使 用 位 差 值。 所 谓 位 差 值 就 是 格 子 （ cell） 距离迷宫中点的最小格子数， 目标的位差值是 0 。 每个格 子的位差值如图 2 所示。
图2
每个格子的位差值
当电脑鼠到达一个格子坐标时， 应该根据传感器检测结果 16］ ［ 16］来保 记录下当前格子的隔墙资料， 可以使用 mapblock［ 存整个迷宫隔墙资料， 表 1 所示隔墙信息的存储方式 。 隔墙资 0 ， 即 料全部初始化为 凡是走过的迷宫格至少有一方没有隔墙， 隔墙资料不为 0 。这样就可以通过单元格存储的隔墙资料是否 为 0 来确定该单元格是否走过 。
表2 迷宫类型 Unpar Unpar Unpar ITB ITB 图4 死路示意图 算法性能比较 搜索步数 +∞ 60 56 +∞ 71 41
搜索算法 沿墙 DFS 位差值 沿墙 DFS 位差值
对于一些特殊的迷宫， 电脑鼠在搜索过程中， 若从某点出发 经过一些点又回到了该点则被标记为环 。可以通过算法来判断 该环是否为封闭循环路径 。 当电脑鼠到达某点， 发现该点以前 已经走过则检查前一个格子， 直到发现某个格子有多路选择 。 判断该格子是否为当前格子， 如果是， 则标记封闭循环路径内的 格子为死路； 如果不是， 则表明不是封闭循环路径 。 如图 5 所 B、 C、 D、 E、 F 和 G 组成了封闭循环路径。当电脑鼠从 G 到达 示， B 时， 因为检测到第二次经过 B， 则检测前一个格子 G， 发现格子 G 只有一路可以走， 并且只能移动到 B。重复检测以前的格子， 直到遇到有多路选择的格子， 即本例中是格子 B。 因为该格子 C， D， E， F 和 G） 是 所以可以得到格子（ B， 是电脑鼠的当前位置， 设置这些格子的 marking 为真。 封闭循环路径， 通过标记死路和封闭循环路径， 该算法不会进入死循环或 确保了该算法的可行性 。 重复走过的路径，
表1 变量位 bit0 bit1 bit2 bit3 墙壁资料存储方式 备注 1 ： 有路； 0 ： 有墙 1 ： 有路； 0 ： 有墙 1 ： 有路； 0 ： 有墙 1 ： 有路； 0 ： 有墙 图3 根据位差值产生的一条路径
代表的绝对方向 上方 右方 下方 左方
当有超过一条路可以走时， 则执行多路程序。 多路程序需 准则可以包括格子走过的次数 、 位差 要根据一些准则选择路径， 值、 直走还是拐弯等。 如果电脑鼠有两个或三个可选方向， 首先要判断的准则是 相邻格子是否走过， 这可以通过该格子的隔墙资料来确定 。 一 种可能性是至少有一个格子没有走过 。 这样的话， 电脑鼠选择 的下一个格子应该是没有走过的格子 。但是如果有超过一个格 子未走过， 则需要根据位差值进一步决定 。 位差值准则是通过 选择具有最小位差值的相邻格子作为可选路径的方法 。如果有 两个格子具有相同的最小位差值， 则选择直走。 向前移动比左 右转弯的优先级要高， 这是因为电脑鼠直走比转弯的速度更快 。 另一种情况是所有的格子都走过， 电脑鼠则选择相邻格子中走 过次数最小的格子进入 。若相邻格子走过的次数相同则再判断 位差值， 若还相同的则选择直走 。
Abstract Micromouse is actually an autonomous mobile robot （ AMR） ． The micromouse finds the optimal path to get to the destination area which is located in the center of labyrinth without any information of the layout． The whole process is an automatic search process． In this paper we studied and realised the potential valuebased path searching algorithm and contour mapbased optimal path algorithm，and also made the improvement on the ability of micromouse’ s tasks accomplishment． Keywords Maze solving algorithm Micromouse robot Potential value Contour map Optimal path
2． 6
实验测试搜索算法
为了评估该算法， 我们在同一迷宫里运行了三个不同的算
法， 即 沿 墙 的、 深 度 优 先 探 索 （ DFS ） 和 基 于 位 差 值 的 搜 索 算法
［5 ］
。
在德州仪器 Unpar 迷宫和 ITB 的迷宫测试中。 使用基于位 差值的搜索算法电脑鼠到达了目标点， 而使用其他两个算法会 导致不同的现象。沿墙算法未能使之到达终点， 而深度优先搜 索算法行驶距离更长。如表 2 所示。
［1 ， 2 ］
竞赛的规则
。
电脑鼠的基本功能是从起点开始走到终点所花费的时间称 “ 。 电脑鼠从第一次激活到运行开始所花费的时 为 运行时间 ” “迷宫时间” 。电脑鼠在比赛时手动辅助的动作称为 “碰 间称为 触”
［1 － 3 ］
电脑鼠搜索路径应该是在没有人工干预的情况下自主完成 的， 也就是说， 需要运用搜索算法使电脑鼠自主行走 。搜索算法 根据电脑鼠当前的位置确定下一步， 以迅速到达 的主要目的是， 迷宫的中心并返回， 同时利用搜索迷宫时得到的隔墙信息找出 从起点到终点并返回的最优路径 。
2． 3
移动策略
电脑鼠的主要行为就是能够在各种不同情况的迷宫中作出
分别对应这三种处理程序： 死路程序、 单路 决定。有三种情况， 程序和多路程序。 当电脑鼠面对 3 面墙时， 需要执行死路程序。 死路程序会 marking 将当前所处格子的 标记为真， 表示下次搜索时不可进 并且电脑鼠向后转 180 度。如图 3 中点 G 所示， 电脑 入该格子， 鼠在 G 点面对上、 下和右 3 面墙。 当只有一条路可以走时， 执行单路程序。 单路程序会选择 唯一的可前进路径。如图 3 所示， 从 A 到 D， 从 D 到 E 和从 G 到 F 之前的一个单元格， 执行单路程序。
DESIGNING AND IMPLEMENTING A MAZE SOLVING ALGORITHM FOR MICROMOUSE
Wang Fenglin Wang Yihuai
（ School of Compoochow University，Suzhou 215006 ， Jiangsu， China）
1
1． 1
电脑鼠走迷宫的规则与流程
迷宫、 电脑鼠的规格
。在试跑时， 需要按照一定的算法得到隔墙信息， 并到达终 跑” 点， 即迷宫搜索算法； 在搜索结束后根据搜索所获得的隔墙信 按照最优路径算法确定最佳路径， 并以最快的速度到达目的 息， 。 冲刺后还可以继续多次试跑和 地， 这次运行被称为“冲刺 ” 冲刺。
0
引
言
电脑鼠必须自成独立系统 。 电脑鼠的长和宽限定在 25cm × 25cm。对电脑鼠的高度没有限制 。
1． 2
“电脑鼠” （ micromouse） ， 所谓 是使用嵌入式微控制器 、 传感 器和机电运动部件构成的一种智能行走装置的俗称， 它可以在 “迷宫” 中自动记忆和选择路径， 寻找出口， 最终达到所设的目 的地
迷宫由 256 个方块（ 单元） 组成， 每个方块的大小为 18 厘米 见方， 排成 16 行 × 16 列。迷宫的隔墙板沿方块的四周布设， 形 成迷宫通道。如图 1 所示。
2
迷宫搜索算法
当电脑鼠移动时， 电脑鼠要知道自己所处的位置， 因此首先
需要定义电脑鼠的坐标和方向， 然后设计基于位差值的搜索
收稿日期： 2009 － 04 － 05 。 王凤林， 硕士生， 主研领域： 嵌入式系统 图1 全迷宫结构 应用， 网络技术。
2． 4
死路的标记和封闭循环路径的避免
死胡同程序（ 路 = 0 ） 。 图 4 中 D 点， 只有一条可能的路可 电脑鼠三面都围着墙时 。 单元格 D 被标记为真， 电脑鼠 以走， 向后转 180 度。当遇到死路时， 电脑鼠应该标记所有的属于该 H， J， N。 死路的格子。图 4 中被标记为死路的死路终点是 D， P— O， 属于死路的格子是 E—F， 和 K。一旦格子被标记为死路， 下一次电脑鼠经过该点时， 将不会把该点作为可选路径 。
第 12 期
算法
［4 ］
王凤林等： 一种电脑鼠走迷宫算法的设计与实现
271
。
2． 1
迷宫坐标和方向
达某个格子后， 该格子的 count 变量需要加 1 。 该变量在搜索算 法中选择路径时要用到 。 当电脑鼠处于某个格子时， 需要完成下面的操作： ① 检测是否到达过该格子 。 ② 通过传感器计算该格子可走的方向 。 ③ 根据该格子可走的方向数， 选择下一步走的方向。 ④ 检查封闭的循环路径和死路， 并更新相应的变量。 ⑤ 移动到下一个格子， 更新当前坐标。 ⑥ 根据坐标检测是否到达终点 。
第 27 卷第 12 期 2010 年 12 月
计算机应用与软件 Computer Applications and Software
Vol. 27 No． 12 Dec． 2010
一种电脑鼠走迷宫算法的设计与实现
王凤林 王宜怀
（ 苏州大学计算机科学与技术学院 江苏 苏州 215006 ）
摘 要 电脑鼠是一个自主移动机器人系统 。电脑鼠的任务是到达迷宫中心的目标区域 。 电脑鼠在不知道迷宫的布局情况下， 必须自己找出到达目标的最优路径 。整个过程是一种自主搜索的过程 。研究和实现了基于位差值的搜索算法和基于等高图的最优 并作出改进提高机器人完成任务的能力 。 路径算法， 关键词 迷宫搜索算法 电脑鼠机器人 位差值 等高图 最优路径