、一、游戏规则二编程要求.,,迷宫(maze)是一个矩形区域,它有一个人口和一个出1在窗口中画出初始时迷宫的状态迷宫随机生成并。。。口在迷宫的内部包含不能穿越的墙或障碍在图1所示的迷验证其合法性(可以通行的迷宫).,。宫中,障碍物沿着行和列放置,它们与迷宫的矩形边界平行。2在自动寻找迷宫路径的每一步用图形标示其状态.,迷宫的人口在左上角,出口在右下角。3自动寻找迷宫路径可以通过定时器或多线程的方法,,假定用nxm的矩阵来描述迷宫,位置(1,1)表示人口,每一步的时间间隔可以自定以人眼观察比较舒服为宜每一(n,m)表示出口,n和m分别代表迷宫的行数和列数。迷宫中步的过程如能实现动画最好。。.。的每个位置都可用其行号和列号来指定在矩阵中,当且仅当4定义迷宫的描述类.。,在位t(i,j)处有一个障碍时其值为1,否则其值为O图2给5在程序中迷宫的大小及每步移动的时间间隔可以通。出了图1中迷宫对应的矩阵描述。过对话框设置(也应该有默认值).迷宫老鼠(花tinamaze)要求寻找一条从人口到出口的路6支持暂停功和继续的功能(在自动寻径过程中可以暂。。径路径是由一组位置构成的,每个位置上都没有障碍,且每停,并继续)、、.,。个位里(第一个除外)都是前一个位置的东南西或北的邻7暂停后可以将当前的状态保存,,。。7居(如图3所示)8可以从中保存的文件中读出某个状态并继续根据要求迷宫的数据应用矩阵来存放。对于路径的寻找采用堆栈来遍历整个迷宫矩阵。只要求找到一条路径即可,从而降低了算法设计的难度。该题目要求能随时停止寻找,并将当前的状态保存,并在下次载人进度继续寻找。为了满足该要求,只能降低迷宫类的封装性,将寻找路径的代码拿到类的外部来实现。这样迷宫类的功能就成为存放迷宫矩阵的数据及相关的参数,如行数、列数等。进度的存取用到的MFC的序列化。三、算法的设计。该算法用到了一个堆栈CeUStack它的是用来保存已经到。。过的单元每个单元用一个Cell结构来描述其中含有该单元所处的位置,其上、下、左、右四个位置哪些是可行的,哪些是障碍,以及该单元是否为障碍等。该结构的描述在文件“.”。,cenh中设当前位于第y行第x列的单元中(当然该单。,元是可行的)先判断当前位置是否为迷宫的左下角即第n列,第m行。若不是,则按下面的规则寻长可能的路径。由于规定了迷宫的人口在左上角,出口在右下角,所以寻找的顺、、序选为右下、左上。按照该顺序试探当前单元的四个方向的单元,当发现一个可行的单元后,将当前的单元放入堆栈中,将下一个可行的单元放入当前位置pos-now;若寻找了一,圈没有可行的单元(实际上是三个方向因为来的方向一定是,。可已一,行的否则是不会到达当前单元的但来路被放人堆栈其中rand()产生的随机数为032767当大于1200,,,了,。中为防止程序进人恶性循环在到达当前位置时就将来时l和0的概率比大约为2比1。,时的方向设置为不可行)则放弃该位置从堆栈中弹出上一有了迷宫描述类,下一步就是写寻找迷宫路径的代码了。。,。,个位置弹出一个元素后应检查堆栈是否为空若为空则题目要求可视化的效果,因此采用定时器来控制步速。定时器。、说明当前位置为人口位置此时查看该位置的右下两个位置,的时间常数由用户指定将上述寻找路径的算法放人OnTimer,,,。是否可行若不可行则说明所有的可行位置已被试探过了()中即可但OnTimer()中的代码除了寻找路径外,还有一项,。没有可行的通路此时即可停止循环此时说明该矩阵是不合重要的任务就是将寻找路径的过程反映到用户窗口去。该功能。口,法的即没有通路的若当前位置不是入再按上面的方nvateetre;()的实现是调用IalidRe(jow)。。l,法寻找可行的路径该算法的程序流程图如图所示调用该函数后OnDraw()便根据当前的状态对窗口进行,e。在程序的实现上我设计了迷宫类CMaz该类的作用主。,ve,重绘为了避免屏幕的闪烁使用玩alidatRect()而不是。:要是保存迷宫矩阵的数据及相关参数迷宫的表示为矩阵中v。,In曲date()此时只是重绘ro一ow指定的矩形区域而不重,。值为0的位置为障碍非0的位置为可行的该类中的矩阵为绘其它区域,所以以前到过的区域并没有被重绘,直到有其它,++一个二维数表但在C中并没有针对二维数据结构的理想窗口班盖此窗口时,才会导致整个窗口的重绘,使以前的状态。,的数据类型当然二维数组是一个选择但其动态生成和维护消失。。。不是很容易因此我选择了使用线性表来表示二