c - DFS算法迷宫生成器

Question

我正在尝试使用 DFS 算法创建一个 ASCII 迷宫(“#”代表一堵墙，“”代表自由空间)，该迷宫从左上角开始，从右下角退出。问题是迷宫开始创建，然后被阻塞，因为它的所有邻居都已被访问过。

我从左上角开始，将单元格标记为已访问并放置一个“”(它代表一个空闲空间)，然后我随机选择该单元格的一个邻居，然后执行相同的操作。不过，我将其放入 while 循环中，我确信这不是一个好主意。

这是我对 DFS 的尝试:

int     generation(t_maze *maze, int pos_y, int pos_x)                                                                                                                                                              
{                                                                                                                                                                                                                   
  int   dest;                                                                                                                                                                                                       

  maze->maze[pos_y][pos_x] = ' ';                                                                                                                                                                                   
  maze->visited[pos_y][pos_x] = '1';                                                                                                                                                                                
  while (maze->maze[maze->height - 1][maze->width - 1] == '#')                                                                                                                                                      
    {                                                                                                                                                                                                               
      if ((dest = my_rand(1, 4)) == 1 && pos_y - 1 >= 0 && maze->visited[pos_y - 1][pos_x] == '0')                                                                                                                  
        generation(maze, pos_y - 1, pos_x);                                                                                                                                                                         
      else if (dest == 2 && pos_x + 1 < maze->width && maze->visited[pos_y][pos_x + 1] == '0')                                                                                                                      
        generation(maze, pos_y, pos_x + 1);                                                                                                                                                                         
      else if (dest == 3 && pos_y + 1 < maze->height && maze->visited[pos_y + 1][pos_x] == '0')                                                                                                                     
        generation(maze, pos_y + 1, pos_x);                                                                                                                                                                         
      else if (dest == 4 && pos_x - 1 >= 0 && maze->visited[pos_y][pos_x - 1] == '0')                                                                                                                               
        generation(maze, pos_y, pos_x - 1);                                                                                                                                                                         
      my_showtab(maze->maze); //it prints the 2d array                                                                                                                                                                                      
      usleep(50000);                                                                                                                                                                                                
    }  


typedef struct  s_maze                                                                                                                                                                                              
{                                                                                                                                                                                                                   
  int           width;                                                                                                                                                                                              
  int           height;                                                                                                                                                                                             
  char          **maze;                                                                                                                                                                                             
  char          **visited;                                                                                                                                                                                          
}               t_maze; 

在结构中，width 是迷宫的宽度height 是迷宫的高度maze 是一个二维数组，应该用 ' ' 和 '#' 填充visited 是一个包含 0 和 1 的二维数组，0:未访问，1:已访问

我想要一个像这样的迷宫(小例子)

 ########
      # #
 ##     #
 #  #
#######  

Answer 1

您的代码会构建一条路径，因为它始终只到达下一个单元格。那不是dfs。你可以这样做:

def dfs(x, y):
    visited[x][y] = true
    maze[x][y] = ' '
    next_cell = random unvisited neighbors of (x, y):
    dfs(next_cell.x, next_cell.y)

重点是:你需要在某个时刻回溯(使用递归很方便)。单一路径不会像您想要的那样(它也可能被卡住并且永远无法到达导出)。