文档介绍：编号       面向对象程序设计I课程设计报告二级学院  计算机科学与工程学院 专  业  计算机科学与技术   班  级    115030702    学生姓名 柴勇 学号********** 指导教师     刘恒洋     时  间    2016年6月    (1)、随机生成迷宫地图;(2)、地图信息存储到文件;(3)、快速寻路,从起点到达终点;(4)、遍历迷宫,并且存储迷宫信息(5)、建立等高表;(6)、找到起点到终点的最短路径。,电脑鼠要知道自己所处的位置,因此首先需要定义电脑鼠的坐标和方向,然后设计基于位差值的搜索算法。1、迷宫坐标和方向为了让电脑鼠记住所走过的各个迷宫格的信息,需要使用坐标对64个迷宫进行编号。2、迷宫搜索算法的设计当电脑鼠到达一个格子坐标时,记录下当前格子的隔墙资料,可以使用Cell[8][8]来保存整个迷宫隔墙资料。隔墙资料全部初始化为0,凡是走过的迷宫格都通过改变Cell里面的visited的值为true标记为已经访问过。当电脑鼠处于某个格子时,需要完成下面的操作:1测是否到达过该格子。2通过传感器计算该格子可走的方向。3根据该格子可走的方向数,选择下一步走的方向。4检查封闭的循环路径和死路,并更新相应的变量。5移动到下一个格子,更新当前坐标。6根据坐标检测是否到达终点。3、移动策略电脑鼠的主要行为就是能够在各种不同情况的迷宫中作出决定。有三种情况,分别对应这三种处理程序:死路程序、单路程序和多路程序。当电脑鼠面对3面墙时,要执行死路程序。死路程序会将当前所处格子的pass标记为真,表示下次搜索时不可进入该格子,并且电脑鼠向后转180度。当只有一条路可以走时,执行单路程序。单路程序会选择唯一的可前进路径。根据位差值产生的一条路径当有超过一条路可以走时,则执行多路程序。多路程序需要根据一些准则选择路径,准则可以包括格子走过的次数、位差值、直走还是拐弯等。如果电脑鼠有两个或三个可选方向,首先要判断的准则是相邻格子是否走过,这可以通过该格子的隔墙资料来确定。一种可能性是至少有一个格子没有走过。这样的话,电脑鼠选择的下一个格子应该是没有走过的格子。但是如果有超过一个格子未走过,则需要根据位差值进一步决定。位差值准则是通过选择具有最小位差值的相邻格子作为可选路径的方法。如果有两个格子具有相同的最小位差值,则选择直走。向前移动比左右转弯的优先级要高,这是因为电脑鼠直走比转弯的速度更快。另一种情况是所有的格子都走过,电脑鼠则选择相邻格子中走过次数最小的格子进入。若相邻格子走过的次数相同则再判断位差值,若还相同的则选择直走。4、死路的标记和封闭循环路径的避免只有一条可能的路可以走,电脑鼠三面都围着墙时。单元格被标记为真,电脑鼠向后转180度。当遇到死路时,电脑鼠应该标记所有的属于该死路的格子。一旦格子被标记为死路,下一次电脑鼠经过该点时,将不会把该点作为可选路径。对于一些特殊的迷宫,电脑鼠在搜索过程中,若从某点出发经过一些点又回到了该点则被标记为环。可以通过算法来判断该环是否为封闭循环路径。当电脑鼠到达某点,发现该点以前已经走过则检查前一个格子,直到发现某个格子有多路选择。判断该格子是否为当前格子,如果是,则标记封闭循环路径内的格子为死路;如果不是,则表明不是封闭循环路径。重复检测以前的格子,直到遇到有多路选择的格子。因为该格子是电脑鼠的当前位置,所以可以得到格子是封闭循环路径,设置这些格子的visited为真。通过标记死路和封闭循环路径,该算法不会进入死循环或重复走过的路径,确保了该算法的可行性。5、遍历迷宫遍历迷宫即是在寻路的基础上将迷宫每一个单元格都走过至少一次,通过判断所有单元格的visited值判断是否已经遍历完迷宫的每一个单元格。6、等高表的制作及获取最短路径通过队列算法获得等高表的信息。将起点的路径值赋值为1,并将起点作为队列的头结点,然后判断起点的周围可以通行的路径,如果有可以通行的路径,删除队列此时的头结点,然后将可通行路径的坐标加入队列,并将其路径值加1;没有可以通行的路径则直接删除头结点。然后将新的头结点周围的信息进行判断,直到头结点的坐标和终点坐标相同为止。等高表建立后,从终点通过判断周围单元格的路径值,将最短路径上的单元格的信息加入链表,然后根据链表的信息,画出最短路径图。,MazePoint和MazeModel用来随机生成迷宫地图,Cell、StackOfCell用来存储地图信息和电脑鼠在迷宫中的位置信息,InterFaceextensApplication用来完成迷宫地图的显示和算法的实现。,蓝色线路代表