Maze Generation - DFS

http://www.migapro.com/depth-first-search/

Basically, you start from a random point and keep digging paths in one of 4 directions(up, right, down, left) until you can’t go any further. Once you are stuck, you take a step back until you find an open path. You would continue digging from there. It’s just the repetition of these.

Create a 2-dimensional int array with odd row and column size. 0 represents paths(orange cell) and 1 would be walls(black cell).

Set all cells to 1(wall). There are no paths right now.

Next, let’s set the starting point. Generate odd numbers for row and col. Set that cell to 0. Use row and col variables to keep track of current location. On the picture above, it would be row = 3, col = 5. For clarity, I will be filling the current cell with red.

Now, choose a random direction(up, right, down, or left) you are moving to. You will always be moving by 2 cells. The picture above illustrates the current cell moving down. There are couple things you need to check when you move. First, you need to check if 2 cells ahead of that direction is outside of the maze. Then, you check if 2 cells ahead is a path(0) or wall(1). If it’s a wall, you can move by setting these 2 cells to 0(path). Update your current location which is row=5, col=5 at this moment.

As you keep digging as above, you notice that you get to a dead end. In this case, keep moving your current cell to previous cells until you are able to move to a new direction. This is called backtracking. Current location is at row=7, col=7, so you would be moving back to row=7, col=5 on the picture above. You can implement this logic using recursive method or stack.

So you keep digging as the picture demonstrates. For better visual, I changed the color of arrow every time it hits a dead end.

Lastly, this is the final result. With this size, it’s just natural that the maze gets too simple. The bigger the maze, the more complicated it will get.

After you choose your starting point, pass that information to the recursive method. In the recursive method, you can do the following…

1. Generate an int array with 4 random numbers to represent directions.
2. Start a for loop to go for 4 times.
3. Set up a switch statement to take care of 4 directions.
4. For that direction, check if the new cell will be out of maze or if it’s a path already open. If so, do nothing.
5. If the cell in that direction is a wall, set that cell to path and call recursive method passing the new current row and column.
6. Done.

public int[][] generateMaze() { int[][] maze = new int[height][width]; // Initialize for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) maze[i][j] = 1;   Random rand = new Random(); // r for row、c for column // Generate random r int r = rand.nextInt(height); while (r % 2 == 0) { r = rand.nextInt(height); } // Generate random c int c = rand.nextInt(width); while (c % 2 == 0) { c = rand.nextInt(width); } // Starting cell maze[r][c] = 0;   //　Allocate the maze with recursive method recursion(r, c);   return maze; }   public void recursion(int r, int c) { // 4 random directions int[] randDirs = generateRandomDirections(); // Examine each direction for (int i = 0; i < randDirs.length; i++) {   switch(randDirs[i]){ case 1: // Up //　Whether 2 cells up is out or not if (r - 2 <= 0) continue; if (maze[r - 2][c] != 0) { maze[r-2][c] = 0; maze[r-1][c] = 0; recursion(r - 2, c); } break; case 2: // Right // Whether 2 cells to the right is out or not if (c + 2 >= width - 1) continue; if (maze[r][c + 2] != 0) { maze[r][c + 2] = 0; maze[r][c + 1] = 0; recursion(r, c + 2); } break; case 3: // Down // Whether 2 cells down is out or not if (r + 2 >= height - 1) continue; if (maze[r + 2][c] != 0) { maze[r+2][c] = 0; maze[r+1][c] = 0; recursion(r + 2, c); } break; case 4: // Left // Whether 2 cells to the left is out or not if (c - 2 <= 0) continue; if (maze[r][c - 2] != 0) { maze[r][c - 2] = 0; maze[r][c - 1] = 0; recursion(r, c - 2); } break; } }   }   /** * Generate an array with random directions 1-4 * @return Array containing 4 directions in random order */ public Integer[] generateRandomDirections() { ArrayList<Integer> randoms = new ArrayList<Integer>(); for (int i = 0; i < 4; i++) randoms.add(i + 1); Collections.shuffle(randoms);   return randoms.toArray(new Integer[4]); }

https://plaxdev.wordpress.com/2017/08/17/maze-generation-depth-first-search-part-1/

https://blog.csdn.net/juzihongle1/article/details/73135920
本文主要讲解的迷宫生成算法有三种：

1.Recursive backtracker ( 递归回溯，也是深度优先算法）

2.Randomized Prim's algorithm（随机Prim算法，让我想起了最小生成树的Prim算法）

3.Recursive division （递归分割算法）

首先，为了方便后续处理，默认的迷宫元素表示为[x,y,w]：

1.我们的迷宫为常规的矩形，因此可以用二维表示一个迷宫单元, 每个迷宫单元表示为一个二维数组元素[x,y]。

3.每个迷宫单元包含左上右下四个属性, 用w表示，分别表示迷宫单元四个面的墙，墙不占据迷宫单元。

首先是深度优先（递归回溯）算法，这个算法可以表示为（根据维基百科）：

1.Make the initial cell the current cell and mark it as visited
2.While there are unvisited cells
1.If the current cell has any neighbours which have not been visited
1.Choose randomly one of the unvisited neighbours
2.Push the current cell to the stack
3.Remove the wall between the current cell and the chosen cell
4.Make the chosen cell the current cell and mark it as visited
2.Else if stack is not empty
1.Pop a cell from the stack
2.Make it the current cell
如果翻译一下，就是：
1.将起点作为当前迷宫单元并标记为已访问
2.当还存在未标记的迷宫单元，进行循环
1.如果当前迷宫单元有未被访问过的的相邻的迷宫单元
1.随机选择一个未访问的相邻迷宫单元
2.将当前迷宫单元入栈
3.移除当前迷宫单元与相邻迷宫单元的墙
4.标记相邻迷宫单元并用它作为当前迷宫单元
2.如果当前迷宫单元不存在未访问的相邻迷宫单元，并且栈不空
1.栈顶的迷宫单元出栈
2.令其成为当前迷宫单元


深度优先构建迷宫的思想就是，每次把新找到的未访问迷宫单元作为优先，寻找其相邻的未访问过的迷宫单元，直到所有的单元都被访问到。通俗的说，就是从起点开始随机走，走不通了就返回上一步，从下一个能走的地方再开始随机走。一般来说，深度优先法生成的迷宫极度扭曲，有着一条明显的主路。我们使用python语言+matplotlib生成的20*30的迷宫如图所示：