Maze generation via Depth First Search¶

Estimated time to read: 11 minutes

You are in charge of implementing a new maze generator for a procedurally generated game. The game is a 2D top-down game, where every level is composed by squared rooms blocked by walls. The rooms are generated by a maze generator, and the walls can be removed to create paths.

There are many ways to implement a maze generation and one of the most common is the Depth First Search algorithm combined with a Random Walk. The algorithm is simple and can be implemented in a recursive or interactive way. The suggested algorithm is as follows:

1. All walls are up;
2. Add the top left cell to the stack;
3. While the stack is not empty:
   1. If the stack top cell has visitable neighbor(s):
      1. Mark the top cell as visited;
      2. List visitable neighbors;
      3. Choose a neighbor (see below);
      4. Remove the wall between the cell and the neighbor;
      5. Add the neighbor to the stack;
   2. Else:
      1. Remove the top cell from the stack, backtracking;

Random Number Generation¶

In order to be consistent with all languages and random functions the pseudo random number generation should follow the following sequence of 100 numbers:

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

Every call to the random function should return the current number the index is pointing to, and then increment the index. If the index is greater than 99, it should be reset to 0.

Direction decision making¶

In order to give consistency on how to decide the direction of the next cell, the following procedure should be followed:

1. List all visitable neighbors of the current cell;
2. Sort the list of visitable neighbors by clockwise order, starting from the top neighbor: UP, RIGHT, DOWN, LEFT;
3. If there is one visitable, do not call random, just return the first neighbor found;
4. If there are two or more visitable neighbors, call random and return the neighbor at the index of the random number modulo the number of visitable neighbors. vec[i]%visitableCount

Input¶

The input is a single line with three 32 bits unsigned integer numbers, C, L and I, where C and L are the number of columns and lines of the maze, respectively, and I is the index of the first random number to be used> I can varies from 0 to 99.

2 2 0

In this case, our map will have 2 columns, 2 lines and the first random number to be used is the first one, 72 because it is pointed by the index 0.

Output¶

Every line is a combination of underscore _, pipe | and empty characters. The _ character represents a horizontal wall and the | character represents a vertical wall.

The initial state of the 2 x 2 map is:

 _ _  
|_|_| 
|_|_| 

In order to interactively solve this, we will add (0,0) to the queue.

The neighbors of the current top (0,0) are RIGHT and DOWN, (0,1) and (1,0) respectively.

Following the clockwise order, the sorted neighbor list will be [(0,1), (1,0)].

We have more than one neighbor, so we call random. The current random index is 0, so the random number is 72 and we increment the index.

The random number is 72 and the number of neighbors is 2, so the index of the neighbor to be chosen is 72 % 2 = 0, so we choose the neighbor (0,1), the RIGHT one.

The wall between (0,0) and (0,1) is removed, and (0,1) is added to the queue. Now it holds [(0,0), (0,1)]. The map is now:

 _ _  
|_ _| 
|_|_| 

Now the only neighbor of (0,1) is DOWN, (1,1). So no need to call random, we just choose the only neighbor.

The wall between (0,1) and (1,1) is removed, and (1,1) is added to the queue. Now it holds [(0,0), (0,1), (1,1)]. The map is now:

 _ _  
|_  | 
|_|_| 

Now the only neighbor of (1,1) is LEFT, (1,0). So no need to call random, we just choose the only neighbor.

The wall between (1,1) and (1,0) is removed, and (1,0) is added to the queue. Now it holds [(0,0), (0,1), (1,1), (1,0)]. The map is now:

 _ _  
|_  | 
|_ _| 

Now, the current top of the queue is (1,0) and there isn't any neighbor to be visited, so we remove the current top (1,0) from the queue and backtrack. The queue is now [(0,0), (0,1), (1,1)].

The current top is (1,1) and there isn't any neighbor to be visited, so we remove (1,1) from the queue and backtrack. The queue is now [(0,0), (0,1)].

The current top is (0,1) and there isn't any neighbor to be visited, so we remove (0,1) from the queue and backtrack. The queue is now [(0,0)].

The current top is (0,0) and there isn't any neighbor to be visited, so we remove (0,0) from the queue and backtrack. The queue is now empty and we finish priting the map state. The final map is:

 _ _  
|_  | 
|_ _| 

And this the only one that should be printed. No intermediary maps should be printed.

Example 1¶

Input 1¶

3 3 0

Output 1¶

 _ _ _  
|_  | | 
|  _| | 
|_ _ _| 

Example 2¶

Input 2¶

3 3 1

Output2¶

 _ _ _  
| |_  | 
|_ _  | 
|_ _ _|