DFS algorithm maze generator

Question

I'm trying to use the DFS algo to create a maze in ASCII ('#' represents a wall and ' ' a free space) that has as start the upper left corner and as exit the lower right corner. The problem is the maze starts its creation and then it's blocked because all its neighbors have been already visited.

I start at the upper left corner, mark the cell as visited and put a ' ' (it represents a free space), then I chose randomly a neighbor of the cell and I do the same. However I put this in a while loop and I'm sure this isn't the good idea.

Here my attempt of the 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;

In the structure, width is the width of the maze height is the height of the maze maze is a 2D array that is supposed to be filled with ' ' and '#' visited is a 2D array with 0 and 1, 0 : unvisited, 1 : visited

I want to have a maze like this (little example)

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

It is not really clear what you are asking. Have you read en.wikipedia.org/wiki/Maze_generation_algorithm ? — Peter de Rivaz
I suggest instead starting with open space and then repeatedly subdividing that space with walls (and doorways), until the point where your open spaces have one or the other dimension as 1. — John Bollinger
yes I did, I wanted to use the DFS recursive backtracker in the wikipedia page to create a maze. — Beben
I see your technique John Bollinger but how could I know if I blocked the exit ? — Beben
If all neighbors have been already visited, you backtrack (i.e. don't do anything and just return), that's why there's "backtracker" in the name. — Bernhard Barker

kraskevich kraskevich · Accepted Answer · 2017-04-13T16:11:49

Your code builds one path as it always goes to only one next cell. That's not a dfs. You could do it like that:

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)

The point is: you need to backtrack at some point (it's convenient to use recursion for it). A single path won't look the way you want (it may also get stuck and never reach the exit).

DFS algorithm maze generator

1 Answers