~小游戏开发——迷宫（普通版）~

迷宫这一小游戏，相信大家都不是过太陌生，可是会玩并不代表会用C++编写出来，呜呜~~

好滴，废话不多说，直接进入主题吧！！！

迷宫问题主要分为：

①如何寻找可通行的道路，即探测法

②进入死胡同后如何回退以便重新寻找通路， 即回溯法

 

 首先，我们初始化并打印迷宫的地图，代码如下：

void InitMaze(int maze[][N], size_t n) //初始化迷宫图 { FILE* fout = fopen("Maze.txt","r"); assert(fout); for(size_t i=0; i<n; ++i) { for(size_t j=0; j<n; ) { char ch = fgetc(fout); if((ch == '0') || (ch == '1')) { maze[i][j] = ch - '0'; ++j; } } } } void PrintMaze(int maze[][N], size_t N) //打印迷宫图 { for(size_t i=0; i<N; ++i) { for(size_t j=0; j<N; ++j) { cout<<maze[i][j]<<" "; } cout<<endl; } cout<<endl; }

我们将每探测一步看作为探测迷宫地图上的一个坐标，故需要创建一个位置结点类，代码如下：

struct Pos //定义位置结点 { size_t _row; //行 size_t _col; //列 };

在探测时，我们需要确定该位置结点是否是合格的，即需要判断坐标的合理性，代码如下：

bool CheckAccess(int maze[][N], size_t N, Pos pos) //判断坐标的位置是否合理 { if(((pos._row>=0) && (pos._row<N)) && ((pos._col>=0) && (pos._col<N)) && (maze[pos._row][pos._col] == 0)) { return true; } return false; }

然后，我们利用探测法、回溯法寻找迷宫的通路，代码如下：

bool GetMazePath(int maze[][N], size_t N, Pos entry) { stack<Pos> path; path.push(entry); while(!path.empty()) { Pos cur = path.top(); //当前所在迷宫的位置 maze[cur._row][cur._col] = 2; //将已走过的位置赋值为2 if(cur._row == N-1) //找到出口 方法: 1.出口给定迷宫地图的一个位置 2.出口给定迷宫地图的一行/列 { return true; } Pos next = cur; //探测该点的上方 next = cur; next._row--; if(CheckAccess(maze, N, next)) { path.push(next); continue; } //探测该点的右方 next = cur; next._col++; if(CheckAccess(maze, N, next)) { path.push(next); continue; } //探测该点的下方 next = cur; next._row++; if(CheckAccess(maze, N, next)) { path.push(next); continue; } //探测该点的左方 next = cur; next._col--; if(CheckAccess(maze, N, next)) { path.push(next); continue; } Pos top = path.top(); maze[top._row][top._col] = 3; //将回溯过的坐标记为3 path.pop(); } return false; }

这样就可以编写出一份简易迷宫代码，测试用例如下：

void TestMaze() { int maze[N][N]; InitMaze(maze, N); PrintMaze(maze, N); Pos entry; entry._row = 2; entry._col = 0; GetMazePath(maze, N, entry); PrintMaze(maze, N); }

我们打印迷宫地图时，采用了文件的方式，如果有志同道合的人看到了这篇文章，想要动手操作一下的话，需要编写一份文本文件Maze.txt，并将它加载到项目的文件夹中，下图是样例。