迷宫问题详解（数据结构实验）

Az1r 2023-03-28 原文

简介

实验项目 2：栈结构及其应用
实验题目：迷宫问题求解
实验内容：
一个迷宫可以看成是由 m × n 个房间组成的矩形，迷宫内部的每个房间有 4个方向，每个方向或者有障碍（如墙）而不能通过，或者无障碍而能通过。入口为左上角房间，出口为右下角房间，问是否有简单路径从入口到出口，若有则输出一条这样的路径；否则，提示迷宫无入口到出口路经。
实验要求：
1. 设计一个迷宫及其障碍的表示方式，并能随机或手动生成迷宫，并以适当方式展示。
2. 设计并实现一个非递归的算法，输出从入口到出口的一条路径（如存在）。
3. 设计并实现一个递归的算法，找出从入口到出口的一条路径（如存在）。
4. 选做：如果有多条路径，设计并实现一个算法找到步数最少的路径（捷径）。
5. 选做：如果有多条路径，设计并实现一个算法找到所有路径。
6. 以适当的方式展示迷宫和所走路径

作业内容三选一，感觉迷宫还行，可以做做，发现迷宫的恰当表示和随机生成有学问啊

迷宫生成

迷宫生成是将迷宫全部初始化为墙，然后打通墙，制造迷宫的过程

基本知识

迷宫生成主要有四种方法

递归回溯算法
- 深度优先搜索，递归地打通未打通的区域
- 思想简单，但生成的迷宫通路十分明显
递归分割算法
- 又名十字递归算法，递归地将地图分为四个房间，然后联通四个房间
- 生成的迷宫就是像一个一个房间，适合RPG游戏
随机Prim算法
- 最小生成树算法，从已有的通路开始每次随机地选择一个方向打通迷宫
- 通路不明显，适合迷宫游戏
Kruskal算法
- 最小生成树算法，利用并查集随机地选择墙打通

这篇博客有动图可以帮助理解迷宫生成

Prim算法

这里使用Prim算法

初始化迷宫全为墙。
选一个是迷宫通路的格子，然后随机选择它的邻墙。一般一开始的时候是起点（左上角）。
随机选择墙时:
如果它联通的格子不是迷宫的通路:
1. 把墙打通。
2. 自然那个格子变成了迷宫的通路.。
如果它联通的格子已经是通路了，选择其他格子去考虑邻墙。

这里的随机使一般的最小生成树Prim算法有所区别，该如何随机选择墙打通呢？

随机化种子

void srand(unsigned int seed) 播种由函数 rand 使用的随机数发生器。

int rand(void) 返回一个范围在 0 到 RAND_MAX 之间的伪随机数。

使用时间作为种子

srand(time(NULL));

srand ((int) time ((time_t *) NULL));

迷宫表示

设迷宫宽为width，高为height

表示迷宫一般是使用 $width * height$ 大小的矩阵来表示，一个单元表示迷宫的通路与否。

如 11 * 4

.*****...**
..**...*.*.
*.*..*.*.*.
*....***...

.表示通路

*或者#表示障碍

但是为了更好的表示迷宫，表示迷宫与通路的关系，方便我们观看

使用墙 + 单元的方式来表示迷宫

则还需一圈外围围住迷宫的围墙

四方向

可以上下左右的走

总共需要 $(2*width + 1)*(2*height + 1)$ 大小的内存来表示

如 4 * 2

+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

空格为一个迷宫单元，其他为墙

八方向

可以上下左右，且对角线的走

这样可以表示单元的上下左右与对角线的通路情况，~~虽然丑~~

很明显，一个九宫格，周围八个都是墙，中间是迷宫的单元

总共需要$(3 * height) * (3 * width)$ 大小的内存
如3 * 3

/=\/=\/=\
| || || |
\=/\=/\=/
/=\/=\/=\
| || || |
\=/\=/\=/
/=\/=\/=\
| || || |
\=/\=/\=/

迷宫解法

主要有三种解法

深度优先搜索 DFS
广度优先搜索 BFS
启发式算法 A*

