c++ - C++递归深度优先搜索迷宫算法以及现在要去哪里？

我一直在尝试使用递归深度优先搜索样式算法来计算迷宫生成器。我知道过去已经做过很多次了，但是根据我自己的理解，我一直在尝试自己重新实现它，以便更好地理解它。

因此，这是我到目前为止的尝试。

#include <iostream>
#include <vector>
#include <algorithm>
#include <unistd.h>

struct vertex {
    int x;
    int y;
};

int main(int argc, char **argv)
{
    // Init the map
    int map_size = 24;
    int half_point = map_size / 2;

    int map[map_size+1][map_size+1];

    for(int y = 0; y < map_size+1; y++) {
        for(int x = 0; x < map_size+1; x++) {
            map[x][y] = 0;
        }
    }

    vertex start;
    start.x = half_point;
    start.y = half_point;

    std::vector<vertex> history;

    // Set start point as visited
    history.push_back(start);
    while( !history.empty() ) {

        vertex v = history.back();

        map[v.x][v.y] = 1;

        // Calculate the directions for each vertex
        vertex N;        N.x = v.x+1;        N.y = v.y;
        vertex S;        S.x = v.x-1;        S.y = v.y;
        vertex E;     E.x = v.x;       E.y = v.y-1;
        vertex W;    W.x = v.x;     W.y = v.y + 1;

        bool can_north = false;  bool can_south = false;  bool can_east = false;   bool can_west = false;

        // Check north and add if relevant
        if( N.x >= 0 && N.x <= map_size && N.y >= 0 && N.y <= map_size && map[N.x][N.y] == 0 ) {  can_north = true; }
        // Check south and add if relevant
        if( S.x >= 0 && S.x <= map_size && S.y >= 0 && S.y <= map_size && map[S.x][S.y] == 0 ) {   can_south = true;   }
        // Check east and add if relevant
        if( E.x >= 0 && E.x <= map_size && E.y >= 0 && E.y <= map_size && map[E.x][E.y] == 0 ) {  can_east = true;  }
        // Check west and add if relevant
        if( W.x >= 0 && W.x <= map_size && W.y >= 0 && W.y <= map_size && map[W.x][W.y] == 0 ) {  can_west = true;  }

        std::vector<vertex> available;
        if(can_north) { available.push_back(N); }
        if(can_south) { available.push_back(S); }
        if(can_east) { available.push_back(E); }
        if(can_west) { available.push_back(W); }

        // Select random element from availables
        if( !available.empty() )
        {
            std::random_shuffle( available.begin(), available.end() );
            vertex aV = available.back();

            history.push_back(aV);

            available.clear();
        } else {
            if( !history.empty() ) {
                history.pop_back();
            }
        }

        // Animate the output to the console
        system("clear");
        for(int y = 0; y < map_size+1; y++) {
            for(int x = 0; x < map_size+1; x++) {
                std::cout << map[x][y] << ", ";
            }
            std::cout << std::endl;
        }
        std::cout << std::endl;

        usleep(5000);
    }

    return 0;
}

每次在显示更新以显示其经过的路径的基本动画之前，都在其中使用Linux系统调用来清除终端。

我不知道，我想了解的是...
1)这实际上是递归的深度优先搜索算法吗？

如果是这样，那么至少我已经正确地理解了这个概念。

2)我将如何将其绘制到图像文件？

最佳答案

我会回答你的第一个问题



在递归深度优先搜索算法中，每个像元具有三个状态中的一个(未访问，正在访问和已访问)。想法是遍历图并访问每个节点。如果节点处于“未访问”状态，它将变为“正在访问”，并且将访问每个邻居。在访问了每个邻居之后，该节点变为“已访问”。为此，您必须记住一次访问过的迷宫中的每个单元，而再也不会遍历它。 history完全填充条件“Visit In Progress”中的每个成员，以及map完全填充条件“Visited”中设置的每个单元。我的答案是:是。

评论您的第二个问题:



要绘制图像，我建议您使用CImg库。查看更多问题The easiest way to draw an image?

如果要绘制遍历的路径，则需要第二个堆栈或类似的容器，在其中记录已完成的所有步骤。也许您可以为每一步绘制从一个栅格到另一个栅格的栅格和箭头。如果您从北向南绘制箭头，然后从右向南移动，而从东向西向下的箭头从西向东移动，您将不会有任何重叠。

关于c++ - C++递归深度优先搜索迷宫算法以及现在要去哪里？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34543266/