DFS算法迷宫生成器-Java 学习之路

我正在尝试使用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;

在结构中，宽度是迷宫高度的宽度是迷宫迷宫的高度是一个二维数组，应该填充''和'＃'访问是一个2D数组，0和1,0：未访问， 1：参观了

我想要一个这样的迷宫（小例子）

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

1 回答

0
您的代码构建一条路径，因为它始终只到达下一个单元格 . 这不是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)
```
关键是：你需要在某个时候回溯（为它使用递归很方便） . 单个路径看起来不像您想要的那样（它也可能卡住并且永远不会到达出口） .
回复于 2024-04-29T20:49:19+08:00

DFS算法迷宫生成器

1 回答

相关问题