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; 

、 幅が迷路の幅 高さが迷路 迷路の高さが充填されることになっている2次元アレイであります「で」と「＃」 が訪れたが、0と1、0と2次元配列である：未訪問、1：私はこの（少し例）のような迷路を持ちたい

を訪れ

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

Answer 1

コードは常に1つの次のセルに移動するため、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) 

ポイントは次のとおりです。あなたは、いくつかの時点でバックトラックする必要があります（それはそれのために再帰を使用すると便利です）。単一のパスは、あなたが望むように見えません（それはまた止まり、出口には到達しません）。