By Rose Ou

更新日期:

文章目录
  1. 1. 迷宫生成
  2. 2. 迷宫求解

本文主要介绍如何通过回溯随机生成单迷宫并通过摸墙算法对生成的迷宫找到通往出口的路线。
以下的讨论只给出核心代码，完整代码可到我的Github。

迷宫生成

回溯算法： 回溯算法也叫试探法，其基本思想是，从一条路往前走，能进则进，不能进则退回来，换一条路再试。

单迷宫： 这里我所生成的迷宫是单迷宫，也就是说它是简单连通图并且没有回路（即实际上它是树结构）。这样的迷宫，里面不存在一堵独立的墙（即墙周围都是通道），也不存在一个独立被分隔开的单元（即单元周围都是墙）。

生成迷宫的步骤：

  1. 一开始所有单元周围都是墙。
  2. 随机选择一个单元作为当前起点，并将起点标记为已访问。
  3. 在这个起点的四面墙中随机选择一面墙。如果被这面墙分隔的两个单元不连通，并且与这面墙相邻的另外一个单元未曾访问过，则拆掉这面墙，并将与这面墙相邻的另外一个单元作为下一个当前起点，并将其标记为已访问。如果当前起点周围所有相邻的单元都已访问过，则回溯到上一个起点再次选择另外一面墙，重复步骤。
  4. 当回溯到最开始所选择的起点时，算法结束，迷宫生成完成。

C++语言实现：
首先，用一个二维数组存放迷宫的连通状态，即存放迷宫每个单元里连通（没有墙）的方向，并将其全部置0，表示迷宫的初始状态为所有单元相互都不连通，即所有单元周围都是墙。

1
2
3
4
5
6
7
8
9
10
11
int **grid;   //存放迷宫连通状态
grid=new int *[WIDTH];
for(int i=0;i<WIDTH;i++){
	grid[i]=new int[HEIGHT];
}

for(int i=0;i<WIDTH;i++){     //全部置0
	for(int j=0;j<HEIGHT;j++){
		grid[i][j]=0;
	}
}

而四个方向我们可以用一个枚举类型表示。

1
enum {N=1,E=4,S=2,W=8};

之所以用N=1,E=4,S=2,W=8表示而不是简单地用N=1,E=2,S=3,W=4表示，是因为迷宫中的单元很有可能会有2个方向是连通的，那样存放连通状态的grid在该单元中就要存放2个方向，而1、2、4、8在二进制表示中分别为0001、0010、0100、1000，1不重复出现在相同的位上，只要将两个方向进行“或”操作，就可以同时存储起来。

然后，随机选择一个单元作为当前起点。

1
2
3
srand((int)time(0));   //生成随机数种子
sx=rand() % WIDTH;     //随机选择起点(sx,sy)
sy=rand() % HEIGHT;

接下来，在这个起点的四面墙中随机选择一面墙，即从四个方向中随机选择一个方向。通过回溯生成迷宫时，一个单元可能会多次随机选择方向，并且不会重复选择，而在每个单元中最多只会随机选择4次墙，所以我们可以用一个数组directions[4]来存放选择方向的顺序，并且对于每个单元都重置方向顺序，从而达到随机选择方向而又不重复选择。

1
2
3
4
5
6
7
8
9
int reset_directions(int *directions, int size) {
	for(int i=0; i<(size - 1); i++) {
		int r = i + (rand() % (size - i));
		int temp = directions[i];
		directions[i] = directions[r];
		directions[r] = temp;
	}
	return 0;
}

接着就是拆墙前进、不断重复步骤和回溯。重复和回溯可通过递归实现，拆墙的过程实际上就是将墙相对于单元的方向设置为连通，用数组grid存放作为单元的连通的方向。朝不同方向前进会造成不同的坐标变化，可以用一个数组DX[9]和一个数组DY[9]来存放不同方向的坐标变化（之所以数组大小为9是因为W=8），而后前进到下一个要走单元时，由于下一个要走的单元的连通方向与当前单元的连通方向是相反的，我们可以用一个数组OPPOSITE[9]来存放每个方向的相反方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
OPPOSITE[N] = S;    //反方向
OPPOSITE[E] = W;
OPPOSITE[S] = N;
OPPOSITE[W] = E;

DX[N] = 0;
DX[E] = 1;
DX[S] = 0;
DX[W] = -1;