这里使用的深度优先搜索 ( DFS )

一条路走到黑，走不动就返回，直到走到终点

DFS就不作过多陈述

代码及运行结果

迷宫数据类型定义

采用结构体，中有6/10个变量
4/8个方向，上下左右，（左上左下右上右下），表示该单元墙的打通情况
Visited变量，在DFS记录是否走过
Path变量，在DFS中记录是否为解法通路

四方向

+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         |     |       |     |   |         |     |   |     |               | |
+ +-+-+-+ + +-+ + +-+-+ + +-+ + +-+ +-+-+ + + +-+ + + + + +-+ +-+-+-+-+-+-+ + +
|   |   |   | |   |   |   |     |   |     | |   | | |   |     |   |       | | |
+-+ + + + +-+ + +-+-+ +-+-+-+-+-+ + + +-+-+ +-+ +-+ +-+ +-+-+-+ + + +-+-+-+ + +
|   | | |   | |   |   |   |   |   | |     | |   |   |   |     | |   |     |   |
+ +-+ + +-+ + + + + +-+ + + + + +-+-+-+-+ +-+ + + +-+ +-+ +-+ +-+ + + +-+ +-+-+
|     | |     | | |   | |   | |     |     |   | | | |     |   |   | | |   |   |
+ +-+-+ +-+-+-+ +-+ + + +-+-+-+ +-+ + +-+-+ +-+-+ + + + +-+-+ + +-+ + + +-+ + +
|     |       | |   | |         | | |       |     | | |     |   |   | |   | | |
+-+-+-+-+-+-+ + + +-+-+ +-+-+-+-+ + + +-+-+-+ +-+-+ + +-+-+ +-+-+-+-+ +-+ + + +
|             |   |     |   |     | |       | |   | |     |         | | |   | |
+ +-+-+-+-+-+ +-+-+ +-+-+ + +-+-+ + + +-+-+ + + + + +-+-+ +-+-+-+-+ + + + +-+ +
|     |     |     |       | |   |   |     |   | |   | |       | |   | |   | | |
+-+-+ + +-+-+-+-+ +-+-+ +-+ + + +-+-+-+-+-+-+-+ +-+-+ + +-+-+ + + +-+ + +-+ + +
|   | |     |   |     | |   | |           |     |   |   |   | | |     | |     |
+-+ + + + + + + +-+-+ +-+ +-+ +-+-+ +-+-+ + +-+-+ + +-+-+-+ + + +-+-+-+ + +-+-+
|   | | | |   | |   |   |   |     | |   | |       | |       |   |       | |   |
+ +-+ + +-+-+-+ + + +-+ +-+ +-+-+ + +-+ + +-+-+-+ + +-+ +-+-+-+-+ +-+-+-+ +-+ +
|     |     |   | |   |   |   |   |   | |     |   |     |     | | |     |   | |
+-+-+-+ +-+ +-+-+ + +-+ + +-+ + +-+-+ + +-+-+ + +-+-+-+-+ + + + + + + +-+-+ + +
|         |       |     |       |           |             | |   |   |     |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +

