我試圖使用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:訪問
我希望有這樣的(小示例)的迷宮
########
# #
## #
# #
#######
這是不是真的清楚你的要求。你讀過https://en.wikipedia.org/wiki/Maze_generation_algorithm嗎? –
我建議,而不是先從開放的空間,然後反覆用細分壁(和門口)那個空間,直到您的空隙具有一種或另一種尺寸爲1 –
是我做到了,我想用遞歸DFS的backtracker點在維基百科頁面創建一個迷宮。 – Beben