阅读:0       作者:严长生

数据结构实践项目之移动迷宫小游戏(初级版)

《移动迷宫》游戏简介:迷宫只有两个门,一个入口,一个出口。一个骑士骑马从入口走进迷宫,迷宫中设置有很多墙壁,对前进方向造成障碍。骑士需要在迷宫中寻找通路以到达出口。

本游戏的迷宫是“移动”的,每次骑士进入迷宫时,迷宫的入口、出口,甚至是迷宫中设置的障碍都是不同的。

设计思路

解决类似的问题,使用回溯法是最行之有效的解题方法。骑士从入口开始,不断地对周围的道路进行试探:若能走通,则进入该位置,继续对周围进行试探;反之,则后退一步,继续寻求其他的可行路径。

通过不停地对可行道路进行试探,结果有两种:
  • 骑士最终找到了一条通往出口的道路;
  • 试探结束,没有通往出口的道路,骑士最终只能被迫返回入口,继续等到迷宫的下一次变化(程序结束)。

实例分析

假设迷宫为一块长为 10 ,宽为 8 的矩形区域,其中随机设置了入口、出口和该区域内可供通行的道路,如下图所示:

提示:迷宫中,‘0’ 表示道路,‘#’ 表示障碍。

当骑士处于入口的位置时,他会前后左右的进行探索式前进,当他发现前方道路可行时,即坐标为(2,1)的通路,此时骑士会快速移动至该位置,进行以该位置为中心的再次探索式前进。

通过骑士不断地探索,对于该实例中列举的迷宫,骑士最终可以找到一条通往出口的道路,如下图所示:

提示:迷宫中,新增的‘X’表示骑士走过的道路(找出一条通路即可)。

完整实现代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef enum {false,true} bool;
//迷宫本身是一个8行10列的矩形
int ROWS=8;
int COLS=10;
//初始化迷宫,随机设置迷宫出入口,同时在迷宫中随机设置可行道路。
void mazeGenerator(char [][COLS],int *,int *,int *,int *);
//使用回溯法从入口处不断地尝试找到出口的路径
void mazeTraversal(char maze[ROWS][COLS],int row,int col,int entryRow,int entryCol,int exitrow,int exitcol);
//迷宫的输出函数
void printMaze(const char[][COLS]);
//判断每一次移动是否有效
bool validMove(const char [][COLS],int,int);

int main()
{
    printf("*********移动迷宫小项目(数据结构就该这么学)*********\n");
    char maze[ROWS][COLS];
    int xStart,yStart,x,y;
    srand(time(0));//种下随机种子数,每次运行种下不同的种子,后序通过rand()函数获得的随机数就不同。
    //通过一个嵌套循环,先将迷宫中各个地方设置为死路(‘#’表示为墙,表示此处不可通过)
    for(int loop=0;loop<ROWS;++loop ){
        for(int loop2=0;loop2<COLS;++loop2 ){
            maze[loop][loop2]='#';
        }
    }
    //初始化迷宫,即在迷宫中随机设置出口、入口和中间的道路,用‘0’表示。通过此函数,可同时得到入口的坐标
    mazeGenerator(maze,&xStart,&yStart,&x,&y);

    printf("迷宫入口位置坐标为(%d,%d);出口位置坐标为:(%d,%d);\n",xStart+1,yStart+1,x+1,y+1);
    printf("迷宫设置如下(‘#’表示墙,‘0’表示通路):\n");
    printMaze(maze);//输出一个初始化好的迷宫
    //使用回溯法,通过不断地进行尝试,试图找到一条通往出口的路。
    mazeTraversal(maze,xStart,yStart,xStart,yStart,x,y);
}
//由于迷宫整体布局为矩形,有四条边,在初始化迷宫的出口和入口时,随机选择不同的两条边作为设置出口和入口的边
void mazeGenerator(char maze[][COLS],int *xPtr,int *yPtr,int *exitx,int *exity){
    int a,x,y,entry,exit;
    do {
        entry=rand()%4;
        exit=rand()%4;
    }while(entry==exit);
    // 确定入口位置,0 代表选择的为左侧的边,1 代表为上边,2代表为右侧的边,3 代表为下边
    if(entry==0){
        *xPtr=1+rand()%(ROWS-2);
        *yPtr=0;
        maze[*xPtr][*yPtr]='0';
    }else if(entry==1){
        *xPtr=0;
        *yPtr=1+rand()%(COLS-2);
        maze[*xPtr][*yPtr]='0';
    }else if(entry==2){
        *xPtr=1+rand()%(ROWS-2);
        *yPtr=COLS-1;
        maze[*xPtr][*yPtr]='0';
    }else{
        *xPtr=ROWS-1;
        *yPtr=1+rand()%(COLS-2);
        maze[*xPtr][*yPtr]='0';
    }
    //确定出口位置
    if(exit==0){
        a=1+rand()%(ROWS-2);
        *exitx=a;
        *exity=0;
        maze[a][0]='0';}
    else if(exit==1){
        a=1+rand()%(COLS-2);
        *exitx=0;
        *exity=a;
        maze[0][a]='0';}
    else if(exit==2){
        a=1+rand()%(ROWS-2);
        *exitx=a;
        *exity=COLS-1;
        maze[a][COLS-1]='0';}
    else{
        a=1+rand()%(COLS-2);
        *exitx=ROWS-1;
        *exity=a;
        maze[ROWS-1][a]='0';
    }
    //在迷宫中央设置多出不同的随机通路
    for(int loop=1;loop<(ROWS-2)*(COLS-2);++loop) {
        x=1+rand()%(ROWS-2);
        y=1+rand()%(COLS-2);
        maze[x][y]='0';}
}