+.+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|.        |     |       |     |   |.......  |     |...|     |               | |
+.+-+-+-+ + +-+ + +-+-+ + +-+ + +-+.+-+-+.+ + +-+ +.+.+ + +-+ +-+-+-+-+-+-+ + +
|...|...|   | |   |   |   |     |...|.....| |   | |.|...|     |   |       | | |
+-+.+.+.+ +-+ + +-+-+ +-+-+-+-+-+.+ +.+-+-+ +-+ +-+.+-+.+-+-+-+ + + +-+-+-+ + +
|...|.|.|   | |   |   |   |   |...| |.....| |   |...|...|     | |   |.....|   |
+.+-+.+.+-+ + + + + +-+ + + + +.+-+-+-+-+.+-+ + +.+-+.+-+ +-+ +-+ + +.+-+.+-+-+
|.....|.|     | | |   | |   | |.    |.....|   | |.| |...  |   |   | |.|...|...|
+ +-+-+.+-+-+-+ +-+ + + +-+-+-+.+-+ +.+-+-+ +-+-+.+ + +.+-+-+ + +-+ +.+.+-+.+.+
|     |.......| |   | |.........| | |.      |.....| | |.....|   |   |.|...|.|.|
+-+-+-+-+-+-+.+ + +-+-+.+-+-+-+-+ + +.+-+-+-+.+-+-+ + +-+-+.+-+-+-+-+.+-+.+.+.+
|            .|   |.....|...|     | |.......|.|   | |     |.........|.| |...|.|
+ +-+-+-+-+-+.+-+-+.+-+-+.+.+-+-+ + + +-+-+.+.+ + + +-+-+ +-+-+-+-+.+.+ + +-+.+
|     |     |.....|.......|.|   |   |     |...| |   | |       | |...|.|   | |.|
+-+-+ + +-+-+-+-+.+-+-+ +-+.+ + +-+-+-+-+-+-+-+ +-+-+ + +-+-+ + +.+-+.+ +-+ +.+
|   | |     |   |.....| |...| |           |     |   |   |   | | |.....| |.....|
+-+ + + + + + + +-+-+.+-+.+-+ +-+-+ +-+-+ + +-+-+ + +-+-+-+ + + +-+-+-+ +.+-+-+
|   | | | |   | |   |...|...|     | |   | |       | |       |   |       |.|   |
+ +-+ + +-+-+-+ + + +-+.+-+.+-+-+ + +-+ + +-+-+-+ + +-+ +-+-+-+-+ +-+-+-+.+-+ +
|     |     |   | |   |...|...|   |   | |     |   |     |     | | |     |...| |
+-+-+-+ +-+ +-+-+ + +-+ +.+-+.+ +-+-+ + +-+-+ + +-+-+-+-+ + + + + + + +-+-+.+ +
|         |       |     |.....  |           |             | |   |   |     |...|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+.+

点击查看代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define WIDTH 39 
#define HEIGHT 11

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#ifdef TRUE
#undef TRUE
#endif /* TRUE */

#define TRUE 1

#define cell_empty(a) (!(a)->up && !(a)->right && !(a)->down && !(a)->left)

typedef struct {
    unsigned int up      : 1;//占一位 
    unsigned int right   : 1;
    unsigned int down    : 1;
    unsigned int left    : 1;
    unsigned int path    : 1;
    unsigned int visited : 1;
}cell;
typedef cell * maze_p;

void CreateMaze (maze_p maze, int width, int height);
void SolveMaze (maze_p maze, int width, int height);
void PrintMaze (maze_p maze, int width, int height);
int SolveMazeRec (maze_p maze, maze_p mp, int width, int height);

int main (int argc, char *argv [])
{
    int width = WIDTH;
    int height = HEIGHT;
    maze_p maze;

    if (argc >= 2)
        width = atoi (argv [1]);//atoi函数， 将一个字符串转化为整数 

    if (argc >= 3)
        height = atoi (argv [2]);

    if (argc >= 4)
        srand (atoi (argv [3]));//随机种子 
    else
        srand ((int) time ((time_t *) NULL));// 用系统时初始化随机种子 

    if (width <= 0 || height <= 0) 
	{
        (void) fprintf (stderr, "Illegal width or height value!\n");//错误输出流 
        exit (EXIT_FAILURE);
    }
    maze = (maze_p) calloc (width * height, sizeof (cell));//申请迷宫大小 
    if (maze == NULL) //申请失败 
	{
        (void) fprintf (stderr, "Cannot allocate memory!\n");//错误输出流 
        exit (EXIT_FAILURE);//宏定义的常量，是1；EXIT_SUCCESS 0  
    }
    CreateMaze (maze, width, height);//随机生成迷宫 

    PrintMaze (maze, width, height);//打印迷宫 

   	(void) puts("\n\nThe solve of maze:\n");
	
    //SolveMaze (maze, width, height);//解决迷宫 
	SolveMazeRec (maze, maze, width, height);
	
	
    PrintMaze (maze, width, height);//打印迷宫 
	
    free (maze);//释放 
    exit (EXIT_SUCCESS);

    return (0);

}/* main */


