2017-04-13 208 views
0

我试图使用DFS算法中创造ASCII迷宫(“#”代表墙壁和'自由空间),有作为启动左上角和退出右下角。问题是迷宫开始创建,然后被阻塞,因为所有的邻居已经被访问过。DFS算法迷宫生成

我在左上角的开始,标志着对小区的访问,把一个“”(它代表了一种自由空间),那么我选择了随机小区的邻居和我做同样的。不过,我把它放在一个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阵列将被填充与 '' 和 '访问#' 是2D阵列具有0和1,0:未访问的,1:访问

我希望有这样的(小示例)的迷宫

######## 
     # # 
##  # 
# # 
####### 
+0

这是不是真的清楚你的要求。你读过https://en.wikipedia.org/wiki/Maze_generation_algorithm吗? –

+0

我建议,而不是先从开放的空间,然后反复用细分壁(和门口)那个空间,直到您的空隙具有一种或另一种尺寸为1 –

+0

是我做到了,我想用递归DFS的backtracker点在维基百科页面创建一个迷宫。 – Beben

回答

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) 

的一点是:你需要在某一时刻回溯(这是方便使用递归的话)。一条路径看起来并不像你想要的那样(它也可能卡住,永远不会到达出口)。

+0

我看到,我的while循环阻止了我的程序。谢谢 – Beben