DFS算法迷宮生成

我試圖使用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：訪問

我希望有這樣的（小示例）的迷宮

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

來源

2017-04-13 Beben

這是不是真的清楚你的要求。你讀過https://en.wikipedia.org/wiki/Maze_generation_algorithm嗎？ –

我建議，而不是先從開放的空間，然後反覆用細分壁（和門口）那個空間，直到您的空隙具有一種或另一種尺寸爲1 –

是我做到了，我想用遞歸DFS的backtracker點在維基百科頁面創建一個迷宮。 – Beben

你的代碼生成一個路徑，因爲它總是去只有一個單元格。這不是一個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)

的一點是：你需要在某一時刻回溯（這是方便使用遞歸的話）。一條路徑看起來並不像你想要的那樣（它也可能卡住，永遠不會到達出口）。

來源

2017-04-13 16:11:49 kraskevich

我看到，我的while循環阻止了我的程序。謝謝 – Beben

DFS算法迷宮生成

回答

相關問題