void CreateMaze (maze_p maze, int width, int height)
{
    maze_p mp, maze_pop;
    char paths [4];
    int visits, directions;

    visits = width * height - 1;//去掉 
    mp = maze;
    maze_pop = mp + (width * height) - 1;//右下角终点 

    while (visits) 
	{
        directions = 0;
			
		// 指针比大小，其实就是地址的比较 
        if ((mp - width) >= maze && cell_empty (mp - width))
            paths [directions ++] = UP;
        if (mp < maze_pop && ((mp - maze + 1) % width) && cell_empty (mp + 1))//判断是不是最右 
            paths [directions ++] = RIGHT;
        if ((mp + width) <= maze_pop && cell_empty (mp + width))
            paths [directions ++] = DOWN;
        if (mp > maze && ((mp - maze) % width) && cell_empty (mp - 1)) //判断是不是最左 
            paths [directions ++] = LEFT;

		//在mp可选择的路中随机一个 
        if (directions) 
		{
            visits--;
            directions = ((unsigned) rand () % directions);

            switch (paths [directions]) 
			{
                case UP:
                    mp->up = TRUE;//标记这个cell向上走 
                    (mp -= width)->down = TRUE;//相反，走过去的cell标记为向下走 
                    break;
                case RIGHT:
                    mp->right = TRUE;
                    (++mp)->left = TRUE;
                    break;
                case DOWN:
                    mp->down = TRUE;
                    (mp += width)->up = TRUE;
                    break;
                case LEFT:
                    mp->left = TRUE;
                    (--mp)->right = TRUE;
                    break;
                default:
                    break;
            }
        } else //没有可走的cell 
		{
            do 
			{
                if (++mp > maze_pop)//超过了就回到起点 
                    mp = maze;
            } while (cell_empty (mp)); // 找到一个已被打通的cell 
        }
    }
}/* CreateMaze */

int SolveMazeRec (maze_p maze, maze_p mp, int width, int height)
{
	mp->visited = TRUE;
	if(mp == (maze + (width * height) - 1))
	{
		mp->path = TRUE;
		return 0;
	}

	
	for(int sel = UP; sel <= LEFT; sel ++ )
	{
		switch(sel)
		{
			case UP:
				if (mp->up && !(mp - width)->visited)
				{
					if( ! SolveMazeRec (maze, mp - width, width, height) )
					{
						mp->path = TRUE;
						return 0;
					}
				}
				break;
			case RIGHT:
				if (mp->right && !(mp + 1)->visited)
				{
					if( ! SolveMazeRec (maze, mp + 1, width, height) )
					{
						mp->path = TRUE;
						return 0;
					}
				}
				break;
			case DOWN:
				if (mp->down && !(mp + width)->visited)
				{
					if( ! SolveMazeRec (maze, mp + width, width, height) )
					{
						mp->path = TRUE;
						return 0;
					}
				}
				break;
			case LEFT:
				if (mp->left && !(mp - 1)->visited)
				{
					if( ! SolveMazeRec (maze, mp - 1, width, height) )
					{
						mp->path = TRUE;
						return 0;
					}
				}
				break;
			default:
				break;
		}
	}
	return 1;
}


void SolveMaze (maze_p maze, int width, int height)
{
    maze_p *stack, mp = maze;
    int sp = 0;

    stack = (maze_p *) calloc (width * height, sizeof (maze_p));
    if (stack == NULL) 
	{
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);
    }
	// 起点已访问  
    (stack [sp++] = mp)->visited = TRUE;

    while (mp != (maze + (width * height) - 1)) //没到终点 
	{

        if (mp->up && !(mp - width)->visited)//可走上，上没去过 
            stack [sp++] = mp - width;
        if (mp->right && !(mp + 1)->visited)
            stack [sp++] = mp + 1;
        if (mp->down && !(mp + width)->visited)
            stack [sp++] = mp + width;
        if (mp->left && !(mp - 1)->visited)
            stack [sp++] = mp - 1;

        if (stack [sp - 1] == mp)
            --sp;//如果走到头了，那就回去一步 

        (mp = stack [sp - 1])->visited = TRUE;//两步 
    }
    while (sp--)//遍历一遍，标记为路径 
        if (stack [sp]->visited)
            stack [sp]->path = TRUE;

    free (stack);

}/* SolveMaze */


