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存储了某一个方格四个方向的挡板信息，高四位用于存储其他信息，低四位用于存储档板的信息，从高位到低位分别对应方向为：上，右，下，左（绝对方向）。上 右 下 左0b x x x x 1 1 0 0& 0b 0 0 0 0 0 1 0 00b 0 0 0 0 0 1
4、 0 0结果不为零，判断为右边有挡板数据的存储方式2.方向信息的存储方向 绝对方向：以小车刚刚开始运行的时候车头面 向的方向作为 “ 上 ” ，其他的方向 类推。相对方向：顾名思义，相对于当前小车所朝向 的方向的方向。例如绝对方向的下 相对于绝对方向的右的相对方向是 右方 数据的存储方式方向的分类：小车的车头朝向的方向：需要分配空间来固定地存储下来，平并且在小车运行的过程中随着转弯而变化，是以绝对方向来表示的。小车转弯的方向：不需要分配单独的空间的固定存储，只需要给不同的转弯方向编制不同的实现函数就行了，例如给向右转弯编制一个函数 TurnRight()，这里的右方是相对方向，亦即是相对于当前
5、小车的车头朝向的方向的方向，例如小车当前是朝着绝对方向的右方的，那么现在右转函数要实现的就是将小车车头转到面向绝对方向的下方，而不是绝对方向的右方。那么转弯后，记录小车的车头方向的变量应该怎样变化呢？数据的存储方式绝对方向和相对方向的变换：假设数值 0， 1， 2， 3分别表示绝对方向的上，右，下，左，那么就用 0， 1， 2， 3中的其中一个数值来表示当前小车车头朝向的方向，当然这个数值是动态变化的，每转弯一次该数值应当变化一次，例如当前方向的数值为 3（左方），那么经过一次右转操作后该数值就应该变化为 0了（上方）。其实转化的规则相当简单，只要右转方向数值就加 1，只要左转方向数值就加 3，只要后转方向数值就加 2，当然可能有越界的情况，所以得出的方向数值再进行模运算对 4取余数得出的结果就是转弯后小车的车头所面向的方向的数值了。数据的存储方式综上所述可以得出如下的表格：数据的存储方式通过前面的表格可以找到当前的小车方向和转弯后的小车方向的对应关系，得出的相对方向和绝对方向的转换公式如下所示：转弯后的绝对方向 =（转弯前的绝对方向 +转弯数值） % 4小车的车头方向一般是用一个全局变量来存储的，方便在转弯的函数中进行修改，避免 C语言中一些作用域的问题。也可以通过传指针的方式来完成，不过定义为全局变量比较方便。