void mazeTraversal(char maze[ROWS][COLS],int row,int col,int entryRow,int entryCol,int exitrow,int exitcol){
    //由于从入口处进入,为了区分走过的通路和没走过的通路,将走过的通路设置为‘x’,
    maze[row][col]='x';
    static bool judge=false;//设置一个判断变量,判断在入口位置是否有通路存在。
    static int succ=0;//用于统计从入口到出口的可行通路的条数
    if (row==exitrow && col==exitcol) {
        printf("成功走出迷宫,道路图如下:\n");
        printMaze(maze);
        succ++;
        return;
    }
    //判断当前位置的下方是否为通路
    if (validMove(maze, row+1, col)) {
        judge=true;//证明起码有路存在,下面证明是否有可通往出口的路
        mazeTraversal(maze, row+1, col,entryRow,entryCol,exitrow,exitcol);//以下方的位置为起点继续尝试
    }
    //判断当前位置的右侧是否为通路
    if (validMove(maze, row, col+1)) {
        judge=true;
        mazeTraversal(maze, row, col+1,entryRow,entryCol,exitrow,exitcol);
    }
    //判断当前位置的上方是否为通路
    if (validMove(maze, row-1, col)) {
        judge=true;
        mazeTraversal(maze, row-1, col,entryRow,entryCol,exitrow,exitcol);
    }
    //判断当前位置的左侧是否为通路
    if (validMove(maze, row, col-1)) {
        judge=true;
        mazeTraversal(maze, row, col-1,entryRow,entryCol,exitrow,exitcol);
    }
    //如果judge仍为假,说明在入口处全部被墙包围,无路可走
    if (judge==false) {
        printf("入口被封死,根本无路可走!\n");
        printMaze(maze);
    }
    //如果judge为真,但是succ值为0,且最终又回到了入口的位置,证明所有的尝试工作都已完成,但是没有发现通往出口的路
    else if(judge==true && row==entryRow && col==entryCol && succ==0){
        printf("尝试了所有道路,出口和入口之间没有通路!\n");
        printMaze(maze);
    }
}
//有效移动,即证明该位置处于整个迷宫的矩形范围内,且该位置是通路,不是墙,也从未走过
bool validMove(const char maze[][COLS],int r,int c){
    return(r>=0&&r<=ROWS-1&&c>=0&&c<=COLS-1&&maze[r][c]!='#'&& maze[r][c]!='x');
}
//输出迷宫
void printMaze(const char maze[][COLS] ){
    for(int x=0;x<ROWS;++x){
        for(int y=0;y<COLS;++y){
            printf("%c ",maze[x][y]);
        }
        printf("\n");
    }
    printf("\n");
}

该程序由于每次运行产生不同的迷宫,所以每次运行结果不同,可自行运行,查看结果,这里不再进行描述。

总结

通过练习《移动迷宫》小游戏,旨在让大家熟悉回溯法的解题思路。

回溯 PK 递归回忆:比如说你在面对一个二叉路口,不知道要走哪条,此时就要做尝试(尝试这个动作就是一个函数)你选择先尝试左边这条,往左边走,走着走着发现又有一个二叉路口,此时你需要上一次尝试的过程中要再做一次尝试,即在函数内再调用一次函数,这是递归。但是如果你发现这条路走不通,就知道上一个二岔路你选择错了,此时你回到原来的岔路口选择右边,这就是回溯(回溯使用递归的思想实现的一种算法结构)。