void PrintMaze (maze_p maze, int width, int height)
{
    int w, h;
    char *line, *lp;

    line = (char *) calloc ((width + 1) * 2, sizeof (char));
    if (line == NULL) 
	{
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);
    }
    maze->up = TRUE;
    (maze + (width * height) - 1)->down = TRUE;
    
	// 第一行 
    for (lp = line, w = 0; w < width; w++) 
	{
        *lp++ = '+';
        if ((maze + w)->up)		//如果为出迷宫路径，则为 . ，否则为 空		 
            *lp++ = ((maze + w)->path) ? '.' : ' ';
        else
            *lp++ = '-';
    }
    //一行 长 2*width + 1 
    *lp++ = '+';
    (void) puts (line);
    
    //system("pause");
    for (h = 0; h < height; h++)// 
	{
        for (lp = line, w = 0; w < width; w++) 
		{
            if ((maze + w)->left)
                *lp++ = ((maze + w)->path && (maze + w - 1)->path) ? '.' : ' ';
            else
                *lp++ = '|';//墙 
            *lp++ = ((maze + w)->path) ? '.' : ' ';
        }
        *lp++ = '|';
        (void) puts (line);
        for (lp = line, w = 0; w < width; w++) 
		{
            *lp++ = '+';
            if ((maze + w)->down)
                *lp++ = ((maze + w)->path && (h == height - 1 ||
                         (maze + w + width)->path)) ? '.' : ' ';
            else

                *lp++ = '-';
        }
        *lp++ = '+';
        (void) puts (line);
        maze += width;
    }
    free (line);

}/* PrintMaze */

八方向

/ \/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\
|    ||    || || ||    || || || |
\=/ =/\ /\= \=/\=/ =/\ /  /\=/\ /
/= /=\/ \/=\ =\/= /=\/  / \/=\/ \
|    ||    ||    || || ||    || |
\  \ /\=/\  \=/\=/\=/\=/\=/\ /\ /
/ \  \/=\/ \ =\/=\/=\/=\/=\/ \/ \
| || || || || || || ||    ||    |
\= \=/  / =/\=/\  \=/ =/\=  = \=/
/=\ = /  /=\/=\/ \ = /=\/=  =\ =\
| || || ||    || ||       || || |
\=  = \=  =/\ /\  \= \=/\=/\= \ /
/=  =\ =  =\/ \/ \ =\ =\/=\/=\  \
|    || || ||    || || || || || |
\=/\=/\=/\=/\=/\=/\=/\=/\=/\=/\ /

/.\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\
|....||....|| || ||....||.|| || |
\=/.=/\./\=.\=/\=/.=/\./../\=/\ /
/=./=\/.\/=\.=\/=./=\/../.\/=\/ \
|.   ||....||....|| ||.||....|| |
\. \ /\=/\. \=/\=/\=/\=/\=/\./\ /
/.\  \/=\/.\ =\/=\/=\/=\/=\/.\/ \
|.|| ||.||.|| || || ||....||.   |
\=.\=/../.=/\=/\  \=/.=/\=..= \=/
/=\.=./../=\/=\/ \ =./=\/=..=\ =\
| ||.||.||    || ||.......||.|| |
\=  = \=  =/\ /\  \= \=/\=/\=.\ /
/=  =\ =  =\/ \/ \ =\ =\/=\/=\. \
|    || || ||    || || || || ||.|
\=/\=/\=/\=/\=/\=/\=/\=/\=/\=/\./