Depth-First Search, Maze Algorithm

What is Depth-First Search?

Depth-first search is an algorithm that can be used to generate a maze. The idea is really simple and easy to implement using recursive method or stack.

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.

First of all, I would like to explain the general idea a little deeper which you can apply using your choice of programming language. After you have the picture in your mind, you can take a look at the sample code and applet in java.

Explanation

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

Explanation 1

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

Explanation 2

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.

Explanation 3

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.

Explanation 4

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.

Explanation 5

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

Explanation 6

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.

Sample Applet




Using Recursive Method

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.
Sample code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 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]);
 }

16 Responses to “Depth-First Search, Maze Algorithm”

  1. This tutorial was very helpful! Thank you!

  2. Anonymous says:

    Could you possibly give an example that also includes backtracking?

  3. admin says:

    One way I think is when the solution involves “progressing forward to test if the new condition is valid” and “if it is invalid, you would return one step back and try another possibility”. You would need to know where the path you took to where you are. Then you would go one step back by using either recursive methods or stacks as ways to track your previous location or action.

    Some examples are Sudoku, finding escape route in a maze, and so on.

  4. Shadovo says:

    Amazingly clear code and description, thank you so much!
    Was incredible easy to translate to the language I needed it for (JavaScript).

  5. Loris says:

    If i try to start the code, i get “NullPointerException” at “if (maze[r][c + 2] != 0)”
    or at the others same lines :( why?

  6. Rickmeister says:

    I actually got inspired by this to start on a Java4k game, adapted the function a bit and added a stack to make it some sort of recursive backtracker. It’s really hypnotic to set up a maze 455 cells wide and 255 cells tall and draw each cell as a 3×3 block (roughly 1366×768). Add a slight delay between the calls to the method and you can kill an hour or two by watching the maze grow :)

  7. Lian says:

    Thanks for the simple explanation! The reason why I used this algorithm is because I made a raycaster, but I couldn’t get sprites to work, so I just said “if I can’t get sprites to work, why not make it a maze game.”

    So I had to port this algorithm to C++ (I used a class called Maze), but I only have one problem.

    The maze has about a 5% chance of not filling one (or 1 to 2% chance two) corners as an empty space, and I’ve reviewed my code with yours and I’ve only seen 1 thing that was different, so I fixed it, and the bug was still there.

  8. ehsan says:

    Perfect and Simple to understand. I needed it for c++

  9. wag says:

    This is getting double walls on columns 0,1 and lines 0,1…

  10. StanE says:

    Here is a PHP converted and slightly modified version with an entry and an exit:
    https://stanislaveckert.de/public_files/maze/maze_src.php

    Demo:
    https://stanislaveckert.de/public_files/maze/maze.php

  11. JJ says:

    what website do you make those kinda maze that are 3D

  12. Horia says:

    Hi,

    May I ask you why do you move two positions at a time? What would happen in a maze 3×3?

    Thanks

    • Anonymous says:

      As I understand it, it moves 2 positions at a time because DFS works by removing the walls between cells. So by moving 2 spaces, the cell in the middle is the ‘wall’ and the cells it jumps to are the paths.

  13. Ding says:

    I’ve written C++ code according to your artical, and it works. Really cool and clear explanation.
    Thank you!

  14. luqman says:

    what if there is step cost of moving up, left and right (1,2,3)

Leave a Reply for Ryan Frappier

Categories