DY[N] = -1;
DY[E] = 0;
DY[S] = 1;
DY[W] = 0;

拆墙前进、不断重复步骤和回溯的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int destroy_wall(int cx, int cy, int **grid) {

    int nx, ny;
    int directions[4] = {N, E, S, W};

    reset_directions(directions, 4); //重置方向顺序

    for(i = 0; i < 4; i++) {
        nx = cx + DX[directions[i]];  //下一个要走单元（即当前起点与选择的墙相隔的单元）
        ny = cy + DY[directions[i]];

        if ( ((nx < WIDTH) & (nx >= 0)) & ((ny < HEIGHT) & (ny >= 0)) ) { //如果下一个单元在grid里，没有超出范围
            if (grid[nx][ny] == 0) {  //如果下一个要走的单元未被访问
                grid[cx][cy] = (int)((int)grid[cx][cy] | (int)directions[i]);  //拆墙，即存放连通的方向
                grid[nx][ny] = (int)((int)grid[nx][ny] | (int)OPPOSITE[directions[i]]); //下一个要走的单元的连通方向为当前单元的连通方向的相反方向
                destroy_wall(nx, ny, grid);  //重复步骤
            }
        }
    }
    return 0;
}

过程分析：
下面通过分析一个实际生成的迷宫的过程来说明。

首先，生成的迷宫以及其最终的连通状态grid如下：

生成迷宫的过程如下：

过程分析如下：

整个迷宫生成回溯的过程如下：

迷宫求解

摸墙算法：单迷宫是只有一种走法的迷宫。对于单迷宫而言，有一种万能的破解方法，即沿着某一面墙壁走。在走的时候，左（右）手一直摸着左（右）边的墙壁，这种方法可能费时最长，也可能会使你走遍迷宫的每一个角落和每一条死路，但你绝不会永远困在里面。
就像这样：

右手摸墙算法流程：

C++语言实现：

首先，我们可以设置righthand为右手的方向，用一个FACE[9]数组存放右手在不同方向时人所面向的方向，用一个TURNLEFT[9]数组存放右手在不同方向时转左之后的方向，用一个TURNRIGHT[9]数组存放右手在不同方向时转右之后的方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
FACE[N]=W;
FACE[E]=N;
FACE[S]=E;
FACE[W]=S;

TURNRIGHT[N]=E;
TURNRIGHT[E]=S;
TURNRIGHT[S]=W;
TURNRIGHT[W]=N;

TURNLEFT[N]=W;
TURNLEFT[E]=N;
TURNLEFT[S]=E;
TURNLEFT[W]=S;

现在我默认将左上角设为入口，右下角设为出口，并默认一开始把右手放在西边。像这样：

右手摸墙求解迷宫的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void solve_maze(int **grid,int **maze){
    int righthand=W;
    int cx=0,cy=0,nx,ny;

    maze[cx][cy]=1;  //maze用来存放迷宫求解的路径顺序
    int flag=1;
    while(1){
        if((cx == (WIDTH-1)) && (cy == (HEIGHT-1)) && (grid[cx][cy] & righthand) == 0){ //当处于右下角的单元并且右手边有墙时即到出口
            maze[cx][cy]=flag;
            flag++;       //每前进一步，flag加1，从而将路径顺序存储进maze
            break;
        }
        if((grid[cx][cy] & righthand) !=  0){  //当右侧无墙
            righthand=TURNRIGHT[righthand];   //右转90度
            maze[cx][cy]=flag;
            flag++;
            cx=cx+DX[FACE[righthand]];     //前进一步
            cy=cy+DY[FACE[righthand]];
        }else{                               //右侧有墙
            if((grid[cx][cy] & FACE[righthand]) !=  0){   //前方无墙
                maze[cx][cy]=flag;
                flag++;
                cx=cx+DX[FACE[righthand]];    //前进一步
                cy=cy+DY[FACE[righthand]];
            }else{
                righthand=TURNLEFT[righthand];   //左转90度
            }
        }
    }
}

这里要注意，并不是当人处于右下角的单元就是走到了出口，有可能人只是摸着上方的墙经过右下角的单元。

把上述例子生成的迷宫求解：

输出maze里所存放的路径顺序：

由于一个单元可能会经过两次，所以路径会叠加，这样看就比较直观了：

因为我比较胖，要霸占半条路。。

文章目录
  1. 1. 迷宫生成
  2. 2. 迷宫求解