电脑老鼠走迷宫竞赛.ppt

《电脑老鼠走迷宫竞赛.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、电脑老鼠走迷宫竞赛算法简介08计算机（1）班龚若皓软件算法所需要实现的功能最基本的功能：1.正确记录迷宫的信息2.正确记录小车的状态（当前的方向，四周的挡板情况等）3.确保小车的移动，停止和转弯的可控性需要实现的核心功能1.实现基本的从起点到终点的寻路过程。2.实现等高表的生成算法。3.实现从当前的位置通过最有效的路径移动到指定的任意位置。（通过建立等高表来实现）4.根据已经得到的迷宫地图信息实现起点到终点的最短路径分析。（通过建立等高表来实现）软件算法所需要实现的功能可拓展的部分：1.适当修改步进电机的驱动函数，提高步进电机的加速和减速功能，提高整体的速度。2.改进寻路算法，最好

2、不要使用传统的右手法则和左手法则，使用向心法则等高效的寻路方法。3.进行数据补全，减少小车进入“死胡同”的次数。4.改进转弯的方式，尽量实现前进中拐弯，同时确保稳定性，提高整体的速度。消除不必要的停顿使小车行驶更加流畅。5.改进传统的等高表路径分析算法，实现加权的等高表算法，将拐弯次数的信息也加入到最短路径的分析过程中。数据的存储方式1.迷宫信息的存储因为迷宫分为16*16=256个方格，所以很直观地可以想到用一个二维矩阵来存储一个迷宫的信息，矩阵中的每一个元素用于存储地图中一个方格的信息，矩阵每个元素可以定义成Byte型，只用其中的四位就可以存储方格四面的挡板信息了，有挡板的方向

3、将对应的位置位，没有挡板的将对应位清零。要获取某一个方格单个方向的挡板信息，只需要做一个简单的与运算在看结果是否为零即可。剩下的四位用于其它的用途，例如在后期的加权等高表生成算法中存储小车的方向信息。初始化的时候将矩阵元素的数值低四位初始化为0，标识改坐标是否被探测过。数据的存储方式举例：假设Byte型的数据Data=0bxxxx1100存储了某一个方格四个方向的挡板信息，高四位用于存储其他信息，低四位用于存储档板的信息，从高位到低位分别对应方向为：上，右，下，左（绝对方向）。上右下左0bxxxx1100&0b000001000b00000100结果不为零，判断为右边有挡板数据的存

4、储方式2.方向信息的存储方向绝对方向：以小车刚刚开始运行的时候车头面向的方向作为“上”，其他的方向类推。相对方向：顾名思义，相对于当前小车所朝向的方向的方向。例如绝对方向的下相对于绝对方向的右的相对方向是右方数据的存储方式方向的分类：小车的车头朝向的方向：需要分配空间来固定地存储下来，平并且在小车运行的过程中随着转弯而变化，是以绝对方向来表示的。小车转弯的方向：不需要分配单独的空间的固定存储，只需要给不同的转弯方向编制不同的实现函数就行了，例如给向右转弯编制一个函数TurnRight()，这里的右方是相对方向，亦即是相对于当前小车的车头朝向的方向的方向，例如小车当前是朝着绝对方向的

5、右方的，那么现在右转函数要实现的就是将小车车头转到面向绝对方向的下方，而不是绝对方向的右方。那么转弯后，记录小车的车头方向的变量应该怎样变化呢？数据的存储方式绝对方向和相对方向的变换：假设数值0，1，2，3分别表示绝对方向的上，右，下，左，那么就用0，1，2，3中的其中一个数值来表示当前小车车头朝向的方向，当然这个数值是动态变化的，每转弯一次该数值应当变化一次，例如当前方向的数值为3（左方），那么经过一次右转操作后该数值就应该变化为0了（上方）。其实转化的规则相当简单，只要右转方向数值就加1，只要左转方向数值就加3，只要后转方向数值就加2，当然可能有越界的情况，所以得出的方向数值再

6、进行模运算对4取余数得出的结果就是转弯后小车的车头所面向的方向的数值了。数据的存储方式综上所述可以得出如下的表格：转弯前的方向转弯方向转弯后的方向0（上方）向左（+3）向左（0+3）%4=30（上方）向右（+1）向右（0+1）%4=10（上方）向后（+2）向后（0+2）%4=21（右方）向左（+3）向上（1+3）%4=01（右方）向右（+1）向下（1+1）%4=21（右方）向后（+2）向左（1+2）%4=32（下方）向左（+3）向右（2+3）%4=12（下方）向右（+1）向左（2+1）%4=32（下方）向后（+2）向上（2+2）%4=03（左方）向左（+3）向下（3+3）%4=23

7、（左方）向右（+1）向上（3+1）%4=03（左方）向后（+2）向右（3+2）%4=1数据的存储方式通过前面的表格可以找到当前的小车方向和转弯后的小车方向的对应关系，得出的相对方向和绝对方向的转换公式如下所示：转弯后的绝对方向=（转弯前的绝对方向+转弯数值）%4小车的车头方向一般是用一个全局变量来存储的，方便在转弯的函数中进行修改，避免C语言中一些作用域的问题。也可以通过传指针的方式来完成，不过定义为全局变量比较方便。小车的运行包括的子过程1.初始探测确定小车的起点坐