如何确保迷宫始终具有有效路径 C++

Question

我正在做我正在阅读的一本书中的练习题，该问题要求动态生成具有给定高度和宽度的迷宫。这个迷宫也必须始终有一条有效路径。这是我遇到问题的部分，我无法弄清楚如何确保始终存在有效路径。这是我的代码，它生成一个迷宫，例如 10x10、20x20、30x30 等。但有时没有有效路径。我试着尽可能多地发表评论，以使其更具可读性，因为它有点乱。感谢您的任何帮助，您可以提供。

#include<iostream>
#include<cstdlib>
#include<ctime>

int main()
{
int row, height; //declaring row and height int variables.
srand(time(NULL)); //seed for different random number;

std::cout<<"Enter row number: "; //prompts user for row number.
std::cin>>row;
std::cout<<"Enter height number: "; //prompts user for height number;
std::cin>>height;

char **maze; //declaring a pointer to a pointer named maze of type char.
maze=new char*[row]; //pointer points to a array of pointers.

for (int i=0;i<row;++i) //assigning an array to each pointer
{
    maze[i]=new char[row];
}

for (int i=1;i<row;++i) //creating random generation of maze * equal walls/borders.
{
    for (int j=1;j<height;++j)
    {
        int a=rand()%5+1; //if the random number divided by 2 does have a remainder than we place a blank space.
        if (a%2!=0)
        maze[i][j]=0;

        else    //otherwise we place a *, 42 is the ASCII code for *.
        maze[i][j]=42;
    }
}

//the code below creates the borders of the maze and guarantees that there is a exist and entrance to the maze.
//(Entrance is at the top, exit is at the bottom of the maze.
maze[0][0]=42;
maze[0][1]=0;

for (int i=2;i<=row;++i)
{
    maze[0][i]=42;
}

for (int i=1;i<height;++i)
{
    maze[i][0]=42;
}

for (int i=0;i<row;++i)
{
    maze[row-1][i]=42;
}

for (int i=0;i<height;++i)
{
    maze[i][height-1]=42;
}
maze[row-1][height-2]=0;

//This code prints the maze.
for (int i=0;i<row;++i)
{
    for (int j=0;j<height;++j)
    {
        std::cout<<maze[i][j];

    }
    std::cout<<"\n";
}

//deleting the maze freeing it from the heap.
for (int i=0;i<row;++i)
delete[] maze[i];

delete[] maze;


}

Answer 1

如果您正在寻找编码解决方案，那么此答案不适合您。但是，这里有一些方法可以完成任务。

假设：

This maze must always have a valid path as well.

这并不排除迷宫有不止一种解决方案。

选项 A - 简单暴力

生成随机迷宫
测试迷宫寻找解决方案
如果没有解决方案从#1重新开始

选项 B - 首先创建解决方案

创建起始位置
创建结束位置
创建一个从头到尾的随机解路径
随机填充迷宫的其余部分，不修改任何已填充的位置
- 例如：用标记值初始化整个网格（例如，'#' 表示尚未填充），这些将在创建解决方案时被适当的值覆盖, 最后当迷宫被随机填充时只有这些值可能被覆盖

Answer 2

确保路径存在的最佳方法是首先将其放置在那里。虽然以前的解决方案：先创建解决方案然后使用您的算法显然可行，但它可能会创建太简单的迷宫。

而不是这个，看看已经建立的算法 generate mazes。

特别是看应用有意义Prim's and Kruskal's algorithm (at that wiki page) and think why exactly minimum spanning tree生成迷宫有意义

Answer 3

我知道我迟到了 post，但更好的方法是使用递归。

具有寻找迷宫起点和终点的功能，以供起点和终点参考。

还有另一个函数 finds_next_move 传递数组、x 和 y，可能还有行和列。 x 和 y 通过引用传递。

然后是另一个布尔函数来验证移动是否为真。所以它会尝试直行，将这些参数传递给 validate_move 函数，如果它 returns 为真则朝那个方向移动，如果为假则尝试其他方向。

在这里使用 if else 就可以了。然后在 if else 语句中相应地增加你的 x 或 y 变量。 validate_move 函数只会在 find_next_move 函数中调用。然后递归循环直到解决方案返回 true。

但如果你走入了死胡同，你将不得不原路返回。所以也只需为此添加 if 语句

您还可以添加一个打印功能，当您移动时会调用该功能，并且在您之前的位置上它会为解决方案打印一条轨迹，如果您必须原路返回，则可以删除该轨迹。

只是我想到的一些基本想法:D

如何确保迷宫始终具有有效路径 C++

How to ensure the Maze always has a valid path C++

c++

algorithm

maze

选项 A - 简单暴力

选项 B - 首先创建解决方案